1.4.4.2 Procédure par séparation et
évaluation PSE
Sans aucun doute, la procédure de séparation et
évaluation (Brunch & Bound) est la technique
préférée pour la résolution optimale des
problèmes de flow shop hybride, mais la plupart des recherches ont
portésur les versions simplifiées du problème [63]. L'une
de ces version simplifiée est le flow shop à deux étages
avec une seule machine au premier étage et deux machines au second
étage. Selon Ruiz et al. [63] la première
procédure traitant ce problème a
étéproposépar Rao [61], plus tard, Bolat et al.
[6] ont étudiéle même problème en
présentant une PSE, des heuristiques et un algorithme
génétique. Le problème inverse ou «miroir» de ce
dernier (deux machines au premier étage et une seule au second
étage) a étéétudiépar Arthanary et Ramaswamy
[1] puis par Mittal et Bagga [54]. Les problèmes avec deux étages
et in machines parallèles au second étage ont
étéétudiés par Lee et Kim [48] en proposant une PSE
avec l'objectif de minimiser la somme total des retards. le problème
d'assemblage (in machine au premier étage et une seule au
second étage) a étéétudiépar Gupta et
al. [32] en proposant une PSE générant de bonnes solutions
en un temps raisonnable.
Les travaux traitants les problèmes du flow shop avec
la prise en compte des dates disponibilitéou des délais de
livraison sont très rare notamment en ce qui concerne la
résolution exactes utilisant une PSE. Nous présentons dans la
suite les travaux de Tadeiet al. [65] et Grabowski qui ont
proposédes PSE pour ces problèmes.
Grabowski [25] a proposéune PSE pour le problème
F2 ri Cmax puis
il a étendu ses recherches dans [28] pour étudier le
problème Fm ri,
qi Cmax, il a
présentéun schéma de branchement reposant sur des bornes
inférieures obtenues en relaxant la contrainte de capacitédes
machines (une machine peut exécuter deux jobs à la fois au lieu
d'un seul jobs). La séquence initiale du noeud racine a
étéobtenue en appliquant une heuristique. Dans chaque noeud de
l'arbre de recherche on a une séquence complète, un chemin
critique et une borne inférieure. A ` chaque permutation, une nouvelle
séquence est générée en affectant un changement
dans le chemin critique, l'auteur affirme que cette approche simplifie les
calculs et l'obtention des bornes inférieures.
Tadeiet al. ont présentédeux
schémas de branchement pour le problème F2
ri Cmax. Pour
les deux schémas, l'obtention d'une séquence de départ
repose sur la règle ERT (Earliest Release Time) qui consiste
à ordonnancer les jobs selon l'ordre croissant des dates de
disponibilitéri.
Pour le premier schéma de branchement, chaque noeud
correspond à une sous séquence de j jobs, les nouveaux
noeuds sont générés par l'ajout d'un
Problèmes d'ordonnancement 24
nouveau job à la position j + 1 après
l'application des propriétés de dominance, pour la phase de
l'évaluation une parmi cinq bornes proposées sera
calculée.
Pour la phase de sélection du nouveau noeud, on cherche
le noeud avec la borne inférieure la plus faible et on commence une
nouvelle phase de génération.
Pour le schéma de branchement dichotomique, chaque
noeud correspond àun ensemble de contraintes de
priorité, les nouveaux noeuds sont générés par
l'ajout de nouvelles contraintes de priorité, ce
schéma utilise le même principe que le schéma
précédent pour l'initialisation de la sous séquence
optimale de départ, puis une propriétéde dominance est
appliquée pour la détermination de l'ensemble des contraintes de
prioritédu noeud racine, ensuite pour une sous séquence
satisfaisant ces contraintes on détermine un chemin critique contenant
deux blocs critiques, pour la phase de génération, de nouveaux
noeuds sont générés en examinant les deux blocs
dérivés.
Les tests effectués pour plusieurs classes d'instances
(10 classes) sur des tailles différentes des problèmes
(jusqu'à200 jobs) indiquent que le premier schéma était
plus performant que le schéma dichotomique (notons que le temps de
calcul était limitéà 300 secondes).
conclusion
Après avoir présentéles notions de base
pour l'ordonnancement, nous avons présentéle problème
étudié, en effet, le présent mémoire
considère un problème de flow shop hybride avec machines
dédiées, avec dates de dis-ponibilitéet délais de
livraison. Bien que les problèmes de flow shop sont les plus
étudiés dans la littérature, les travaux portant sur des
problèmes semblables au notre sont très rares. Nous avons
orienténos travaux vers
le développement et l'adaptation des méthodes de
résolution approchées àsavoir les heuristiques
et le méta-heuristiques.
| 
