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 n où X €
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
| 
