Comme SAT et TSP, plusieurs problèmes réels s'apparentent à des problèmes d'ordonnancement : 'scheduling problems'. Ces problèmes constituent une classe des plus importante en optimisation combinatoire étant donnée l'importance et le nombre d'applications réelles dont ils sont issues, ainsi que la difficulté de leur résolution. De façon générale, on rencontre les problèmes d'ordonnancements dans des situations où pour réaliser un ensemble d'opérations, il est nécessaire d'allouer des ressources à ces opérations au cours du temps pour satisfaire certaines contraintes ou certaines fonctions de coût.
Par exemple, considérons l'ordonnancement du décollage et/ou de l'atterrissage des avions dans un aéroport. Chaque vol possède une fenêtre de temps pendant laquelle il peut/doit décoller et/ou atterrir. Aussi, il peut typiquement exister des contraintes sur l'interval minimum de temps qui sépare deux atterrissages/décollages donnés. Un problème d'optimisation consiste alors à ordonnancer les décollages/atterrissages afin de minimiser, par exemple, le retard total induit par le séquencemment des vols. La littérature regorge d'autres exemples encore plus complexes qui s'apparentent à ce type de problème d'ordonnancement, e.g., chaine de production industrielle, tournoi sportifs, etc.
Dans ce TP, on considère une version simple et générique d'un problème d'ordonnancement, appelé SMTWTP (Single machine Total Weighted Tardiness Problem). Derrière ce nom 'barbare' se cache en fait une classe de problèmes à l'énoncé simple. Plus précisément, dans cette classe, on considère qu'on est donnée n tâches (Jobs) J := (J1 , … , Jn) à ordonnancer sur une seule machine M. Chaque tâche j possède un temps d'exécution pj donnée. Chaque tâche possède aussi un temp 'due' dj qui définit la 'deadline' à laquelle l'exécution de la tâche devrait être terminée. Enfin, chaque tâche possède un poid wj qui renseigne sur son importance (e.g., criticité, coût en terme de bénéfices/pertes, etc).
Notre problème consiste alors à ordonnancer séquentiellement les tâches sur la machine M (déterminer une séquence d'exécution des tâches) afin d'optimiser une fonction de coût.
Pour cela, et ayant donnée un ordonnancement O fixé (c.à.d une séquence d'exécution des tâches sur la machine), on note Cj le temps de complétion de la tâche j. On définit alors Tj := max{ Cj - dj , 0 }. Le coût de l'ordonnancement O est alors définit par la fonction F :
F(O) := ∑j=1,...,n wj . Tj = w1 . T1 + w2 . T2 + ... + wn . Tn
Le problème que l'on aimerait résoudre est de trouver un ordonnancement O* qui minimise F : F(O*) <= F(O), pour tout O.
SMTWTP est un problème relativement simple en optimisation, e.g., les contraintes et les données sont simplement modélisables. Il n'en reste moins qu'il est difficile à résoudre (NP-difficile) et apparaît comme un sous problème récurrent dans plusieurs contextes sous d'autres contraintes plus compliquées.
Par exemple, dans notre exemple d'ordonnancement de vols, en supposant que l'aéroport possède une seule piste d'atterrissage, qu'il n'y a que des avions qui décollent, qu'il n'y a aucune contraintes de temps d'attente entre les décollages, la machine M peut alors modéliser la piste de l'aéroport, les tâches J modélisent les décollages sur la piste, les temps pj modélisent le temps que met un avion d'un certain type pour décoller de la piste, les temps dj modélisent le temps maximum avant lequel un avion devrait décoller pour être à l'heure à destination, les poids wj modélisent la pénalité que devra payer la compagnie si le vol arrive en retard à destination.
Pour nous entrainer aux techniques d'optimisation qui nous intéressent, nous allons travailler sur des instances particulières de ce problème de taille 100. Ces instances font parties de librairie OR-lib où par ailleurs d'autres classes de problèmes d'ordonnancement et d'autres types de classes sont répertoriés et étudiés par la communauté scientifique.
Dans cette séance, nous allons commencer par nous familiariser avec les instances et vous aller proposer des solutions simples pour résoudre ces instances.
Télécharger les instances wt100.txt. Ces instances sont dans un format texte suivant une sémantique précise. Liser le fichier wtinfo.txt de description des instances (en anglais).
Écrire un programme (java) qui permet de lire les instances. Tester le.
Écrire un programme qui permet de générer une solution aléatoire au problème pour une instance donnée. Tester le.
En triant les tâches suivant les dj, écrire un programme qui calcule une solution au problème. Tester le. Indication : trier les jobs par ordre croissant de leurs dj (les cas d'égalité sont traités de façon aléatoire). Cette heuristique s'appelle EDD (Earliest Due Date).
En s'inspirant du TSP, imaginer une heuristique constructive pour notre problème. Écrire le programme correspondant. Tester le. Indication : trier les jobs par ordre croissant de leurs échéances modifiées mddj := max{C + pj , dj} où C est la somme des temps d'exécution des jobs déjà ordonnancés. Cette heuristique s'appelle MDD (Modified Due Date).
Comparer les solutions trouvées entre vous.
Comparer les solutions trouvées par rapport au meilleurs connues : wtbest100b.txt.
D'autres instances existent que vous pouvez utiliser pour tester vos algorithmes.
Instances difficiles de taille 1000 mais dans un autre format : chaque fichier contient n lignes, chaque ligne référence le job j et précise les données (pj, wj, dj). Aussi disponible ici.
Autres Instances de taille jusqu'à 500.