2.12.4 ordonnancement en atelier
sériel (flow shop) :
Dans un système de flow shop, chaque tâche doit
passer par toutes les machines dans le même ordre. On dit que toutes les
tâches ont la même gamme opératoire. Toutes les tâches
ont le même ordre de traitement c'est-à-dire elles doivent
être traitées par la machine 1 puis par la machine 2 ...
Ceci n'implique cependant pas que sur chaque machine l'ordre
de passage des tâches soit identique.si c'est le cas, on parle de flow
shop de permutation.
o Chaque tâche i est
composée de m opérations Oij (j = 1; ...; m),
où Oi doit être effectuée sur Mj .
o Relations de précédences :
Oi1 <Oi2<
......<Oim i = 1; ...; n
o Le problème revient donc à trouver l'ordre
Pj des tâches pour chaque
machine j.
o Critère Cmax. (le temps
d'achèvement de la dernière tâche)
Bernard
Travaux en
attente Travaux
terminés
Machines
Figure 5: problème de flow
shop
2.12.5 Atelier
général (job shop) :
Dans un système de job shop, le sous-ensemble de
machines qui vont traiter les tâches et /ou l'ordre de traitement
sont arbitraires, mais doivent être spécifiés a priori.
MACHINE 3
MACHINE 2
MACHINE6
MACHINE4
MACHINE6
MACHINE5
Travail
fini
Travail en attente
Figure 6 : job shop à 4 travaux et
6 machines
Le problème d'ordonnancement de type job shop à
deux jobs, avec la prise en compte de contraintes de disponibilité des
machines se définit de la manière suivante :
o Un ensemble de m machines doit réaliser deux travaux
J1, J2.
o Chaque travail Ji est composé d'une séquence
linéaire de n opérations {Oi1, Oi2, ...,
Oin}.
o Chaque machine ne peut réaliser qu'une
opération à la fois et chaque opération Oij
nécessite une seule machine à la fois, durant pij
unités de temps.
2.12.6 5 Atelier ouvert (open
shop) :
Dans un système d'open shop, chaque tâche doit
passer par toutes les machines mais l'ordre de traitement n'est pas
donné.
o Chaque tâche i est composée de m
opérations Oij (j = 1; ... ; m), où Oij
doit être effectuée sur
Mj.
o Pas de relation de précédence.
o Le problème revient donc à trouver les ordres
des tâches (ordres des
opérations appartenant à une même
tâche) et les ordres des machines
(ordre des opérations effectuées sur la
même machine).
On peut synthétiser et généraliser cette
typologie ainsi que l'illustre la figure ( 7 ) proposée par [BILLAUT
99] :
Machines parallèles avec affectation
générale
Machines parallèles
Machine unique
Machine non
ensemble de
Dupliquée
machine
commun
Flow shop hybride
travaux
travaux travaux
mona-opération
mona-opération mona-opération
Flow shop avec affectation générale
Flow shop
machine non
ensemble de
dupliquée
machine commun
gamme unique gamme unique
gamme unique
Job shop avec affectation générale
Job shop
Machine non
Job shop généralisée
dupliquée
ensemble de
machine commun
avec gamme
avec
gamme
avec gamme
Open shop avec affectation généralisée
Open shop
Open shop généralisée
machine non
ensemble de
dupliquée
machine commun
Figure
7:Une typologie des problèmes d'ordonnancement (d'après
[Billaut99])
| 
