Problèmes d’ordonnancement des ateliers de type 1|𝛽|𝛾

1

3

2

4

3

7

4

2

3

σ 𝐶𝑖 = 40

4

0 3 7 14 16

M1

4

1

2

3

0 2 5 9

16

Est-ce la valeur optimale ?

σ 𝐶𝑖 = 32

𝟏 || σ 𝑪𝒊

Lemme : Un ordonnancement est optimal pour 1 || σ 𝐶𝑖si et seulement si 𝑝𝑖 ≤ 𝑝𝑖+1

SPT : Shortest Processing Time Un ordonnancement est optimal pour 1 || σ 𝐶𝑖 si et seulement si tâches sont rangées dans l’ordre croissant de 𝑝𝑖.

les

𝟏 || σ 𝒘𝒊𝑪𝒊

• Un problème à 1 seule machine • Objectif: minimiser la somme des encours tout en considérant des poids ( importance, coûts,

poids des clients, etc.)

• Toutes les tâches sont disponibles à l’instant t = 0

𝑖 𝑝𝑖 𝑤𝑖

1

3

2

2

4

5

3

7

1

4

2

1

𝟏 || σ 𝒘𝒊𝑪𝒊

• Un problème à 1 seule machine • Objectif: minimiser la somme des encours tout en considérant des poids ( importance, coûts,

poids des clients, etc.)

• Toutes les tâches sont disponibles à l’instant t = 0

• Comparé au cas précédent, on utilisera la SPT pondérée (Weighted SPT, WSPT).

Règle de Smith : WSPT : Un ordonnancement est optimal pour 1 || σ 𝑤𝑖𝐶𝑖 si et seulement si les tâches sont rangées dans l’ordre croissant de 𝑝𝑖/𝑤𝑖.

𝟏 || σ 𝒘𝒊𝑪𝒊

𝑖 𝑝𝑖 𝑤𝑖 𝒑𝒊/𝒘𝒊

1

3

2

2

4

5

1,5

0,8

3

7

1

7

4

2

1

2

M1

2

1

4

3

0 4 7 9 16

σ 𝐶𝑖 = 36

𝟏 |𝒓𝒊| σ 𝑪𝒊

• Un problème à 1 seule machine • Objectif: minimiser la somme des temps de traitement tout en respectant la disponibilité des

tâches.

2

4

5

3

7

3

𝑖 𝑝𝑖 𝑟𝑖

1

3

0

3

4

2

9

2

σ 𝐶𝑖 = 43

4

L’ordre croissant de 𝒓𝒊:

M1

1

0 3 10 14 16

L’ordre 1-2-3-4 :

M1

1

2

3

σ 𝐶𝑖 = 51

4

0 3 5 9 16

18

Comment avoir l’ordonnancement optimal ?

Théorème : Les problèmes 𝟏|𝒓𝒊| σ 𝒘𝒊𝑪𝒊 ,𝟏|𝒓𝒊| σ 𝑪𝒊 et𝟏 𝒓𝒊, 𝒑𝒓𝒎𝒑 σ 𝒘𝒊𝑪𝒊 sont des problèmes NP-difficile. Toutefois, il est possible de résoudre le problème : 𝟏 𝐫𝐢, 𝐩𝐫𝐦𝐩 σ 𝐂𝐢 .

Résolution du problème 𝟏 𝐫𝐢, 𝐩𝐫𝐦𝐩 σ 𝐂𝐢: SRPT (Shortest Remaining Processing Time) Affecter la machine à la tâche de plus courte durée sous la condition suivante : quand une tâche arrive, elle préempte la machine si sa durée est plus petite que la durée résiduelle de la tâche en cours.

• Un problème à 1 seule machine • Objectif: minimiser la somme des temps de traitement tout en respectant la disponibilité des

𝟏 |𝒓𝒊, 𝒑𝒓𝒎𝒑| σ 𝑪𝒊

tâches.

M1

𝑖 𝑝𝑖 𝑟𝑖

1

3

0

2

4

5

3

7

3

4

2

9

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

• Un problème à 1 seule machine • Objectif: minimiser la somme des temps de traitement tout en respectant la disponibilité des

𝟏 |𝒓𝒊, 𝒑𝒓𝒎𝒑| σ 𝑪𝒊

tâches.

M1

1

2

4

5

3

7

3

4

2

9

𝑖 𝑝𝑖 𝑟𝑖

1

3

0

3

0 3 5

Seule la tâche 3 est disponible

La tâche 2 est désormais disponible Temps restant pour la tâche 3 est de 5 Temps restant pour la tâche 2 est de 4 ➔ On interrompe la tâche 3 et on commence la tâche 2.

𝟏 |𝒓𝒊, 𝒑𝒓𝒎𝒑| σ 𝑪𝒊

On termine la tâche 3.

M1

1

3’

2

4

3’’

0 3 5 9 11 16

À partir du 9, la tâche 4 est disponible. Temps restant pour la tâche 3 est de 5. Temps restant pour la tâche 4 est de 2. ➔ donc je choisi la tâche 4.

෍ 𝐶𝑖 = 44

1||𝑳𝒎𝒂𝒙

• Un problème à 1 seule machine • Objectif: minimiser le retard. • 𝐿𝑖 = 𝐶𝑖 − 𝑑𝑖 : le retard algébrique. • 𝑇𝑖 = 𝑀𝑎𝑥 (0, 𝐶𝑖 − 𝑑𝑖 ) : le vrai retard.

𝑖 𝑝𝑖 𝑑𝑖

1

3

3

2

4

6

3

7

18

4

2

9

1||𝑳𝒎𝒂𝒙

Théorèmes : règle de Jackson EDD : Earliest Due Date Un ordonnancement est optimal pour 1 || 𝐿𝑚𝑎𝑥 si les tâches sont rangées dans l’ordre croissant de 𝑑𝑖.

𝑖 𝑝𝑖 𝑑𝑖 𝐶𝑖 − 𝑑𝑖

1

3

3

0

2

4

6

1

3

7

18

-2

4

2

9

0

M1

1

2

4

3

𝐿𝑚𝑎𝑥 = 1

0 3 7 9

16

Théorèmes : règle de Jackson EDD : Earliest Due Date Un ordonnancement est optimal pour 1 ||𝑳𝒎𝒂𝒙 si les tâches sont rangées dans l’ordre croissant de 𝑑𝑖.

EDD minimise le plus retard « vrai » =𝑻𝒎𝒂𝒙

Toutefois, un ordonnancement qui minimise 𝑻𝒎𝒂𝒙 ne minimise forcément pas 𝑳𝒎𝒂𝒙.

1|𝒓𝒊|𝑻𝒎𝒂𝒙

• Un problème à 1 seule machine • Objectif: minimiser le retard maximal sous contraintes de disponibilité. • 𝐿𝑖 = 𝐶𝑖 − 𝑑𝑖. • 𝑇𝑖 = 𝑀𝑎𝑥 (0, 𝐶𝑖 − 𝑑𝑖 ).

N.B: Les problèmes qui considèrent à la fois les contraintes de disponibilité et celles de la date de fin souhaitée (𝑟𝑖 et 𝑑𝑖 ) sont généralement difficiles à résoudre. Toutefois, si la préemption est permise, ça facilitera la résolution.

1|𝒓𝒊|𝑻𝒎𝒂𝒙

1|𝒓𝒊, 𝒑𝒓𝒎𝒑|𝑻𝒎𝒂𝒙

Résolution: EDD modifiée À tout instant, affecter à la machine, la pièce disponible avec 𝑑𝑖 minimal.

1|𝒓𝒊, 𝒑𝒓𝒎𝒑|𝑻𝒎𝒂𝒙

𝑖 𝑝𝑖 𝑑𝑖 𝑟𝑖

1

3

3

0

2

4

6

5

3

7

18

3

4

2

9

9

M1

1

3’

2

4

3’’

0 3 5 9 11 16

1|𝒓𝒊, 𝒑𝒓𝒎𝒑|𝑻𝒎𝒂𝒙

𝑖 𝑝𝑖 𝑑𝑖 𝑟𝑖 𝐶𝑖 - 𝑑𝑖 𝑇𝑖

1

3

3

0

0

0

2

4

6

5

3

3

3

7

18

3

-2

0

4

2

9

9

2

2

M1

1

3’

2

4

3’’

0 3 5 9 11 16

𝑇𝑚𝑎𝑥 = 3

• Un problème à 1 seule machine • Objectif: minimiser la somme des retards. • 𝑇𝑖 = 𝑀𝑎𝑥 (0, 𝐶𝑖 − 𝑑𝑖 ) (tardiness).

𝟏|| σ 𝑻𝒊

𝑬𝑫𝑫, σ 𝑻𝒊 = 𝟏𝟎

M1

2

1

𝑖 𝑝𝑖 𝑑𝑖 𝐶𝑖 - 𝑑𝑖 (EDD) 𝐶𝑖 - 𝑑𝑖 (SPT)

1

3

6

1

-1

3

2

4

5

-1

4

4

2

12

4

-10

3

7

9

5

7

4

0 4 7 14 16

SPT, σ 𝑻𝒊 = 𝟏𝟏

M1

4

1

2

3

0 2 5 9 16

Comment avoir l’ordonnancement optimal ?

Heuristique MDD : Le problème 𝟏|| σ 𝑻𝒊 est NP-difficile au sens fort. Donc on propose le recours à l’heuristique de Baker et Bertrand qui se base sur la règle MDD (modified due date) où:

𝑀𝐷𝐷𝑖 𝑡 = max(𝑡 + 𝑝𝑖, 𝑑𝑖)

• 𝑀𝐷𝐷𝑖 𝑡 est le délai modifié de la tâche 𝑖 à la date 𝑡 • Heuristique 𝑀𝐷𝐷𝑖 𝑡

: à la date 𝑡 , dès que la machine devient

disponible, on affecte la tâche 𝑖 ayant le plus faible 𝑀𝐷𝐷𝑖 𝑡

• Un problème à 1 seule machine • Objectif: minimiser la somme des retards. • 𝑇𝑖 = 𝑀𝑎𝑥 (0, 𝐶𝑖 − 𝑑𝑖 ).

𝟏|| σ 𝑻𝒊

𝑖 𝑝𝑖 𝑑𝑖

1

3

6

2

4

5

3

7

9

4

2

12

𝑀𝐷𝐷𝑖 𝑡 = max(𝑡 + 𝑝𝑖, 𝑑𝑖)

𝟏|| σ 𝑻𝒊

t

0

𝑀𝐷𝐷𝑖

1

6

2

5

3

9

4

12

M1

2

0 4

𝑀𝐷𝐷𝑖 𝑡 = max(𝑡 + 𝑝𝑖, 𝑑𝑖)

t

0

4

𝑀𝐷𝐷𝑖 𝑀𝐷𝐷𝑖

𝟏|| σ 𝑻𝒊

1

6

7

2

5

--

3

9

11

4

12

12

M1

2

1

0 4 7

𝑀𝐷𝐷𝑖 𝑡 = max(𝑡 + 𝑝𝑖, 𝑑𝑖)

t

0

4

7

𝑀𝐷𝐷𝑖 𝑀𝐷𝐷𝑖 𝑀𝐷𝐷𝑖

𝟏|| σ 𝑻𝒊

1

6

7

--

2

5

--

--

3

9

11

14

4

12

12

12

M1

2

1

4

3

0 4 7 9 16

𝑀𝐷𝐷𝑖 𝑡 = max(𝑡 + 𝑝𝑖, 𝑑𝑖)

t

0

4

7

𝑀𝐷𝐷𝑖 𝑀𝐷𝐷𝑖 𝑀𝐷𝐷𝑖 𝐶𝑖-𝑑𝑖 𝑇𝑖

σ 𝑻𝒊= 8

𝟏|| σ 𝑻𝒊

1

6

7

--

1

1

2

5

--

--

-1

0

3

9

11

14

7

7

4

12

12

12

-3

0

M1

2

1

4

3

0 4 7 9 16

Exemple 2 ∶ 𝑴𝑫𝑫 − 𝟏|| σ 𝑻𝒊

• Un problème à 1 seule machine • Objectif: minimiser le nombre des retards • 𝑈𝑖 = 0 si 𝐶𝑖 ≤ 𝑑𝑖 , 𝑈𝑖 = 1 sinon.

𝟏|| σ 𝑼𝒊

𝑖 𝑝𝑖 𝑑𝑖 𝐶𝑖 − 𝑑𝑖 𝑇𝑖 𝑈𝑖

1

3

6

-3

0

0

2

4

5

2

2

1

3

7

9

-3

0

0

4

2

12

7

7

1

𝑴𝑫𝑫, ෍ 𝑼𝒊 = 𝟐

M1

1

2

4

3

0 3 7 9 16

𝟏|| σ 𝑼𝒊 Est-ce l’ordonnancement optimal ?

Algorithme d’Hodson et Moore : Le problème 𝟏|| σ 𝑼𝒊 est polynomial qui peut être résolu par l’algorithme d’Hodson et Moore : 1. Ranger les travaux selon la règle 𝑬𝑫𝑫 = 𝑨 2. Déterminer les𝑪𝒊 3. Soit 𝑅 = ∅ 4. Tant qu’il existe des travaux en retard dans 𝑨 faire :

• soit 𝑘, la position du premier travail en retard • soit 𝐿 le plus long travail (en terme de 𝒑𝒊) parmi les 𝑘 premiers (qui précèdent

le 1er retard)

➔ 𝐴 = 𝐴 − {𝐿} et 𝑅 = 𝑅 + {𝐿} • Avancer les tâches en aval de 𝐿 (sans modifier l’ordre 𝐸𝐷𝐷) • déterminer les 𝑪𝒊

5. Les séquences optimales sont données par les éléments de 𝐴 ordonnancés selon

𝐸𝐷𝐷 suivis par les éléments de 𝑅 dans un ordre quelconque.

𝟏|| σ 𝑼𝒊

𝑖 𝑝𝑖 𝑑𝑖 𝐶𝑖 − 𝑑𝑖 𝑈𝑖

1

3

6

1

1

2

4

5

-1

0

3

7

9

5

1

4

2

12

4

1

1. Ranger les travaux selon la règle 𝑬𝑫𝑫 ∶ 𝟐 − 𝟏 − 𝟑 − 𝟒

M1

2

1

3

4

0 4 7 14 16

𝟏|| σ 𝑼𝒊

𝑝𝑖 𝑑𝑖 𝑈𝑖

1

3

6

0

4

2

12

0

2

4

5

1

3

7

9

1

A Condition d’arrêt : Pas de retard dans l’ensemble A

R

M

1

1

4

2

3

0 3 5 9 16

Application :𝟏|| σ 𝑼𝒊

Remarques …

Ratio critique

On calcule le ratio du temps de traitement d’une tâche sur le temps restant avant la date le plus élevé promise. (Traitement par ordre décroissant du CR).

la priorité est donnée à la commande dont

le ration critique est

𝑅𝐶 =

𝑑𝑎𝑡𝑒 𝑝𝑟𝑜𝑚𝑖𝑠𝑒 − 𝑡𝑒𝑚𝑝𝑠 𝑑′𝑜𝑝é𝑟𝑎𝑡𝑖𝑜𝑛 𝑡𝑒𝑚𝑝𝑠 𝑑′𝑜𝑝é𝑟𝑎𝑡𝑖𝑜𝑛

Remarques …

Le stretch d'une tâche est défini comme son temps dans le systèmedivise par sa durée (le rapport entre son temps d'écoulement et son temps de traitement requis)

Stretch

𝑆𝑖 =

𝐶𝑖 𝑝𝑖