Ordonnancements d'atelier à une machine
C'est le cas très particulier où il n'y a pas du tout de contraintes de précédence et où on a seulement une ressource qui existe en un seul exemplaire.
Nous présentons seulement ici les cas les plus connus que l'on résout très facilement, même si les solutions n'ont rien à voir avec la théorie des graphes (puisque le graphe a disparu avec les contraintes de précédence).
Description du problème de base à une machine
Un ensemble de N produits doit être traité sur une machine.
-------------------------------------
La durée de traitement du produit i est p(i).
La notation traditionnelle des durées en ordonnancement d'atelier est p(i) où "p" est utilisé pour "processing time".
De même, en ordonnancement d'atelier, le traitement d'un produit sur une machine est généralement appelé une opération.
p(i) est donc la durée de l'opération du produit i sur la machine.
------------------------------------
Les produits sont disponibles à partir de l'instant 0.
Les produits sont indépendants les uns des autres (pas de contraintes de précédence).
La machine est toujours disponible.
La machine ne peut traiter qu'un seul produit à la fois.
Critères utilisés pour le problème de base à une machine
S'il n'y a pas de contrainte de précédence et si la machine est toujours disponible,
on peut ordonnancer sans interruption les produits sur la machine de l'instant 0 à l'instant M=somme des durées des opérations.
Le critère durée totale de l'ordonnancement n'a donc aucun intérêt.
Par ailleurs, tout ordonnancement correspond à un ordre de passage des produits dans l'atelier.
Si les produits présents dans l'atelier nécessite, par exemple, de l'énergie pour les chauffer ou pour les refroidir pendant toute leur durée de présence dans l'atelier, alors pour minimiser l'énergie utilisée, il faut minimiser la somme des temps de présence des produits dans l'atelier.
Si on note F(i) la date de fin de l'opération i dans l'ordonnancement retenu.
Le critère minimiser la somme des temps de présence F(i) des produits dans l'atelier est un critère intéressant.
Si l'énergie utilisée dépend du produit.
On note w(i) la quantité d'énergie utilisée par le produit i par unité de temps où le produit est présent.
w(i) est aussi appelé le poids du produit i.
Le critère minimiser la somme des w(i).F(i) est un critère intéressant.
Si le client à qui est destiné le produit i l'attend au plus tard à l'instant d(i), délai pour le produit i, alors le produit i a un retard T(i)=F(i)-d(i) si F(i)>d(i) et T(i)=0 dans le cas contraire.
Une pénalité w(i) peut être attribué soit au fait que le produit i est livré en retard, soit au nombre d'unités de temps de retard pour le produit i.
On note NT le nombre de produits en retard et ret(i)=1 si i est en retard et 0 sinon
Le critère NT = nombre de produits livrés en retard est un critère intéressant.
Le plus grand retard T(i) est un critère intéressant.
Le critère somme des w(i).ret(i) est un critère intéressant.
Le critère somme des T(i) est un critère intéressant.
Le critère sommes des w(i)*T(i) est un critère intéressant.
Fondamental : Ordre optimal pour le critère somme des temps de présence
Pour minimiser la somme des F(i), il suffit de trier les produits dans l'ordre croissant de leur durée p(i).
Fondamental : Ordre optimal pour le critère somme pondérée des temps de présence
Pour minimiser la somme des w(i).F(i), il suffit de trier les produits dans l'ordre croissant des ratios p(i)/w(i).
Fondamental : Ordre optimal pour le critère du plus grand retard
Pour minimiser le plus grand retard Tmax, il suffit de trier les produits dans l'ordre croissant des d(i).
Fondamental : Ordre optimal pour le critère nombre de tâche en retard
Pour minimiser le nombre de produits en retard, on utilise l'algorithme de Moore.
Initialisation
RT = ensemble des opérations définitivement en retard à la fin de l'ordonnancement initialisé à vide ;
NDeb = ensemble des opérations à ordonnancer au début = toutes les tâches ;
On trie les opérations de Ndeb
par ordre croissant des délais et on calcule les retards.
Nret est le nombre d'opérations en retard dans NDeb ainsi ordonné ;
tantque Nret>2 faire
Soit j la position de la dernière opération en retard dans NDeb.
On cherche l'opération o de plus longue durée entre les positions 1 et j.
On envoie l'opération o dans RT et on l'ôte de Ndeb.
On trie les opérations de Ndeb
par ordre croissant des délais et on calcule les retards.
Nret est le nombre d'opérations en retard dans NDeb ainsi ordonné ;
fintantque
La solution est constituée des opérations de Ndeb dans l'ordre croissant des délais suivies des opérations restantes dans un ordre quelconque.
Remarque :
Les autres critères correspondent à des problèmes difficiles et nous ne les considérons pas ici dans ce cours sur la théorie des graphes qui n'est pas spécifiquement un cours d'ordonnancement.
