WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

Optimisation heuristique du problème d'entreposage d'objets en trois dimensions.

( Télécharger le fichier original )
par Mulindwa Chirac RUHAMYA
Universite adventiste de Lukanga - Licence 2012
  

précédent sommaire suivant

Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy

Chapitre premier : REVUE DE LA LITTERATURE

Des nombreux chercheurs avant nous se sont intéressés au domaine d'optimisation combinatoire, plus particulièrement dans la conception des logiciels d'optimisation de la coupe et entreposages des articles. Plusieurs méthodes ont été utilisées pour résoudre ce problème. Cette revue de littérature nous permettra de situer notre sujet par rapport à des recherches antérieures afin d'établir un créneau unique pour notre recherche. En plus de ça, cette partie sera pour nous, une occasion de fournir les informations de fond en ce qui concerne notre sujet pour comprendre les termes clés qui constituent notre thème.

I.1. Optimisation

D'après le petit Larousse (1980), l'optimisation c'est l'action de donner à un investissement, une entreprise ou une machine un rendement maximale. Selon Microsoft Encarta (2008), l'optimisation est une action de réguler (quelque chose) dans le but d'obtenir la plus grande efficacité possible.

Pour Nzalamingi (2012), l'optimisation est une branche des mathématiques, cherchant à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à déterminer le meilleur élément d'un ensemble en fonction d'un critère quantitatif donné. Aujourd'hui, nombreux des systèmes susceptibles d'être décrits par un modèle mathématique sont optimisés. Ils sont extrêmement variés : optimisation d'un trajet, de la forme d'un objet, d'un prix de vente, d'une réaction chimique, du contrôle aérien, du rendement d'un appareil, du fonctionnement d'un moteur, de la

8

gestion des lignes ferroviaires, du choix des investissements économiques, de la construction d'un navire jusqu'à l'optimisation des espaces de stockage et de la coupe de matériel. L'optimisation de ces systèmes permet de trouver une configuration idéale, d'obtenir un gain d'effort, de temps, d'argent, d'énergie, de matière première, de satisfaction, des rebus ou encore d'espaces. Très loin de constituer une liste exhaustive, ces quelques exemples attestent la variété des formulations et préfigurent la diversité des outils mathématiques susceptibles de résoudre ces problèmes.

En termes simples et pratiques, l'optimisation des processus consiste à améliorer les procédures d'usage et les manières de réaliser les tâches de manière à atteindre une productivité maximale l'entreprise. Cette optimisation vise donc à minimiser les couts et contraintes restreignant la productivité et à maximiser les gains favorisant l'efficacité. Pour ce qui concerne ce travail les contraintes sont constituées des places inutilisables dans les dépôts alors que les gains sont constitués des place ou case bien utilisées aux entrepôts.

La qualité des résultats et des prédictions du système optimisé dépendent de la pertinence du modèle, de l'efficacité de l'algorithme et des moyens pour le traitement numérique. Et ce travail est concerné par le modèle et l'algorithme du système de découpage et entreposage d'article.

D'après Nzalamingi (2012), les modèles d'optimisation sont repartis en plusieurs classes dont nous pouvons relever :

- L'optimisation linéaire qui étudie le cas où la fonction objectif et les contraintes caractérisant l'ensemble de possibilités sont linéaires. C'est une méthode très employée pour établir les programmes des raffineries pétrolières, mais aussi pour

9

déterminer la composition la plus rentable d'un mélange salé, sous contraintes, à partir des prix de marché du moment.

- L'optimisation linéaire en nombres entiers étudie les problèmes d'optimisation linéaire dans lesquels certaines ou toutes les variables sont contraintes de prendre des valeurs entières.

- L'optimisation quadratique étudie le cas où la fonction objectif est une forme quadratique (avec contraintes linéaires)

- L'optimisation non linéaire étudie le cas général dans lequel l'objectif ou les contraintes (ou les deux) contiennent des parties non linéaires, éventuellement non-convexes.

- L'optimisation stochastique étudie le cas dans lequel certaines des contraintes dépendent de variables aléatoires. En optimisation robuste, les aléas sont supposés être situés dans des intervalles autour de positions nominales et on cherche à optimiser le système soumis à de tels aléas, dans le pire des cas.

- L'optimisation combinatoire (optimisation discrète) consiste à trouver dans un ensemble discret un parmi les meilleurs sous-ensembles (ou solutions) réalisables, la notion de meilleure solution étant définie par une fonction objectif.

Comme lu dans Wikimedia Foundation (2013), l'optimisation combinatoire est en fait une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l'algorithmique et la théorie de la complexité. On parle également d'optimisation discrète. Dans sa forme la plus générale, un problème d'optimisation combinatoire (on dit aussi d'optimisation discrète) consiste à trouver dans un ensemble discret un parmi les meilleurs sous-ensembles (ou solutions) réalisables, la notion de meilleure solution étant définie par une fonction objectif. Formellement, étant donnés :

10

- un ensemble discret N,

- une fonction d'ensemble f : 2N ? R, dite fonction objectif, et

- un ensemble R sous-ensembles de N, dont les éléments sont appelés les

solutions réalisables,

Un problème d'optimisation combinatoire consiste à déterminer

L'ensemble des solutions réalisables ne saurait être décrit par une liste exhaustive car la difficulté réside ici précisément dans le fait que le nombre des solutions réalisables rend son énumération impossible, ou bien qu'il est NP-complet de dire s'il en existe ou non. La description de R est donc implicite, il s'agit en général de la

liste, relativement courte, des propriétés des solutions réalisables. La plupart du temps on est dans les cas particuliers suivants :

- et R = X n Z nX R n et la cardinalité de R est

exponentielle en n,

- R = conv (n) n Z n donc les propriétés de R se traduisent en contraintes linéaires,

c'est-à-dire que X est un polyèdre de R n,

-

 

L' Optimisation combinatoire consiste à trouver le meilleur entre un nombre fini de choix. Autrement dit, minimiser une fonction, avec contraintes, sur un ensemble fini. Quand le nombre de choix est exponentiel (par rapport à la taille du problème), mais que les choix et les contraintes sont bien structurées, des méthodes mathématiques doivent et peuvent intervenir, comme dans le cas " continu ", pour permettre de trouver la solution en temps polynomial (par rapport à la taille du problème). Le travail de l'équipe consiste à développer des algorithmes polynomiaux

11

et des théorèmes sur des structures discrètes qui permettent de résoudre ces problèmes.

Trouver une solution optimale dans un ensemble discret et fini est un problème facile en théorie : il suffit d'essayer toutes les solutions, et de comparer leurs qualités pour voir la meilleure. Cependant, en pratique, l'énumération de toutes les solutions peut prendre trop de temps ; or, le temps de recherche de la solution optimale est un facteur très important et c'est à cause de lui que les problèmes d'optimisation combinatoire sont réputés si difficiles. La théorie de la complexité donne des outils pour mesurer ce temps de recherche. De plus, comme l'ensemble des solutions réalisables est défini de manière implicite, il est aussi parfois très difficile de trouver ne serait-ce qu'une solution réalisable.

Quelques problèmes d'optimisation combinatoire peuvent être résolus (de manière exacte) en temps polynomial par exemple par un algorithme glouton, un algorithme de programmation dynamique ou en montrant que le problème peut être formulé comme un problème d'optimisation linéaire en variables réelles.

Dans la plupart des cas, le problème est NP-difficile et, pour le résoudre, il faut faire appel à des algorithmes de branch and bound, à l'optimisation linéaire en nombres entiers ou encore à la programmation par contraintes. En pratique, on se contente très souvent d'avoir une solution approchée, obtenue par une heuristique ou une métaheuristique. Pour certains problèmes, on peut prouver une garantie de performance, c'est-à-dire que l'écart entre la solution obtenue et la solution optimale est borné. Chacune de ces méthodes sera exploitée d'avantage dans le deuxième chapitre de notre travail.

12

précédent sommaire suivant






Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy








"Le doute est le commencement de la sagesse"   Aristote