Contribution à la résolution des problèmes de flow shop avec machines dédiées, avec dates de disponibilité et délais de livraison

1.1.4 ComplexitéLa complexitédes problèmes ordonnancement est définie suivant la com-

plexitédes méthodes de résolution et celle des algorithmes utilisés .

Selon Garey et Johnson [21], la complexitéd'un algorithme est exprimée par le nombre d'instructions élémentaires exécutées pendant son exécution. C'est une fonction exprimant le temps d'exécution au pire des cas, en fonction de la taille de l'instance étudiée du problème.

On distingue les algorithmes selon leurs complexités par :

- Algorithme polynomial : c'est un algorithme dont le nombre d'instruc-tion est expriméen fonction de n (oùn est la taille du problème) de la manière suivante : O(n^x) (pour un certain x).

- Algorithme exponentiel : un algorithme dont le nombre d'instruction s'exprime comme suit : O(xⁿ) (avec x est un entier), i.e. le nombre d'instruction n'est pas bornépar un polynôme de n.

Par ailleurs, la complexitédes problèmes de décision est classéessentielle-ment selon deux classes :

- Classe P : classe des problèmes pouvant être résolus en un temps polynomial, i.e. on a trouvéun algorithme de complexitéO(n^x) (pour un certain x) qui les résout. la classe P comprend les problèmes dits Facile.

- Classe NP (Non-Deterministic Polynomial Time) : c'est la classe des problèmes qu'on a pas encore trouvédes algorithmes polynomial qui les résout (ou qu'il n'existe pas des algorithmes polynomiales pour les

Problèmes d'ordonnancement 8

Problèmes d'ordonnancement 9

résoudre) , ces problèmes sont en fait associéa des algorithmes exponentiels .

Un problème de décision est un problème admettant uniquement deux réponses possibles : «oui», ou «non», alors que pour un problème d'optimi-sation on doit chercher à déterminer une solution qui optimise un critère donné, notons qu'àchaque problème d'optimisation on peut associer un problème de décision. On peut donc classéles problèmes d'optimisation selon les problèmes de décisions qui leur sont affectés; on dit par exemple qu'un problème d'optimisation est NP-difficile si le problème de décision associéest NP-Complet.

1.1.5 Représentation des problèmes d'ordonnancement

Un problème d'ordonnancement peut être représenter à l'aide de plusieurs méthodes, à savoir la méthode PERT(Program Evaluation and Review Technique , la méthode MPM (Méthode des Potentiels Métra) et le diagramme de Gantt.

La solution d'un problème d'ordonnancement est généralement représentée par le digramme de Gantt, ce diagramme a étéinventéen 1917 par Henry L. Gantt pour modéliser la planification des tâches nécessaires à la réalisation d'un projet. Grâce à sa facilitéde lecture et mise en place ce diagramme est toujours le plus utilisé.