Généralités sur la théorie de l’ordonnancement

NOTIONS DE COMPLEXITÉ

En général, les problèmes d’ordonnancement appartiennent à une classe plus large de problèmes de recherche combinatoire. Un problème de recherche combinatoire P est un ensemble de paires (I;A) où :
1. I est une instance du problème considéré, en d’autres termes, c’est une affectation de valeurs particulières aux paramètres définissant le problème.
2. A  est une réponse (solution) à l’instance I.

Nous distinguons deux sous-classes de problèmes de recherche combinatoire, à savoir :
— Les problèmes de décision, dont la solution prendra la forme d’un oui ou d’un non.
— Les problèmes d’optimisation, dont la réponse spécifie une solution qui optimise un certain objectif.

N.B. Dans le reste du document, nous supposons, sauf mention contraire, que nous traitons des problèmes de minimisation.

Pour tout problème d’optimisation combinatoire, il existe un problème de décision associé. Le codage des problèmes de recherche (de leurs paramètres) est l’un des plus importants aspects abordés lors de la conception de méthodes pour leur résolution.

Généralement, pour coder une instance I d’un problème P, nous utilisons une chaîne x(I) de symboles issus d’un certain alphabet 1 S et combinés suivant les règles d’un schéma de codage particulier e. La taille en entrée jIj de l’instance I sera alors la longueur de la chaîne x(I). Usuellement, il est intéressant d’exprimer la taille en entrée d’une instance I en fonction du nombre d’éléments d’un certain ensemble dont la cardinalité est dominante pour l’instance.

Un algorithme est une procédure servant à résoudre un problème, i.e. il s’agira de trouver une réponse (oui ou non) pour les problèmes de décision et une solution optimale pour les problèmes d’optimisation. Dans le cadre de la résolution d’un problème d’optimisation, on peut considérer des méthodes approchées qui fournissent des solutions réalisables qui tendent vers mais ne garantissent pas l’optimalité.

La complexité temporelle d’un algorithme A permettant de résoudre un problème P est une fonction associant à chaque taille en entrée d’une instance I de P un nombre maximum d’étapes élémentaires (ou unités de temps) d’un ordinateur nécessaires à la résolution d’une instance de cette taille au moyen de l’algorithme A.

Du point de vue de la complexité, il existe deux différentes classes d’algorithmes :
1. Les algorithmes polynomiaux, dont la complexité temporelle est en O(p(k)) pour un certain polynôme p, k étant la taille en entrée d’une instance. Ces algorithmes sont considérés comme « bons » car ils induisent souvent un temps de calcul assez raisonnable.
2. Les algorithmes exponentiels, dont la complexité temporelle ne peut être bornée.

Un ensemble fini de symboles polynomialement

Leur temps d’exécution peut très rapidement devenir prohibitif avec l’augmentation de la taille en entrée de l’instance considérée. Seulement, il n’est pas toujours possible de résoudre un problème à l’aide d’un algorithme de complexité polynomiale, souvent, seuls des algorithmes exponentiels existent.

En pratique, il n’est pas nécessaire d’avoir la forme explicite de la complexité temporelle d’un algorithme, mais plutôt une borne supérieure qui permettrait de donner une indication sur le comportement de la fonction complexité avec l’augmentation de la taille de l’instance du problème considéré.

Comme spécifié précédemment, nous pouvons associer à tout problème d’optimisation un problème de décision, les deux classes de problèmes pourront être analysées de la même manière car un problème de décision n’est pas plus difficile du point de vue calcul que le problème d’optimisation auquel il est associé. Ceci induit qu’une résolution polynomiale d’un problème d’optimisation induit la résolution polynomiale du problème de décision associé.

Inversement, si le problème de décision est « difficile », le problème d’optimisation auquel il est associé le sera aussi. Les principales classes de problèmes sont comme suit :
1. La classe P qui contient les problèmes de décision ayant un algorithme polynomial pour leur résolution.
2. La classe NP qui contient les problèmes de décision pour qui une réponse positive (oui) peut être vérifiée en temps polynomial. De ce fait, la relation P NP est établie.

APPROCHES DE RÉSOLUTION

Des décennies des travaux intensifs de recherche tous plus inventifs les uns que les autres n’ont toujours pas permis de trouver un algorithme « efficace » pour la résolution des problèmes NP-durs d’ordonnancement, il n’en demeure pas moins vrai que beaucoup de progrès et d’avancées ont été accomplis depuis que ces derniers se sont invités dans la cour des problèmes d’optimisation combinatoire, il y a de cela plusieurs décennies. La suite de cette section offre une vue d’ensemble sur les principales classes de méthodes utilisées en ordonnancement.

ALGORITHMES CONSTRUCTIFS

Ces algorithmes permettent de construire une solution optimale à partir des données du problème en suivant des règles simples qui déterminent l’ordre de traitement des tâches (ces algorithmes sont polynomiaux). Généralement, les méthodes constructives incluent une connaissance du problème qui implique une bonne compréhension de la structure de la solution.

MÉTHODES ÉNUMÉRATIVES

La section suivante sera consacrée aux méthodes énumératives. Les méthodes abordées, à savoir la programmation dynamique et la méthode branch-and-bound, sont toutes deux des méthodes d’énumération implicite, c’est à dire qu’elle considèrent certaines solutions indirectement, sans les évaluer explicitement.

La programmation dynamique

La programmation dynamique est une méthode d’énumération qui trouve ses origines dans les travaux de Bellman de 1957 [Bellman (1957)]. Cette méthode est applicable à tout problème pouvant être décomposé en une séquence de sous-problèmes imbriqués de telle manière que la solution de l’un de ces sous-problèmes dépend de la solution de celui qui le précède. La méthode repose sur le principe d’optimalité de Bellman 2, ce qui permet de décrire le critère 2. qui stipule que toute partie d’une solution optimale est optimale pour le problème restreint qu’elle défini.

Branch-and-bound

Soit M une borne inférieure de la fonction objectif du problème considéré ; le fait de trouver une solution réalisable d’évaluation M signifie que cette dernière est optimale. Ainsi, le fait de borner la valeur de la fonction objectif permet de réduire -parfois substantiellement- l’espace de recherche. Ceci combiné à l’adage : « diviser pour mieux régner » donne le principe du Branch-and-Bound (Séparation et Évaluation).

L’idée du Branch-and-Bound, méthode d’énumération implicite, consiste à diviser le problème principal -dont les solutions forment un ensemble S- en sous-problèmes, généralement deux à deux disjoints, qui seront éventuellement eux-mêmes divisés par la suite de la même manière après leurs résolutions engendrant ainsi des sous-ensembles de plus en plus petits de S. Ces derniers sont considérés comme les ensembles de solutions des sous-problèmes du problème original. L’étape d’évaluation (bounding) calcule une borne inférieure pour chaque sousproblème généré.

MÉTHODES APPROCHÉES

Les méthodes approchées sont des algorithmes permettant de trouver une ou plusieurs solutions réalisables pour un problème donné. Elles sont également appelées méthodes incomplètes, et ce, car elles « troquent » la complétude 5 contre l’efficacité 6. En effet, ces méthodes sont caractérisées par leur « rapidité », ce qui semble remédier à notre problème qui est la « lenteur » des méthodes exactes. Elles sont ainsi très adéquates pour les instances de grandes tailles 7, ainsi que pour celles caractérisées par des données approchées ou dynamiques.

Notons que, ces méthodes possédant pour la plupart une composante aléatoire, leur rapidité est contrebalancée par le fait qu’elle n’offrent strictement aucune garantie d’optimalité pour les solutions qu’elles donnent. Néanmoins, nous verrons que cela ne présente pas de sérieux problèmes. Nombre de méthodes approchées appliquées en ordonnancement donnent des résultats très satisfaisants, parfois même inespérés.

Deux types de méthodes approchées ont été appliquées en ordonnancement : les heuristiques et les métaheuristiques. Les premières sont spécifiques (dédiées) à certaines classes de problèmes, tandis que les secondes sont une sorte d’ossature générale à adapter au problème à résoudre.

Une condition nécessaire à l’application de ce type de méthodes est que leur complexité temporelle soit dans le pire des cas bornée supérieurement par un polynôme d’ordre réduit en la taille en entrée de l’instance.

Heuristiques

Les heuristiques, du grec heuriskein qui signifie trouver, sont des méthodes approchées spécifiques à un problème donné. Elles permettent d’aboutir « rapidement » à une solution réalisable de l’instance du problème à résoudre. Même si elles sont relativement efficaces en pratique, ces méthodes ont pourtant leurs  limites.

En plus d’être spécifiquement dédiées à un problème donné, les heuristiques sont particulièrement caractérisées par le fait de converger, voire d’être piégées dans des minimums locaux. Pour remédier à cela, de nouvelles approches de résolutions, dont la conception est totalement différente ont vu le jour : Les Métaheuristiques.

Métaheuristiques

Longtemps désignées comme étant des « heuristiques modernes », les métaheuristiques, du grec heuriskein qui signifie « trouver » et meta qui signifie « de niveau supérieur », furent nommées ainsi par Fred Glover en 1986 [Blum et Roli (2008)]. Elles sont, en quelque sorte, des méthodes heuristiques pour la génération de méthodes heuristiques [Cook (2012)] ; il s’agit d’une sorte d’ossature générale (framework) caractérisée par un ensemble de concepts fondamentaux qui lui sont propres ; elles possèdent toutes un haut niveau d’abstraction, ce qui leur permet d’être utilisées pour la résolution d’un large éventail de problèmes, et ce, en procédant par leur adaptation à l’instance du problème à résoudre. Elles requièrent des techniques permettant de trouver rapidement des solutions de bonne qualité dans des espaces de recherche très grands et très complexes. Ces méthodes utilisent souvent des caractéristiques spécifiques du problème dans le but d’améliorer et d’accélérer la convergence, si ces caractéristiques ne sont pas disponibles au départ, un processus d’apprentissage permettra d’accumuler dynamiquement 22 de l’information pendant le processus de recherche [Blazewicz et al. (2001)].

L’existence des métaheuristiques de manière indépendante des problèmes qu’elles résolvent a permis d’élargir les horizons de recherche et de puiser de nouvelles idées dans des domaines très différents ; ainsi, des chercheurs appartenant à des domaines scientifiques très variés ont pu apporter leur contribution.

Au-delà de cela, les métaheuristiques ont en commun le fait que toutes permettent une plus large exploration de l’espace des solutions car chacune possède un mécanisme propre qui lui permet, par le biais d’une utilisation intelligente et biaisée de l’aléatoire (se basant sur la mémoire, l’expérience, ou la descente), d’échapper aux optimums locaux. Les métaheuristiques sont principalement caractérisées par leur simplicité d’implémentation, ce qui leur a valu de recevoir une attention considérable, sans cesse croissante, depuis environ une quarantaine d’années.

MÉTHODOLOGIE DE RÉSOLUTION D’UN PROBLÈME D’OPTIMISATION COMBINATOIRE DÉTERMINISTE

Les problèmes d’ordonnancement déterministes faisant partie des problèmes d’optimisation combinatoire déterministes, l’approche générale d’analyse de ces problèmes peut leur être appliquée, tout en prenant en compte cependant leurs particularités. Souvent, le temps alloué à la résolution d’un problème d’ordonnancement est très limité, ainsi, seuls les algorithmes polynomiaux d’ordre réduit sont d’un intérêt pratique. L’examen de la complexité des problèmes considérés est ainsi à la base de leur analyse.

Si un problème appartient à P, un algorithme polynomial doit avoir été trouvé, auquel cas une recherche d’algorithmes pourra être orientée vers l’amélioration de la complexité existante. Dans la démarche d’analyse d’un nouveau problème d’optimisation, s’il n’est pas dans P, il faut d’abord voir s’il a déjà été prouvé qu’il était N P-dur, et dans le cas contraire, tester son appartenance à cette classe de problèmes. Si nous prouvons que le problème considéré est N P-dur, il faudra alors admettre que pour les plus grandes instances, il ne sera pas possible de trouver une solution optimale sans passer un temps excessivement grand pour l’obtenir. Les transformations polynomiales construites entre les différents problèmes existants sont souvent très utiles lors de l’analyse de nouveaux problèmes.

Cependant, en pratique, un problème ne peut être laissé sans solution. L’on utilisera alors des heuristiques ou algorithmes d’approximation qui produisent des solutions réalisables, souvent de très bonne qualité, mais sans en garantir l’optimalité. Bien entendu, les heuristiques ne seront utilisées que si la taille de l’instance du problème considéré rend l’utilisation de toute méthode exacte infaisable.

En fait, plusieurs possibilités s’offrent à nous :
— Relaxer certaines contraintes du problème et résoudre le problème relaxé (par exemple considérer des temps de traitement unitaires ou encore une certaine forme de contraintes de précédence). La solution obtenue peut être une bonne approximation de la solution du problème original.
— Utiliser des algorithmes d’approximation polynomiaux d’ordre réduit dont l’évaluation est effectuée au travers d’analyses au pire cas, de taux de convergence ou encore d’analyse du comportement moyen.
— Utiliser des méthodes exactes. Dans le cas d’un problème NP-dur au sens faible, un algorithme pseudo-polynomial peut être construit. Ce dernier pourra fournir de bons résultats en pratique pour les problèmes de tailles moyennes, les « purs » algorithmes exponentiels étant exclus vue la complexité du problème.

Table des matières

Introduction générale 
1 Concepts de base 
1.1 Notions de complexité
1.2 Approches de résolution
1.3 Méthodologie de résolution d’un problème d’optimisation combinatoire déterministe
2 Généralités sur la théorie de l’ordonnancement
2.1 Introduction
2.2 Description de modèles et notations
2.3 Classification et hiérarchie des problèmes
2.4 Ordonnancement avec opérateurs
3 Revue de la littérature
3.1 Ordonnancement d’ateliers
3.2 Ordonnancement d’ateliers avec opérateurs
3.3 Flow shop
3.4 Job shop
3.5 Open shop
4 Flow shop de permutation avec temps de réglages
4.1 Introduction
4.2 Description du problème
4.3 L’approche MBO de base
4.4 Étude expérimentale
4.5 Conclusion
5 Flow shops avec opérateurs
5.1 Introduction
5.2 Description des problèmes et notation
5.3 Mode de changement d’affectation en fin de tâche
5.4 Mode de changement d’affectation libre
6 Job shops avec opérateurs
6.1 Introduction
6.2 Minimisation du makespan
6.3 Minimisation du retard algébrique maximum
7 Open shops avec opérateurs 
7.1 Introduction
7.2 Description du problème
7.3 Étude de complexité
7.4 Conclusion
Conclusion générale
Bibliographie