2.2.2 Heuristique H2
Le principe de cette heuristique est semblable à celui
de l'heuristique H1, mais cette fois la première machine
virtuelle aura comme durées opératoires les dates de
disponibilité, et la seconde machine virtuelle aura comme durées
opératoires la somme des durées ai, bi et
qi pour chaque job i E [1, n] :
av i = ri V 1
< i < n
bv i = ai +
bi + qi V 1 = i =
n
Une fois les deux machines virtuelles sont crées, on
applique l'algorithme de Johnson.
Exemple Soit les valeurs de l'instance
donnés dans le Tableau 2.1, les durées opératoires sur les
machines virtuelles sont données dans le Tableau 2.3.
Tableau 2.3 - Machines virtuelles pour H2
Jobs av i bv i
J1 8 10
J2 6 20
J3 2 16
J4 9 13
J5 9 14
Maintenant on peut appliquer l'algorithme de Johnson en
considérant le problème F2 || Cmax, on obtient
l'ordonnancement suivant :
SH2 =? J3J2J1J4J5 ?
Le makespan de cette solution est Cmax(SH2) =
37.
2.2.3 Heuristique H3
Cette Heuristique fait appel au principe de l'heuristique de
Palmer, mais avec l'intégration des dates de disponibilitéri
et les délais de livraisons qi en combinant ces deux
paramètres respectivement avec les durées opératoires de
la machine commune et celles des machines du second étage.
L'indice de Palmer se calcul comme suit :
Palmeri = (ri + ai) - (bi +
qi) ? 1 = j = n
Finalement, on ordonnance les indices de Palmer selon l'ordre
croissant.
Exemple Reprenant l'exemple donnédans
le Tableau 2.1, les indices de Palmer sont donnés dans le Tableau 2.4
:
Tableau 2.4 - Indice de Palmer Heuristique
H3
Jobs Palmeri
J1 6
J2 -2
J3 -4
J4 8
J5 -1
En triant les indices selon l'ordre croissant on obtient :
SH3 =? J3J2J5J1J4 ?
Le makespan de cette solution est Cmax(SH3) =
32.
2.2.4 Heuristique H4
L'heuristique H4 reprend le même principe que
l'heuristique précédente, sauf que l'on ignore le
paramètre qi. L'indice de Palmer se calcul donc comme suit :
Palmeri = (ri + ai) - bi ?
1 = j = n
Finalement, on ordonnance les indices de Palmer selon l'ordre
croissant.
Présentation des méthodes de résolution
32
Exemple Reprenant l'exemple donnépar
le Tableau 2.1, les indices de Palmer sont :
Tableau 2.5 - Indice de Palmer pour H4
Jobi Palmeri
J1 10
J2 8
J3 -2
J4 12
J5 0
En triant les indices selon l'ordre croissant on obtient :
SH4 = < J3J5J2J1J4
>
Le makespan de cette solution est
Cmax(SH4) = 34.
2.2.5 Heuristique H5
Cette heuristique s'inspire de celle proposée par Potts
[60] pour le F2 | ri |
Cmax. L'idée consiste à ordonnancer les
jobs disponibles selon l'ordre de Johnson. La création des deux machines
virtuelles s'impose afin d'appliquer l'algorithme de Johnson, leur
configuration est la suivante :
av i = ai +
ri V 1 < i < n
bv i = bi V 1
< i < n
Pour chaque itération, on prend les jobs disponibles et
on applique l'ordre de Johnson, ce qui nous nous fournit une exploitation
optimale de la date de disponibilité.
Exemple Soit l'exemple décrit dans le
tableau 2.1 :
|
Jobs
|
ri
|
ai
|
bi
|
qi
|
|
J1
|
8
|
4
|
2
|
4
|
|
J2
|
6
|
6
|
4
|
10
|
|
J3
|
2
|
5
|
9
|
2
|
|
J4
|
9
|
6
|
3
|
4
|
|
J5
|
9
|
2
|
11
|
1
|
Présentation des méthodes de résolution
33
les durées opératoires sur les machines
virtuelles sont données dans le Tableau 2.6
Tableau 2.6 - Machines virtuelles pour l'instance 2.1,
H5
Jobs av i 1 bv i
J1 12 2
J2 12 4
J3 7 9
J4 15 3
J5 11 11
Pour la première itération, on
sélectionne le job J3 étant donnéqu'il est le
1er à être disponible, à la date 7, la
machine Mc termine l'exécution de J3 et
devient de nouveau disponible pour exécuter. L'inspection des dates de
disponibilitérévèle que J2 est le seul job
disponible dans l'atelier, on l'ordonnance directement après J3
ce qui nous donne la séquence partielle -<
J3J2 >-, à la date 13 la machine
Mc termine l'exécution de J2 et devient de
nouveau disponible. L'inspection des dates de
disponibilitérévèle que tous les jobs sont prêt
à être exécuter. On applique alors l'ordre de Johnson en
considérant les machines virtuelles ce qui donne :
SH5 =-<
J3J2J5J4J1 >-
Le makespan de cette solution est Cmax(SH5) =
31.
| 
