Contribution à la résolution des problèmes de flow shop avec machines dédiées, avec dates de disponibilité et délais de livraison

1.3 Présentation du problème étudié

Dans cette section, nous cherchons à présenter le problème considérépar le présent mémoire. En effet, il s'agit d'un problème de flowshop hybride avec machines dédiées, avec dates de disponibilitéet délais de livraison :

Fm+1 | T = m, ri, qi | Cmax

Ce problème décrit un atelier qui se compose de deux étages, avec une seule
machine au premier étage appelée machine commune M_c et m machines

au deuxième étages appelées machines dédiées. Les jobs sont disponibles ^àl'atelier à des dates appelées dates de disponibilitéri, ils s'exécutent en pre-

mier lieu sur la machine commune puis suivant le type de job Typek (avec k E {1, . . . , m}), le job sera exécutésur une seule machine au deuxième étage. Enfin tous les jobs ont des durées appelées délais de livraison qi à passer avant de quitter l'atelier. Les temps opératoires ainsi que les dates ri et délais qi sont supposés supérieurs à zéro, et les machines du deuxième étage sont indépendantes les unes des autres. Notons ici qu'une machine ne peut exécuter qu'un seul job à la fois. Le passage des jobs est unidirectionnel et chaque jobs doit ainsi s'exécuter sur deux machines.

D'autre part, dans cette configuration les jobs seront répartis, au second étage, en sous permutations selon leurs Type notée ð^k oùk E {1, . . . , m}, d'oùtout job peut être identifier par une sous permutation et une position correspondante.

Soient S une sous permutation de ð et ñ la position du job j dans S, le job j peut être identifiépar ð^ä _ñ. A ` titre d'exemple, soit la permutation suivante : ð =? J1J6J5J3J2J4 ?, les jobs seront répartis sur les machines du second étage comme indique la Figure 1.2.

Problèmes d'ordonnancement 11

Le job J3 peut être identifiépar sa sous permutation à savoir Ir¹ et sa position dans cette sous permutation 2, on note Ir¹₂.

1.3.1 Calcul du makespan

Pour le problème _Fm+1 T = m, ri, qi _Cmax, le calcul du makespan pour une solution donnée passe par la recherche du chemin critique sur la succession des opérations qui se définit comme étant le chemin le plus long sur l'ensemble des chemins possibles. Un chemin peut être définit par la donnée de trois jobs Ir_u, Ir_v et Ir^k_w avec 1 < u < v < net 1 < w < nk (voir Figure 1.3) qui vont définir une succession d'opérations des jobs sur les machines M_c et Mk. L'ordre de passage des ces jobs en partant de la date de disponibilitédu premier job r_u, en passant par les durées opératoires sur la machine commune (on tient compte des jobs ordonnancés entre Ir_u et Ir_v), ainsi que celles sur la machine Mk (Ir_v ... Ir^k_w) constitue un chemin d'opération dont la longueur Cl(u, v, w, k) constitue une borne inférieure sur le makespan de la solution. La formule de calcul de la longueur du chemin l(u, v, w, k) est donc la suivante :

Cl(u, v, w, k) = (rðu +

?v i=u

aði +

?w i=v^'

bðk i + qðkw) (1.1)

Avec

1 < u < v < n

k

Ir_v = Ir_v'

v' < w < nk

Oùv' est la position du job Ir_v sur la machine Mk, i.e Ir_v = Ir^k_v'

Le makespan d'un ordonnancement est égale à la date de sortie du dernier job de l'atelier, c'est à dire qu'il correspondent au chemin le plus long. On peut ainsi écrire :

Cmax = Max(Cl(u, v, w, k)) (1.2)

1<u<v<n

ð_v=ðk

_v'

v<w<n_k 1<k<m

Problèmes d'ordonnancement 12

- _?v aði = 2 aji = 6

i=u i=1

-

?w i=v^'

bðk i =

2 ? i=1

bð2 i = 6 + 1 + 5 = 12

FIGURE 1.3 - Calcul du makespan

(avec v^' = 1 et w = 2 : positions des jobs j2 et j4 sur la machine M2 )

Exemple

Afin de mieux illustrer le mode de calcul, on considère une instance à 5 jobs et 2 machines au second étage, cherchons le makespan de la solution ð =? j1j2j3j4j5 ?.

Jobs ri ai bi qi Type

1	2	4	4	5	1
2	5	2	6	6	2
3	3	3	5	5	1
4	4	4	5	14	2
5	6	4	7	4	1

Soit un chemin critique définissant le makespan caractérisépar les trois jobs ð_u, ð_v et ð_w (avec ð_u = j1, ð_v = j2 et ð_w = j4).

en appliquant la formule précédente on obtient :

- r_u = r1 = 2

Problèmes d'ordonnancement 13

Problèmes d'ordonnancement 14

- qðk w = q?k 4 = 14

En faisant la somme on obtient Cmax = 34, la Figure 1.4 représente cette solution à l'aide du diagramme de Gantt.

FIGURE 1.4 - Exemple pour le calcul du makespan