Problèmes d’ordonnancement sur plusieurs machines

𝐶𝑚𝑎𝑥 = 9

𝑃𝑚|𝑝𝑟𝑚𝑝|𝐶𝑚𝑎𝑥

Pour le problème 𝑃𝑚|𝑝𝑟𝑚𝑝|𝐶𝑚𝑎𝑥 , la solution optimale est obtenue avec l’algorithme de Mac Naughton (1959).

𝐶𝑚𝑎𝑥 ≥ max ෍ 𝑖

𝑃𝑖 𝑚

, max(𝑃𝑖)

Elle représente la borne inférieure pour le problème 𝑃𝑚||𝐶𝑚𝑎𝑥

Et la solution optimale pour 𝑃𝑚|𝑝𝑟𝑚𝑝|𝐶𝑚𝑎𝑥

Comment avoir l’ordonnancement optimal ?

Algorithme de Mac Naughton : On définit:

𝑀∗ = 𝑚𝑎𝑥 𝑚𝑎𝑥𝑖 𝑃𝑖, ෍

𝑖

𝑃𝑖 𝑚

1. Mettre les tâches sur la première machine, selon un ordre quelconque et sans

considérer la préemption.

2. Découper la séquence au niveau de M* et placer les tâches en aval de M* sur la machine suivante. Terminer l’ordonnancement des tâches non affectées sur cette machine.

3. Répéter l’étape 2 jusqu’à ce que toutes les tâches soient ordonnancées.

𝑖 𝑝𝑖

5

M3

1

3

2

4

3

7

4

2

5

3

6

5

𝑀∗ = 𝑚𝑎𝑥 𝑚𝑎𝑥𝑖 𝑃𝑖, ෍

𝑖

𝑃𝑖 𝑚

= 𝑚𝑎𝑥 7,8 = 8

6

0 3 8

M2

3’’

4

0 6 8

M1

1

2

3’

0 3 7 8

Exemple 1 :

Exemple 2 :

𝑃𝑚|| σ 𝐶𝑖

Comment avoir l’ordonnancement optimal ?

• Pour le problème 1|| σ 𝐶𝑖, la SPT donne la solution optimale.

• Pour le problème 𝑃𝑚|| σ 𝐶𝑖 , on appliquera la SPT généralisée qui consiste à :

• Ordonnancer les tâches selon la règle SPT.

• Affecter la première tâche de la liste non réalisée à la première machine disponible.

• NB: on souligne que la règle SPT généralisée n’est pas la seule qui optimise 𝑃𝑚|| σ 𝐶𝑖.

𝑖 𝑝𝑖

1

3

2

4

3

7

4

2

M3

5

6

5

5

3

3

𝑃𝑚|| σ 𝐶𝑖

➔SPT : 4-1-5-2-6-3

σ 𝐶𝑖=32

0 3 10

M2

1

6

0 3 8

M1

4

2

0 2 6

Exemple :

Plan du cours

1

2

3

4

5

6

Introduction et problématique générale

Machines parallèles

Flow shop

Job shop

Exemples : Résolution avec Lekin et Cplex

Travaux dirigés

𝛼|𝛽|𝛾

Problèmes d’ateliers « Flow Shop (𝜶 = 𝑭) »: C’est un atelier séquentiel, linéaire ou aussi dit à cheminement unique où les étapes de transformation sont identiques pour tous les produits fabriqués . Chaque Job est constitué d’un ensemble de tâches qui doivent s’exécuter sur les mêmes machines dans le même ordre et une seule fois.

• m machines en série : ligne de production • La gamme opératoire des jobs est une chaine • Chaque job est composé de m opérations exécutées une à la suite de l’autre sur les m

machines

Préliminaires • On souligne que les séquences de passage des tâches sur les machines peuvent différer

d’une machine à une autre.

• Dans le cas où le changement de séquence n’est pas permis : Flow shop de permutation.

➔ un ordonnancement est dit de permutation si la séquence (l’ordre d’exécution) des jobs

est la même sur toutes les machines • Une dominance est une propriété vérifiée par au moins une solution optimale.

•

les ordonnancements de permutation sont dominants pour les problèmes F2//Cmax et F2//∑Ci les ordonnancements de permutation sont dominants pour le problème F3//Cmax.

• • Les ordonnancements de permutation ne sont plus dominants sur 4 machines.

𝐹2||𝐶𝑚𝑎𝑥 Pour le problème 𝐹2||𝐶𝑚𝑎𝑥 , on cherche à trouver la séquence optimale des tâches sur chaque machine( par conséquent l’affectation des tâches).

• Un problème à 2 machines en série. • Objectif: minimiser 𝐶𝑚𝑎𝑥

Exemple : dans un atelier, les produits passent successivement sur une machine outil M1 et un poste de finition M2

𝑖 𝑝𝑖1 𝑝𝑖2

1

3

2

2

4

3

3

7

5

4

2

7

5

3

4

6

5

2

𝑀1 =⇒ 𝑀2

M2

1

2

3

4

5

6

0 3 5 7 10 14 19 26 29

31

M1

1

2

3

4

5

6

0 3 7 14 16 19 24

𝑖 𝑝𝑖1 𝑝𝑖2

1

3

2

2

4

3

3

7

5

4

2

7

5

3

4

6

5

2

Est-ce l’ordonnancement optimal ?

𝐶𝑚𝑎𝑥 = 31

Comment avoir l’ordonnancement optimal ?

Règle à suivre :Algortihme de Johnson pour 𝑭𝟐||𝑪𝒎𝒂𝒙 • Former deux ensembles :

• S1 : tous les travaux tels que pi1 < pi2 • S2: tous les travaux tels que pi1 > pi2 • Les travaux ayant : pi1 = pi2 peuvent être dans S1 ou S1

• Ordonnancer les tâches :

• S1 selon l’ordre croissant de pi1 (règle SPT) • S2 selon l’ordre décroissant de pi2 (règle LPT)

• Cet ordonnancement est noté SPT(1)-LPT(2) • Remarque : Plusieurs ordonnancements peuvent être générés

Algortihme de Johnson

𝑖 𝑝𝑖1 𝑝𝑖2

1

3

2

2

4

3

3

7

5

4

2

7

5

3

4

6

5

2

• S1 : tous les travaux tels que pi1 < pi2: 4-5 • S2: tous les travaux tels que pi1 > pi2 :1-2-3-6

• S1 selon Pi1 croissant (SPT): 4-5 • S2: selon l’ordre décroissant de Pi2 (règle LPT) : 3-2-1-6

• Ordonnancement optimal : 4-5- 3-2-1-6

𝑀1 =⇒ 𝑀2

M2

4

5

3

2

1

6

0 2 9 13 18 21 24 26

M1

4

5

3

2

1

6

0 2 5 12 16 19 24

𝑖 𝑝𝑖1 𝑝𝑖2

1

3

2

2

4

3

3

7

5

4

2

7

5

3

4

6

5

2

𝐶𝑚𝑎𝑥 = 26

𝐹3||𝐶𝑚𝑎𝑥 Pour le problème 𝐹3||𝐶𝑚𝑎𝑥 , on cherche à trouver la séquence optimale des tâches sur chaque machine( par conséquent l’affectation des tâches).

• Un problème à 3 machines en série. • Objectif: minimiser 𝐶𝑚𝑎𝑥

Le problème 𝑭𝟑||𝑪𝒎𝒂𝒙 est un problème NP-difficile. Toutefois, dans le cas où la deuxième machine est dominée soit par la première machine soit par la troisième machine, autrement dit, le (min Pi1≥ max Pi2) ou (min Pi3≥ max Pi2), le problème peut être résolu.

Comment avoir l’ordonnancement optimal ?

Règle à suivre :Algorithme de Johnson pour 𝑭𝟑||𝑪𝒎𝒂𝒙

• Créer deux machines fictives M’1 et M’2 dont les durées d’exécution suivantes :

• Appliquer l’algorithme de Johnson pour avoir une séquence optimale.

P’i1 = Pi1 + Pi2 et P’i2 =Pi2 + Pi3

𝐹3||𝐶𝑚𝑎𝑥

𝑖 𝑝𝑖1 𝑝𝑖2

𝑝𝑖3

1

6

2

5

2

4

3

5

3

7

1

7

4

3

2

6

5

3

3

5

6

5

2

4

• S1 : tous les travaux tels que p’i1 < p’i2: 2-4-5 • S2: tous les travaux tels que p’i1 > p’i2 :1-3-6

1 𝑖 𝑝′𝑖1 8 𝑝′𝑖2 7

2

7

8

3

8

8

4

5

8

5

6

8

6

7

6

• S1 selon P’i1 croissant (SPT): 4-5-2 • S2: selon l’ordre décroissant de P’i2 (règle LPT) : 3-1-6

• Ordonnancement optimal : 4-5-2-3-1-6

M3

M2

4

5

2

3

1

6

0 5 10 15 20 27 32

36

4

5

2

3

1

6

0 3 5 6 9 10 13 17 18 23 25 28 30

M1

4

5

2

3

1

6

0 3 6 10 17 23 28

𝑖 𝑝𝑖1 𝑝𝑖2

𝑝𝑖3

1

6

2

5

2

4

3

5

3

7

1

7

4

3

2

6

5

3

3

5

6

5

2

4

𝐶𝑚𝑎𝑥 = 36

𝐹𝑚||𝐶𝑚𝑎𝑥 Pour le problème 𝐹𝑚||𝐶𝑚𝑎𝑥 , on cherche à trouver la séquence optimale des tâches sur chaque machine( par conséquent l’affectation des tâches).

• Un problème à m machines en série. • Objectif: minimiser 𝐶𝑚𝑎𝑥 • m >= 3 ➔ problème NP difficile (cas général)

Heuristique CDS (Campbell, Dudek et Smith (1970) pour 𝑭𝒎||𝑪𝒎𝒂𝒙

• Générer m-1 solutions en appliquant l’algorithme de Johnson sur (m-1) sous problèmes à deux machines fictives. La première regroupe les k premières machines, la deuxième regroupe les k dernières machines, k varie de 1 à m-1. Les temps opératoires de chaque tâche i (i = 1...n), sur ces deux machines fictives sont données par :

• Retenir la meilleure des m-1 solutions (plus faible Cmax)

Application: Soit le problème à 3 machines et 5 tâches, dont les temps opératoires sont données par le tableau ci-dessous :

1 𝑖 𝑝𝑖1 10 𝑝𝑖2 5

2

7

6

𝑝𝑖3

3

11

3

14

3

7

4

6

9

2

5

4

7

13

k varie de 1 à m-1 ➔ k varie entre 1 et 2.

1 𝑖 𝑝𝑖1 10 𝑝𝑖2 5

2

7

6

𝑝𝑖3

3

11

1 𝑖 𝑝1𝑖1 10 𝑝1𝑖2

3

2

7

11

3

14

3

7

3

14

7

4

6

9

2

4

6

2

5

4

7

13

5

4

13

K=1:

m-1 solutions ➔ 2 solutions

K=2:

3

2

4

1

5 𝑖 𝑝2𝑖1 15 13 17 15 11 𝑝2𝑖2

17 10 11 20

8

L’ordonnancement obtenu en appliquant l’algorithme de Johnson est 5-2-3-1-4 La séquence optimale est 5-2-4-3-1 et l'ensemble des tâches sera terminé au bout de 49. ➔Le meilleur ordonnancement parmi ces deux solutions est 5-2-4-3-1 avec une date d'achèvement de 49

Application

Plan du cours

1

2

3

4

5

6

Introduction et problématique générale

Machines parallèles

Flow shop

Job shop

Exemples : Résolution avec Lekin et Cplex

Travaux dirigés

Rappel

Problèmes d’ateliers « Job Shop (𝜶 = 𝑱) »:

Règle à suivre :Algorithme de Jackson pour 𝑲𝒎||𝑪𝒎𝒂𝒙

𝐽𝑚||𝐶𝑚𝑎𝑥

• Le problème 𝐽𝑚||𝐶𝑚𝑎𝑥 est NP-difficile pour m ≥ 3 • Le problème 𝐽2||𝐶𝑚𝑎𝑥 est polynomial : algorithme de Jackson 1. Soit A l’ensemble des tâches utilisant les machines 1 puis 2, rangées

selon la règle de Johnson

2. Soit B l’ensemble des tâches utilisant les machines 2 puis 1, rangées

selon la règle de Johnson

3. Soit C l’ensemble des tâches utilisant uniquement la machine 1, rangées

dans n’importe quel ordre

4. Soit D l’ensemble des tâches utilisant uniquement la machine 2, rangées

dans n’importe quel ordre

• Faire passer sur la machine 1 :A, puis C, puis B. • Faire passer sur la machine 2 : B, puis D, puis A

𝐽2||𝐶𝑚𝑎𝑥

𝐽2||𝐶𝑚𝑎𝑥

Plan du cours

1

2

3

4

5

6

Introduction et problématique générale

Machines parallèles

Flow shop

Job shop

Exemples : Résolution avec Lekin et Cplex

Travaux dirigés