Constructions agrégatives d’ordonnancements pour des
jobs-shops statiques, dynamiques et réactifs
Bernard Penz
To cite this version:
Bernard Penz. Constructions agrégatives d’ordonnancements pour des jobs-shops statiques, dynamiques et réactifs. Modélisation et simulation. Université Joseph-Fourier - Grenoble I, 1994.
Français. �tel-00005107�
HAL Id: tel-00005107
https://tel.archives-ouvertes.fr/tel-00005107
Submitted on 25 Feb 2004
HAL is a multi-disciplinary open access
archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.
L’archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d’enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
These
presentee par
Bernard PENZ
Pour obtenir le titre de
Docteur de l'universite Joseph Fourier - Grenoble 1
(arr^etes ministeriels du 5 juillet 1984 et du 30 mars 1992)
Specialite : Mathematiques Appliquees
Formation Doctorale : Recherche Operationnelle
Constructions agregatives d'ordonnancements pour
des job-shops statiques, dynamiques et reactifs
soutenue le 5 decembre 1994 devant le jury suivant :
MM
Pierre Ladet
Alain Guinet
Marino Widmer
Pierre Lopez
Lionel Dupont
Gerd Finke
President
Rapporteur
Rapporteur
Examinateur
Directeur
Directeur
These preparee au sein du laboratoire ARTEMIS-IMAG
ii
Remerciements
Je commencerai par remercier M. Pierre Ladet d'avoir accepte de
presider ce jury. J'ai eu l'occasion, dans le cadre du Groupement Scienti que Interdisciplinaire pour la Productique (GSIP), de travailler dans
son equipe et d'apprecier son dynamisme.
Ma reconnaissance va ensuite aux rapporteurs, M. Alain Guinet et
M. Marino Widmer, ainsi qu'a M. Pierre Lopez. Tous trois ont consacre
beaucoup de temps a lire mon document. Je les remercie ici pour leurs
corrections constructives, leur contact direct et sympathique.
A ARTEMIS-IMAG, mes deux codirecteurs, M. Lionel Dupont et
M. Gerd Finke, ont taille le cadre administratif de ce travail. Le document a beaucoup gagne en clarte a la suite des nombreuses lectures de
M. Lionel Dupont durant ces derniers mois. Je l'en remercie ici, ainsi
que pour l'aide qu'il m'a fournie tout au long de ma these.
Comme je l'ai deja signale, j'ai eu l'occasion de travailler avec des
chercheurs exterieurs au laboratoire ARTEMIS-IMAG, M. Zdeneck Binder, remarquable par la profusion des idees, M. Abderamane Fadil,
M. Vladimir Bourgade, et M. Luiz Manoel Aguilera. De ce dernier, j'ai
beaucoup apprecie la rigueur, les idees, la generosite qui ont fait un ami
autant qu'un collaborateur.
iv
Toujours dans le m^eme cadre, j'ai encadre M. Alexis Maire pour son
DEA de Genie Industriel. Son excellent travail m'a bien pro te puisque
la programmation d'une partie des heuristiques est de son fait. Qu'il
soit remercie ici pour l'abscence de bugs.
Je remercie en bloc toute l'equipe d'ARTEMIS-IMAG et en particulier la joyeuse bande des thesards avec lesquels ces trois ans de theses
sont trop vite passes.
Aux heures diciles, la famille est toujours la. Je la remercie pour
le reconfort qu'elle m'a apporte avant, pendant et apres la soutenance.
Resume
Dans ce memoire, notre objectif est de presenter une nouvelle approche de resolution pour des problemes d'ordonnancement de type
job-shop. Les problemes traites sont de grande taille, ce qui, du fait
de la complexite du probleme, ne permet d'envisager que l'utilisation
d'heuristiques. Cette approche propose une alternative aux algorithmes
bases sur des regles de priorite, generalement utilises. Le principe de
l'approche est de construire une succession d'ordonnancements partiels,
en agregeant les jobs les uns apres les autres. L'agregation consiste a
inserer toutes les operations du job a agreger sans changer l'ordre des
operations dans l'ordonnancement partiel precedent.
Dans un premier temps, des methodes issues de l'approche sont
proposees pour resoudre le probleme classique du job-shop. Ensuite,
ces methodes sont etendues pour traiter des problemes de job-shop generalise, ou l'a ectation des operations aux machines n'est pas xee
au depart. Pour nir, des problemes de job-shop dynamiques et reactifs sont abordes. Dans ceux-ci, l'arrivee aleatoire de jobs et l'arr^et de
machines sont pris en compte. Les methodes agregatives sont particulierement bien adaptees a la resolution de ce type de probleme.
vi
vii
Table des matieres
Introduction
1 Le probleme du job-shop
1.1 Le probleme
1.1.1 Les donnees
1.1.2 Les contraintes
1.1.3 Les objectifs
1.1.4 La complexite
1.2 Les modelisations
1.2.1 La modelisation par graphe disjonctif
1.2.2 Les modelisations en programmation mathematique
1.2.2.1 Le modele de A.S. Manne
1.2.2.2 Le modele de E. Pinson
1.2.2.3 Le modele de H.M. Wagner
1.2.2.4 Le modele de E.H Bowman
1.2.3 La modelisation polyedrale
1.2.4 La modelisation algebrique
1.3 Les methodes de resolution
1.3.1 Une classi cation des methodes
1.3.2 Les problemes polyn^omiaux
1.3.2.1 Le probleme a deux machines
1.3.2.2 Le probleme a deux jobs
1.3.3 Les methodes heuristiques
1.3.3.1 Les heuristiques constructives
1.3.3.2 Les heuristiques amelioratrices
1.3.3.3 Les reseaux de neurones
: : : : : : : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : : :
: : : : : : :
: : : : : : : : : : : : : : : : : : : : : : : : :
: : : : : : : :
: : : : : : : : :
: : : : : : :
: : : : : : :
: : : : : : : : : : : : :
: : : : : : : : : : : : :
: : : : : : : : : : : : : : : : :
: : : : : : : : : :
: : : : : : : : : : : :
: : : : : :
: : : : : : : : :
: : : : : : : : : : : : :
: : : : : :
: : : : :
: : : : : : : : :
1
5
6
6
7
8
8
9
9
11
11
12
12
15
16
17
19
19
20
20
22
23
23
26
33
TABLE DES MATIE RES
viii
1.3.3.4 L'intelligence arti cielle
1.3.3.5 Caracterisation des solutions admissibles
1.3.4 Les methodes exactes
1.3.5 Les methodes de relaxation
1.3.6 Les methodes de decomposition
: : : : : : : : :
: : : : : : : : : : : : : : : :
: : : : : : : : : : : :
: : : : : : : : : :
2 Une approche par agregation
2.1 Le principe de l'agregation
2.1.1 Ordonnancement partiel sur jobs
2.1.2 L'agregation de deux jobs
2.1.3 L'agregation d'un job et d'un ordonnancement
partiel
2.1.4 L'agregation de deux L
ordonnancements partiels
2.2 Les algorithmes de type +1 2.2.1 L'algorithme general de resolution
2.2.2 Les procedures de selection des jobs L
2.2.3 Une procedure basee sur l'agregation 1 2
2.2.4 Des procedures d'agregation par decoupage du
temps
2.2.4.1 Decoupage du temps et agregation globale
2.2.4.2 Decoupage du temps et insertion iterative
2.2.4.3 Decoupage du temps et insertion relative
2.2.5 Agregation globale par
fonction co^ut
L
2.3 Les algorithmes de type
2.3.1 L'algorithme general de resolution
2.3.2 Les procedures de groupement des jobs
2.3.2.1 Une methode de decomposition
2.3.2.2 Un regroupement de jobs dissemblables
2.3.2.3 Un regroupement de jobs decales
2.3.3 Les procedures d'agregation
2.4 L'amelioration locale
2.4.1 Amelioration par permutations
2.4.2 La reagregation
2.5 Resultats numeriques
2.5.1 Presentation des jeux de donnees
2.5.2 Resultats et conclusions
2.6 Conclusion
: : : : : : : : : : : : : : : : :
l
: : : : : : : : :
: : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : : : : :
:
Jl
Pl
: : : : : : : : : : : : :
: : : : : : : : :
: : : : : : : :
J
J
: : :
: : : : : : : : : : : : : : : : : : : : : : : :
: : : : : : :
Pl
Pr
: : : : : : : : : : : : : :
: : : : : : : : :
: : : : : :
: : : : :
:
: : : :
: : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : :
: : : : : : : : : :
: : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : :
: : : : : : : : :
: : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : : : : : : :
34
34
35
37
37
39
40
40
42
46
46
47
47
49
49
50
50
56
56
61
66
69
69
69
72
72
73
74
74
76
76
78
78
84
TABLE DES MATIE RES
ix
3 Le job-shop generalise
87
3.1 Une presentation du probleme
3.1.1 Description du probleme
3.1.2 Les methodes de resolution connues
3.2 Les modelisations du probleme
3.2.1 La modelisation de H.M. Wagner
3.2.2 Une nouvelle modelisation
3.3 Des methodes de resolution
3.3.1 Heuristiques constructives une-phase
3.3.2 Heuristiques constructives deux-phases
3.3.2.1 L'a ectation lineaire
3.3.2.2 L'a ectation lineaire avec capacites
3.3.2.3 L'a ectation de separation
3.3.2.4 L'a ectation de decomposition
3.3.3 Heuristiques amelioratrices
3.3.3.1 Optimisation par permutations d'operations
3.3.3.2 Optimisation par rea ectations
3.3.3.3 Optimisation par permutations et reaffectations
3.3.3.4 Optimisation par reagregation
3.4 Resultats numeriques
3.4.1 Presentation des jeux de donnees
3.4.2 Resultats et conclusions
3.5 Conclusion
: : : : : : : : : : : : : : :
: : : : : : : : : : : : : :
: : : : : : : :
: : : : : : : : : : : : : : :
: : : : : : : : :
: : : : : : : : : : : : :
: : : : : : : : : : : : : : : :
: : : : : : :
: : : : : :
: : : : : : : : : : :
: : :
: : : : : : : :
: : : : :
: : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : :
: : : : :
: : : : : : : : : : : : : : : : :
: : : : : :
: : : : : : : : : : : : : : : : : : : :
: : : : : : : : :
: : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : : : : : : :
4 Le job-shop dynamique et reactif
4.1 Presentation du probleme
4.1.1 Description du probleme
4.1.2 Les methodes de resolution connues
4.1.2.1 Decomposition en job-shop statique
4.1.2.2 Les regles de priorite
4.2 Une approche de resolution
4.2.1 L'algorithme general de resolution
4.2.2 L'arrivee aleatoire des jobs
4.2.3 Les arr^ets machine
4.2.3.1 La rea ectation
88
88
90
90
91
93
95
95
97
97
98
99
100
101
101
101
102
103
103
104
104
107
111
: : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : :
: : : : : : : :
: : :
: : : : : : : : : : :
: : : : : : : : : : : : : : : :
: : : : : : : : :
: : : : : : : : : : : : :
: : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : :
112
112
114
114
115
117
117
119
119
121
TABLE DES MATIE RES
x
4.2.3.2 La reagregation
4.2.4 La reoptimisation locale
4.3 Resultats numeriques
4.3.1 Presentation des jeux de donnees
4.3.2 Resultats et conclusions
4.3.2.1 Resultats pour l'atelier 1
4.3.2.2 Resultats pour l'atelier 2
4.3.2.3 Resultats pour l'atelier 3
4.3.2.4 Remarques generales
4.4 Conclusion
: : : : : : : : : : : : : :
: : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : :
: : : : : : : : :
: : : : : : : : : : : : : :
: : : : : : : : :
: : : : : : : : :
: : : : : : : : :
: : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : : : : : : :
Conclusion
121
123
123
125
126
130
132
135
138
141
143
xi
Table des gures
1.1
1.2
1.3
1.4
1.5
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
2.10
2.11
2.12
2.13
2.14
2.15
2.16
2.17
2.18
2.19
2.20
2.21
2.22
Une classi cation des methodes de resolution
Algorithme de liste par regles de priorite
Algorithme tabou
Algorithme de recuit simule
Algorithme genetique
Plan avec obstacles
Reseau associe au plan
Resultat de l'exemple
Algorithme general base sur +1 L L
Algorithme d'agregation base sur 1 2
Algorithme de decoupage du temps et agregation globale
Resultat de l'agregation globale
Algorithme de decoupage du temps et insertion iterative
Premiere insertion pour l'agregation iterative
Deuxieme insertion pour l'agregation iterative
Derniere insertion pour l'agregation iterative
Algorithme de decoupage du temps et insertion relative
Premiere insertion pour l'agregation relative
Deuxieme insertion pour l'agregation relative
Derniere insertion pour l'agregation relative
Algorithme d'agregation a l'aide d'une fonction co^ut
Resultat de l'agregation par fonction
co^ut
L
Algorithme general base sur
Algorithme d'amelioration locale par permutations
Algorithme d'amelioration par reagregations
Les types d'instances generees
Job-shop, atelier 1
: : : : : : :
: : : : : : : : :
: : : : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : :
Jl
Pl : : : : : : : : : : :
J
J
: : : : : : : : :
: : : : : : : : : : : : : :
: : : : : : :
: : : : : :
: : : : : : :
:
: : : : : : :
: : : : : : :
: : : : : : :
: : :
: : : : : : : :
Pl
Pr : : : : : : : : : : : :
: : :
: : : : : : :
: : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : :
21
24
27
30
31
43
45
45
48
51
54
55
57
58
59
60
62
63
64
65
67
68
70
75
77
79
83
TABLE DES FIGURES
xii
2.23
2.24
2.25
3.1
3.2
3.3
3.4
3.5
3.6
3.7
4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
4.9
4.10
4.11
4.12
4.13
4.14
4.15
Job-shop, atelier 2
Job-shop, atelier 3
Job-shop, problemes classiques
Matrice des temps operatoires pour le job
Algorithme d'amelioration par rea ectations
Composition des ateliers
Les types d'instances generees
Job-shop generalise, atelier 1
Job-shop generalise, atelier 2
Job-shop generalise, atelier 3
Algorithme general
Algorithme de resolution general
Algorithme de rea ectation apres arr^et d'une machine
Algorithme de reagregation apres arr^et d'une machine
Composition des ateliers
Les types d'instances generees
Job-shop dynamique, atelier 1
Job-shop reactif, atelier 1
Job-shop dynamique et reactif, atelier 1
Job-shop dynamique, atelier 2
Job-shop reactif, atelier 2
Job-shop dynamique et reactif, atelier 2
Job-shop dynamique, atelier 3
Job-shop reactif, atelier 3
Job-shop dynamique et reactif, atelier 3
: : : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : :
Ji
: : : : : : :
: : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : :
: :
: :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : :
: : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : :
: : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : :
: : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : :
84
85
86
89
102
104
105
107
108
108
116
120
122
124
125
127
131
132
133
134
135
136
137
138
139
INTRODUCTION
1
Introduction
\L'ordonnancement est la distribution des ressources dans le temps
pour realiser un ensemble d'activites". Cette de nition tres generale
de l'ordonnancement donnee par K.R. Baker [9] ne permet pas de voir
le nombre important de problemes que ce domaine comprend. En effet, l'ordonnancement est lie a des secteurs de recherches et d'activites
tres varies. En informatique tout d'abord, le partage de la memoire, le
choix des t^aches a envoyer aux processeurs se modelisent comme des
problemes d'ordonnancement [17]. L'organisation de grands projets de
constructions navales ou aeronautiques, de grands chantiers routiers ou
ferroviaires et en general les constructions de travaux publics font egalement appel a cette theorie [36]. En n, nous pouvons citer l'organisation
de la production dans les entreprises manufacturieres [60].
La theorie de l'ordonnancement est une branche de la recherche operationnelle. Elle consiste en la recherche de modeles mathematiques et
la mise au point de methodes de resolution ecaces des problemes poses. Depuis plus de quarante ans, un e ort de recherche important est
mene par les informaticiens, les automaticiens et les specialistes de la
recherche operationnelle. Les problemes traites par la theorie de l'ordonnancement sont classes en di erentes categories, comme les problemes
de machine simple, les problemes de machines paralleles, les problemes
de type ow-shop, job-shop, open-shop, et l'ordonnancement de projets. Pour plus de details, de nombreux ouvrages de reference traitent
de tous ces problemes [9] [48] [57] [95].
2
INTRODUCTION
Dans ce memoire de these, nous nous interessons plus particulierement aux problemes de type job-shop et a quelques unes de ses generalisations. Avec les problemes de machines simples et paralleles, le
job-shop est sans doute le probleme de la theorie de l'ordonnancement
le plus traite. Du fait de sa complexite importante, il demeure certainement l'un des problemes de l'optimisation combinatoire le plus dicile.
Mettre au point une methode de resolution pour ce probleme n'est
pas chose facile. Les criteres a prendre en compte sont nombreux lors
de son elaboration, et la connaissance de la structure du probleme n'est
pas susante. En e et, il est indispensable de savoir si l'on privilegie
la qualite de la solution cherchee ou la rapidite du temps de calcul.
Ces criteres etant opposes, il faut choisir l'un ou l'autre, ou trouver un
compromis. La deuxieme diculte est la taille des instances traitees
par la methode. Il n'est pas possible de traiter de la m^eme facon un
probleme de tres petite taille et un probleme de tres grande taille. Ces
dicultes seront prises en compte lors de la conception des methodes
de resolution proposees plus loin.
L'approche que nous allons proposer dans les pages suivantes se veut
une alternative aux methodes basees sur des regles de priorite, communement utilisees pour traiter les problemes d'ordonnancement de taille
importante. De plus, elle est developpee plus particulierement pour la
resolution de problemes faisant intervenir des evenements aleatoires durant le deroulement de l'ordonnancement. C'est ainsi que seront traites
les arrivees aleatoires de jobs et les arr^ets momentanes des machines.
Le premier chapitre est consacre a un etat de l'art sur le job-shop
statique et deterministe. Celui-ci est une des representations les plus
simples d'un atelier de fabrication. Apres avoir presente ce probleme,
nous faisons un tour d'horizon des di erentes facons de le modeliser.
En n, nous proposons une classi cation des methodes de resolution
connues en distinguant les di erentes approches.
Dans le deuxieme chapitre, nous proposons une nouvelle approche
de resolution basee sur un principe d'agregation. Cette nouvelle approche consiste a construire une succession d'ordonnancements partiels
INTRODUCTION
3
en ajoutant des jobs les uns apres les autres. L'objectif de cette approche
est d'aborder progressivement les dicultes du probleme de maniere a
casser sa complexite. Une premiere partie est consacree a l'explication
du principe d'agregation. Dans la suite, nous proposons des algorithmes
de resolution generaux et donnerons des procedures d'agregation et de
selection des jobs utilisees dans ces algorithmes. Pour nir, des tests
comparatifs des di erentes heuristiques seront donnes et commentes.
Le troisieme chapitre est consacre au probleme du job-shop generalise. La generalisation vient du fait que, contrairement au job-shop
statique et deterministe, les operations de chaque job ne sont pas a ectees a une machine unique, mais peuvent ^etre executees par plusieurs
machines. En plus des dicultes du job-shop statique et deterministe, le
job-shop generalise ajoute le probleme d'a ectation des operations aux
machines. Dans ce chapitre, nous decrivons le probleme et di erentes
modelisations. Ensuite, nous proposons quelques approches de resolution basees principalement sur l'agregation. Pour nir, nous ferons une
etude comparative de ces methodes en les testant sur une bibliotheque
de jeux de donnees prealablement creee.
Nous abordons, dans le quatrieme chapitre, les aspects dynamiques
et reactifs qui peuvent ^etre lies aux problemes de job-shop. Ce type de
probleme s'attache a la fois a la creation de l'ordonnancement a partir
d'un ensemble de jobs, mais egalement au deroulement de l'ordonnancement au cours du temps. Par aspect dynamique, nous entendons le fait
que certains jobs peuvent arriver dans l'atelier a un instant quelconque
du deroulement de l'ordonnancement initialement prevu. La reactivite
est liee au phenomene d'arr^et des machines, pour cause de pannes, par
exemple. Pour cela, nous reprenons le probleme du job-shop generalise
et ajoutons des phenomenes aleatoires comme l'arr^et d'une machine ou
l'arrivee d'un job supplementaire. Si les problemes traites precedemment (job-shop statique et deterministe et job-shop generalise) etaient
\o -line", c'est-a-dire que toutes les donnees sont connues des le commencement de l'optimisation, le job-shop dynamique est un probleme
\on-line", c'est-a-dire que des donnees arrivent aleatoirement au cours
du temps. Dans un premier temps, nous decrivons le probleme et faisons le tour d'horizon des methodes connues. Ensuite, nous proposons
4
INTRODUCTION
une methode de resolution basee sur le principe d'agregation et sur
les resultats obtenus pour le job-shop generalise. Pour nir, nous comparerons les heuristiques avec des algorithmes bases sur des regles de
priorite, sur une bibliotheque de jeux de donnees creee a cet e et.
Pour conclure ce memoire de these, nous reprendrons les grandes
lignes du travail e ectue et presente ici. L'approche developpee est trop
generale pour que toutes les possibilites de son utilisation puissent ^etre
decrites. Pour cela, nous donnerons quelques directions de recherche
qu'il nous semble interessant de suivre.
5
Chapitre 1
Le probleme du job-shop
Le probleme du job-shop statique et deterministe est un des problemes de la theorie de l'ordonnancement et de l'optimisation combinatoire les plus traites [9] [30] [48] [95]. Il est dit statique car toutes les
donnees du probleme sont connues au depart (les aspects dynamiques
seront abordes dans le chapitre 4) et deterministe car les temps associes
a chaque operation sont parfaitement determines (l'incertitude sur les
durees des operations ne sera pas traitee dans cette these). Par la suite,
les termes de statique et deterministe seront volontairement omis. Le
job-shop propose, du fait de sa structure fortement combinatoire, des
dicultes importantes pour la recherche de l'optimalite de ses solutions,
et m^eme pour la recherche d'heuristiques performantes.
Le but de cet etat de l'art est de presenter le probleme et de repertorier toutes les methodes de resolution envisagees ces dernieres annees.
En aucun cas, un jugement de valeur ne sera porte sur l'ecacite des
methodes proposees car les approches donnees et les natures m^emes des
problemes traites sont extr^emement variables.
Dans un premier temps, le job-shop est presente en precisant les
donnees, les contraintes et les objectifs du probleme. Quelques modeles
classiques et moins classiques tires de la litterature sont ensuite exposes.
Certains modeles servent de support a la mise en place de methodes de
resolution, d'autres, ne sont interessants que par leur c^ote theorique.
Nous proposons une classi cation des methodes de resolution connues
CHAPITRE 1. LE PROBLE ME DU JOB-SHOP
6
et a partir de celle-ci, nous repertorions les principales heuristiques et
methodes exactes que l'on peut trouver dans la litterature.
1.1 Le probleme
Les variations autour du probleme du job-shop sont nombreuses et il
n'est pas possible de trouver dans la litterature une formulation unique
de celui-ci. Nous donnons ici une formulation la plus generale possible
et se rapprochant de l'ensemble de ce que l'on peut trouver sur ce sujet.
1.1.1 Les donnees
La terminologie utilisee dans le domaine de l'ordonnancement est
issue du contexte industriel et plus precisement des ateliers de fabrication des entreprises manufacturieres. Nous emploierons tout au long de
ce memoire les termes de job, operation, machine, gamme operatoire ou
encore temps operatoire. Les donnees du probleme sont les suivantes :
1. Un ensemble M de m machines. Chaque machine est specialisee
et ne peut e ectuer qu'un seul type d'operation. Une machine
est notee M avec k = 1, ..., m. Le nombre total d'operations
executees par cette machine est note m .
k
k
2. Un ensemble J de n jobs. Chaque job est compose d'une gamme
operatoire i.e. une suite lineaire xee de n operations. Cette sequence ne depend que du job et peut varier d'un job a l'autre.
Un job est note J avec i = 1, ..., n.
i
i
3. L'operation O est la jeme operation dans la gamme operatoire
de J . La date de debut calculee de O sera notee t .
i;j
i
i;j
i;j
4. L'operation O necessite l'utilisation de la machine M . Le fait
que la machine demandee par l'operation O soit M s'ecrit
R(O ) = M . La duree de O sur M , appelee temps operatoire, est notee p .
i;j
k
i;j
i;j
k
i;j
i;j
k
k
5. Au total, no = P ==1 n operations sont a executer dans l'atelier.
i
i
n
i
7
1.1. LE PROBLEME
Il est frequent de trouver une formulation plus restrictive du probleme de job-shop. Dans celle-ci, chaque job passe sur les m machines
de l'atelier une fois et une seule. Tous les jobs sont donc constitues de
m operations et chaque machine doit e ectuer n operations. Le nombre
total d'operations no est alors n m et le probleme est dit carre si
n = m.
Une autre restriction de ce probleme amene a un probleme de owshop. Dans ce cas, et pour chaque operation O , R(O ) = M . Ainsi,
la jeme operation de chaque job est executee sur la jeme machine.
i;j
1.1.2
i;j
j
Les contraintes
Cet atelier de fabrication, introduit precedemment, est soumis a
des contraintes technologiques. Ces contraintes touchent a la fois les
possibilites d'utilisation des machines et les liens qui peuvent exister
entre les operations. Ces contraintes sont les suivantes :
1. Les machines sont independantes les unes des autres (pas d'utilisation d'outil commun, par exemple).
2. Une machine ne peut executer qu'une seule operation a un instant
donne.
3. Chaque machine est disponible pendant toute la periode de l'ordonnancement. En particulier, les pannes de machines ne sont
pas prises en compte dans le modele du job-shop (ce probleme est
traite dans le chapitre 4).
4. Une operation en cours d'execution ne peut pas ^etre interrompue
(il n'y a pas de preemption).
5. Les jobs sont independants les uns des autres. En particulier, il
n'existe aucun ordre de priorite attache aux jobs.
Certaines des methodes presentees plus loin fonctionnent egalement
si l'on supprime une ou plusieurs des contraintes donnees ici.
8
CHAPITRE 1. LE PROBLE ME DU JOB-SHOP
1.1.3 Les objectifs
Trouver un ordonnancement admissible revient a determiner une
sequence de passage des operations sur les machines respectant les
contraintes du probleme. Le but est ensuite de minimiser ou maximiser une fonction objectif pour trouver la ou les meilleures solutions. Le
resultat d'un ordonnancement, generalement donne sur un diagramme
de Gantt, est uniquement fonction des dates de debut calculees des
operations.
Dans la litterature, nous pouvons trouver un nombre important de
fonctions objectif. La plus courante est sans doute la duree totale de
l'ordonnancement (makespan) notee Cmax. Nous pouvons egalement citer la moyenne des temps d'achevement de chaque job, le retard maximum des jobs par rapport a une date d'achevement prevue, la moyenne
des retards, etc [9] [48]. Dans la suite de ce memoire et pour tous les
problemes traites, nous prendrons comme objectif, la duree totale de
l'ordonnancement Cmax.
1.1.4 La complexite
Le probleme du job-shop est classe par la theorie de la complexite
[49] [50] [56] parmi les problemes NP-diciles au sens fort. Nous pouvons trouver la demonstration de ce resultat dans A. H. G. Rinnooy
Kan [95]. Le principe de la demonstration repose sur une reduction polyn^omiale d'un probleme de ow-shop vers un probleme de knapsack.
Au dela de la complexite theorique, la taille des instances que l'on
traite est tres importante pour le choix de la methode de resolution.
Pour un temps de calcul donne, il est possible de resoudre optimalement
des problemes de petite taille, alors qu'il devient dicile de trouver une
bonne solution admissible pour un grand probleme.
Nous proposons une classi cation des problemes en fonction de leurs
nombre de job, nombre d'operations par job et nombre de machines.
Cette classi cation permettra, dans la suite, de reperer facilement les
1.2. LES MODE LISATIONS
9
types de problemes auxquels sont dediees les methodes de resolution.
{ Problemes de petite taille : Problemes de moins de 20 jobs,
moins de 10 machines et moins de 10 operations par jobs.
{ Problemes de taille moyenne : Problemes entre 20 et 50 jobs, de
5 a 15 machines et de 5 a 15 operations par jobs.
{ Problemes de grande taille : Problemes de plus de 50 jobs, de
plus de 5 machines et de plus 5 operations par machines.
1.2 Les modelisations
Traiter un probleme d'une telle complexite necessite toujours une
modelisation precise. La formulation la plus classique est sans aucun
doute sous forme de graphe disjonctif, mais les modelisations en programmation mathematique sont les plus anciennes. Il existe egalement
des modelisations polyedrales et algebriques du probleme. Cette section
va t^acher de resumer l'ensemble des modelisations existantes.
1.2.1 La modelisation par graphe disjonctif
La modelisation sous forme de graphe disjonctif est tres certainement la plus employee pour representer les problemes d'ordonnancement, et en particulier le probleme du job-shop. Cette formulation est
tres souvent utilisee dans la mise au point de methodes de resolution.
Presentee pour la premiere fois par B. Roy [98] en 1964, elle fut reprise
un peu plus tard par E. Balas [10]. Elle est a l'origine des premieres
methodes de resolution ecaces pour traiter le probleme.
Le job-shop est represente par un graphe = (
[ ), ou
est l'ensemble des sommets du graphe , est l'ensemble des arcs
conjonctifs et est l'ensemble des arcs disjonctifs :
G
G
X; C
D
X
C
D
{ L'ensemble des sommets de contient + 2 elements. Parmi
ceux-ci, sommets sont associes a chacune des operations
. Par la suite, on notera ces sommets . Deux sommets
X
G
no
no
Oi;j
no
Oi;j
deb
CHAPITRE 1. LE PROBLE ME DU JOB-SHOP
10
et
sont ajoutes et representent le debut et la n de l'ordonnancement. Le sommet precede tous les sommets du graphe
et
succede a tous. Tous les sommets correspondant a des
operations sont ponderes par leur temps operatoire.
{ L'ensemble contient les arcs conjonctifs representant les contraintes de precedence entre les operations d'un m^eme job (gamme
operatoire). Il existe donc un arc entre les sommets
et +1
pour = 1
et = 1
, 1. De plus, il existe des arcs
entre et 1 et, entre
et
pour = 1
.
{ L'ensemble contient les arcs disjonctifs issus de la contrainte
qu'une machine ne peut executer qu'une operation a la fois. Il
existe donc un arc et un arc retour entre les operations
et
pour 6= , utilisant la m^eme machine ( ( ) = ( )).
f in
deb
G
f in
C
Oi;j
i
; :::; n
deb
j
Oi;j
; :::; ni
Oi;
Oi;ni
f in
i
; :::; n
D
Oa;b
Oc;d
a
c
R Oa;b
R Oc;d
Pour construire un ordonnancement admissible sur le graphe , il
sut d'arbitrer chacune des disjonctions. Cela revient a choisir, pour
chaque paire d'arcs, seulement un arc qui determinera l'ordre de passage
sur la machine. Pour que l'ordonnancement soit parfaitement de ni, il
faut que l'arbitrage soit complet (toutes les disjonctions sont arbitrees)
et compatible (le graphe est sans circuit) [98].
G
Sur le graphe ainsi obtenu, nous utilisons alors un systeme de potentiels qui respecte les contraintes du probleme. Ces potentiels representent en fait la date de debut calculee de chaque operation. Nous
obtenons les equations suivantes :
ti;j
+1 t
1
i;j
+
( =1
pi;j
i
; =1
; :::; n j
; :::; ni
, 1)
(1.1)
tc;d
ta;b
+
pa;b
si on a un arc de
Oa;b
vers
Oc;d
(1.2)
ta;b
tc;d
+
pc;d
si on a un arc de
Oc;d
vers
Oa;b
(1.3)
ti;
tdeb
tf in
ti:ni
( =1
i
+
pi;ni
)
(1.4)
; :::; n
( =1
i
)
; :::; n
(1.5)
1.2. LES MODE LISATIONS
11
L'equation 1.1 represente les contraintes de gamme operatoire entre
les di erentes operations d'un m^eme job. Les equations 1.2 et 1.3, qui
representent une contrainte de disjonction, ne sont pas actives dans
les m^emes conditions. L'une seulement sur les deux est active selon
que l'arbitrage d'une disjonction donne un arc plut^ot qu'un autre. Les
equations 1.4 et 1.5 representent les contraintes de debut et de n d'ordonnancement. La duree totale de l'ordonnancement Cmax est alors
donnee par la valeur de tfin.
1.2.2 Les modelisations en programmation mathematique
C'est en terme de programmation mathematique [16] qu'ont ete formules les premiers exemples de job-shop [20] [78] [110]. Nous presentons
maintenant quelques uns de ces modeles parmi les plus courants. Dans
les deux premiers modeles, les contraintes de gamme operatoire et les
contraintes de debut et de n sont representees par les m^emes equations que precedemment (cf equations 1.1, 1.4 et 1.5). Le seul probleme
reside dans les contraintes de capacite des machines(1.2 et 1.3), une
machine ne pouvant executer qu'une seule operation a la fois (cf 1.1.2).
Les deux derniers modeles reprennent toutes les contraintes.
1.2.2.1 Le modele de A.S. Manne
La programmation lineaire en nombres entiers est un outil tres utilise pour la formulation de nombreux problemes de l'optimisation combinatoire. Pour cette formulation, A.S. Manne [78] de nit une variable
nouvelle pour chaque paire ordonnee d'operations utilisant la m^eme
a;b pour la paire (O ; O ) si
machine. Cette variable en 0 , 1 s'ecrit yc;d
a;b c;d
(R(Oa;b) = ROc;d ) = Mk :
a;b =
yc;d
(
0 si Oa;b precede Oc;d sur Mk
1 si Oc;d precede Oa;b sur Mk
(1.6)
On suppose, de plus, la connaissance d'une borne superieure BS de
la duree totale de l'ordonnancement. Cette borne peut simplement ^etre
12
CHAPITRE 1. LE PROBLE ME DU JOB-SHOP
la somme de tous les temps operatoires. Les contraintes de disjonction
peuvent alors ^etre formulees par les equations suivantes :
a;b
tc;d ta;b + pa;b , BS yc;d
(1.7)
a;b)
ta;b tc;d + pc;d , BS (1 , yc;d
(1.8)
Dans ce modele, pour chaque arbitrage d'une paire d'arcs disjonctifs, seule l'une des contraintes 1.7 et 1.8 est active. Ainsi, quand l'ara;b vaut 0. La contrainte 1.8 est alors
bitrage donne Oa;b avant Oc;d, yc;d
inactive puisque signi ant ta;b ,1, ce qui est toujours vrai, et la
contrainte 1.7 est active puisque devenant tc;d ta;b + pa;b.
Dans ce modele, en plus des no variables ti;j , nous avons pour chaque
machine Mk , mk mk2,1 variables supplementaires correspondant a
chaque paire d'operations sur la machine. Aux (no , n) contraintes
de gammes operatoires (cf 1.1), s'ajoutent mk (mk , 1) contraintes
de disjonctions (1.7 et 1.8).
1.2.2.2 Le modele de E. Pinson
E. Pinson [87] propose une formulation en terme de programmation mathematique. Il regroupe en une seule equation quadratique les
deux equations disjonctives pour chaque paire d'operations (Oa;b; Oc;d)
utilisant la m^eme machine R(Oa;b ) = R(Oc;d ) = Mk .
(ta;b , tc;d + pa;b) (tc;d , ta;b + pc;d ) 0
(1.9)
Ce modele comporte donc seulement no variables ti;j , (no , n)
contraintes de gamme operatoire et mk mk2,1 contraintes de disjonction (1.9).
1.2.2.3 Le modele de H.M. Wagner
La modelisation que nous exposons maintenant est due a H.M. Wagner [110]. C'est en fait une restriction d'une modelisation d'un job-shop
generalise que nous presenterons dans le chapitre 3.
1.2. LES MODE LISATIONS
13
Dans ce modele, la variable principale est x(i;jl), les autres variables
sont exposees ensuite.
(
Oi;j passe sur R(Oi;j ) en leme position
= 10 sisinon
x(i;jl)
(1.10)
t(kl) : date de debut de la leme operation sur Mk
(1.11)
s(kl) : duree entre la n de la leme operation et le
(1.12)
debut de la (l + 1)eme sur Mk (variables d'ecart)
s0k : duree entre 0 et la premiere operation sur Mk
(1.13)
Tx(kl) : temps operatoire de la leme operation sur Mk
(1.14)
mk : nombre d'operations executees sur Mk
(1.15)
Les premieres contraintes (1.16) signi ent qu'une operation et une
seule est en leme position sur la machine Mk .
X
O
i;j j
R(O )=M
i;j
x(i;jl) = 1 pour k = 1; :::; m; l = 1; :::; mk
(1.16)
k
Les contraintes suivantes (1.17) imposent qu'une operation Oi;j ne
soit a ectee qu'a une place et une seule :
l=X
m
k
l=1
x(i;jl) = 1 pour i = 1; :::; n; j = 1; :::; ni
(1.17)
Les contraintes 1.18 determinent le temps operatoire de la leme operation executee sur Mk .
Tx(kl) =
iX
=n
i=1
pi;j x(i;jl) pour k = 1; :::; m; l = 1; :::; mk
(1.18)
CHAPITRE 1. LE PROBLE ME DU JOB-SHOP
14
Les contraintes de gamme operatoire s'expriment pour deux operations Oi;j et Oi;j+1, de la facon suivante :
) )
t(kl11) + pi;j x(i;jl1) t(kl22) + BS (2 , x(i;jl1) , x(i;jl2+1
(1.19)
pour l1 = 1; :::; mk1 ; l2 = 1; :::; mk2
Cette contrainte n'est active que si l'operation Oi;j est executee sur
la machine R(Oi;j ) = Mk1 en l1eme position et Oi;j+1 en l2eme position sur
R(Oi;j+1 ) = Mk2 . Si une de ces deux conditions n'est pas respectee, la
contrainte n'est pas active.
En n, le calcul des dates de debut au plus t^ot des operations sur les
machines se fait par les contraintes suivantes :
0
t(1)
k = sk pour k = 1; :::; m
t(kr) =
l=X
r,1 l=1
(1.20)
Tx(kl) + s(kl) pour k = 1; :::; m; r = 1; :::; mk (1.21)
Les dernieres contraintes (1.22) permettent de calculer le Cmax :
tmk k + Txmk k Cmax pour k = 1; :::; m
(1.22)
Dans ce modele, le nombre de variables et de contraintes est beaucoup plus eleve que pour les modeles precedents. A chaque(l)operation
Oi;j telle que R(Oi;j ) = Mk , sont associees mk variables xi;j . Les variables t(kl) sont au nombre de mk sur chaque machine Mk , et les variables d'ecart s(kl) au nombre de mk , 1. A ces variables, s'ajoutent m
variables s0k et no variables Tx(kl). Au niveau des contraintes, nous avons
(no , n) contraintes de gammes operatoires (1.19), no contraintes d'affectation d'une operation en position l dans la sequence de la machine,
no contraintes imposant une seule operation en leme position sur Mk ,
no contraintes de temps operatoires (1.18) et 2 m + no contraintes de
dates au plus t^ot (1.20, 1.21 et 1.22).
1.2. LES MODE LISATIONS
15
1.2.2.4 Le modele de E.H Bowman
E.H Bowman [20] utilise, pour sa formulation du probleme sous
forme de programme lineaire en nombres entiers, les variables x
pour chaque operation O et un decoupage du temps en periode de
longueur 1. Il suppose de plus la connaissance d'une borne superieur
BS de la valeur de la solution optimale. La variable x a pour signication :
(
si O utilise R(O ) = M a l'instant t
x = 01 sinon
(1.23)
i;j;t
i;j
i;j;t
i;j
i;j
k
i;j;t
Les contraintes suivantes assurent que l'operation O necessite
l'utilisation de la machine M pendant p unite de temps.
i;j;
k
X
t=B S
x
i;j;t
t=1
=p
i;j
(i = 1; :::; n; j = 1; :::; n )
i;j
i
(1.24)
Une machine n'e ectue qu'une operation a la fois. La somme des
x , pour un instant t et une machine M donnes, doit ^etre inferieur
ou egale a 1.
i;j;t
k
X
Oi;j
j
x
i;j;t
R(Oi;j )=Mk
1
(k = 1; :::; m; t = 1; :::; BS )
(1.25)
Les contraintes de precedences sont alors exprimees par :
p x
i;j
i;j +1;r
X,1
t=r
x
(1.26)
i;j;t
t=1
(i = 1; :::; n; j = 1; :::; n , 1; t = 1; :::; BS )
i
Les contraintes de non preemption sont exprimees par :
p (x
i;j
i;j;t
,x
i;j;t+1
)+
X
r =B S
r =t+2
x
i;j;r
p
i;j
(1.27)
CHAPITRE 1. LE PROBLE ME DU JOB-SHOP
16
(i = 1; :::; n; j = 1; :::; ni)
Pour nir, la fonction objectif Cmax s'ecrit en tenant compte du
fait que la duree totale de l'ordonnancement ne peut ^etre inferieure au
temps necessaire pour produire le job le plus long :
Cmax xi;n ;t t
i
(i = 1; :::; n; t = 1; :::; BS )
(1.28)
Le modele de E.H. Bowman contient encore plus de variables et
de contraintes que celui de H.M. Wagner. Les variables xi;j;t sont au
nombre de no BS . Nous avons no contraintes de temps operatoires
(1.24), m BS contraintes garantissant qu'une seule operation est executee a un instant donne par une machine (1.25), no BS contraintes
de gammes operatoires et no (BS , 1) contraintes de non preemption.
Nous remarquons directement que la connaissance d'une bonne borne
superieure BS permet de limiter considerablement le nombre d'equations.
M.L. Fisher [42] [43] a egalement propose un modele faisant intervenir le nombre d'operations sur une machine a un instant donne.
1.2.3 La modelisation polyedrale
L'approche polyedrale s'est beaucoup developpee dans le domaine
de l'optimisation combinatoire [58]. De nombreux problemes comme le
voyageur de commerce font intervenir ce genre de representation pour
leur description [71]. Le principe est de trouver les contraintes lineaires
de nissant des demi- espaces. L'intersection de ces demi-espaces donne
un polyedre dont les sommets representent une solution realisable du
probleme. Si l'on se donne une fonction objectif lineaire, l'utilisation
d'un programme lineaire permet d'obtenir la solution optimale. Bien
entendu, le nombre de contraintes est exponentiel par rapport a la taille
du probleme.
Le modele polyedral pour des problemes d'ordonnancement a ete
introduit par E. Balas [11] en 1985. Il de nit un vecteur solution t dont
1.2. LES MODE LISATIONS
17
les composantes sont les dates de debut calculees de chacune des
operations a ordonnancer. est alors l'ensemble de tous les vecteurs
veri ant les contraintes du probleme. Il considere le polyedre comme
etant l'enveloppe convexe des points de . On a alors :
ti;j
no
T
t
P
T
P
T
=
=
( )
(1.29)
conv T
8
>
<
t
>
:
ti;j
2<
no
ta;b
tc;d
+1 t + p
t 1 0
+
i;j
i;
pc;d
_
tc;d
9
>
=
i;j
ta;b
+
pa;b
>
;
(1.30)
Il en deduit ensuite toute les facettes du polyedre ( ) ou est
l'ensemble des operations appartenant a une clique de disjonctions.
Il presente pour nir une procedure permettant de couper une solution donnee par un sous-ensemble de contraintes, s'appuyant sur la
theorie des polyedres bloquants. Des travaux developpes par M. Queyranne [91] [90] pour des problemes de machines simples peuvent ^etre
utilises dans le cadre de la resolution de problemes de job-shop.
P K
K
Malheureusement, pour le probleme du job-shop, cette modelisation
ne semble pas ^etre utilisable. Elle n'a ete employee que tres recemment
par D. Appelgate et W. Cook [7] pour trouver de bonnes bornes inferieures dans une methode separation et evaluation. Toutefois, il parait
tres dicile d'utiliser cette technique pour developper des methodes de
resolution ecaces.
1.2.4 La modelisation algebrique
Cette modelisation, tres formelle, est sans doute la moins utilisee
dans le domaine de l'ordonnancement. Nous presentons ici les structures
algebriques du probleme comme elles ont ete donnees dans R.V. Rogers
et K.P. White [96].
Soit (
! ) tel que:
{ = f j =1
; =1
operations;
O; RI ; RM ;
O
Oi;j i
;P
; :::; n j
; :::; ni
g est l'ensemble de toutes les
18
CHAPITRE 1. LE PROBLE ME DU JOB-SHOP
{ RI est une relation d'equivalence sur O de nissant les operations
communes a un job;
{ RM est une relation d'equivalence sur O de nissant les operations
communes a une machine;
{ ! est une relation d'ordre non re exive sur O de nissant les
precedences entre les operations;
{ P = fpi;j ji = 1; :::; n; j = 1; :::; ni g est l'ensemble des temps operatoires
Chaque job Ji est une classe d'equivalence d'operations determinee
par RI . L'espace quotient qui en resulte O=RI = fJ1; :::; Jng est une
partition de O. J (Oi;j ) = Ji est alors une surjection de O dans O=RI .
De la m^eme facon, chaque machine Mk est une classe d'equivalence d'operations determinee par RM . L'espace quotient qui en resulte
O=RM = fM1; :::; Mmg est une partition de O. M (Oi;j ) = Mk est alors
une surjection de O dans O=RM .
La gamme operatoire pour un job Ji est une relation d'ordre !i
de nie par la restriction de ! a Ji.
!i=! \(Ji Ji)
L'ensemble des contraintes de gamme operatoire pour chaque job
est alors donne par f(!i; Ji) jj = 1; :::; n g.
De la m^eme facon, la sequence des operations sur une machine est
une relation d'ordre !k de nie par la restriction de ! a Mk .
!k =! \(Mk Mk )
L'ensemble des contraintes de precedence sur une machine est alors
donne par f(!k ; Mk ) jk = 1; :::; m g.
Recemment, K.K. Tahboub et N.G. Odrey [102] ont propose une
modelisation du probleme de job-shop en utilisant des resultats issus
de l'algebre (Max; +) [31].
1.3. LES METHODES
DE RESOLUTION
19
Ces modelisations sont mathematiquement tres interessantes mais
ne nous indique pas de direction en ce qui concerne les methodes de
resolution. Aucun article a ce jour ne mentionne ces modelisations sinon [96] et [102].
1.3 Les methodes de resolution
Les methodes de resolution proposees au cours de ces quarante dernieres annees sont nombreuses, et sont le re et de l'eventail des methodes dont on dispose pour traiter les problemes de l'optimisation
combinatoire [85]. Nous nous proposons, dans cette section, de classi er
toutes les approches qui ont servi de support a la creation d'algorithmes
d'optimisation. Dans un premier temps, nous decrirons les methodes de
resolution exactes pour des classes de problemes polyn^omiaux, puis les
methodes heuristiques pour le probleme general. Nous traiterons ensuite les methodes de resolution exactes pour le probleme general. Les
methodes de relaxation constitueront la section suivante et pour nir,
nous donnerons quelques references sur les methodes de decomposition.
Le but de la classi cation n'est pas de comparer les methodes en
fonction de leur \performances" pour la resolution du probleme. Le plus
souvent, les auteurs ne traitent pas les m^emes problemes de job-shop
et n'ont pas les m^emes objectifs. Si certaines methodes sont adaptees
aux problemes de grande taille (beaucoup de jobs et/ou beaucoup de
machines), d'autres ne traitent que des problemes a environ dix jobs
et dix machines. Par ailleurs, des algorithmes sont construits pour ^etre
rapide au detriment de la qualite de la solution, alors que d'autres
recherchent l'optimalite de la solution.
1.3.1 Une classi cation des methodes
Cette section contient une classi cation des approches utilisees pour
resoudre le probleme du job-shop statique et deterministe ( gure 1.1).
Nous pouvons constater assez rapidement que le job-shop a inspire de
nombreux auteurs et que les propositions de methodes de resolution
sont extr^emement variees. Les methodes dediees a la resolution du pro-
CHAPITRE 1. LE PROBLE ME DU JOB-SHOP
20
bleme c^otoient l'utilisation des methodes classiques de l'optimisation
combinatoire. Il est egalement interessant de constater que le probleme
du job-shop est un terrain d'essai privilegie pour le test de nouvelles
approches de resolution au m^eme titre que le probleme du voyageur de
commerce.
Dans cette classi cation, apparaissent les principales references pour
chaque approche de resolution. Chacune d'elles est plus amplement
discutee dans les sections suivantes.
1.3.2 Les problemes polyn^omiaux
Comme nous l'avons vu precedemment (cf 1.1.4), le probleme du
job-shop est un probleme NP-dicile au sens fort. Toutefois, il existe
quelques cas particuliers de ce probleme qui peuvent ^etre resolus en
temps polyn^omial.
1.3.2.1 Le probleme a deux machines
Le premier de ces problemes faciles est le job-shop a deux machines.
Dans celui-ci nous avons quatre types de jobs :
{ Type 1 : Les jobs n'ayant qu'une operation sur la machine
M1
.
{ Type 2 : Les jobs n'ayant qu'une operation sur la machine
M2
.
{ Type 3 : Les jobs ayant la premiere operation sur
xieme sur 2.
M1
et la deu-
{ Type 4 : Les jobs ayant la premiere operation sur
xieme sur 1.
M2
et la deu-
M
M
La regle de S.M. Johnson [65] dit que pour les jobs de type 3 precede sur les machines 1 et 2 si
( 1 2) ( 2 1). Il
en est de m^eme pour les jobs de type 4. On obtient ainsi une sequence
des jobs 3 pour les jobs de type 3 et 4 pour les jobs de type 4. On
construit une sequence aleatoire 1 avec les jobs de type 1 et 2 avec les
jobs de type 2. La regle de J.R. Jackson [64] dit qu'un ordonnancement
Ja
Jb
M
M
S
M in pa; ; pb;
M in pa; ; pb;
S
S
S
1.3. LES ME THODES DE RE SOLUTION
21
! Probleme du job-shop
! Les methodes pour les problemes polyn^omiaux
! Le probleme a deux machines [3] [64] [65] [69] [101]
! Le probleme a deux jobs [6] [22] [23]
! Les methodes de relaxation [46]
! Les methodes de decomposition [35] [74] [88]
! Les methodes exactes
! La programmation dynamique [13]
! Le branch and bound [7] [8] [10] [12] [21] [28] [29] [47] [70]
! Le branch and cut [7]
! Le programmation mathematique [75]
! Les methodes heuristiques
! Les heuristiques constructives
! L'approche par operations [33] [84] [107] [113] [59]
! L'approche par machines [2]
! L'approche par jobs [86] (cf chapitre 2)
! Les heuristiques amelioratrices
! La methode tabou [33] [79] [103] [106]
! Le recuit simule [77] [104] [105] [106]
! Les algorithmes genetiques [32] [34] [41] [83]
! Les methodes dediees [107] [113]
! Les reseaux de neurones [115] [116]
! L'intelligence arti cielle [14]
Fig.
1.1 - Une classi cation des methodes de resolution
22
CHAPITRE 1. LE PROBLE ME DU JOB-SHOP
est optimal si on adopte sur la machine M1 l'ordre donne par S3, S1,S4
et sur la machine M2, l'ordre donne par S4, S2, S3.
Il existe des cas particuliers de job-shop a trois machines pour lesquels on a un algorithme optimal derive du precedant [48]. Une generalisation de ce probleme a ete proposee par Strusevitch [101] dans
laquelle il donne un algorithme pour resoudre un super-shop (gamme
operatoire non xee) a deux machines.
Il existe d'autres problemes polyn^omiaux de type job-shop a deux
machines. Parmi ceux-ci nous pouvons citer le probleme a deux machines et temps operatoires unitaires (cas particulier du precedent) [3]
[69].
1.3.2.2 Le probleme a deux jobs
Le deuxieme probleme polyn^omial presente est le job-shop a deux
jobs J1 et J2. S.B. Akers [6] presente une reduction de ce probleme
a un probleme de plus court chemin dans le plan avec obstacles rectangulaires. Les temps operatoires des operations de J1 (resp J2) sont
representes par la longueur des intervalles sur l'axe des abscisses (resp
sur l'axe des ordonnees) et les obstacles representent l'utilisation d'une
m^eme machine. Un ordonnancement realisable correspond alors a un
chemin de O a F avec les proprietes suivantes :
{ Les segments du chemin sont paralleles a l'un des axes (une operation d'un seul job est executee) ou diagonaux (des operations
des deux jobs sont executees).
{ Le chemin ne doit pas passer par l'interieur des obstacles materialisant l'utilisation d'une m^eme machine pour les deux jobs.
La duree totale de l'ordonnancement associee a un tel chemin est
la somme des longueurs des segments verticaux et horizontaux et de la
projection sur un des deux axes des segments diagonaux.
Un algorithme de resolution tres performant de ce probleme a ete
donne par P. Brucker [22]. Une generalisation a ete proposee plus tard,
1.3. LES METHODES
DE RESOLUTION
23
utilisant les m^emes techniques graphiques, par P. Brucker et B. Jurisch [23]. Ces algorithmes seront detailles dans la section 2.1.2.
1.3.3 Les methodes heuristiques
Comme pour tous les problemes NP-complets, la recherche d'heuristiques performantes est une des preoccupations des specialistes du
domaine. Le principe d'une methode heuristique est de trouver en un
temps polyn^omial une solution realisable la meilleure possible [100].
Dans cette recherche, les objectifs poursuivis sont parfois di erents.
Certains privilegient la rapidite de calcul au detriment de la qualite
de la valeur optimale, d'autres s'interessent plus a la quasi-optimalite
du resultat au detriment du temps. Dans la mesure du possible, nous
t^acherons dans la suite, de decrire l'ensemble des heuristiques connues
a ce jour en precisant leur inter^et.
1.3.3.1 Les heuristiques constructives
Le principe de ces methodes est de construire une solution du probleme a partir des donnees initiales. Les methodes proposees dans ce
contexte sont nombreuses, mais elles peuvent ^etre regroupees en differentes categories. Nous commencerons par les methodes basees sur
les operations. Nous parlerons ensuite des methodes basees sur les machines puis par celles basees sur les jobs.
Approche par operations. L'utilisation de regles de priorite est de
loin la technique la plus employee pour resoudre les problemes d'ordonnancement. Elle consiste en une approche operation par operation. Le
principe de l'algorithme est donne dans la gure 1.2.
S.S. Panwalkar et W. Iskander [84] ont repertorie plus d'une centaine
de regles de priorite et ont propose une classi cation de celles-ci. Depuis,
de nombreux auteurs [107] ont proposes d'autres regles originales ou des
evolutions de regles existantes.
Les regles de priorite peuvent ^etre utilisees di eremment. En e et,
l'algorithme presente precedemment peut ^etre completement inverse et
CHAPITRE 1. LE PROBLE ME DU JOB-SHOP
24
1. INITIALISATION
Faire la liste de toutes les operations disponibles a l'instant initial,
f 1j = 1
g.
2. SELECTION
DE L'OPERATION
Selectionner l'operation selon la regle de priorite choisie et la placer dans la sequence des operations sur la machine.
3. MISE A JOUR DE LA LISTE
Retirer l'operation choisie de la liste et y ajouter la suivante dans
la gamme operatoire.
^
4. CONDITION D'ARRET
Recommencer ce processus tant qu'il existe des operations non
traitees.
oi;
i
Fig.
; :::; n
1.2 - Algorithme de liste par regles de priorite
1.3. LES METHODES
DE RESOLUTION
25
les operations sont traitees par ordre decroissant dans les gammes operatoires. La liste est constituee au depart des operations qui n'ont pas de
successeurs. Le choix se fait selon une regle de priorite, l'operation est
sortie de la liste et l'operation qui la precede dans la gamme operatoire
y est introduite.
M. Dell'Amico et M. Trubian [33] proposent une approche bidirectionnelle consistant a ordonnancer les premieres operations des jobs
selon la premiere methode et les dernieres operations selon la deuxieme.
Cette approche semble donner de meilleurs resultats que les precedentes.
En n, F. Werner et A. Winkler [113] proposent une methode basee
sur une technique d'insertion d'operation. Les operations sont inserees
dans un ordonnancement partiel par ordre decroissant de leur duree
operatoire.
Dernierement, A. Guinet et M. Legrand [59] ont propose une reduction du probleme de job-shop a un probleme de ow-shop. Ils utilisent
ensuite des heuristiques de resolution de problemes de ow-shop.
Les principaux atouts de ces techniques sont certainement une grande facilite de mise en uvre informatique et une vitesse de calcul tres
importante. Toutefois, les resultats obtenus pour la valeur de la fonction
objectif sont parfois assez eloignes de la valeur optimale. Ces techniques
sont tres interessantes pour les problemes de grande et tres grande taille.
Approche par machine. Le principe de resolution est de trouver
un sequencement sur les machines, les unes apres les autres. Cette approche n'a pas ete tres developpee et seule l'heuristique \Shifting Bottleneck" de J. Adams et al. [2] est connue. Dans celle-ci, la premiere
etape consiste a determiner la machine goulot (machine posant le plus
de probleme pour son sequencement). Lors de la deuxieme etape, un
probleme de machine simple avec temps de latences est resolu (cf J. Carlier [26]). Il faut en fait trouver une sequence de passage sur la machine
selectionnee sachant que certains jobs ne peuvent commencer avant une
26
CHAPITRE 1. LE PROBLE ME DU JOB-SHOP
date xee, somme des temps operatoires des operations qui la precedent
dans sa gamme operatoire, et qu'un certain temps doit s'ecouler entre
le n d'une operation et la n de l'ordonnancement, somme des temps
operatoires des operations qui lui succedent dans sa gamme operatoire.
Quand le sequencement est realise sur une machine, on en selectionne
une autre et l'on recommence le processus, jusqu'a ce que toutes les
machines aient ete traitees.
J. Adams et al. proposent, apres le traitement de chaque machine, de
reoptimiser le resultat partiel obtenu, toujours en utilisant la procedure
de resolution du probleme a une machine de J. Carlier.
Cette methode donne de tres bons resultats sur des problemes de
petite et moyenne taille. Par contre, la resolution du probleme a une
machine necessitant l'utilisation d'un algorithme branch and bound,
l'heuristique n'est pas tres adaptee a la resolution de problemes de
grande et tres grande taille.
Approche par jobs. A ce jour, aucune technique n'a ete developpee
sur le principe du traitement job par job. Dans le chapitre 2, nous
proposerons un certain nombre d'heuristiques basees sur ce principe.
1.3.3.2 Les heuristiques amelioratrices
Le principe de ces methodes n'est plus de construire un ordonnancement a partir des donnees initiales du probleme, mais de modi er le
resultat d'un ordonnancement admissible en vue d'ameliorer la valeur
de la fonction objectif. La plupart de ces methodes utilise la notion de
voisinage de solution. Elle consiste donc a explorer les solutions voisines
d'une solution donnee et a en selectionner une, pour ensuite continuer
le processus d'exploration. A chaque etape de ce processus, la solution
choisie n'ameliore pas forcement la valeur de la fonction objectif ce
qui permet de sortir de minima locaux. E. H. L. Aarts et al. [1] ont
recemment propose une etude comparative de plusieurs des methodes
decrites maintenant.
1.3. LES METHODES
DE RESOLUTION
27
1. CALCUL DE LA SOLUTION INITIALE
Calculer une solution realisable avec une methode constructive.
2. RECHERCHE DU MOUVEMENT
Chercher le meilleur mouvement (permutation de deux operations
du chemin critique par exemple) pour obtenir la meilleure solution
voisine, hormis par les mouvements places dans la liste tabou.
3. MISE A JOUR DE LA LISTE
Stocker le mouvement dans la liste tabou, enlever le mouvement
le plus ancien de la liste.
^
4. CONDITION D'ARRET
Recommencer la recherche de solution jusqu'a veri er une condition d'arr^et (nombre limite de mouvement, temps de calcul, etc).
Fig.
1.3 - Algorithme tabou
La methode tabou. La methode tabou, elaboree par F. Glover [54]
[55] est basee sur les notions de voisinage de solution et de mouvements
interdits. Le voisinage d'une solution est un ensemble de solutions que
l'on peut atteindre a partir de la premiere en e ectuant un mouvement
prede ni (permutation de deux operations par exemple). Chaque mouvement est ajoute dans une liste de taille xee (liste tabou) qui contient
les mouvements interdits. Le principe de l'algorithme est donne dans
la gure 1.3.
La notion de voisinage, mais egalement la taille de la liste tabou
et les conditions d'arr^et peuvent ^etre tres di erentes. Nous presentons
maintenant les voisinages les plus connus :
{ Une solution voisine s d'une solution s est obtenue en permutant
deux operations u et v successives sur la m^eme machine si l'arc
0
CHAPITRE 1. LE PROBLE ME DU JOB-SHOP
28
( ) est sur le chemin critique. De plus, P.J.M. Van Laarhoven et
al. [106] montrent la propriete qu'il existe forcement une sequence
de mouvement qui mene a une solution optimale.
{ Un deuxieme voisinage est donne par H. Matsuo et al. [79]. Ils
utilisent la m^eme regle que les precedents avec la restriction que
dans les arcs entrant de , au moins un ne soit pas sur le chemin
critique (la m^eme chose pour les arcs sortant de ). Dans ce cas,
la solution optimale peut ne pas ^etre atteinte par une sequence
de mouvements mais cela limite la taille du voisinage etudie.
{ M. Dell'Amico et M. Trubian [33] proposent une generalisation
du premier voisinage. Dans ce cas, plus d'une permutation est
possible en m^eme temps. La propriete de P.J.M. Van Laarhoven
est veri ee.
{ M. Dell'Amico et M. Trubian [33] proposent egalement un voisinage par blocs. Un bloc est une sequence d'operations sur une
machine telle que les arcs entre deux operations successives sont
sur le chemin critique. Si le bloc s'ecrit comme = (
)
ou et sont des blocs et une operation, deux solutions
voisines sont donnees par (
) et (
). La propriete de
P.J.M. Van Laarhoven est encore veri ee.
u; v
u
v
b
0
b
b
00
b
0
b ; x; b
00
x
0
00
x; b ; b
0
00
b ;b ;x
E. Taillard [103] a propose recemment un algorithme parallele pour
resoudre le probleme du job-shop. Il utilise le premier voisinage cite
pour la mise en uvre informatique de l'algorithme sur un reseau de
transputers. La methode tabou est egalement utilisee pour la resolution
de job-shop avec contraintes d'outillages [114].
La procedure tabou est particulierement interessante car elle peut
^etre arr^etee soit en fonction de la valeur de la solution courante, soit en
fonction du temps de calcul ecoule. Ainsi, il est possible de trouver un
compromis entre e ort de calcul et qualite de la solution obtenue.
La diculte principale reside dans l'equilibre entre l'e ort de construction d'une solution admissible de depart et l'e ort d'amelioration.
En e et, meilleure est la solution de depart et moins l'on a a ameliorer
1.3. LES METHODES
DE RESOLUTION
29
celle-ci pour s'approcher de l'optimal. Ce probleme n'a pas encore fait
l'objet d'etudes importantes.
La methode tabou est d'autant plus ecace que le probleme traite
est de petite taille. Dans ce cas, le nombre de solutions voisines reste
limite et l'etude complete realisable. Par contre, cette methode est fortement ralentie par l'augmentation de la taille. En e et, plus le probleme est grand et plus le voisinage est important ce qui fait exploser
le nombre de solutions voisines. Dans ce dernier cas, il serait interessant
de reduire la taille du voisinage. Pour l'instant, il n'existe pas d'articles
traitant des problemes de grande et tres grande taille.
Le recuit simule. Le recuit simule f^ut developpe par S. Kirkpa-
trick [67] [68]. Comme la methode tabou, il est une des approches les
plus utilisees pour la resolution des problemes d'optimisation combinatoire. Basee sur un algorithme de simulation de recuit de metaux, elle
s'inspire de modeles de la physique statistique. Le principe de voisinage
est identique a la methode tabou, seules changent la selection de la solution suivante dans le processus iteratif et la condition d'arr^et ( gure
1.4).
P.J.M. Van Laarhoven et E.H.L. Aarts [105], et P.J.M. Van Laarhoven [104] ont fait une etude tres approfondie de cette methode. Le fait
d'a ecter aux solutions du voisinage une probabilite de selection permet
de ne pas obliger la fonction objectif a decro^tre strictement. Si c'etait le
cas, la solution obtenue serait dans un minimum local. Cette technique
(comme le tabou) permet de selectionner des solutions voisines faisant
augmenter la fonction objectif, avec une certaine probabilite. Des resultats recents sur cette technique sont donnes par P.J.M. Van Laarhoven
et al [106]. Un article recent de H.R. Lourenco [77] compare le recuit
simule avec d'autres methodes de voisinage comme le tabou.
Les remarques faites sur le contr^ole entre le temps de calcul et la
qualite de la solution pour la methode tabou restent valables pour le
recuit simule. Il en est de m^eme pour les remarques sur la taille des
problemes.
30
CHAPITRE 1. LE PROBLE ME DU JOB-SHOP
1. CALCUL DE LA SOLUTION INITIALE
Calculer une solution realisable avec une methode constructive.
2. CALCUL DU MOUVEMENT
Choisir dans le voisinage de la solution courante, une des solutions
a ectees d'une certaine probabilite.
^
3. CONDITION D'ARRET
Recommencer la recherche de solution jusqu'a veri er une condition d'arr^et (valeur d'une fonction energie).
Fig.
1.4 - Algorithme de recuit simule
Les algorithmes genetiques. Les algorithmes genetiques sont ins-
pires de la theorie de l'evolution et datent des travaux de I. Rechenberg [94], J.H. Holland [62] et H.-P. Schwefel [99]. Contrairement aux
algorithmes de recherche locale tels que le recuit simule ou le tabou
qui manipulent une seule solution realisable, les algorithmes genetiques
considerent une population de solutions realisables appelees individus.
Le but de la methode est de faire evoluer la population en e ectuant des
mutations, des croisements et une selection des individus. La mutation
est une operation unaire qui modi e la structure d'un individu (semblable a la mutation genetique). Le croisement est une operation binaire
qui a partir de deux individus en produit deux nouveaux (cross-over
pour le croisement des genes). La phase de selection consiste a supprimer les individus les moins forts (les solutions les moins interessantes).
Le principe des algorithmes genetiques est donne dans la gure 1.5.
L'idee de base est que travailler avec une population permet d'identi er et d'explorer les proprietes qu'ont en commun les bonnes solutions.
Comme les types de voisinage sont varies pour les methodes tabou ou
recuit simule, les types de mutation, de croisement et de selection peuvent ^etre nombreux. De plus, quelques amenagement de l'algorithme
1.3. LES METHODES
DE RESOLUTION
31
1. CALCUL DE LA POPULATION INITIALE
Construire une population de solutions realisables en utilisant des
methodes constructives (cf section 1.3.3.1).
2. CALCUL DES NOUVEAUX INDIVIDUS
Accro^tre la population en ajoutant des individus issus de mutations ou de croisements d'individus de la generation precedente.
3. SELECTION
DES INDIVIDUS
Selectionner les meilleurs individus pour revenir a la taille de la
population initiale.
^
4. CONDITION D'ARRET
Recommencer les croisements et les mutations jusqu'a veri er une
condition d'arr^et.
Fig.
1.5 - Algorithme genetique
32
CHAPITRE 1. LE PROBLE ME DU JOB-SHOP
precedent sont possibles comme l'utilisation de methodes amelioratrices
(tabou, recuit simule, etc) pour faire evoluer les individus apres la phase
de mutation et de croisement en vue d'avoir des solutions dans des minima locaux. De nombreux travaux ont ete realises sur les algorithmes
genetiques et le job-shop. Parmi ceux-ci, nous pouvons citer L. Davis
[32], E. Falkenauer [41], U. Dorndorf [34] et K. Nakano [83].
Les problemes lies a cette methode sont extr^emement nombreux.
Le premier est bien entendu la taille de la population et sa creation.
Prendre une population nombreuse ralentirait considerablement la phase de mutation et croisements alors qu'une taille reduite peche par un
manque de diversite ce qui est contraire a la philosophie de la methode.
Le deuxieme probleme appara^t quand la taille de l'instance traitee
devient importante. Dans ce cas, deux solutions tres eloignees au niveau
des sequences sur les machines peuvent avoir des valeurs de fonction
objectif proches. Il est alors dicile de trouver des proprietes fortes
caracterisant les bonnes solutions. Ceci est par contre possible quand
le probleme est de petite et moyenne taille.
Les methodes amelioratrices dediees. Certaines methodes ame-
lioratrices sont completement dediees au probleme du job-shop. Concues specialement pour ce type de probleme, elles utilisent au maximum
les structures de celui-ci.
Nous pouvons citer, pour commencer, les techniques d'insertion de
F. Werner et A. Winkler [113]. A partir d'une solution realisable trouvee par une methode constructive utilisant une technique semblable
(cf 1.3.3.1), la procedure iterative selectionne une operation appartenant au chemin critique et tente de l'inserer a un autre endroit dans la
sequence des operations sur la machine. Dans cette technique, le voisinage d'insertion peut ^etre plus ou moins grand selon que l'on desire
explorer plus ou moins de solution avant d'e ectuer l'insertion.
R. Vancheeswaran et M.A. Townsend [107] propose une procedure
d'optimisation appelee \critical job perturbation procedure ". Le principe est de traiter les operations du job critique, job dont la n de la
1.3. LES METHODES
DE RESOLUTION
33
derniere operation determine la n de l'ordonnancement. Certaines de
ses operations sont placees avant les operations des jobs precedents sur
les m^emes machines. La procedure recalcule ensuite les dates de debut
des operations. Si les changements e ectues n'ameliorent pas la fonction objectif, un autre job est traite. Le choix du job critique peut ^etre
fait en fonction d'autres criteres comme le rang, somme des numeros
de place dans les sequences d'operations des di erentes machines.
Dans ces deux methodes, l'inter^et majeur est la exibilite d'utilisation. En e et, il est possible de contr^oler pour l'une le nombre de
positions a explorer pour l'insertion et pour l'autre, le choix ou non
d'avancer les operations du job critique dans le sequencement des machines. Ce contr^ole permet donc de tenir compte de la taille du probleme
traite et ainsi limiter l'espace de recherche. Toutefois, ne permettant pas
de degradation de la solution courante, ces methodes ne permettent pas
de sortir de minima locaux.
1.3.3.3 Les reseaux de neurones
Depuis quelques annees, la theorie des reseaux de neurones s'est
beaucoup developpee. Lancee par W.S. Mc Culloch et W.H. Pitts [80] en
1943, elle a pour but de simuler le fonctionnement du cerveau humain.
C'est dans les annees 1960 qu'un premier reseau de neurones est realise :
il s'agit du perceptron de F. Rosenblatt [97]. Apres que les limites
theoriques du perceptron aient ete montrees, les reseaux de neurones
ont retrouve un second soue gr^ace au travaux de J. Hop eld [63].
Cette technique nouvelle a d'abord ete testee sur des problemes traites
par l'intelligence arti cielle (reconnaissance de formes, traitement du
signal, aide a la decision). Puis, reprise par des specialistes de recherche
operationnelle, elle a ete utilisee pour la resolution des problemes du
domaine. Le job-shop n'a pas echappe a cette regle, et les recherches
sur sa resolution a partir de reseaux de neurones sont actuellement en
cours dans de nombreux laboratoires. Nous citerons sur ces travaux, les
articles de C.S. Zhang et al. [115], et de D.N. Zhou et al. [116].
34
CHAPITRE 1. LE PROBLE ME DU JOB-SHOP
1.3.3.4 L'intelligence arti cielle
L'intelligence arti cielle est un outil de plus en plus present dans
le domaine de l'ordonnancement. Son principe de resolution peut tres
bien s'appliquer pour des problemes d'optimisation combinatoire [14].
Le raisonnement temporel, la propagation de contraintes et la recherche
combinatoire sont des notions que l'on retrouve a la fois dans la recherche operationnelle et l'intelligence arti cielle. E. Bensana [14] decrit l'impact que peut avoir l'intelligence arti cielle sur des problemes
d'ordonnancement.
1.3.3.5 Caracterisation des solutions admissibles
Certaines demarches tendent, plut^ot que trouver une solution optimale du probleme, a chercher des classes de solutions admissibles. L'approche retenue est alors de chercher, a partir des conditions initiales du
probleme et d'un objectif xe, a exprimer les conditions necessaires que
tout ordonnancement admissible devra respecter [39].
Peut intervenir dans ce type de recherche, la notion de dominance,
qui permet de dire si une t^ache doit preceder toutes les autres ou succeder a toutes. Dans ce contexte, on peut citer les travaux de J. Erschler
et al. [38] [37] et ceux de J. Carlier [25] [26] [27]. Ces travaux concernent essentiellement le probleme d'ordonnancement sur une machine
unique, mais une application au probleme du job-shop est propose par
J. Carlier et E. Pinson [28] et E. Pinson [87].
L'originalite de l'approche est de developper des regles d'inference
qui travaillent uniquement a partir des contraintes du probleme, sans
prendre en compte le moindre critere, et qui vont permettre, par des
deductions symboliques (du type relations de precedence ou de nonprecedence entre deux operations ou entre une operation et un groupe
d'operations par exemple) de reduire l'ensemble initial a une partie des
solutions admissibles [76].
Dans le m^eme esprit, F. Roubellat et al. [73] propose une notion
de t^aches permutables. Dans ce cas, l'ordonnancement se fait en deux
1.3. LES METHODES
DE RESOLUTION
35
temps. Dans une premiere phase on determine des groupes de t^aches de
telle sorte que toute permutation dans chacun des groupes peut donner un ordonnancement admissible. Dans la seconde, il ne reste plus
qu'a choisir une permutation dans chacun des groupes en fonction de
l'objectif que l'on recherche. Cette derniere approche est surtout interessante dans le cas du job-shop reactif (cf chapitre 4) car elle permet de
changer de solution en fonction du deroulement de l'ordonnancement
previsionnel.
1.3.4 Les methodes exactes
Le but des methodes exactes est de trouver, en un temps de calcul
le plus court possible, la solution optimale du probleme. Pour tous
les problemes de l'optimisation combinatoire classes NP-complet, ceci
constitue un de . Si les recherches sur les methodes exactes sont tres
nombreuses pour des problemes phare comme le voyageur de commerce,
le job-shop a interesse de nombreux auteurs.
Parmi les methodes de resolution exactes de problemes d'optimisation combinatoire et en particulier de problemes d'ordonnancement, le
branch and bound est la plus utilisee [9] [30] [48] [72] [81]. Le principe de base de cette methode est de separer l'espace des solutions en
plusieurs parties (phase de branchement) et evaluer pour chacune de
ces branches une borne inferieure de ses solutions. Le but est de couper les branches dont on sait qu'elles ne contiennent pas de solutions
d'evaluation inferieures a une solution de reference. Les techniques de
branchement et de calcul de bornes inferieures sont tres variees [19] [70],
nous ne donnerons ici que quelques references bibliographiques de bases
permettant d'avoir plus de details sur ces methodes. A partir de 1965,
un certain nombre d'approches de resolution utilisant le principe de generation d'ordonnancements actifs [53] ont ete proposees : S. Ashour et
al. [8], G.H. Brooks et C.R. White [21], M. Florian et al. [47]. D'autres
algorithmes de ce genre furent developpes par E. Balas [10] en 1969,
B.J. Lageweg et al. [70], J.R. Barker et G.B. McMahon [12], J. Carlier
et E. Pinson [28], D. Applegate et W. Cook [7], J. Carlier et E. Pinson [29].
36
CHAPITRE 1. LE PROBLE ME DU JOB-SHOP
Comme nous l'avons vu dans la section 1.2.2, la programmation
mathematique est un outil de modelisation interessant pour le probleme
du job-shop. Recemment, des tests ont ete e ectues sur les modeles
classiques presentes dans la section 1.2.2 par C.S. Liao et C.T. You
[75]. Une comparaison des temps de calcul est exposee dans leur article,
mais les exemples traites sont de petite taille (3 a 5 jobs et 3 a 10
machines). Pour des tailles plus importantes, le temps de calcul semble
trop important pour que ces methodes soient directement utilisables.
L'approche polyedrale (cf 1.2.3) n'a pas ete tres utilisee en tant que
telle pour la mise en uvre de methode de resolution. Cette technique
dite de plan de coupe est beaucoup utilisee, avec des resultats probants,
pour la resolution du voyageur de commerce par exemple. Le principe
d'un tel algorithme est de calculer la solution donnee par la resolution
d'un programme lineaire dont les contraintes forment un sous-ensemble
des contraintes de nissant le polyedre. La deuxieme phase consiste a
analyser la solution trouvee pour determiner les contraintes du probleme non veri ees. Ces contraintes sont introduites dans le programme
lineaire et une nouvelle solution est calculee. La diculte reside dans
le fait que pour une solution donnee par la resolution du programme
lineaire, il est tres dicile de trouver les contraintes non respectees.
La structure du polyedre est mathematiquement interessante, mais son
exploitation reste trop dicile. D. Applegate et W. Cook [7] ont utilise
les contraintes les plus simples pour developper un algorithme branch
and bound.
La programmation dynamique, developpee par R. Bellman [13] est
une des techniques pour la resolution optimale de problemes combinatoires. Tres utilisee pour les problemes a une machine [61], cette
technique n'a pas ete utilisee pour la resolution du job-shop.
Comme nous le disions plus haut, trouver une solution optimale
pour un probleme NP-complet constitue un de . Il n'est donc pas surprenant de voir qu'un probleme de taille 10 jobs, 10 machines propose
par M.L. Fischer et G.L. Thompson dans l'ouvrage de J.F. Muth et
G.L. Thompson [82] en 1963 ne soit resolu par J. Carlier et E. Pinson [28] qu'en 1989. Pour des tailles petites et quelques fois moyennes
1.3. LES METHODES
DE RESOLUTION
37
des problemes, les algorithmes exacts peuvent ^etre performants, mais
des que la taille augmente, ces methodes perdent leur ecacite et deviennent inutilisables.
1.3.5 Les methodes de relaxation
Les methodes de relaxation ont un double r^ole dans la resolution de
problemes d'optimisation combinatoire [52]. D'une part, elles donnent
de bonnes bornes inferieures pour augmenter l'ecacite de methodes
branch and bound, d'autre part, elles sont a la base de methodes de
resolutions comme la relaxation lagrangienne [42] [43] [44] [45]. Le
principe de ces methodes et de relaxer un certain nombre de contraintes
de facon a rendre plus facile la resolution du probleme. Dans le cas du
job-shop, M.L. Fisher et al. [46] propose une approche tres interessante.
Dans celle-ci, ils experimentent dans un premier temps la relaxation
des contraintes de ressources de machines et ensuite des contraintes de
gammes operatoires. Cette methode donne de bonnes solutions pour
des problemes de petite taille mais n'a pas ete testee pour des tailles
plus importantes.
1.3.6 Les methodes de decomposition
Les methodes de decomposition spatiale ne sont pas reellement des
methodes de resolution du probleme du job-shop. Le principe d'une
telle approche est de casser la complexite du probleme en decomposant
le probleme initial en plusieurs sous-problemes plus faciles a resoudre.
Le but d'une telle methode est regrouper les jobs utilisant le m^eme
ensemble de machines. L'objectif est alors de rendre les plus independant possibles les groupes de jobs. Pour cela, il faut qu'un job n'utilise
que des machines lies a son groupe, et qu'une machine ne traite que des
jobs d'un m^eme groupe. Pour decomposer un probleme de ce type des
methodes comme la technologie de groupe peuvent ^etre utilisees [35].
Nous ne voulons pas detailler ici toutes les methodes de decomposition,
mais nous donnons simplement quelques references [35] [88]. Quand le
probleme est decompose, deux cas se presentent. La decomposition est
dite parfaite (les sous problemes sont completement independants). La
38
CHAPITRE 1. LE PROBLE ME DU JOB-SHOP
resolution de chacun des sous-problemes separement donne une solution globale de l'ordonnancement. Si la decomposition n'est pas parfaite
(certains jobs passent sur des machines liees a des groupes di erents) la
resolution de chaque sous-probleme ne donne pas une solution realisable
du probleme global et il faut traiter les problemes de liens residuels. H.
Lemonias [74] propose une methode de synchronisation pour ce probleme.
39
Chapitre 2
Une approche par agregation
La methode proposee maintenant s'attache a la resolution de probleme de job-shop statique et deterministe. L'objectif des heuristiques
qui en decoulent est la minimisation de la longueur maximale de l'ordonnancement (Cmax). Si la plupart des methodes mises en uvre ces
dernieres annees (cf 1.3.3.1) utilisent comme elements de base les operations (regles de priorite) [84] [113] ou les machines (Shifting Bottleneck
Procedure) [2], notre approche utilise les jobs. Le principe de cette methode est de construire des ordonnancements partiels en agregeant a
un ordonnancement deja etabli un job ou un autre ordonnancement
partiel. Les algorithmes generaux qui en resultent sont bases sur deux
procedures particulieres, les procedures de selection des jobs et d'agregation.
L'un des objectifs de cette approche par agregation est de contr^oler
d'une part l'e ort d'optimisation en fonction de la taille de l'instance
traitee, mais egalement le temps de calcul et la qualite de la solution.
Pour cela, un certain nombre d'heuristiques sont proposees, certaines
privilegiant la rapidite et sont ainsi adaptees a la resolution de problemes de grande et tres grande taille, d'autres optimisent de facon
plus ne et sont plus adaptees a des problemes de petite et moyenne
taille.
Dans un premier temps, nous allons de nir un ordonnancement partiel sur un ensemble de jobs et le principe d'agregation entre deux jobs.
40
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
Ensuite, cette approche sera generalisee pour les agregations d'un job
et d'un ordonnancement partiel et l'agregation de deux ordonnancements partiels. Dans une deuxieme partie, nous proposerons un algorithme general de resolution et des procedures de selection et d'agregation particuliere bases sur le principe d'agregation entre un job et
un ordonnancement partiel. Ensuite, un algorithme general et des procedures d'agregation bases sur le principe d'agregation de deux ordonnancements partiels seront decrites. En n, nous parlerons de procedures
d'amelioration locale. Pour nir, les heuristiques proposees seront testees sur un ensemble de problemes representatifs.
2.1
Le principe de l'agregation
Dans cette nouvelle approche, les jobs sont ordonnances les uns
apres les autres et a chaque etape un ou plusieurs ordonnancements
partiels realisables sont crees. Ce principe repose sur deux concepts de
la theorie de l'ordonnancement : la selection selon des regles de priorite et la creation d'ordonnancements partiels. Les deux etapes cles
des algorithmes generaux donnes plus loin sont donc les procedures de
selection d'un job (ou d'un ordonnancement partiel) selon un critere
prede ni et l'agregation du job (ou de l'ordonnancement partiel) a un
ordonnancement partiel courant.
Reprenons tout d'abord le modele sous forme de graphe disjonctif
que nous avons de ni dans la section 1.2.1. Un probleme de job-shop
est represente par un graphe = (
[ ), ou est l'ensemble
des sommets du graphe , est l'ensemble des arcs conjonctifs et
est l'ensemble des arcs disjonctifs). Dans la suite de ce chapitre, nous
travaillerons a partir de ce modele.
G
G
X; C
D
X
C
D
2.1.1 Ordonnancement partiel sur jobs
l
A partir du probleme de job-shop = (
[ ) a jobs, il
est possible d'extraire un sous-probleme a jobs avec
. Ce
sous-probleme est represente par le graphe disjonctif , graphe partiel
du graphe . Nous pouvons donc ecrire = (
[ ) ou est
G
X; C
Pl
D
n
l
l < n
Gl
G
Gl
Xl ; Cl
Dl
Xl
2.1. LE PRINCIPE DE L'AGRE GATION
41
compose des sommets et et des sommets associes aux operations
des jobs de l'ensemble l . Les ensembles d'arcs l et l sont composes
des arcs de liant les sommets de l.
deb
f in
P
C
G
D
X
Le sous-probleme l et son graphe disjonctif associe l etant denis, nous appellerons ordonnancement partiel l une solution de l.
Cette solution correspond a un arbitrage complet et compatible des
paires d'arcs disjonctifs, selection pour chaque paire d'un des deux arcs
(cf 1.2.1). L'ensemble des arcs disjonctifs l est reduit a l'ensemble l.
Pour que la solution l soit realisable il est bien sur necessaire que le
graphe solution l = ( l l [ l ) soit acyclique. Par la suite, nous
noterons la longueur de l'ordonnancement partiel max( l ). Pour une
representation simpli ee de la solution sur le graphe, il n'est pas necessaire de conserver la totalite des arcs de l , mais garder pour chaque
clique de disjonction un chemin representant l'ordre de passage des
operations sur la machine.
P
G
P
P
D
D
P
G
X ;C
D
C
P
D
Pour chaque solution l du probleme a jobs, nous pouvons de nir
deux nouvelles variables par operation. Ces variables seront appelees
date de debut au plus t^ot et date de debut au plus tard, et seront
respectivement notees i;j et i;j pour une operation i;j . La date au plus
t^ot i;j est la date avant laquelle l'operation i;j ne peut commencer,
soit parce que l'operation precedente dans sa gamme operatoire n'est
pas achevee, soit parce que l'operation precedente sur la machine n'est
pas nie. Sur le graphe solution l, i;j represente le plus long chemin
(somme des ponderations sur les sommets) du sommet au sommet
. Sur le graphe
i;j exclu. Nous associons la valeur max au sommet
l, i;j represente le plus long chemin du sommet i;j inclus au sommet
et represente ainsi une latence de n. Le calcul de i;j se fait donc en
enlevant a la valeur max, la somme des temps operatoires du chemin
le plus long. Au niveau de l'ordonnancement, ces variables donnent
respectivement le temps minimum qui doit s'ecouler avant de pouvoir
commencer l'operation i;j , et le temps minimum qui doit s'ecouler
apres l'execution de l'operation pour achever l'ordonnancement.
P
r
l
q
O
r
O
G
r
deb
O
G
C
q
f in
O
f in
q
C
O
42
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
A partir de ces deux variables, nous pouvons introduire la notion de
marge associee a une operation. Nous noterons mai;j la marge associee
a l'operation Oi;j . Celle-ci est egale a :
mai;j = Cmax , (ri;j + qi;j + pi;j )
(2.1)
Elle represente, au niveau de l'ordonnancement, la valeur du decalage possible de l'operation sans que le resultat de l'ordonnancement
(Cmax) ne soit altere.
Dans le graphe solution, nous appellerons chemin critique, un chemin liant deb a fin dont tous les sommets ont une marge nulle. En generalisant, nous appellerons graphe critique, un sous-graphe du graphe
solution dont tous les sommets ont une marge nulle. Cela signi e que
si l'on decale une operation de ce chemin ou de ce graphe critique, la
duree de l'ordonnancement sera augmentee d'autant.
2.1.2 L'agregation de deux jobs
L'agregation la plus simple est certainement celle qui a partir de
deux jobsLJ1 et J2 genere un ordonnancement. Nous la noterons J1 L J2,
le signe representant l'agregation. Ce cas particulier est polyn^omial et
constitue un job-shop a deux jobs. Nous donnons maintenant le principe
de resolution developpe par S.B. Akers [6] et l'algorithme performant de
P. Brucker [22] qui en decoule. La methode est illustree sur un exemple
( gure 2.1).
Considerons maintenant l'exemple avec les jobs suivants : J1 est
constitue de trois operations. O1;1 a un temps operatoire de 4 unites
de temps sur M1, O1;2 de 3 unites de temps sur M2, et O1;2 de 6 unites
de temps sur M3. En ce qui concerne J2, les trois operations sont O2;1
qui necessite 5 unites de temps sur M1, O2;2 qui necessite 2 unites de
temps sur M3, et O2;3 qui necessite 7 unites de temps sur M2.
Comme nous l'avons vu dans la section 1.3.2.2, ce probleme peut
^etre ramene a un probleme de plus court chemin dans le plan avec
obstacles rectangulaires ( gure 2.1). P. Brucker [22] propose dans un
2.1. LE PRINCIPE DE L'AGRE GATION
43
J2
6
F
14
=(13,14)
,
,
,
,
,
2
,
,
,,
7
3
5
1
O = (0,0)
,
,,
,,
4
Fig. 2.1 -
7
13
Plan avec obstacles
-
J1
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
44
premier temps de modeliser le probleme du plan avec obstacles sous la
forme d'un reseau. Ce reseau est constitue de deux
sommets et
dont les coordonnees sont respectivement (0 0) et Pjj==1n2 2;j Pjj==1n1 1;j ,
et des sommets associes au angles nord-ouest ( ) et sud-est ( ) des
obstacles rectangulaires. Il existe un arc :
O
;
p
NO
;
F
p
SE
{ entre le sommet et les sommets
et du premier obstacle
rencontre en partant du point et en se deplacant suivant la
droite = .
O
NO
SE
O
y
x
{ entre un sommet
d'un obstacle et les sommets du premier
obstacle rencontre en partant du point
et en se deplacant
suivant la direction = .
NO
NO
y
x
{ entre un sommet
d'un obstacle et les sommets du premier
obstacle rencontre en partant du point
et en se deplacant
suivant la direction = .
SE
SE
y
x
{ entre un sommet et si a partir de ce sommet et suivant la
jX
=n2
direction = on arrive sur une des droites =
2;j ou
F
y
x
=
X
j =n1
j =1
x
y
j =1
p
;j .
p1
Les arcs, ainsi construits sur ce reseau ( gure 2.2), sont ponderes
par le maximum des longueurs des projections sur les axes de coordonnees. Ce reseau peut ^etre construit en ( A log A) etapes ou A est le
nombre d'obstacles dans le plan.
O n
n
n
La deuxieme partie de l'algorithme consiste a chercher le plus court
chemin dans le reseau. Cette phase necessite ( A ) etapes. Le resultat
obtenu donne la duree totale de l'ordonnancement et la sequence des
operations sur les di erentes machines ( gure 2.3).
O n
2.1. LE PRINCIPE DE L'AGRE GATION
45
: 2 NO S
S
7 1 NO Z
SS
ZZ
Z~ 2 SE H S
S
H
H
HHSHjSw
O
*
7
SS
3 NO
SS
>
SS
w 1 SE
XXXXz 3 SE 9
5
4
7
7
9
1
7
7
F
9
Reseau associe au plan
Fig. 2.2 -
M
9
O
O
1;1
2;1
M
O
2
O
1;2
2;3
M
O
3
4
Fig. 2.3 -
7
9
2;2
O
11
Resultat de l'exemple
1;3
18
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
46
2.1.3 L'agregation d'un job et d'un ordonnancement partiel
Le principe d'agregation developpe dans la section precedente est
polyn^omial L
et le resultat obtenu est optimal. Dans le cas de l'agregation +1 , il ne semble pas possible de trouver un algorithme
polyn^omial et de faible complexite donnant une solution optimale.
Les
L
algorithmes developpes sur le principe de l'agregation +1
seront
de type heuristique.
Jl
Pl
Jl
Pl
L'agregation +1 L consiste a donner une sequence des operations sur chaque machine en conservant l'ordre des operations donne
par l'ordonnancement partiel . Cela revient a creer un ordonnancement partiel +1.
Jl
Pl
Pl
Pl
Au niveau du graphe disjonctif, cela consiste a reprendre le resultat
de l'ordonnancement des premiers jobs = (
[ ) et a ajouter
les sommets correspondant au job +1 pour construire le graphe disjonctif +1 , dont certaines des disjonctions sont deja arbitrees (celles
de ). Le principe d'agregation utilise sur ce graphe a pour but de selectionner pour chaque paire d'arcs disjonctifs de +1 non arbitree, un
unique arc. Pour que l'ordonnancement partiel +1 soit realisable il est
bien sur necessaire que le graphe +1 obtenu soit acyclique (cf 1.2.1).
l
Gl
Xl ; Cl
Dl
Jl
Gl
Pl
Dl
Pl
Gl
2.1.4 L'agregation de deux ordonnancements partiels
L'agregation de deux ordonnancements partiels et est en fait
une generalisation du concept decrit dans la section precedente. Comme
dans l'agregation d'un job avec un ordonnancement partiel, le principe
est de conserver les ordres de passage des operations sur les machines
correspondantes dans les deux ordonnancements partiels. L'objectif est
alors d'inserer pour chaque machine les operations de (resp. )
utilisant celle-ci dans la sequence donnee pour le passage des operations
de (resp. ).
Pl
Pr
Pl
Pr
Pr
Pl
Au niveau du graphe disjonctif, cela consiste a reprendre les re-
2.2. LES ALGORITHMES DE TYPE
J
L+1
L L
47
P
sultats des ordonnancements des premiers jobs l = ( l l [ l)
et des suivants r = ( r r [ r ) pour creer le graphe disjonctif
l+r = ( l [ r l [ r [ l [ r ), dont une partie des disjonctions
est arbitree. Ensuite, le but est d'arbitrer les disjonctions pour chaque
paire d'arcs disjonctifs de l+r . Pour que l'ordonnancement partiel l+r
soit realisable, il est bien sur necessaire que le graphe l+r obtenu soit
acyclique (cf 1.2.1).
l
r
G
G
X
X ;C
X ;C
C
D
G
X ;C
D
D
D
D
P
G
2.2 Les algorithmes de type J +1 L P
l
l
Le type d'agr
egation que nous allons maintenant developper est
L
l'agregation l+1 l . Pour commencer, nous donnons un algorithme
general de resolution du job-shop, puis nous detaillerons, dans la suite,
les procedures de selection des jobs et les procedures d'agregation.
J
P
2.2.1 L'algorithme general de resolution
L'idee de base de l'algorithme general de resolution base sur l'agregation l+1 L l est de traiter les jobs les uns apres les autres en
construisant a chaque etape, un ordonnancement partiel.
J
P
L'algorithme constructif de la gure 2.4 decrit le deroulement de la
methode. On constate que cette methode repose sur deux procedures
particulieL
res, une de selection des jobs (pas 2 et 4) et une d'agregation l+1 l (pas 5). Les procedures de selection ferontLl'objet de
la section 2.2.2 alors que des procedures d'agregation l+1 l seront
proposees dans les sections 2.2.3 2.2.4 et 2.2.5.
J
P
J
P
Cet algorithme constructif peut ^etre legerement modi e par l'ajout
entre les pas 5 et 6 d'une procedure d'amelioration locale. Ce type
de procedure sera discute dans la section 2.4. L'algorithme propose
precedemment est sequentiel et ne permet pas d'envisager des calculs
en parallele.
48
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
1. INITIALISATION
Faire la liste des jobs a ordonnancer.
2. SELECTION
DES DEUX PREMIERS JOBS
Utilisation d'une regle de priorite pour la selection des deux premiers jobs (somme des temps operatoires).
3. AGREGATION
Utilisation d'une procedure d'agregation pour la creation du premier ordonnancement partiel (algorithme de P. Brucker, cf 2.1.2).
4. SELECTION
DU JOB A AGREGER
Utilisation d'une regle de priorite pour la selection du job a agreger (somme des temps operatoires).
5. AGREGATION
Utilisation d'une procedure d'agregation du type J +1 L P .
^
6. CONDITION D'ARRET
l
l
(a) Si tous les jobs sont traites, arr^eter.
(b) Sinon, retourner en 4.
Fig.
2.4 - Algorithme general base sur J +1 L P
l
l
2.2. LES ALGORITHMES DE TYPE
J
L+1
L L
49
P
2.2.2 Les procedures de selection des jobs
Pour ce qui est des procedures de selection des jobs, nous proposons,
le m^eme type de regles de priorite que pour les algorithmes constructifs
bases sur ce principe (cf 1.3.3.1), mais appliquees aux jobs au lieu des
operations.
En premier lieu, il est possible d'envisager des regles de priorite
statiques. Ces regles ne dependent que des donnees du probleme et
sont independantes du processus de construction des ordonnancements
partiels. Nous pouvons donc determiner des l'initialisation un ordre de
selection des jobs lie par exemple a la duree totale de ceux-ci ou au
nombre d'operations qu'ils contiennent.
Dans un deuxieme temps, nous considererons des regles de priorite
dynamiques tenant compte cette fois du deroulement du processus de
construction des ordonnancements intermediaires. La priorite peut ^etre
donnee au job dont l'operation la plus longue utilise une machine goulot
(ayant le plus d'operations sur le chemin critique). Ce type de regles est
bien entendu plus interessant mais demande des calculs supplementaires
lors de la phase de selection.
Nous ne voulons pas ici faire un catalogue des regles de priorite
possibles pour la selection des jobs. Il est evident que l'on peut creer
un nombre important de regles en generalisant celles existantes pour
les algorithmes de liste. Pour tous les tests e ectues par la suite, nous
ne considererons que la somme des temps operatoires de chaque job.
L
2.2.3 Une procedure basee sur l'agregation J1 J2
La premiere methode d'agregation Jl+1 L Pl que nous proposons est
iterative et basee sur le principe d'agregation de deux jobs [86]. A une
certaine etape de l'algorithme general ( gure
2.4), un nouveau job est
selectionne et le probleme Pl+1 Jl+1 L Pl est a resoudre. La procedure d'agregation utilise alors le fait que Pl est un ordonnancement
partiel construit sur les jobs S = fJ1; :::; Jlg. Le principe est de selectionner un job Jy de S et de l'agreger avec le job Jl+1. Cette agregation
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
50
permet d'arbitrer les disjonctions entre les operations de ces deux jobs.
A l'iteration suivante, un job de S n fJ g est selectionne et agrege avec
J +1 en tenant compte de tous les arbitrages determines auparavant et
des dates de debut au plus t^ot et au plus tard issues du graphe G
associe a l'ordonnancement partiel P .
y
l
l
l
Cette procedure est basee sur une generalisation de l'algorithme de
P. Brucker pour le probleme a deux jobs. P. Brucker et B. Jurisch [23]
ont developpe un algorithme permettant de resoudre le probleme de
job-shop a deux jobs tenant compte de precedences et de dates au plus
t^ot r et au plus tard q . L'algorithme que nous proposons est donne
dans la gure 2.5.
i;j
i;j
2.2.4 Des procedures d'agregation par decoupage
du temps
Nous proposons maintenant des techniques d'agregation basees sur
un decoupage du temps en intervalles, suivi de l'insertion des operations
du job a agreger. Dans un premier temps, nous decrirons une methode
ou les operations sont reparties dans les intervalles et inserees en une
seule fois. La deuxieme procedure insere les operations iterativement
et dans l'ordre de la gamme operatoire de facon a tenir compte des
decalages possibles a l'issue de chaque insertion. En n, la troisieme
procedure insere egalement les operations iterativement mais dans un
ordre xe par une regle de priorite.
2.2.4.1 Decoupage du temps et agregation globale
Cette procedure repose sur l'idee simple que les premieres operations
d'un job J +1 a agreger, doivent ^etre inserees au debut de l'ordonnancement partiel alors que les dernieres doivent plut^ot ^etre inserees a la n.
Ceci se justi e aisement par le fait que si la derniere operation O +1 +1
est placee au debut de l'ordonnancement courant, celui-ci est pratiquement decale de la longueur de J +1 (la somme des temps operatoires),
car il faut respecter la gamme operatoire et toutes les operations de
J +1 seront donc en debut d'ordonnancement. De m^eme, si O +1 1 est
placee en n d'ordonnancement, celui-ci sera egalement augmente de
l
l
;nl
l
l
l
;
2.2. LES ALGORITHMES DE TYPE J
+1
L
L P
L
51
1. INITIALISATION
Faire la liste S des jobs de P .
2. SELECTION
DU JOB A AGREGER
Selectionner un job J de S selon une regle de priorite (somme
des temps operatoires).
3. AGREGATION
Agreger le job J selectionne avec J +1 en utilisant la procedure
de P. Brucker et B. Jurisch (J L J +1).
4. MISES A JOUR
Mettre a jour les precedences, les dates de debut au plus t^ot r
et au plus tard q dans l'ordonnancement partiel, et supprimer
J de S .
^
5. CONDITION D'ARRET
l
x
x
l
x
l
i;j
i;j
x
(a) Si tous les jobs de S sont traites ou si toutes les disjonctions
sont arbitrees, arr^eter.
(b) Sinon, retourner en 2
Fig.
2.5 - Algorithme d'agregation base sur J1 L J2
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
52
la longueur de l+1 car toutes les operations de
l'ordonnancement.
J
l+1
J
seront a la n de
Dans un premier temps, nous allons decouper la duree totale de
l'ordonnancement partiel max( l), en autant d'intervalles qu'il y a
d'operations dans le nouveau job. Pour cela, nous commencons par
calculer la marge relative, notee
, disponible pour l'insertion des
operations :
C
P
MR
MR
max ,
=
X
j =n +1
l
C
j =1
(2.2)
l+1;j
p
La marge relative ainsi calculee, nous proposons trois manieres de
la repartir sur la duree totale de l. Bien entendu, d'autres repartitions
pourraient ^etre envisagees.
P
{ La repartition lineaire : la marge relative sera repartie de facon egale pour chaque operation l+1;j et l'intervalle donne pour
l'insertion d'une operation sera de longueur :
O
l+1;j +
p
h
h
(2.3)
MR
l+1
n
i
Ainsi, l'operation l+1;1 devra ^etre inseree dans l'intervalle
0 l+1;1 + nMR
+1 ,
l'operation l+1;2 dans
MR
MR
l+1;1 + n +1 l+1;1 + l+1;2 + 2 n +1
et ainsi de suite.
{ La repartition geometrique : dans ce cas, une plus grande part
de la marge relative est a ectee a l'operation l+1;1 et la part de
la marge relative decro^t en s'approchant de la derniere operation.
Nous obtenons des intervalles pour l+1;j de taille :
p
O
;p
l
i
O
l
;p
p
l
O
O
l+1;j + (nl+1 + 1 , j ) M R p
n
2
l+1 ( l+1 + 1)
n
(2.4)
2.2. LES ALGORITHMES DE TYPE J
+1
L
L P
L
53
Ce type de decoupage est plus adapte a une agregation iterative
comme celle qui sera presentee dans la section 2.2.4.2.
{ La repartition relative : nous considerons que les operations
les plus dures a inserer sont celles dont le temps operatoire est
le plus grand. Dans ce cas, les intervalles seront proportionnels
au temps operatoire de l'operation. La taille de l'intervalle pour
l'operation O +1 sera alors :
l
p +1
l
;j
+
;j
p +1
Xp
r
=
r
l
ni
=1
MR
;j
+1
l
(2.5)
;r
Dans chacun des intervalles calcules, il faut maintenant inserer l'operation correspondante. Le principe est de construire la liste des emplacements disponibles pour placer l'operation. Un emplacement est en
fait une position dans la sequence d'operations sur une machine. Sa
taille ta est calculee en faisant la di erence entre la date de debut au
plus tard de l'operation O qui suit et la date de n au plus t^ot de
l'operation O qui precede. On a alors :
a;b
c;d
ta = q
a;b
, (r + p )
c;d
c;d
(2.6)
Ensuite, nous choisirons l'emplacement dont la di erence entre le
temps operatoire et la longueur de l'emplacement est minimum. D'autres possibilites sont envisageables comme choisir l'emplacement dont
la taille correspond le plus au temps operatoire de l'operation (di erence entre le temps operatoire et la longueur de l'emplacement est
proche de zero). Dans cette etape, nous e ectuons une agregation dite
globale car des que les intervalles sont xes pour chaque operation,
le choix de l'insertion pour une operation est independant des autres.
Ainsi, on pourrait commencer par inserer la derniere operation plut^ot
que la premiere sans que cela ne change le resultat de la procedure.
L'algorithme ainsi obtenu est donne dans la gure 2.6. Un exemple de
ce type d'agregation est donne dans la gure 2.7.
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
54
1. CALCUL DE LA MARGE RELATIVE
Calcul de la marge relative MR en vue du decoupage en
intervalles.
2. CALCUL DES INTERVALLES
n +1
l
(a) Decoupage lineaire.
(b) Ou decoupage geometrique.
(c) Ou decoupage relatif.
3. INSERTION DES OPERATIONS
Pour chaque operation, insertion dans le meilleur emplacement
de l'intervalle considere.
4. MISE A JOUR
Calcul des dates au plus t^ot et au plus tard apres agregation.
Fig.
2.6 - Algorithme de decoupage du temps et agregation globale
2.2. LES ALGORITHMES DE TYPE J
O5 1
+1
L
L P
55
L
O5 2
;
O5 3
;
;
J5
M1
M2
M3
?
O1 1
;
O3 1
O2 2
;
O2 1
O3 2
;
;
O2 3
;
O1 3
;
M4
O4 3
;
?
O1 2
;
O3 3
;
;
O4 1
O2 4
;
8
Fig.
?
O4 2
;
;
21
2.7 - Resultat de l'agr
egation globale
30
56
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
2.2.4.2 Decoupage du temps et insertion iterative
Le principe de cette procedure d'agregation est sensiblement le m^eme que la procedure de la section 2.2.4.1. Au depart, seul l'intervalle
de la premiere operation est calcule, suivant l'un des principes expliques plus haut. Dans cet intervalle, l'operation va ^etre inseree dans
l'emplacement le meilleur. Ensuite, les dates de debut au plus t^ot et
au plus tard sont recalculees tenant compte des operations inserees. La
deuxieme operation du job est ensuite traitee. Un nouvel intervalle de
temps est calcule entre la n au plus t^ot de la premiere operation et la
n de l'ordonnancement, et l'operation est ensuite inseree. Le processus
se poursuit tant qu'il reste des operations non traitees.
L'algorithme qui en decoule est donne dans la gure 2.8. Cette methode est moins rapide que la precedente du fait du recalcul des dates
au plus t^ot et au plus tard, mais permet un meilleur choix de la zone
d'insertion car la marge relative est recalculee apres chaque insertion.
Une economie de temps de calcul pourrait ^etre faite si seulement la
marge relative etait recalculee sans recalcul des dates au plus t^ot et
au plus tard. Dans ce dernier cas, les perturbations apportees par les
premieres insertions ne seraient pas repercutees dans la suite et cela
reviendrait a une methode directe comme celle de la section 2.2.4.1.
Les trois gurent qui suivent (2.9 2.10 2.11) montrent comment sont
inserees les operations du job.
2.2.4.3 Decoupage du temps et insertion relative
Tout en conservant les principes de decoupage du temps et insertion
iteratives, nous proposons maintenant d'inserer les operations dans un
ordre qui ne suit plus forcement celui de la gamme operatoire. En e et,
certaines operations peuvent poser plus de dicultes que les autres
pour ^etre placees dans l'ordonnancement partiel. Ceci peut ^etre d^u a
la valeur du temps operatoire ou a un taux d'occupation de la machine
deja tres eleve. Pour tenir compte de ce phenomene, l'algorithme de la
gure 2.12 accorde un intervalle d'autant plus grand que l'operation est
dicile a inserer.
2.2. LES ALGORITHMES DE TYPE JL+1 L PL
57
1. CALCUL DE LA MARGE RELATIVE
Calcul de la marge relative pour les operations restant a traiter
(calcul de MR sur l'intervalle entre la n de l'operation precedente
et Cmax(Pl)).
2. CALCUL DE L'INTERVALLE POUR L'OPERATION
COURANTE
Calcul de l'intervalle sur un horizon compris entre la n de l'operation precedente et la n de l'ordonnancement.
(a) Decoupage lineaire.
(b) Ou decoupage geometrique.
(c) Ou decoupage relatif.
3. INSERTION DE L'OPERATION
COURANTE
Pour l'operation courante, insertion dans le meilleur emplacement
de l'intervalle considere.
4. MISE A JOUR
Calcul des dates au plus t^ot et au plus tard tenant compte des
operations deja inserees.
5. SELECTION
DE L'OPERATION
COURANTE
(a) S'il reste des operations non traitees, selectionner l'operation
suivante et retourner en 1.
(b) Sinon, arr^eter.
Fig.
2.8 - Algorithme de decoupage du temps et insertion iterative
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
58
O5 1
O5 2
;
O5 3
;
;
J5
M1
M2
?
O1 1
;
O3 1
;
O1 2
;
M3
O2 2
;
O4 1
;
8
Fig. 2.9 -
O1 3
;
M4
;
;
O3 2
;
O4 3
;
O2 3
;
O2 1
O3 3
O4 2
;
O2 4
;
30
Premiere insertion pour l'agregation iterative
2.2. LES ALGORITHMES DE TYPE J
+1
L
L P
59
L
O5 2
O5 3
;
;
J5
O5 1
;
M1
M2
M3
O1 1
O2 2
;
O3 1
;
O2 1
O3 2
;
;
;
O4 1
2.10 -
O4 2
;
O2 4
;
7
;
O2 3
O1 3
;
O4 3
;
?
O1 2
;
M4
Fig.
O3 3
;
;
19,5
30
Deuxieme insertion pour l'agregation iterative
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
60
O
5;3
O
5;1
M
1
O
M O
2
M
3
O
1;1
O
3;1
2;1
M
3;2
O
1;3
O
4
2;3
O
4;2
?
O
4;1
2;4
18
Fig. 2.11 -
4;3
O
5;2
O
O
3;3
O
1;2
O
O
2;2
34
Derniere insertion pour l'agregation iterative
2.2. LES ALGORITHMES DE TYPE JL+1 L PL
61
Si l'on considere comme critere de diculte pour l'insertion le temps
operatoire de chaque operation, nous pouvons envisager un decoupage
semblable a la repartition relative precedemment decrite. Toutefois, si
l'on garde strictement la repartition relative, cela n'apporte rien de plus
que la methode de la section 2.2.4.2. Pour cela, l'intervalle considere sera
augmente de part et d'autre d'un certain pourcentage pour augmenter
le nombre de possibilites d'insertion.
Dans cette methode, les operations sont traitees iterativement par
ordre decroissant de leur diculte d'insertion comme le montrent les
gures 2.13 2.14 et 2.15.
2.2.5 Agregation globale par fonction co^ut
L'algorithme de la gure 2.16 montre le principe de cette troisieme
approche d'agregation. Le but est ici d'agreger le job d'une maniere
globale en tenant compte de la totalite de l'ordonnancement partiel et
non plus d'un intervalle de temps.
Le principe de la methode est de repertorier l'ensemble (ou un sousensemble) des emplacements disponibles pour chacune des operations
du job a agreger. Le placement de l'operation dans un des emplacements possibles entra^nera un co^ut dependant a la fois de la place de
l'operation dans la gamme operatoire du job, de la marge disponible
dans l'emplacement selectionne, etc. La fonction co^ut total pour le job
aura alors pour valeur la somme des co^uts entra^nes par le placement
de chaque operation dans un emplacement. On realisera l'a ectation
dans les emplacements permettant d'obtenir la valeur minimale pour
la fonction co^ut total (cf algorithme de la gure 2.16).
Nous presentons maintenant un exemple de fonction co^ut a minimiser. Pour cela, on de nit la fonction co^ut total Fjob pour ce job comme
etant la somme des fonctions co^ut de chacune de ses operations (Fop).
X
Fjob = Fop
(2.7)
Pour le calcul de la valeur de Fop de chaque operation, on choisit de
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
62
1. CALCUL DE LA MARGE RELATIVE
Calcul de la marge relative pour les operations restant a traiter
(calcul de MR sur l'intervalle entre la n au plus t^ot de l'operation
precedente et le debut au plus tard de l'operation suivante).
2. CALCUL DE L'INTERVALLE POUR L'OPERATION
COURANTE
(a) Calcul de l'intervalle par decoupage relatif
(b) Augmentation de l'intervalle en fonction de l'operation courante
3. INSERTION DE L'OPERATION
COURANTE
Pour l'operation courante, insertion dans le meilleur emplacement
de l'intervalle considere.
4. MISE A JOUR
Calcul des dates au plus t^ot et au plus tard tenant compte des
operations deja inserees.
5. SELECTION
DE L'OPERATION
COURANTE
(a) S'il reste des operations non traitees, selectionner l'operation
suivante et retourner en 1.
(b) Sinon, arr^eter.
Fig.
2.12 - Algorithme de decoupage du temps et insertion relative
2.2. LES ALGORITHMES DE TYPE J
O5 1
+1
L
L P
63
L
O5 2
;
O5 3
;
;
J5
M1
M2
M3
O1 1
O2 2
;
O3 1
;
O2 1
O3 2
;
;
O2 3
;
O1 3
;
O4 3
;
?
O1 2
;
M4
;
O4 2
;
O4 1
O2 4
;
6
Fig.
O3 3
;
2.13 -
;
23
30
Premiere insertion pour l'agregation relative
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
64
O
O
5;1
M
1
O
M
3
O
1;1
M O
2
5;3
O
3;1
2;1
M
3;2
O
1;3
O
4
2;3
O
4;2
?
O
4;1
2;4
18
Fig. 2.14 -
4;3
O
5;2
O
O
3;3
O
1;2
O
O
2;2
34
Deuxieme insertion pour l'agregation relative
2.2. LES ALGORITHMES DE TYPE J
+1
L
L P
65
L
O5 1
;
M1
M2
M3
?
O1 1
;
O3 1
;
;
O4 1
;
11
Fig.
;
O1 3
;
;
O2 3
;
O3 2
O4 3
;
O5 2
;
O2 1
O3 3
;
O1 2
;
M4
O2 2
O4 2 O5 2
;
;
O2 4
;
34
2.15 - Derniere insertion pour l'agregation relative
66
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
prendre en compte :
{ La taille du temps mort sur la machine ou A est la valeur de la
di erence entre le temps operatoire et le temps mort. Ceci permet
d'avantager les temps morts les plus grands.
{ La position du temps mort dans l'ordonnancement :
B = dt , Cnmax j
(2.8)
l+1
ou dt est le debut du temps mort et j le numero de l'operation. Ceci decoupe l'ordonnancement en intervalle et avantage les
temps morts proches de l'intervalle correspondant a l'operation a
inserer.
La valeur de Fop sera une combinaison lineaire de ces deux parametres.
Fop = A + B
(2.9)
Pour l'a ectation d'une operation sur un temps mort, il faudra faire
attention a respecter les precedences. Ceci pourra se faire, soit en ne
permettant pas l'a ectation d'une operation au temps mort ne correspondant pas, soit en rajoutant une grande valeur dans les fonctions
co^uts correspondant aux temps morts impossibles. Un exemple d'insertion par fonction co^ut est donne dans la gure 2.17.
2.3 Les algorithmes de type Pl Pr
L
Comme dans la section sur l'agregation Jl+1 Pl , nous proposons
ici un algorithme general de resolution du probleme. Dans ce type de
resolution, la phase de selection est tres importante car elle determine
le type d'agregation que l'on doit utiliser par la suite.
L
2.3. LES ALGORITHMES DE TYPE PL L PR
67
1. EMPLACEMENTS DISPONIBLES
Faire la liste des emplacements disponibles (en totalite ou partiellement).
^
2. MINIMISATION DE LA FONCTION COUT
Minimisation de la fonction co^ut donnant l'a ectation des operations et la position dans les sequences operatoires des machines.
3. INSERTION DES OPERATIONS
Insertion des operations dans les emplacements obtenus a la suite
de la minimisation de la fonction co^ut.
4. MISE A JOUR
Calcul des dates au plus t^ot et au plus tard apres l'agregation.
Fig.
2.16 - Algorithme d'agregation a l'aide d'une fonction co^ut
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
68
O
M
1
O
;
M
3
O
3;1
O
2;1
M
4
O
5;2
? O2 2
1;1
M O
2
O
5;1
O
O
3;3
4;3
O
1;2
?
2;3
O
3;2
O
4;1
O
1;3
5;3
O
?
4;2
O
2;4
30
Fig. 2.17 -
Resultat de l'agregation par fonction co^
ut
2.3. LES ALGORITHMES DE TYPE PL L PR
69
2.3.1 L'algorithme general de resolution
L'algorithme
de la gure 2.18 utilise L
a la fois le principe d'agregation
L
Jl+1 Pl et le principe d'agregation Pl Pr . Le but de la methode est
de traiter les jobs par groupes pour constituer un certain nombre d'ordonnancements partiels. Ensuite, il faut agreger ces ordonnancements
partiels pour construire l'ordonnancement nal.
Il est possible d'ajouter apres les pas 3 et 6 une procedure d'amelioration locale (cf 2.4). De plus la structure de cet algorithme permet le
calcul en parallele de chaque ordonnancement partiel pour chaque sous
groupe de jobs.
Dans l'algorithme propose, la deuxieme phase (pas 5 a 7) consiste
a agreger sequentiellement les ordonnancements partiels generes dans
la premiere phase (pas 1 a 4). Il est bien s^ur possible de regrouper a
nouveau ces ordonnancements partiels en di erents sous-groupes pour
recreer de nouveaux ordonnancements partiels de taille plus importante.
La encore, ces calculs peuvent s'e ectuer en parallele.
2.3.2 Les procedures de groupement des jobs
Trois manieres de grouper les jobs sont maintenant envisagees. La
premiere repose sur le principe de decomposition. La deuxieme est fondee sur un groupement de jobs di erents, tandis que la troisieme regroupe des jobs dit decales.
Bien entendu, ces facons de regrouper les jobs sont tres liees a la
nature du probleme traite et a la procedure d'agregation des ordonnancements partiels choisie pour la suite de l'algorithme.
2.3.2.1 Une methode de decomposition
La premiere selection que nous proposons est liee a des techniques
de decomposition [74] [88]. Elle consiste a regrouper les jobs utilisant
les m^emes machines, et de sorte qu'une machine ne travaille que pour
executer les operations d'une famille de jobs. Cette selection peut ^etre
70
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
1. INITIALISATION
Faire la liste des jobs a traiter.
2. SELECTION
D'UNE FAMILLE DE JOBS
Selectionner un sous-ensemble des jobs selon une regle de priorite
(cf 2.3.2).
3. AGREGATION
(suivant algorithme gure 2.4)
Agreger les jobs selectionnes pour creer un ordonnancement partiel.
^
4. CONDITION D'ARRET
Si tous les jobs sont traites, continuer.
Sinon, retourner en 2.
5. SELECTION
D'UN ORDONNANCEMENT PARTIEL
Selectionner un nouvel ordonnancement partiel selon une regle de
priorite (longueur des ordonnancements partiels).
6. AGREGATION
Utiliser une procedure d'agregation du type P L P pour agreger
l'ordonnancement partiel selectionne a l'ordonnancement courant
(cf 2.3.3).
^
7. CONDITION D'ARRET
l
r
(a) Si tous les ordonnancements partiels sont traites, arr^eter.
(b) Sinon, retourner en 5.
Fig.
2.18 - Algorithme general base sur P L P
l
r
2.3. LES ALGORITHMES DE TYPE P
L
L P
R
71
faite par l'utilisation d'une methode de technologie de groupes [35] qui
permet de minimiser le nombre de machines a ectees a des familles differentes. Le principe de la methode est, dans un premier temps, d'ecrire
la matrice d'incidence jobs-machines. Dans cette matrice en 0{1, l'element a vaut 1 si J utilise M et 0 sinon. Ensuite, et par des permutations de lignes et de colonnes, il faut rendre la matrice au maximum
bloc-diagonnale, et minimiser la somme des elements hors blocs. Ce
probleme est NP-complet mais de nombreuses heuristiques ont deja ete
developpees.
i;j
i
j
Si la decomposition est parfaite (aucunes machines communes entre
les di erentes familles), la resolution independante des sous-problemes
permet d'obtenir une solution generale du probleme. Dans ce cas, chaque famille peut ^etre traitee comme
un probleme a part entiere et une
L
des techniques d'agregation J +1 P peut ^etre utilisee.
l
l
Quand la decomposition n'est pas parfaite et que des machines servent a executer des operations de di erentes familles, la resolution des
sous-problemes ne sut plus pour donner une solution generale. Une
phase d'agregation des blocs est alors necessaire. Cette procedure peut
^etre basee soit sur une technique de decoupage du temps, soit sur l'utilisation d'une fonction co^ut (cf 2.3.3).
L'un des avantages de cette methode de decomposition est le fait
que l'on regroupe les jobs utilisant les m^emes machines. Ceci permet de
traiter un sous-probleme de taille moins importante. De plus, une bonne
optimisation de chacun des sous-problemes doit permettre d'obtenir une
bonne solution globale, d'autant plus que la decomposition est parfaite.
Deux dicultes majeures peuvent se produire. La premiere est que
la decomposition n'est pas bonne (trop de liens entre les di erents groupes). Ceci se produit, par exemple, quand le probleme traite est tel
que chaque job doit passer sur toutes les machines. Dans ce cas, la
procedure d'agregation des ordonnancements partiels devra resoudre
les con its que la decomposition n'aura pas traites. Le deuxieme probleme pouvant survenir est que la decomposition, pour ^etre acceptable,
genere des groupes de jobs de taille importante. Deux solutions sont
72
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
alors envisageables, soit traiter le groupe de jobs au complet par une
des methodes d'agregation precedente, soit le rediviser en utilisant une
technique comme celle presentee dans les sections suivantes.
2.3.2.2 Un regroupement de jobs dissemblables
Cette methode, a l'inverse de la precedente, constitue des groupes
de jobs n'utilisant pas ou peu les m^emes machines. L'avantage de cette
methode est de pouvoir realiser des groupes importants de jobs faciles
a traiter, car chaque groupe ne genere pas beaucoup de con its. Si nous
reprenons la matrice d'incidence jobs-machines, le but est maintenant
d'extraire un ensemble de sous-matrices. Pour chacune d'elles, il faut
minimiser le nombre maximum de 1 par ligne, ce qui correspond a
minimiser le nombre d'operations sur chaque machine pour une famille
de jobs.
La diculte est en fait repoussee au niveau de l'agregation des ordonnancements partiels. Dans ce cas, agreger les ordonnancements partiels les uns apres les autres permet de resoudre les con its au fur et
a mesure sans trop augmenter la complexite du probleme. L'utilisation
de la procedure d'optimisation locale permet egalement d'ameliorer les
solutions intermediaires.
2.3.2.3 Un regroupement de jobs decales
Cette methode de selection constitue des groupes de jobs dont la
particularite est d'utiliser les m^emes machines mais pas au m^eme moment dans la gamme operatoire de leur job. En e et, la methode de decomposition regroupait des jobs utilisant le m^eme ensemble de machines
sans distinction de la place dans la gamme operatoire. Ici, le principe
est de regrouper des jobs dont les operations sur une machine donnee
ne sont pas situes au m^eme rang dans la gamme operatoire. Cette approche permet d'arbitrer directement les disjonctions evidentes, dans
ces sous-problemes. Ainsi, l'operation O 1 sera placee avant l'operation
O sur la machine M . Ces arbitrages etant realises dans chaque famille de jobs, il ne seront pas remis en cause lors des agregations des
ordonnancements partiels.
a;
b;nb
k
2.3. LES ALGORITHMES DE TYPE PL L PR
73
L'avantage de cette methode reside dans le fait que la procedure de
selection des jobs est moins dicile a mettre en uvre qu'une procedure de decomposition par technologie de groupe. Par contre, la phase
d'agregation des blocs est plus technique et necessite une procedure ne
d'optimisation et surtout l'emploi d'une methode d'amelioration locale,
voire d'une methode tabou (cf 2.4).
2.3.3 Les procedures d'agregation
Les methodes que
nous proposons maintenant sont basees sur l'agreL
gation de type Ph Pl et directement issues des methodes decrites dans
les sections 2.2.4.1, 2.2.4.2 et 2.2.5. Elles utilisent soit un decoupage du
temps, soit une fonction co^ut.
Dans ce type de methodes, le choix des familles de jobs est tres
important et determine egalement le choix de la procedure d'agregation
qu'il faut mettre en uvre pour une bonne optimisation.
Pour ce qui est du decoupage du temps, nous proposons la m^eme
approche que pour l'agregation Jl+1 L Pl . La marge relative MR est
calculee comme la valeur absolue de la di erence entre les Cmax des
deux ordonnancements partiels Pl et Pr (Cmax(Pl) et Cmax(Pr )).
MR = jCmax(Pl ) , Cmax(Pr )j
(2.10)
On prendra donc comme principe d'agreger le plus petit ordonnancement partiel au plus long. Les intervalles sont alors determines de la
m^eme facon que precedemment et les insertions d'operations egalement.
La premiere etape consiste a repartir la marge relative sur le chemin
critique. Cela xe des intervalles pour le debut et la n de chaque operation. Dans une deuxieme etape, on tient compte des precedences dans
Pr pour determiner les intervalles des operations hors chemin critique.
L'agregation realisee, il est important de mettre en uvre une procedure d'amelioration locale pour optimiser la solution courante.
La methode d'agregation bloc par bloc peut egalement ^etre traitee
par l'utilisation d'une fonction co^ut. Pour celle-ci, nous reprenons exac-
74
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
tement la m^eme fonction que nous avons proposee dans la section 2.2.5.
Dans ce cas, le co^ut total de l'agregation de l'ordonnancement partiel
sera la somme des co^uts de chacune des operations de cet ordonnancement partiel.
Le choix de la procedure d'agregation est fortement lie a la procedure de groupement des jobs. Une procedure de decomposition regroupera les con its a l'interieur de chaque famille et les con its interfamilles seront peu nombreux. Dans ce cas, l'utilisation d'une procedure
de type decoupage du temps et agregation global, ou avec une fonction
co^ut simple sera susante. Par contre, pour un groupement de jobs dissemblables, peu de con its seront arbitres dans chaque sous-probleme
et la procedure d'agregation devra ^etre plus sophistiquee.
2.4 L'amelioration locale
Apres les phases d'agregation, la solution obtenue peut ^etre amelioree rapidement par une procedure d'amelioration locale. Dans ce but,
nous proposons une methode d'optimisation locale basee sur des permutations d'operations. En fonction du nombre de con its arbitres par
la procedure d'agregation, il est possible d'utiliser une procedure directe (uniquement des permutations qui ameliorent le Cmax), soit une
procedure de type tabou.
Il est egalement possible d'utiliser un principe de reagregation. Celui-ci consiste a retirer de l'ordonnancement un ou plusieurs jobs critiques, et de les reintroduire a nouveau en les agregeant.
2.4.1 Amelioration par permutations
Cette procedure de reoptimisation est classique dans le domaine de
l'ordonnancement. Elle consiste a choisir deux operations successives
sur une machine et tenter de les permuter pour diminuer la duree totale
de l'ordonnancement. Bien entendu, ces operations doivent ^etre sur le
chemin critique sans quoi la permutation n'ameliorerait pas la solution.
Cette methode est tres utilisee dans les heuristiques de type tabou ou
2.4. L'AME LIORATION LOCALE
75
1. CHOIX DE DEUX OPERATIONS
Choix de deux operations successives du graphe critique utilisant
la m^eme machine.
2. PERMUTATION DES OPERATIONS
(a) Permutation des deux operations selectionnees.
(b) Calcul de la duree totale de l'ordonnancement, Cmax, apres
permutation.
(c) Si le nouveau Cmax est inferieur a l'ancien, valider la permutation, sinon l'annuler.
^
3. CONDITION D'ARRET
(a) Si aucune permutation de deux operations successives du
graphe critique n'ameliore le Cmax, arr^eter.
(b) Sinon, retourner en 1.
Fig.
2.19 - Algorithme d'amelioration locale par permutations
recuit simule [33] [79] [105].
Nous presentons, dans l'algorithme de la gure 2.19, la phase de
permutation des operations. Cette methode permet de faire converger
la solution de l'ordonnancement vers un minimum local. Quelques amenagements de cet algorithme nous permettent de mettre en uvre une
methode tabou. Celle-ci demande un temps de calcul plus important,
qui ne se justi e pas quand on cherche des solutions intermediaires, surtout au debut de la phase de construction, ou la qualite de la solution
n'est pas primordiale. Par contre, lors des dernieres agregations, il peut
^etre interessant d'utiliser une methode tabou.
76
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
2.4.2 La reagregation
L'algorithme de reoptimisation suivant ( gure 2.20) par du principe
que dans l'ordonnancement cree, certains jobs sont critiques et determinent ainsi la duree totale Cmax. Le but de la procedure est donc
de supprimer de l'ordonnancement calcule, le ou les jobs dont les operations sont sur le graphe critique. La deuxieme phase consiste a les
reintroduire dans l'ordonnancement en utilisant une technique d'agregation.
Le choix du job critique peut ^etre realise de plusieurs facons. Tout
d'abord en considerant que le job qui determine la duree totale est celui
dont la derniere operation nit au plus t^ot a la date Cmax. Le deuxieme
critere de selection que l'on peut envisager concerne le nombre d'operations sur le graphe critique. Dans ce cas, on retirera de l'ordonnancement le job qui possede le plus d'operations critiques. Une troisieme
possibilite pour choisir le job a ^oter est de calculer la somme des temps
operatoires des operations critiques pour chaque job, et de selectionner
le job dont le temps maximum est critique.
Il est possible, apres l'enlevement du job critique, de reoptimiser
l'ordonnancement en utilisant la procedure de permutation decrite precedemment. Ceci permet de plus de modi er quelque peu la forme de
l'ordonnancement et eviter que la procedure d'agregation ne redonne
la m^eme solution.
2.5 Resultats numeriques
Les di erents algorithmes presentes dans ce chapitre sont maintenant testes sur des jeux de donnees issus de la litterature, ainsi que
sur des instances generees pour l'experimentation. Ceux-ci sont compares avec des algorithmes constructifs bases sur des regles de priorite.
Apres une rapide presentation des jeux de donnees crees, les resultats
numeriques seront commentes.
2.5. RE SULTATS NUME RIQUES
77
1. CHOIX D'UN JOB CRITIQUE
Choix d'un job dont une ou plusieurs operations sont sur le graphe
critique.
2. REAGR
EGATION
DU JOB
(a)
(b)
(c)
(d)
Enlevement du job selectionne.
Calcul du nouvel ordonnancement, apres enlevement du job.
Reagregation du job.
Si le nouveau Cmax est inferieur a l'ancien, valider la reagregation, sinon l'annuler.
^
3. CONDITION D'ARRET
(a) Si aucune reagregation n'ameliore le Cmax, arr^eter.
(b) Sinon, retourner en 1.
Fig.
2.20 - Algorithme d'amelioration par reagregations
78
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
2.5.1 Presentation des jeux de donnees
Les methodes developpees ont pour but de trouver, dans un temps
le plus court possible, une solution admissible au probleme. L'objectif de celles-ci est de traiter des instances de taille importante, jusqu'a
100 jobs. Pour cela, ont ete generees les instances repertoriees dans la
gure 2.21. Les jeux de donnees sont repartis en 3 ateliers possedant
respectivement 7 machines, 10 machines et 15 machines. Pour chacun
de ces ateliers, deux types de jobs sont envisages, les jobs ayant un faible
nombre d'operations dans leur gamme operatoire (4 pour l'atelier 1 par
exemple) et les jobs passant sur toutes les machines exactement une
fois. Pour les jobs ne passant pas par toutes les machines, le choix de
la machine pour une operation donnee est tire selon une loi uniforme
sur l'ensemble des machines. Pour les jobs passant sur toutes les machines, la machine utilisee par la premiere operation est tiree selon la loi
uniforme sur l'ensemble. Pour l'operation j , la machine est tiree selon
la loi uniforme sur l'ensemble des machines non encore utilisees par le
job. Tous les temps operatoires sont tires selon la loi uniforme entre
5 et 55. Pour chacun des types proposes, 25 instances sont generees
et les resultats presentes sont des moyennes sur ces 25 instances. Des
instances issues de la litterature ont egalement ete traitees. Parmi elles,
5 viennent de J. Adams et al. [2], et 3 viennent de M.L. Fischer et
G.L. Thompson [82].
2.5.2 Resultats et conclusions
Les regles de priorite choisies pour l'experimentation sont classiques
dans le domaine de l'ordonnancement [84] [108] [112]. Dans la le d'attente de chaque machine, sont placees les operations disponibles a la
date de liberation de la machine, mais aussi les operations pouvant arriver des la n d'execution de leur predecesseur de gamme. Ceci permet
d'anticiper l'arrivee des operations et de pouvoir choisir l'operation a
executer avec des connaissances supplementaires. Les regles utilisees
sont les suivantes :
{ RP1 : Pour les operations pouvant commencer au plus t^ot, choisir
l'operation ayant le plus petit temps operatoire (Shortest Processing Time, SPT).
2.5. RE SULTATS NUME RIQUES
!
Types d'instances
! Atelier 1 (7 machines)
! 4 operations par jobs
! 25, 50 ou 100 jobs
! 7 operations par jobs
! 25, 50 ou 100 jobs
! Atelier 2 (10 machines)
! 7 operations par jobs
! 25, 50 ou 100 jobs
! 10 operations par jobs
! 25, 50 ou 100 jobs
! Atelier 3 (15 machines)
! 11 operations par jobs
! 25, 50 ou 100 jobs
! 15 operations par jobs
! 25, 50 ou 100 jobs
Fig.
2.21 - Les types d'instances g
enerees
79
80
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
{ RP2 : Pour l'ensemble des operations de la le d'attente, choisir
l'operation ayant le plus petit temps operatoire (SPT modi e).
{ RP3 : Pour les operations pouvant commencer au plus t^ot, choisir l'operation appartenant au job ayant le plus grand nombre
d'operations a venir (Most Operations Remaining, MOPNR).
{ RP4 : Pour l'ensemble des operations de la le d'attente, choisir l'operation appartenant au job ayant le plus grand nombre
d'operations a venir (MOPNR modi e).
{ RP5 : Pour les operations pouvant commencer au plus t^ot, choisir
l'operation appartenant au job ayant le plus grand temps operatoire a venir (Most Work Remaining, MWKR).
{ RP6 : Pour l'ensemble des operations de la le d'attente, choisir
l'operation appartenant au job ayant le plus grand temps operatoire a venir (MWKR modi e).
Pour l'etude des resultats, nous ne conserverons pas l'ensemble des
regles de priorite. Pour chaque serie de problemes (25 instances dont on
calcule la moyenne), nous garderons la meilleure regle, la plus mauvaise
et la moyenne de toutes les regles. Le but n'etant pas de comparer ces
regles, nous ne preciserons pas laquelle est la meilleure et laquelle est
la plus mauvaise.
La borne inferieure presentee dans les tableaux de resultats est le
maximum sur toutes les machines de la somme des temps operatoires
des operations devant ^etre executees sur la machine.
Nous presentons maintenant 6 methodes permettant de tester a la
fois les procedures d'agregation et les procedures d'amelioration locale.
En ce qui concerne les procedures d'agregation nous testons les agregations globales, iteratives et par fonction co^ut. Pour ce qui est des
procedures d'amelioration, nous testons la permutation,
et la reagreL
gation. Les algorithmes bases sur le principe P P sont en cours
de developpement et ne gurent pas dans les resultats. L'algorithme
l
r
2.5. RE SULTATS NUME RIQUES
81
d'agregation base sur la procedure de P. Brucker a ete teste separement
et sans utilisation de methodes d'amelioration locale. Les resultats de
cette procedure sont presentes dans [86]. L'integration des methodes
d'amelioration locale sont en cours.
La methodes utilisees sont :
{ OPT1 :
1. Amelioration par permutations
2. Agregation globale
{ OPT2 :
1. Amelioration par permutations
2. Agregation iterative
{ OPT3 :
1. Amelioration par permutations
2. Agregation par fonction co^ut
{ OPT4 :
1. Amelioration par permutations et reagregations
2. Agregation globale
{ OPT5 :
1. Amelioration par permutations et reagregations
2. Agregation iterative
{ OPT6 :
1. Amelioration par permutations et reagregations
2. Agregation par fonction co^ut
82
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
Pour ne pas multiplier les tests numeriques, nous avons fait une
etude prealable sur la repartition de la marge relative dans les procedures d'agregation ainsi que sur le choix de l'emplacement pour inserer
l'operation. A l'issue de ces tests nous avons choisi de ne presenter que
l'agregation globale avec une repartition lineaire de la marge relative,
et l'agregation iterative avec une repartition geometrique de la marge
relative. Apres avoir teste plusieurs criteres de choix de l'emplacement
d'insertion, ou ta representera la taille de l'emplacement considere et
p le temps operatoire de l'operation a inserer, nous avons retenu le
critere :
i;j
Cr = ta , 2 p
i;j
(2.11)
En ce qui concerne la fonction co^ut, nous avons retenu egalement
le critere precedent, et la fonction consiste donc a minimiser la somme
pour toutes les operations du job, de ce critere.
Les resultats obtenus sont donnes dans les tableaux des gures 2.22,
2.23 et 2.24 . Dans ces tableaux, la premiere colonne indique le nombre
de jobs a ordonnancer et la deuxieme, le nombre d'operations dans
la gamme operatoire de chaque job. Suivent ensuite les resultats des
6 methodes d'optimisation que nous proposons. Pour nir, les quatre
dernieres colonnes donnent les resultats des algorithmes bases sur les
regles de priorite et le pourcentage d'amelioration entre la meilleure
methode OPT et la meilleure regle de priorite.
Pour chacun des trois ateliers, les resultats obtenus montrent que les
methodes OPT sont tres legerement meilleures que les regles de priorite.
En moyenne, l'e ort d'optimisation superieur des methodes agregatives
permet une amelioration des durees totales de l'ordonnancement de 1 a
3% selon les ateliers. Toutefois, les methodes agregatives ne garantissent
pas une amelioration sensible par rapport aux regles de priorite.
En regle generale, les methodes utilisant la reagregation (OPT4,
OPT5, OPT6) sont plus performantes que celles utilisant uniquement
les permutations (OPT1, OPT2, OPT3). Dans chacun de ces deux
groupes, l'agregation par fonction co^ut donne de meilleurs resultats
2.5. RE SULTATS NUME RIQUES
n
n
BI
25 25 50 50 100
4
7
4
7
4
514 886 825 1482 1637
OPT1
520 876 926 1675 1939
OPT2
498 869 914 1648 1924
OPT3
481 884 935 1662 1926
OPT4
485 861 921 1642 1918
OPT5
472 867 902 1637 1905
OPT6
468 847 908 1623 1921
OPT , BI 15,0 14,0 9,3 9,5 16,4
BI
Min
479 871 912 1669 1937
Max
587 915 1021 1743 2084
Moy
522 898 986 1706 2015
Min , OPT 2,3 2,8 0,4 2,8 1,7
OPT
Fig. 2.22 - Job-shop, atelier 1
i
83
100
7
2896
3197
3172
3212
3196
3204
3149
8,7
3194
3324
3275
1,4
que l'agregation iterative et cette derniere donne de meilleurs resultats
que l'agregation globale.
Les methodes agregatives sont bien s^ur moins rapides que les regles
de priorite, mais les temps de calcul ne sont pas tres important. Sur
une station de travail SPARC 10, l'instance de taille la plus importante
ne necessite que 5 minutes.
Sur les exemples issus de la litterature, nous pouvons faire les m^emes
remarques que pour les trois ateliers precedents. Les resultats sont presentes dans la gure 2.25. On constate que les valeurs de la duree totale
de l'ordonnancement sont assez eloignees de la valeur optimale. Ceci
s'explique par le fait que les methodes developpees ont pour but une
optimisation rapide. Le temps de calcul pour chacun des problemes de
la gure 2.25 est de l'ordre de la seconde. Dans la ligne BI , les valeurs
optimales sont mentionnees par une etoile.
84
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
n
n
BI
25 25 50 50 100
7 10
7
10
7
538 758 1089 1457 2029
OPT1
658 903 1283 1767 2431
OPT2
645 880 1289 1752 2456
OPT3
618 889 1257 1692 2426
OPT4
623 845 1275 1712 2405
OPT5
621 873 1268 1705 2342
OPT6
604 852 1235 1680 2383
OPT , BI 12,3 11,5 13,4 15,3 15,4
BI
Min
624 892 1254 1723 2401
Max
752 993 1321 1867 2657
Moy
702 943 1291 1813 2512
Min , OPT 3,1 5,6 1,5 2,6 2,5
OPT
Fig. 2.23 - Job-shop, atelier 2
i
2.6
100
10
2891
3297
3305
3269
3237
3259
3182
10,1
3208
3473
3367
0,8
Conclusion
L'approche proposee dans ce chapitre est une alternative aux regles
de priorite. Son souci principal est de developper de nouvelles methodes
d'optimisation rapides pour traiter des problemes de tailles importantes. A partir de celles-ci, des propositions de methodes d'optimisation ont ete faites. Bien entendu, les possibilites o ertes par cette
approche n'ont pas toutes ete investiguees.
Les resultats obtenus lors de l'experimentation des quelques methodes presentees plus haut, font appara^tre un reel inter^et a l'utilisation de cette approche. M^eme si pour certaines d'entre elles les resultats
sont moins bons que ceux donnes par les regles de priorite, les plus performantes sont interessantes.
L'un des atouts remarquables de cette approche est sa exibilite. En
e et, le choix des procedures d'agregations et des procedures d'amelio-
2.6.
85
CONCLUSION
n
n
BI
25 25 50 50 100
11 15 11 15 11
561 723 1022 1674 2082
OPT1
706 902 1243 1687 2329
OPT2
672 918 1247 1621 2341
OPT3
681 871 1224 1648 2305
OPT4
669 839 1198 1625 2278
OPT5
643 854 1231 1582 2314
OPT6
658 827 1185 1577 2281
OPT , BI 14,6 14,4 16,0 9,9 9,4
BI
Min
666 836 1203 1625 2312
Max
754 987 1326 1721 2423
Moy
703 898 1241 1654 2397
Min , OPT 3,6 1,1 1,5 3,0 1,5
OPT
Fig. 2.24 - Job-shop, atelier 3
i
100
15
2867
3254
3247
3197
3145
3205
3120
8,8
3152
3368
3274
1,0
ration locale permet de contr^oler l'e ort d'optimisation. En fonction de
la taille de l'instance traitee, il est donc possible de selectionner telles
ou telles procedures d'agregation et d'amelioration de facon a limiter
le temps de calcul.
L'agregation des jobs par fonction co^ut est certainement la methode
la plus performante des trois testees. Il parait clair que ce type d'agregation merite d'^etre developpe. Il a l'avantage a chaque agregation d'un
job de tenir compte de l'ensemble des emplacements disponibles pour
l'insertion des operations. Le choix d'une bonne fonction, necessitant
peu de calcul, est sans doute la voie la plus interessante a explorer pour
traiter rapidement le probleme de job-shop statique et deterministe.
CHAPITRE 2. UNE APPROCHE PAR AGRE GATION
86
n
ni
BI
OPT1
OPT2
OPT3
OPT4
OPT5
OPT6
OPT B I
,
BI
M in
M ax
M oy
M in
, OPT
OPT
10
10
1234*
1504
1512
1467
1425
1367
1324
10
10
943*
1253
1220
1135
1142
1073
1121
20
15
654
854
865
882
823
831
812
20
15
635
921
903
854
798
825
812
20
15
656
987
1003
957
963
925
908
6
6
55*
68
72
64
63
67
59
10
10
930*
1322
1302
1254
1167
1135
1091
20
5
1165*
1642
1701
1682
1584
1497
1435
7,3
13,8
24,1
25,7
38,4
7,2
17,3
23,2
1348
1606
1464
1089
1249
1135
807
890
831
839
957
887
885
948
909
65
89
71
1160
1396
1279
1429
1739
1599
1,8
1,5
,0 6
4,4
,2 5
10,2
6,3
,0 4
Fig.
2.25 -
;
;
Job-shop, problemes classiques
;
87
Chapitre 3
Le job-shop generalise
Nous presentons dans ce chapitre une extension du probleme traite
jusqu'a present, appele job-shop generalise. La di erence entre les deux
problemes reside dans l'a ectation des operations sur les machines. Si
dans le job-shop statique et deterministe, une operation est a ectee des
le depart a une machine specialisee, dans le job-shop generalise une operation peut ^etre executee par plusieurs des machines mais a ectee a une
seule. Ainsi, pour chaque operation, il existe un ensemble de machines
utilisables. Ce type d'atelier de production est plus complexe que le
precedent, mais sera vu uniquement sur un plan statique. Les donnees
sont connues au depart de l'optimisation et seule la construction de
l'ordonnancement sera abordee.
Les methodes de resolution proposees dans ce chapitre sont basees
sur le principe d'agregation et poursuivent les m^emes objectifs que celles
proposees dans le chapitre precedent. Ainsi, elles sont concues pour
contr^oler l'e ort d'optimisation en privilegiant plus ou moins le temps
de calcul par rapport a la qualite de la solution.
Ce probleme comprenant a la fois le probleme d'a ectation des operations aux machines et le probleme de l'ordonnancement de celles-ci,
des methodes separant ou liant ces deux optimisations seront proposees.
Dans une premiere section, nous de nirons le probleme du job-shop generalise, a partir de la de nition du job-shop vue dans le chapitre 1.
Puis, nous ferons un tour d'horizon des methodes connues pour le reso-
CHAPITRE 3. LE JOB-SHOP GE NE RALISE
88
lution de ce probleme. Les modelisations du probleme feront l'objet de
la deuxieme partie. Nous presenterons la modelisation de H.M. Wagner
et proposerons une nouvelle formulation du job-shop generalise sous
forme de programmation lineaire en nombres entiers. La troisieme section sera consacree a di erentes propositions de methodes de resolution
basees sur le principe d'agregation. Nous detaillerons trois types de methodes approchees : les heuristiques constructives une-phase, les heuristiques constructives deux-phases et les heuristiques amelioratrices.
Nous nirons ce chapitre par des resultats numeriques. Les jeux de
donnees utilises seront expliques et des conclusions sur les tests seront
donnees.
3.1 Une presentation du probleme
3.1.1 Description du probleme
Le probleme du job-shop generalise contient, du fait de sa structure,
deux problemes classiques de l'optimisation combinatoire : le probleme
de l'a ectation lineaire et le probleme de l'ordonnancement. Les donnees et les contraintes de ce probleme sont les suivantes :
1. Un ensemble M de m machines. Une machine est notee M avec
k = 1; :::; m.
k
2. Un ensemble J de n jobs. Chaque job est compose d'une gamme
operatoire i.e. une sequence lineaire de n operations xee. Cette
sequence ne depend que du job et peut varier d'un job a l'autre.
Un job est note J avec i = 1; :::; n.
i
i
3. Une operation O represente la jeme operation du job J . Cette
operation necessite un temps operatoire p qui ne sera xe que
lors de l'a ectation de l'operation sur une machine. La date de
debut calculee de l'operation O sera toujours notee t .
i;j
i
i;j
i;j
i;j
4. L'operation O necessite,
n pour ^etre realis
oee, une des machines
de l'ensemble R(O ) = M 1 ; M 2 ; :::; M . Le temps operatoire
sur la machine M pour l'operation O sera note p .
i;j
i;j
k
k
kq
k
i;j
i;j;k
3.1. UNE PRE SENTATION DU PROBLE ME
89
n 1 2 : : : ni
1 pi;1;1 pi;2;1 : : : pi;n ;1
2 pi;1;2 pi;2;2 : : : pi;n ;2
...
...
... . . . ...
m pi;1;m pi;2;m : : : pi;n ;m
Fig. 3.1 - Matrice des temps op
eratoires pour le job Ji
k j
i
i
i
La di erence entre le job-shop classique et le job-shop generalise
reside dans le fait qu'une operation peut ^etre executee sur plusieurs
machines avec des temps operatoires di erents. Pour un job Ji, on obtient donc la matrice des temps operatoires dont les colonnes sont les
operations composant le job et les lignes les machines disponibles pour
ces operations ( gure 3.1). Le fait, pour une certaine operation Oi;j , que
pi;j;k = +1 signi e que la machine Mk ne peut pas executer l'operation
Oi;j .
Les donnees sont soumises aux contraintes suivantes :
1. Les machines sont independantes les unes des autres.
2. Une machine ne peut executer qu'une seule operation a un instant
donne.
3. Chaque machine est disponible pendant toute la periode de l'ordonnancement. En particulier, les pannes de machines ne sont pas
prises en compte.
4. Une operation en cours d'execution ne peut ^etre interrompue (il
n'y a pas de preemption).
5. Les jobs sont independants les uns des autres. En particulier, il
n'existe aucun ordre de priorite attache aux jobs.
Le probleme ne consiste plus uniquement a trouver une sequence
des operations sur chaque machine mais egalement a determiner une
a ectation de chaque operation sur une machine. Le but de l'ordonnancement est de trouver le temps de production minimum pour l'ensemble
des jobs (Cmax).
90
CHAPITRE 3. LE JOB-SHOP GE NE RALISE
3.1.2 Les methodes de resolution connues
Ce probleme a tres peu ete traite et les articles qui lui font reference
sont rares. En fait, les methodes les plus utilisees pour le resoudre sont
les regles de priorite. L'algorithme est le m^eme que celui presente dans
le premier chapitre. La regle de priorite resout en m^eme temps le probleme d'a ectation et le probleme d'ordonnancement. C'est ce que nous
appellerons par la suite une methode une-phase.
Une autre approche consiste a separer la phase d'a ectation et la
phase de resolution de l'ordonnancement. C'est ce nous appellerons
une methode deux-phases. A. Fadil et al. [40] proposent une methode
en trois etapes, a ectation, decomposition et resolution. Celle-ci e ectue, dans un premier temps, l'a ectation des operations aux machines.
Ensuite, elle met en uvre une methode de decomposition par technologie de groupes [35] pour minimiser le nombre d'operations liees a
plusieurs groupes de machines. Si ce nombre est trop important, l'affectation est remise en cause pour ameliorer la decomposition. Quand
la decomposition est susante, chaque sous-probleme est resolu par un
algorithme exact (J. Carlier et E. Pinson [28]). Si des liens persistent
entre les groupes de machines malgre la rea ectation, une methode de
synchronisation est mise en uvre.
Pour le probleme du job-shop generalise, un cas particulier est polyn^omial. Il s'agit du probleme de job-shop a deux jobs avec plusieurs
choix de machines pour chaque operation. P. Brucker et R. Schlie [24]
ont propose un algorithme base sur la resolution graphique du job-shop
a deux jobs. Ceci constitue une generalisation de la methode de resolution du probleme a deux jobs presentee dans la section 2.1.2.
3.2 Les modelisations du probleme
Cette section est consacree a la modelisation du probleme de jobshop generalise. Actuellement, seule la modelisation en programmation
mathematique existe. Si pour le job-shop statique et deterministe, le
modele sous forme de graphe disjonctif est le plus repandu, il n'existe
3.2. LES MODE LISATIONS DU PROBLE ME
91
pas de modele faisant intervenir les graphes pour le job-shop generalise.
Dans un premier temps, une modelisation en programmation lineaire en nombres entiers proposee par H.M. Wagner [110] sera exposee.
Ensuite, nous proposons une nouvelle formulation faisant appara^tre a
la fois des variables d'a ectation et des variables de precedences.
3.2.1 La modelisation de H.M. Wagner
La premiere modelisation sous forme de programme lineaire en nombres entiers est due a H.M. Wagner. Le cas particulier du job-shop
statique et deterministe a ete traite dans la section 1.2.2.3 et represente
une restriction du modele general que nous presentons maintenant. Les
variables utilisees sont les m^emes que pour le cas particulier traite plus
haut.
(
si Oi;j est la leme operation sur Mk
(
l
)
xi;j;k = 01 sinon
(3.1)
t(kl) : est la date de debut de la leme operation sur Mk
s(kl) : est la duree entre la n de la leme operation et le
debut de la (l + 1)eme sur Mk
s0k : est la duree entre 0 et la premiere operation sur Mk
mk : est le nombre maximum d'operations pouvant
^etre executees sur Mk
Tx(kl) : est le temps operatoire de la leme operation sur Mk
(3.2)
(3.3)
(3.4)
(3.5)
(3.6)
Dans ce modele, une operation Oi;j peut ^etre executee par plusieurs
machines Mk1 ; Mk2 ; :::; Mkq . La premiere contrainte signi e que l'operation Oi;j n'est a ectee qu'a une seule machine parmi Mk1 ; Mk2 ; :::; Mkq
et a une seule place.
l=X
mk1
l=1
l)
x(i;j;k
1
+
l=X
mk2
l=1
l)
x(i;j;k
2
+ ::: +
l=X
mkq
l=1
l)
x(i;j;k
=1
q
(3.7)
CHAPITRE 3. LE JOB-SHOP GE NE RALISE
92
(i = 1; :::; n; j = 1; :::; n )
i
La deuxieme contrainte signi e que sur la machine M , en position
l, pas plus d'une operation n'est a ectee.
k
X
(3.8)
l
j 2 (
Oi;j Mk
x( ) 1
R Oi;j
)
i;j;k
(k = 1; :::; m; l = 1; :::; m )
k
La contrainte 3.9 determine le temps operatoire de la leme operation
executees sur M .
k
X
Tx( ) =
l
k
j 2 (
Oi;j Mk
R Oi;j
x( )
p
)
(3.9)
l
i;j;k
i;j;k
pour k = 1; :::; m; l = 1; :::; m
k
Les contraintes de gamme operatoire s'expriment pour deux operations O et O +1 sur les machines M1 et M2 respectivement, de la
facon suivante :
i;j
i;j
t( 11) + p
l
k
i;j;k1
x(
l1
)
i;j;k1
t( ) + BS (2 , x(
l2
l1
k2
)
i;j;k1
, x(
)
+1
l2
i;j
;k2
) (3.10)
(l1 = 1; :::; m 1 ; l2 = 1; :::; m 2 )
k
k
Cette contrainte n'est active que si l'operation O est executee sur
la machine M 1 en l1eme position et O +1 en l2eme position sur M 2 . Si
une de ces deux conditions n'est pas respectee, la contrainte n'est pas
active.
i;j
k
i;j
k
En n, le calcul des dates de debut au plus t^ot des operations sur les
machines se fait par les contraintes suivantes :
t(1) = s0 pour k = 1; :::; m
k
t( ) = s0 +
l
k
(3.11)
k
r
=X
,1 l
k
r
=1
Tx( ) + s( )
r
k
r
k
(3.12)
3.2. LES MODE LISATIONS DU PROBLE ME
93
pour k = 1; :::; m; l = 2; :::; mk
Les dernieres contraintes permettent de calculer le Cmax :
tmk + Txmk Cmax pour k = 1; :::; m
k
(3.13)
k
3.2.2 Une nouvelle modelisation
Nous proposons maintenant une formulation du probleme en programmation lineaire en nombres entiers, mettant en evidence l'a ectation des operations aux machines et le sequencement.
Tout d'abord, la variable xi;j;k represente l'a ectation de la jeme
operation du job Ji sur la machine Mk .
(
Oi;j est a ectee Mk
xi;j;k = 10 sisinon
)
(3.14)
a;b represente l'ordre dans lequel sont e ectuees les
La variable yc;d
operations Oa;b et Oc;d .
a;b =
yc;d
(
1 si Oa;b est e ectuee avant Oc;d
0 sinon
)
(3.15)
Les equations 3.16 forment les contraintes d'a ectation. Elles impliquent qu'une operation est a ectee a une seule machine.
X
M 2R(O )
k
xi;j;k = 1 pour i = 1; :::; n et j = 1; :::; ni
(3.16)
i;j
Les equations 3.17 et 3.18 representent les contraintes de gammes
operatoires et de n d'ordonnancement.
ti;j+1 ti;j +
X
M 2R(O )
k
i;j
xi;j;k pi;j;k
(3.17)
CHAPITRE 3. LE JOB-SHOP GE NE RALISE
94
pour = 1
i
max
C
i,1
et = 1
; :::; n
X
j
i;n
t
i
+
; :::; n
i;ni )
k
i;n ;k pi;n ;k
x
M 2R(O
i
i
pour = 1
i
; :::; n
(3.18)
En n, les dernieres equations permettent d'arbitrer les disjonctions
entre des operations utilisant les m^emes machines. Si pour les operations a;b et c;d l'intersection de ( a;b ) et ( c;d ) n'est pas vide, les
contraintes s'ecrivent pour une machine k commune :
O
O
R O
R O
M
y
a;b
c;d
c;d + ya;b
c;d
t
=1
(3.19)
a;b
c;d
a;b + yc;d pa;b;k , B S ya;b
t
,
BS
,
BS
X
R O et M
X
M2
r
(
M 2R(O
r
a;b
t
a;b )
c;d )
6 M
r=
et M 6
a;b;r
x
k
c;d;r
x
M
r=
(3.20)
k
c;d
a;b
c;d + ya;b pc;d;k , B S yc;d
t
,
BS
,
BS
X
R O et M
X
M2
r
(
M 2R(O
r
a;b )
c;d )
x
6 M
r=
et M 6
r=
(3.21)
a;b;r
k
M
x
c;d;r
k
Ces deux dernieres contraintes ne peuvent pas ^etre actives en m^eme
temps, et dans la plupart des cas, aucune des deux ne l'est. Pour une
machine k donnee et appartenant a ( a;b ) et ( c;d ), les contraintes
ne sont pas actives si l'une ou les deux operations ne sont pas a ectees
a k . Dans le cas ou les deux operations sont a ectees a k , soit
a;b
c;d
c;d vaut 1 et la contrainte 3.21 est active, soit a;b vaut 1 et alors, la
contrainte 3.22 est active.
M
R O
R O
M
y
M
y
3.3. DES METHODES
DE RESOLUTION
95
3.3 Des methodes de resolution
Les methodes de resolution proposees dans cette section utilisent le
principe d'agregation. Trois approches di erentes seront developpees.
La premiere comprend les methodes constructives une-phase, qui b^atissent l'ordonnancement en m^eme temps qu'elles donnent une a ectation pour les operations. La deuxieme approche permet de developper
des methodes constructives deux-phases. Ces methodes separent l'affectation des operations aux machines et l'ordonnancement proprement
dit [4] [5]. En n, nous proposons des heuristiques amelioratrices pour
ameliorer les solutions donnees par les methodes constructives precedentes. Ces methodes sont basees sur la rea ectation des operations
aux machines, sur la permutation des operations du chemin critique et
en n sur la reagregation des jobs.
3.3.1
Heuristiques constructives une-phase
Le principe des methodes constructives une-phase est de construire,
a partir des donnees initiales, un ordonnancement realisable. De plus,
la construction se passe en une seule etape ou sont m^eles l'a ectation
des operations aux machines et l'ordonnancement.
Ce principe est utilise dans les methodes de resolution basees sur des
regles de priorite. Dans ces algorithmes, toutes les operations pouvant
^etre executees sur une machine sont placees dans la le d'attente de
celle-ci. Une operation peut donc gurer dans plusieurs les d'attente
et, au moment ou elle est choisie pour ^etre executee sur une machine,
elle doit ^etre ^otee des autres les. Ainsi, le choix de l'operation dans la
le resout en m^eme temps le probleme d'a ectation et le probleme de
l'ordonnancement.
Nous proposons maintenant une generalisation des methodes d'agregation presentees dans la section 2.3. Les algorithmes permettant de
traiter le probleme du job-shop generalise sont les m^emes que ceux des
gures 2.6, 2.8 et 2.16. La di erence reside dans le fait que la liste des
emplacements disponibles ne sont plus sur une seule machine mais sur
l'ensemble des machines pouvant executer l'operation a inserer. Cela
96
CHAPITRE 3. LE JOB-SHOP GE NE RALISE
donne une marge de manuvre plus grande pour l'insertion de l'operation mais multiplie le nombre de possibilites a explorer.
Pour ce qui est des heuristiques par decoupage du temps, le calcul de
la marge relative ne peut pas ^etre fait comme pour le probleme du jobshop statique et deterministe, dans la mesure ou le temps operatoire
de chaque operation n'est pas xe (l'a ectation n'est pas faite). Ce
calcul est donc realise en tenant compte, soit de la moyenne des temps
operatoires sur les di erentes machines candidates, soit en utilisant le
minimum ou le maximum de ceux-ci. La taille des intervalles etant
plut^ot indicative, ce choix n'est pas d'une grande importance.
Dans le cas de l'heuristique par decoupage du temps et agregation
globale (section 2.2.4.1), la diculte principale est de ne pas trop charger une machine rapide, machine sur laquelle les temps operatoires sont
petits. En e et, il serait tentant de placer l'operation sur la machine
l'executant le plus rapidement, mais de ce fait, plusieurs operations du
m^eme job pourraient se trouver a ectees a la m^eme machine et ainsi
la surcharger. La duree de l'ordonnancement s'en trouverait augmentee de facon importante. L'agregation etant globale et les choix des
emplacements d'insertion independants, il est necessaire de prevoir ce
phenomene. Pour cela, nous proposons de tenir compte de cette surcharge des machines en calculant, pour chaque insertion envisagee, la
di erence entre le temps operatoire de l'operation et la longueur de
l'emplacement choisi. Ainsi, nous interdisons que deux operations du
m^eme job soient executees sur la m^eme machine, si pour ces deux operations la di erence calculee est positive.
Pour l'heuristique par decoupage du temps et agregation iterative,
le probleme precedent ne se pose pas. Les operations etant inserees
les unes apres les autres et les dates de debut au plus t^ot et au plus
tard etant recalculees apres chaque insertion, on peut inserer dans le
meilleur intervalle possible sans risque de surcharger une machine. Le
seul probleme est donc le nombre d'emplacements a considerer. Il en
est de m^eme pour l'insertion relative.
En n, l'heuristique basee sur une fonction co^ut est confrontee aux
3.3. DES METHODES
DE RESOLUTION
97
deux problemes precedents, le nombre d'emplacements et la surcharge
des machines. Dans ce cas, il est necessaire de faire intervenir dans la
fonction ces deux considerations. Pour le probleme de surcharge d'une
machine, le choix de celle-ci sera pondere par rapport a son taux d'utilisation.
3.3.2
Heuristiques constructives deux-phases
Les heuristiques constructives deux-phases ont pour but de separer
la phase d'a ectation et la phase d'ordonnancement. Ce genre de methodes est deja tres utilise pour la resolution du probleme du \vehicle
routing" par exemple [18] , ou les phases d'a ectation et de routage
sont separees.
Quand l'a ectation est realisee, chaque operation est liee a une machine et l'on se ramene a un probleme de job-shop statique et deterministe. Dans ce genre de methode, la phase d'ordonnancement est tres
dependante des choix que l'on fait pour l'a ectation. Quatre processus
d'a ectation sont maintenant discutes ainsi que leurs in uences sur le
choix de la procedure d'ordonnancement.
3.3.2.1 L'a ectation lineaire
L'idee la plus naturelle est bien sur de minimiser le temps total de
fonctionnement de l'atelier de production. Pour cela, il sut de choisir
pour chaque operation O , le minimum des temps operatoires sur les
machines disponibles. On a alors :
p = 2min p
(3.22)
i;j
i;j
Mk
R(Oi;j )
i;j;k
La diculte principale vient du fait que certaines machines plus
rapides que les autres vont se trouver surchargees. Pour eviter ce phenomene indesirable, une solution est de limiter la capacite des machines.
Ainsi, une machine m^eme rapide sera chargee a peu pres autant que les
autres. Le probleme peut se modeliser de la facon suivante. Soit x
la variable d'a( ectation.
O est a ectee a M
x = 10 sisinon
(3.23)
i;j;k
i;j
i;j;k
k
CHAPITRE 3. LE JOB-SHOP GE NE RALISE
98
L'objectif est maintenant de minimiser la charge de la machine la
plus employee, CHmax. On a alors les equations suivantes :
min CHmax
X
M RO
X
k
2
(
xi;j;k = 1
k
(i = 1; :::; n; j = 1; :::; ni)
(3.25)
i;j )
O jM 2R(O
i;j
(3.24)
i;j )
xi;j;k pi;j;k CHmax
(k = 1; :::; m)
(3.26)
Les equations 3.25 representent les contraintes de l'a ectation classique. Elles precisent qu'une operation est a ectee a une machine et
une seule. Les equations 3.26 (une pour chaque machine) totalisent les
temps operatoires des operations qui lui sont a ectees. Ainsi, la minimisation de la charge maximum (CHmax) entra^ne un equilibrage des
charges sur les di erentes machines.
Cette modelisation est semblable a celle proposee par C.N. Potts [89]
pour la resolution de problemes de machines paralleles. Le principe est
de relaxer les contraintes d'integrite des variables xi;j;k , puis de resoudre
le programme lineaire. Pour les variables fractionnaires, une heuristique
permet ensuite de les arrondir pour obtenir une solution en 0{1. Ceci
est vrai egalement dans les modeles des paragraphes suivants.
3.3.2.2 L'a ectation lineaire avec capacites
Nous proposons maintenant une methode d'a ectation lineaire ou
les capacites des machines sont prises en compte. Ces capacites sont
estimees en fonction de la somme des temps operatoires sur chaque
groupe de machines. Ce type d'a ectation s'adapte particulierement
bien aux ateliers dans lesquels les machines appartiennent a des groupes
et tels que chaque operation est a ectee a un groupe.
Pour un groupe de machines donne Gr , une operation peut passer
sur chacune des machines avec des temps operatoires di erents. On peut
alors calculer le temps operatoire moyen pour l'execution de l'operation,
pi;j . On calcule alors la capacite d'une machine comme etant la somme
3.3. DES METHODES
DE RESOLUTION
99
des temps operatoires moyens de toutes les operations liees a ce groupe,
divisee par le nombre de machines du groupe. On obtient ainsi pour
chaque groupe Gr , une charge maximum CHmax(Gr ). On obtient donc
la formulation suivante :
X X X xi;j;k pi;j;k
i j k
X xi;j;k = 1 (i = 1; :::; n; j = 1; :::; ni)
M RO
X xi;j;k pi;j;k CHmax(Gr) (k = 1; :::; m)
min
k
2
i=n j =n k=m
i
=1
(
k
=1
(3.27)
(3.28)
i;j )
O jM 2G
i;j
=1
(3.29)
r
Les contraintes de ce probleme sont les m^emes que pour la formulation precedente mais la fonction objectif exprime directement la
minimisation de la somme des temps operatoires.
3.3.2.3 L'a ectation de separation
Le but de cette a ectation est de repartir l'utilisation des di erentes
machines dans les gammes operatoires des jobs. De ce fait, on evite par
exemple qu'une machine e ectue la premiere operation de tous les jobs.
Ainsi, chaque machine doit realiser un nombre equilibre de premiere
operation, de deuxieme operation, etc.
L'equilibrage est bien sur le souci principal de cette a ectation, mais
il ne doit pas eluder la minimisation de la somme des temps operatoires. C'est pourquoi, le modele suivant tient compte en m^eme temps
de l'equilibrage (critere principal d'a ectation), mais egalement de la
minimisation de la somme des temps operatoires.
Les contraintes 3.26 sont scindees en plusieurs contraintes, une pour
chaque position de l'operation dans la gamme operatoire. Ainsi, il existe
une contrainte pour chaque machine et chaque position dans la gamme
operatoire des jobs. Le probleme s'ecrit :
min CHmax
(3.30)
CHAPITRE 3. LE JOB-SHOP GE NE RALISE
100
i n
X
xi;j;k pi;j;k CHmax
=
i=1
i=n
(j = 1; :::; max
n ; k = 1; :::; m) (3.31)
i=1 i
Ce type d'a ectation est particulierement adapte pour l'utilisation
d'une procedure d'agregation Pl L Pr . Dans ce cas, il est possible de
mettre en place une procedure de groupement par une methode de
decomposition ou de regroupement de jobs decales (cf 2.3.2).
3.3.2.4 L'a ectation de decomposition
Nous proposons, pour nir, une a ectation en deux phases pour
la decomposition du probleme. La premiere consiste a regrouper les
machines en ^lots. La deuxieme phase est chargee de repartir les jobs
a ordonnancer dans ces ^lots. Cette approche a deja ete proposee par
L.M. Aguilera [4]. Le principe est de construire autant de famille de
jobs qu'il y a d'^lots de machines. Ensuite, les jobs sont repartis dans
les di erentes familles en vue d'^etre executes sur les machines de l'^lot.
Dans le souci d'equilibrer les charges entre le ^lots, l'utilisation d'un des
modeles precedents est indispensable.
Il est necessaire que chaque ^lot comporte au moins un exemplaire
des machines pouvant executer les operations des jobs. Ainsi, quelque
soit le job, toutes ses operations pourront ^etre a ectees a une machine
de l'^lot et par la eviter un lien avec un autre ^lot.
Quand cette repartition des machines est faite, les jobs sont a ectes
a un ^lot. Il est ensuite possible de traiter chaque ^lot comme un jobshop statique et deterministe si une machine de chaque type est presente
dans chaque^lot, ou comme un job-shop generalise si plusieurs machines
de chaque type gurent dans les ^lots.
Chaque sous-probleme peut alors ^etre resolu independamment des
autres et la resolution de chacun donne une solution au probleme general.
3.3. DES METHODES
DE RESOLUTION
101
3.3.3 Heuristiques amelioratrices
Les heuristiques amelioratrices que nous proposons maintenant sont
directement issues des methodes exposees dans le chapitre precedent.
Toutefois, l'a ectation des operations aux machines ajoute un degre de
liberte supplementaire et permet de concevoir une approche de reoptimisation par rea ectation.
3.3.3.1 Optimisation par permutations d'operations
La procedure decrite dans la section 2.4 peut ^etre utilisee directement sur les solutions intermediaires ou sur la solution nale. Celle-ci
( gure 2.4) ne joue que sur le placement des di erentes operations dans
les sequences des machines mais pas sur l'a ectation.
L'inter^et principal de cette methode est son utilisation dans une heuristique deux-phases ou l'a ectation et l'ordonnancement sont separes.
Ceci permet de dissocier franchement les deux phases, et ainsi former
deux niveaux de decisions tres independants. Ce genre de fonctionnement est utilise dans des systemes de gestion de production [4] [5].
3.3.3.2 Optimisation par rea ectations
La deuxieme maniere d'ameliorer une solution utilise le principe de
rea ectation. Celui-ci consiste a choisir une operation du graphe critique et de la rea ecter sur une autre machine moins chargee. De la
m^eme facon que pour la procedure decrite precedemment, cette methode peut ^etre integree dans une heuristique de type tabou.
L'algorithme de la gure 3.2 montre le fonctionnement d'une procedure simpli ee. En e et, il est possible, en utilisant le principe de
rea ectation, de modi er la procedure pour qu'elle prenne en compte
la rea ectation de plusieurs operations en m^eme temps. Ceci permet
par exemple l'echange des deux operations d'une machine a l'autre.
Cette methode est interessante car une a ectation qui pourrait sembler naturelle, par exemple a ecter l'operation a la machine la plus ra-
CHAPITRE 3. LE JOB-SHOP GE NE RALISE
102
1. CHOIX D'UNE OPERATION
Choix d'une operation du chemin critique.
2. REAFFECTATION
(a) Rea ectation de l'operation selectionnee sur une autre machine.
(b) Calcul de la duree totale de l'ordonnancement, Cmax, apres
rea ectation.
(c) Si le nouveau Cmax est inferieur a l'ancien, valider la rea ectation, sinon l'annuler.
^
3. CONDITION D'ARRET
(a) Si aucune rea ectation n'ameliore le Cmax, arr^eter.
(b) Sinon, retourner en 1.
Fig.
3.2 - Algorithme d'amelioration par rea ectations
pide, chargerait sans doute de facon importante quelques machines et
en sous-emploierait d'autres.
De la m^eme maniere que pour la procedure precedente qui n'agissait
que sur l'ordre des operations, cette heuristique n'agit que sur l'a ectation des operations aux machines. Elle est donc tres adaptee aux
methodes dissociant les phases d'a ectation et d'ordonnancement.
3.3.3.3 Optimisation par permutations et reaffectations
Cette methode utilise les deux procedures decrites precedemment.
Plusieurs manieres de les combiner permettent d'ameliorer le rendement
de chacune.
3.4. RE SULTATS NUME RIQUES
103
Dans un premier temps, il est possible d'appeler les deux procedures
alternativement. A partir d'une solution realisable donnee, la premiere
procedure appelee est la permutation. Celle-ci fonctionne tant que des
permutations d'operations sont realisees. A l'issue de cette etape, la
procedure de rea ectation est appelee et recherche d'eventuelles rea ectations interessantes. Un aller-retour entre ces deux procedures permet
une reoptimisation plus importante. Cette approche peut ^etre utilisee
dans un contexte ou les deux niveaux de decisions (a ectation et ordonnancement) sont dissocies.
Une deuxieme possibilite est d'appeler alternativement ces deux procedures sans attendre que toutes les possibilites de permutation ou de
rea ectation ne soient epuisees. Ceci permet entre autres d'eviter les
tests signi ant qu'il n'y a plus de permutations (resp. rea ectations)
possibles.
3.3.3.4 Optimisation par reagregation
Le principe de reagregation est le m^eme que celui de la section 2.4.2.
Cette approche resout en m^eme temps les problemes d'a ectation et
d'agregation.
En e et, quand un job est retire de l'ordonnancement, et reintroduit
par une procedure d'agregation, celle-ci gere a la fois le choix de la machine pour les operations a inserer et l'emplacement dans la sequence
de la machine. Ceci permet une reoptimisation plus globale et est donc
interessante a utiliser en n d'optimisation. Ce type d'optimisation ne
tient pas compte d'une eventuelle separation entre les niveaux d'a ectation et d'ordonnancement et ne peut donc pas ^etre utilise dans ce
contexte.
3.4 Resultats numeriques
Les methodes que nous testons dans cette section sont principalement des generalisations des methodes presentees dans le chapitre
precedent. Le probleme de job-shop generalise n'est pas couramment
CHAPITRE 3. LE JOB-SHOP GE NE RALISE
104
Atelier 1
Atelier 2
Atelier 3
Nombre de groupes Nombres de machines
3
2-3-2
3
5-4-7
6
2-3-2-4-3-3
Fig. 3.3 - Composition des ateliers
traite et il n'existe pas de jeux de donnees dans la litterature. De ce
fait, et pour les besoins de l'experimentation, nous avons genere une
bibliotheque d'instances de ce probleme.
3.4.1 Presentation des jeux de donnees
Dans le but de balayer une large gamme de problemes, nous avons
considere 3 types d'atelier resume dans le tableau de la gure 3.3.
Chaque atelier est compose de groupes de machines et chaque groupe
contient plusieurs machines. Ainsi, une operation qui sera a ectee a un
groupe de machines ne pourra ^etre executee que par une des machines
de celui-ci. Toutefois, il est possible que certaines machines du groupe ne
puissent e ectuer l'operation. L'atelier 1 est de petite taille, 7 machines
reparties en 3 groupes. Les ateliers 2 et 3 sont de taille plus importante,
respectivement 16 et 17 machines, mais reparties di eremment dans les
groupes. Dans l'atelier 2, les machines sont divisees en 3 groupes alors
que pour l'atelier 3, elles sont divisees en 6 groupes. Les instances du
probleme que nous proposons sont decrites dans la gure 3.4. Pour chacun des ateliers, di erents types de jobs sont envisages ainsi que leurs
nombres.
Pour chacun des types d'ateliers et chaque type de jobs, 25 instances
ont ete generees, cela dans le but de calculer des moyennes sur ces 25
instances.
3.4.2 Resultats et conclusions
Les regles de priorite choisies pour l'experimentation sont les m^emes
que celles du chapitre precedent. Seulement, la le d'attente d'une machine contient toutes les operations pouvant ^etre executees sur celle-ci.
3.4. RE SULTATS NUME RIQUES
!
Types d'instances
! Atelier 1
! 4 operations par jobs
! 25, 50 ou 100 jobs
! 8 operations par jobs
! 25, 50 ou 100 jobs
! Atelier 2
! 4 operations par jobs
! 50, 100 ou 150 jobs
! 8 operations par jobs
! 50, 100 ou 150 jobs
! Atelier 3
! 7 operations par jobs
! 50, 100 ou 150 jobs
! 12 operations par jobs
! 50, 100 ou 150 jobs
Fig.
3.4 - Les types d'instances g
enerees
105
106
CHAPITRE 3. LE JOB-SHOP GE NE RALISE
Une operation pouvant ^etre executee par plusieurs machines, une operation peut gurer dans plusieurs les d'attente. Le choix d'une operation
dans une le resoudra a la fois l'a ectation et l'ordonnancement. Une
operation choisie sera bien entendu retiree des autres les d'attente ou
elle etait presente. De la m^eme facon que pour le job-shop statique et
deterministe, nous ne garderons dans les tableaux de resultats que les
regles donnant la meilleure et la moins bonne des solutions, ainsi que
la moyenne des regles.
Les methodes OPT testees sont les generalisations des methodes
etudiees dans le chapitre 2. Au niveau des procedures d'amelioration,
les deux procedures utilisees sont l'amelioration par permutations et
rea ectations d'une part, et l'amelioration par reagregations d'autre
part.
Les resultats obtenus pour chacun des trois ateliers sont tres semblables (cf gures 3.5, 3.6 et 3.7). On constate que pour le probleme de
job-shop generalise, les methodes OPT donnent de tres bons resultats
par rapport aux regles de priorite. Selon le type d'atelier, le pourcentage
d'amelioration entre la meilleure methode OPT et la meilleure regle de
priorite varie entre 7 et 8 %. La deuxieme remarque importante est que
dans la plupart des cas, la plus mauvaise methode OPT est meilleure
que la meilleure des regles de priorite.
En ce qui concerne la comparaison des methodes agregatives, nous
arrivons aux m^emes conclusions que pour le job-shop statique et deterministe. Premierement, la methode d'agregation par fonction co^ut
domine tres legerement l'agregation iterative, qui elle-m^eme domine
l'agregation globale. Deuxiemement, la procedure de reagregation permet d'ameliorer sensiblement les resultats obtenus par une simple application de l'amelioration par permutations et rea ectations.
Ces tests ont egalement ete e ectues sur une station de travail
SPARC 10. Pour une instance de 150 jobs composes de 15 operations
chacun a ordonnancer dans l'atelier 3, le temps de calcul n'excede jamais 30 minutes. Pour l'atelier 1, le temps de calcul varie entre 15
secondes pour 25 jobs de 4 operations sans reagregation, a 12 minutes
3.5.
107
CONCLUSION
n
n
25 25 50 50 100
4
8
4
8
4
OPT1
475 827 875 1479 1682
OPT2
487 845 851 1422 1651
OPT3
459 802 868 1397 1648
OPT4
473 819 853 1421 1667
OPT5
471 782 857 1389 1626
OPT6
452 789 846 1372 1603
Min
498 835 903 1462 1679
Max
575 971 1072 1708 1897
Moy
534 895 1002 1554 1734
Min , OPT 10,2 6,8 6,7 6,6 4,7
OPT
Fig. 3.5 - Job-shop g
eneralise, atelier 1
i
100
8
3463
3387
3415
3398
3312
3324
3458
3759
3582
4,0
pour 100 jobs de 8 operations avec reagregation. Les temps pour les
ateliers 2 et 3 sont comparables pour des instances et des methodes
equivalentes.
3.5
Conclusion
Le job-shop generalise se compose des deux problemes diciles que
sont l'a ectation des operations aux machines et l'ordonnancement des
operations. Les methodes agregatives une-phase que nous avons proposees et testees dans ce chapitre sont particulierement bien adaptees a
ce type de problemes.
La phase d'agregation proprement dite gere a la fois l'a ectation
et l'ordonnancement. L'utilisation d'un critere bien adapte (cf 2.5.2),
permet de selectionner une machine rapide pour l'operation consideree,
car minimisant le temps operatoire, et de trouver un emplacement interessant pour l'insertion de l'operation dans la sequence de la machine
choisie.
En ce qui concerne l'amelioration locale, les procedures de rea ec-
CHAPITRE 3. LE JOB-SHOP GE NE RALISE
108
n
n
25
25
50
50
100
100
4
8
4
8
4
8
OPT1
409
698
737
1367
1189
2148
OPT2
401
681
728
1381
1151
2123
OPT3
382
682
732
1336
1163
2097
OPT4
378
679
744
1342
1170
2121
OPT5
389
654
721
1326
1149
2049
OPT6
369
661
723
1311
1134
2057
413
701
763
1403
1218
2159
514
912
895
1757
1385
2461
462
794
812
1459
1257
2223
11,9
7,2
5,8
7,0
7,4
5,0
i
Min
Max
Moy
Min ,
OPT
OPT
Fig. 3.6 -
Job-shop generalise, atelier 2
n
n
25
25
50
50
100
100
7
12
7
12
7
12
OPT1
695
1101
1289
2393
1897
3159
OPT2
659
1049
1257
2261
1812
3106
OPT3
669
1012
1294
2307
1789
3121
OPT4
672
1031
1251
2243
1826
3045
OPT5
631
995
1229
2195
1749
3065
OPT6
644
989
1221
2179
1763
3012
689
1056
1319
2308
1897
3148
802
1397
1598
2639
2103
3493
738
1205
1429
2486
1986
3322
9,2
6,8
8,0
5,9
7,6
4,5
i
Min
Max
Moy
Min ,
OPT
OPT
Fig. 3.7 -
Job-shop generalise, atelier 3
3.5.
CONCLUSION
109
tations et de permutations permettent, pour la premiere de corriger
une a ectation mauvaise, et pour la deuxieme de corriger l'ordonnancement. En e et, lors de la phase d'agregation, une machine faiblement
utilisee peut attirer une operation alors que celle-ci necessite un temps
operatoire important. La procedure de rea ectation peut alors modier ceci en faisant passer l'operation sur une machine plus adaptee. De
m^eme, la sequence des operations n'etant pas modi ee lors de l'agregation d'un nouveau job, il est possible que l'ordonnancement puisse
^etre ameliore par une simple permutation. L'utilisation en alternance
des ces deux procedures permet une amelioration sensible de la solution courante a chaque nouvelle agregation. La reagregation modi e
plus profondement la structure de la solution courante. Une utilisation
couplee avec les deux procedures precedentes permet une amelioration
encore plus importante.
Comparees avec les regles de priorite, les methodes agregatives donnent des solutions plus interessantes. Bien entendu, le temps de calcul
est tres nettement superieur pour les methodes OPT. Toutefois, le choix
du type d'agregation et d'amelioration locale permet de contr^oler ce
temps pour qu'il ne devienne pas trop important.
110
CHAPITRE 3. LE JOB-SHOP GE NE RALISE
111
Chapitre 4
Le job-shop dynamique et
reactif
Le job-shop dynamique et reactif [112] [111] introduit une nouvelle
diculte dans la problematique classique de l'ordonnancement tel que
nous l'avons traitee dans les chapitres 1 a 3. Le but est de trouver
un ordonnancement previsionnel admissible le meilleur possible et de
suivre son deroulement dans un atelier de production. Lors de cette
execution, deux types d'aleas peuvent se produire : l'arr^et momentane
d'une machine et l'arrivee d'un nouveau job. Il est alors necessaire de
reagir en temps reel a ces perturbations pour redonner rapidement un
nouvel ordonnancement admissible.
Ces deux types d'aleas sont generalement traites separement dans
la litterature. L'arrivee de nouveaux jobs a des instants quelconques du
deroulement des operations dans l'atelier constitue l'ordonnancement
dynamique. D'autre part, les arr^ets des machines sont traites dans le
cadre de l'ordonnancement reactif.
Le job-shop dynamique et reactif fait partie des problemes on-line.
Dans ces problemes, a l'inverse des problemes consideres jusqu'a present, les donnees ne sont pas toutes connues au depart de l'optimisation.
L'optimisation se fait donc sur l'ensemble des jobs connus a un instant
donne. Le but des methodes est donc de tenir compte en temps reel des
aleas et de proposer le plus rapidement possible la meilleure solution.
112
CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF
Apres avoir de ni le probleme, nous ferons un rapide tour d'horizon
sur quelques methodes connues pour sa resolution. Nous proposerons
ensuite un principe de resolution base sur l'agregation ou nous utiliserons quelques uns des resultats sur le job-shop generalise. Les methodes
seront testees sur des jeux de donnees crees pour l'experimentation.
4.1 Presentation du probleme
Le probleme de job-shop dynamique et reactif n'est pas reellement
associe a un modele d'atelier de production comme le sont le job-shop
statique et deterministe et le job-shop generalise. Son inter^et est plut^ot
de rendre vivant l'atelier de production considere en abordant les problemes d'arr^ets des machines et d'arrivees aleatoires des jobs. Dans un
premier temps, les structures de l'atelier et les contraintes liees aux aspects dynamiques seront exposees. Ensuite, les approches de resolution
connues seront decrites.
4.1.1 Description du probleme
Le type d'atelier de production considere pour le probleme du jobshop dynamique et reactif est le m^eme que celui du job-shop generalise.
Les donnees sont donc les suivantes :
1. Un ensemble M de m machines. Une machine est notee M avec
k = 1; :::; m.
2. Un ensemble J de n jobs. Chaque job est compose d'une gamme
operatoire i.e. une sequence lineaire de n operations xee. Cette
sequence ne depend que du job et peut varier d'un job a l'autre.
Un job est note J avec i = 1; :::; n.
3. Une operation O represente la jeme operation du job J . Cette
operation necessite un temps operatoire p . La date de debut
calculee de l'operation O sera toujours notee t .
4. L'operation O necessite,
n pour ^etre realis
oee, une des machines
de l'ensemble R(O ) = M 1 ; M 2 ; :::; M . Le temps operatoire
sur la machine M pour l'operation O sera note p .
k
i
i
i;j
i
i;j
i;j
i;j
i;j
i;j
k
k
kq
k
i;j
i;j;k
4.1. PRE SENTATION DU PROBLE ME
113
La di erence entre le job-shop generalise et le job-shop dynamique
reside dans les aspects dynamiques. Pour tenir compte de ces aspects
dans l'atelier, certaines hypotheses utilisees dans les problemes precedents sont a supprimer. Ainsi, l'hypothese qu'une machine est disponible pour toute la duree de l'ordonnancement est a abandonner. Les
contraintes auxquelles est soumis l'atelier sont donc les suivantes :
1. Les machines sont independantes les unes des autres.
2. Une machine ne peut executer qu'une seule operation a un instant
donne.
3. Chaque machine peut ^etre arr^etee a un instant quelconque du
deroulement de l'ordonnancement. Au moment ou l'arr^et se produit, la date de remise en route est xee (on considere ici que
l'estimation de la duree des pannes ou de la maintenance est correcte).
4. Une operation en cours d'execution ne peut ^etre interrompue (il
n'y a pas de preemption) sauf si la machine s'arr^ete avant que
l'operation ne soit nie. Dans ce cas, le reste de l'operation sera
poursuivi soit sur la m^eme machine au moment de son redemarrage soit sur une autre. Le temps operatoire restant sera recalcule
en fonction de la rapidite de la machine choisie pour nir l'operation.
5. Les jobs sont independants les uns des autres. En particulier, il
n'existe aucun ordre de priorite attache aux jobs.
6. Les jobs ne sont pas tous connus au depart, certains peuvent arriver a un instant quelconque de l'ordonnancement. A cet instant,
le job est parfaitement de ni (gamme operatoire, machines utilisables pour chaque operation et temps operatoires).
Le probleme consiste non seulement a determiner une a ectation
de chaque operation sur une machine et a trouver une sequence des
operations, mais egalement a tenir compte au cours du temps des evenements aleatoires pouvant se produire. Dans notre etude, et comme
114
CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF
pour les problemes precedents, le but de l'ordonnancement est de trouver le temps de production pour la totalite des jobs le plus court possible
(minimisation de Cmax).
4.1.2 Les methodes de resolution connues
Pour la resolution des problemes de job-shop dynamique et reactif,
deux grandes idees ont deja ete developpees. La premiere privilegie l'optimisation de l'ordonnancement propose aux depens du temps de calcul
et e ectue une decomposition du probleme en une serie de problemes
de job-shop statique. La seconde methode est basee sur l'utilisation
de regles de priorite, ce qui necessite un temps de calcul tres court et
permet de repondre rapidement a un alea.
4.1.2.1 Decomposition en job-shop statique
Cette methode ne s'applique pas directement au probleme que nous
traitons, mais a un probleme voisin, le job-shop dynamique avec minimisation de la somme des retards. Une adaptation de la methode permettrait de traiter un probleme dynamique et reactif. Cette approche
presentee par N. Raman et F.B. Talbot [92] a pour but de decomposer un job shop dynamique en une serie de job-shops statiques. Cette
approche est bien s^ur adaptable au probleme que nous traitons maintenant. Le principe de cette approche consiste en un recalcul complet de
l'ordonnancement a l'arrivee de chaque nouvel alea. Des qu'un nouveau
job arrive ou qu'une machine s'arr^ete, l'ordonnancement prevu est alors
annule et les donnees sont entierement reprises pour un nouveau calcul
de l'ordonnancement previsionnel (algorithme de la gure 4.1).
La m^eme demarche peut s'appliquer au probleme qui nous interesse
dans ce memoire. A la date ou un alea survient, on prend les donnees
du probleme, sans tenir compte de l'ordonnancement previsionnel precedent, et l'on recalcul un nouvel ordonnancement a partir des donnees.
Les jobs dont toutes les operations ont ete executees ne gureront plus
dans la liste. Les jobs dont seulement une partie des operations a ete
executee seront introduits dans la liste, en les restreignant aux operations restantes. Les jobs dont aucune des operations ne sera traitee
4.1. PRE SENTATION DU PROBLE ME
115
seront mis completement dans la liste. L'ensemble des donnees ainsi
reconstitue, il faut mettre en uvre une methode exacte (branch and
bound par exemple) pour redonner un ordonnancement previsionnel
optimal, au sens de la minimisation de la longueur totale.
L'avantage de cette methode est sans aucun doute la qualite des
solutions trouvees. En e et, pour chaque alea, un nouvel ordonnancement tenant compte de la totalite des donnees est calcule. Par contre,
le temps de calcul est important et cette methode perd de son inter^et lors d'arr^et machines ou d'arrivees de job frequents. On peut donc
l'envisager dans des systemes de tres petite taille avec de rares aleas.
4.1.2.2 Les regles de priorite
L'utilisation de regles de priorite [15] [51] [84] est de loin la technique
la plus employee pour resoudre les problemes d'ordonnancement dynamique et reactif. Dans cette approche, l'ordonnancement est construit
au fur et a mesure des besoins. A chaque fois qu'une machine se libere,
une regle de priorite determine l'operation qui va ^etre executee sur cette
machine, parmi la liste des operations candidates. Cette methode assure
a la fois l'a ectation des operations aux machines et l'ordonnancement.
Les nombreuses regles etudiees [15] [51] [66] [108] [109] peuvent
^etres classees suivant leurs caracteristiques. Tout d'abord, ces regles
peuvent ^etre locales ou globales, statiques ou dynamiques. Une regle
est dite locale si elle n'utilise que les informations contenues dans la
le ou elle est utilisee, elle est globale si elle utilise des informations de
l'ensemble du systeme. Une regle statique a ecte a une piece une priorite constante durant tout l'ordonnancement, elle est dynamique si la
valeur de cette priorite peut evoluer au cours du temps ou de l'avancement dans l'ordonnancement. Nous pouvons par exemple citer quelques
une des regles les plus classiques tel que FIFO (First In First Out) qui
realise en priorite l'operation arrivee la premiere, SPT (Shortest Processing Time) qui choisit l'operation ayant le temps operatoire le plus
court.
La caracteristique de cette approche est de ne pas construire l'or-
116
CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF
1. INITIALISATION
Faire la liste des jobs a ordonnancer.
2. CALCUL D'UNE SOLUTION
Calculer un ordonnancement avec les jobs presents dans la liste
par une methode optimale minimisant la dure totale (Cmax).
D'UN JOB
3. ARRIVEE
(a) Supprimer de l'ordonnancement les operations deja realisees.
(b) Reconstruire la liste des jobs a ordonnancer.
(c) Retourner en 2.
^ D'UNE MACHINE
4. ARRET
(a) Supprimer de l'ordonnancement les operations deja realisees.
(b) Reconstruire la liste des jobs a ordonnancer en tenant
compte de la panne.
(c) Retourner en 2.
5. FIN DE L'ORDONNANCEMENT
L'ordonnancement se termine quand toutes les operations sont
achevees.
Fig.
4.1 - Algorithme general
4.2. UNE APPROCHE DE RE SOLUTION
117
donnancement previsionnel et de ne pas anticiper sur le deroulement de
l'ordonnancement. L'utilisation d'une telle methode se justi e quand le
systeme est complexe et que les arrivees des aleas sont frequentes.
4.2
Une approche de resolution
L'approche proposee maintenant est basee sur le principe d'agregation, developpe dans les chapitres precedents. L'idee de base de cette
approche est de construire un ordonnancement previsionnel qui sera
suivi tant qu'il n'y a pas d'aleas. Des qu'un alea survient, le but et
de reagir pour proposer a nouveau un ordonnancement previsionnel.
L'objectif est de conserver a tout instant du deroulement de l'ordonnancement, un ordonnancement previsionnel complet et optimise. Ceci
permet d'avoir une vue globale de l'ordonnancement a venir, a l'inverse
des regles de priorite qui construisent l'ordonnancement au fur et a mesure des liberations des machines ou des arrivees des aleas. A chaque
arrivee d'un job, la structure de l'ordonnancement previsionnel n'est
pas modi e et le nouveau job est agrege a l'ordonnancement existant.
Lors d'un arr^et machine, une procedure de rea ectation des operations
aux machines ou une procedure de reagregation est mise en uvre pour
repondre a la perturbation.
Cette methode tente non seulement de trouver un compromis entre
le temps de calcul pour la resolution du probleme (regle de priorite) et la
recherche de la meilleure solution (decomposition en job-shop statique),
mais egalement de repondre rapidement aux aleas en proposant un
nouvel ordonnancement partiel.
4.2.1 L'algorithme general de resolution
Avant de donner l'algorithme general de resolution du job-shop dynamique et reactif, nous allons detailler les points essentiels du deroulement du probleme. A l'instant initial, nous connaissons l'ensemble M
des machines disponibles ainsi qu'un sous-ensemble des jobs a ordonnancer. De ce fait, nous sommes confrontes a un probleme de job-shop
generalise. Le but est alors de construire un ordonnancement prevision-
118
CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF
nel en minimisant la duree totale (Cmax). Celui-ci peut ^etre construit
par n'importe quel algorithme de resolution du job-shop generalise. En
particulier, tous les algorithmes developpes dans le chapitre 3 sont utilisables. Cet ordonnancement previsionnel se deroulera tant qu'il n'y a
pas d'aleas (arr^ets de machines ou arrivee de nouveaux jobs).
A l'arrivee d'un nouveau job, nous nous xons comme objectif de
garder un maximum d'informations issues de l'ordonnancement previsionnel qui est deja optimise, plut^ot que de recalculer un ordonnancement complet comme le proposent N. Raman et F.B. Talbot [92].
Pour cela, les di erentes operations du nouveau job sont inserees dans
l'ordonnancement precedent. La description precise de cette agregation
sera presentee dans la section 4.2.2.
Le deuxieme type d'aleas pouvant se produire est l'arr^et d'une machine. Lorsque cet arr^et est de courte duree cela ne change pas de
facon signi cative l'ordonnancement prevu et un simple decalage dans
le temps des operations concernees sut pour absorber l'alea. Pour
cela, il sut de decaler les dates de debut de chaque operation sur la
machine de la duree de l'arr^et et eventuellement leurs successeurs de
gamme. Par contre, si cet arr^et est d'une duree plus importante, une rea ectation des operations que la machine en panne devait realiser sera
e ectuee. Chaque operation sera alors dirigee vers une autre machine en
fonctionnement. Cette rea ectation sera realisee de la m^eme facon que
pour l'agregation de nouvelles operations, a savoir par insertion entre
deux operations de l'ordonnancement previsionnel et pendant les temps
morts machine. Le comportement detaille de la methode lors de l'arr^et
d'une machine sera explique dans la section 4.2.3. Une autre possibilite
serait de retirer de l'ordonnancement previsionnel, les jobs touches par
l'arr^et de la machine et de les reagreger.
Apres chaque modi cation de l'ordonnancement pour une des deux
raisons precedentes, une amelioration locale sera e ectuee si le Cmax
est fortement augmente. Cette optimisation s'appuie sur trois procedures particulieres utilisant respectivement des permutations d'operations, des rea ectations ou des reagregations de jobs. La procedure de
permutation agit sur deux operations successives sur la m^eme machine
4.2. UNE APPROCHE DE RE SOLUTION
119
et tente de les intervertir pour ameliorer la solution courante. La procedure de rea ectation e ectue la rea ectation d'une operation sur une
autre machine plus disponible et ceci toujours dans le but d'optimiser la solution courante. Bien entendu, une combinaison de ces deux
procedures est envisageable. En n, il est possible d'enlever de l'ordonnancement, des jobs critiques et de les reagreger. Ces procedures seront
presentees dans la section 4.2.4.
Chacun des points abordes dans les paragraphes precedents permettent de construire l'algorithme general presente dans la gure 4.2.
4.2.2 L'arrivee aleatoire des jobs
Comme nous l'avons vu dans la section 4.2.1, l'arrivee d'un job J
compose de n operations perturbe le deroulement de l'ordonnancement
previsionnel. Notre objectif est ici de faire face a cette perturbation en
veillant a conserver une bonne solution sans calculs excessifs. Pour cela,
nous utilisons le principe d'agregation qui permet de conserver l'a ectation et l'ordre precedent de passage des operations sur les machines
et d'inserer les nouvelles operations dans l'ordonnancement precedent.
i
i
Pour realiser cette agregation, il est possible d'utiliser les methodes
d'agregation une-phase developpees dans le chapitre precedent. L'agregation etant faite, il est ensuite possible d'ameliorer la solution donnee
par une methode d'optimisation locale.
4.2.3 Les arr^ets machine
Dans un probleme de job-shop dynamique, un des aleas possibles
est l'arr^et d'une machine M a un instant quelconque t du deroulement
de l'ordonnancement [93] et pendant une duree xee au moment de
l'arr^et t . Ceci entra^ne une perturbation a laquelle il faut faire face
pour redonner un ordonnancement admissible en vue de poursuivre la
production.
k
k
Dans ce but, nous proposons deux procedures comportant deux alternatives possibles en fonction de la duree de l'arr^et (algorithmes de
120
CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF
1. INITIALISATION
Calculer un ordonnancement avec les jobs presents a la date t = 0
par une methode constructive minimisant la dure totale (Cmax).
2. AMELIORATION
LOCALE
Optimisation de l'ordonnancement par permutations, rea ectations ou reagregations (cf 4.2.4).
D'UN JOB
3. ARRIVEE
(a) Supprimer de l'ordonnancement les operations deja realisees.
(b) Agreger le nouveau job (cf 4.2.2).
(c) Retourner en 2.
^ D'UNE MACHINE
4. ARRET
(a) Supprimer de l'ordonnancement les operations deja realisees.
(b) Si l'arr^et est court, decaler les operations de la duree de
l'arr^et.
(c) Sinon rea ecter les operations sur une autre machine ou reagreger les jobs touches (cf 4.2.3).
(d) Retourner en 2.
5. FIN DE L'ORDONNANCEMENT
L'ordonnancement se termine quand toutes les operations sont
achevees.
Fig.
4.2 - Algorithme de resolution general
4.2. UNE APPROCHE DE RE SOLUTION
121
la gure 4.3 et 4.4). Si la duree de la panne k est petite, environ de la
duree moyenne d'une operation sur cette machine, la procedure opere
un simple decalage des operations sur cette machine. Ceci pouvant entra^ner un decalage des operations suivantes, il est alors necessaire de
recalculer les dates au plus t^ot et au plus tard. Dans le deuxieme cas, si
la duree k est grande, superieure a la duree moyenne d'une operation
sur la machine, un decalage peut augmenter la duree totale de l'ordonnancement de facon trop importante. Il est alors necessaire de mettre
en uvre une procedure de calcul plus importante.
t
t
4.2.3.1 La rea ectation
Une premiere solution est de mettre en uvre une rea ectation
des operations concernees par l'arr^et de la machine. Dans ce cas, la
procedure determine les operations qui etaient prevues sur la machine
defaillante dans l'intervalle de temps [ + k ] et tente de les inserer
dans les sequences operatoires des autres machines. La derniere operation pourra eventuellement ^etre simplement decalee. Le principe de
cette methode et, dans un premier temps, de trouver pour l'operation
a rea ecter, l'intervalle entre et la date de debut au plus tard de
l'operation qui suit dans la gamme operatoire du job. Ensuite, il faut
chercher les temps-morts sur les machines disponibles dans l'intervalle
considere (cf 2.2.4). Il est bien sur obligatoire de veri er la validite de
la solution en n'inserant pas d'operations avant leurs predecesseurs de
gamme operatoire. Apres avoir e ectue ces rea ectations, il faut a nouveau mettre a jour les dates au plus t^ot et au plus tard. L'insertion se
fait comme les insertions precedentes (cf 2.2.4), dans les emplacements
les plus grands ou les plus proches de la duree operatoire de l'operation.
t; t
t
t
4.2.3.2 La reagregation
Une deuxieme possibilite pour traiter le probleme des arr^ets est la
reagregation. Le principe est de supprimer de l'ordonnancement previsionnel, les jobs dont une au moins des operations est touchee par
l'arr^et de la machine. Ensuite, il est possible d'ameliorer le nouvel ordonnancement obtenu avant de reagreger les jobs. Ceci est interessant
dans le cas ou beaucoup de jobs sont concernes par l'arr^et de la ma-
122
CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF
^ D'UNE MACHINE
1. ARRET
Arr^et de la machine k pour une duree de k a l'instant .
2. MISE A JOUR DE L'ORDONNANCEMENT PREVISIONNEL
Suppression des operations achevees avant la date .
^
3. IMPORTANCE DE L'ARRET
M
t
t
t
(a) Si k est petit, decalage des operations sur la machine et
retourner en 5.
(b) Si k est grand, aller en 4.
4. REAFFECTATION
Rea ectation des operations de la machine k initialement prevues dans l'intervalle de temps [ + k ], sur d'autres machines
disponibles.
5. CALCUL DU PERT
Calcul des dates au plus t^ot et au plus tard.
t
t
M
t; t
Fig.
t
4.3 - Algorithme de rea ectation apres arr^et d'une machine
4.3. RE SULTATS NUME RIQUES
123
chine. La derniere phase consiste a reagreger les jobs enleves. Pour cela,
nous pouvons utiliser une des procedures d'agregation proposees avant.
L'ordre dans lequel les jobs sont reintroduits est dependant du choix
de la procedure de selection.
4.2.4 La reoptimisation locale
Le principe de reoptimisation des solutions n'est bien s^ur pas different des principes expliques dans les chapitres 2 et 3. Le choix des
methodes est surtout lie au temps dont on dispose pour l'amelioration
par rapport au deroulement de l'ordonnancement previsionnel.
Dans le cas ou l'atelier est peu perturbe, calculer une bonne solution
est interessant. Cela permet une bonne optimisation et d'obtenir un
ordonnancement quasi-optimal qui sera suivi sur une longue periode.
Par contre, si l'atelier est fortement perturbe, l'inter^et est plut^ot de
reagir vite aux aleas et limiter les phases de reoptimisation locale. En
e et, il n'est pas necessaire de calculer de tres bonnes solutions si elles
doivent ^etre remises en cause peu de temps apres.
4.3 Resultats numeriques
Dans le but de valider notre approche par agregation pour le jobshop dynamique et reactif, nous avons compare nos resultats avec ceux
obtenus par des algorithmes bases sur des regles de priorite. Dans un
premier temps, et comme il n'existe pas d'exemples classiques pour le
job-shop dynamique dans la litterature, nous avons cree une bibliotheque de jeux de donnees. Ces jeux de donnees regroupent plusieurs
types d'atelier de production et des problemes de tailles di erentes.
Ensuite, quelques methodes de resolution issues de notre approche sont
testees sur cette bibliotheque et comparees avec des algorithmes classiques. Pour nir, les resultats obtenus sont commentes.
124
CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF
^ D'UNE MACHINE
1. ARRET
Arr^et de la machine Mk pour une duree de tk a l'instant t.
2. MISE A JOUR DE L'ORDONNANCEMENT PREVISIONNEL
Suppression des operations achevees avant la date t.
^
3. IMPORTANCE DE L'ARRET
(a) Si tk est petit, decalage des operations sur la machine et
retourner en 5.
(b) Si tk est grand, aller en 4.
4. ENLEVEMENT
DES JOBS
Enlevement des jobs dont les operations sont touchees par l'arr^et
de la machine.
5. REAGR
EGATION
Reagregation des jobs enleves.
6. CALCUL DU PERT
Calcul des dates au plus t^ot et au plus tard.
Fig.
4.4 - Algorithme de reagregation apres arr^et d'une machine
4.3. RE SULTATS NUME RIQUES
Atelier 1
Atelier 2
Atelier 3
125
Nombre de groupes Nombre de machines
3
2-3-2
3
5-4-7
6
2-3-2-4-3-3
Fig. 4.5 - Composition des ateliers
4.3.1 Presentation des jeux de donnees
Le probleme de job-shop dynamique que nous avons decrit dans ce
chapitre est rarement traite avec les m^emes contraintes et les m^emes
objectifs dans la litterature [9] [17] [48]. Le plus souvent, les deux problemes que constituent l'ordonnancement dynamique et l'ordonnancement reactif sont separes. Le premier ne traite que les aspects dynamiques representes par l'arrivee aleatoire de jobs et pour le second,
seule la reaction a un arr^et machine est prise en compte.
C'est pour cela que nous proposons la creation d'une bibliotheque
de jeux de donnees correspondant au probleme que nous avons de ni
dans ce chapitre. Pour cela, plusieurs types d'ateliers sont proposes et
pour chacun d'eux plusieurs types de production. Le nombre de jobs,
d'operations par jobs ainsi que le type et le nombre des aleas peuvent
varier.
En ce qui concerne les ateliers, 3 types sont proposes (tableau de la
gure 4.5). Ces ateliers sont les m^emes que ceux qui nous ont servis dans
le chapitre precedent pour generer les instances du job-shop generalise.
Le nombre de jobs presents a l'instant initial est d'environ 25 pour
l'atelier 1, 50 pour l'atelier 2 et 60 pour l'atelier 3. Ces jobs peuvent
avoir des caracteristiques di erentes. Ainsi, nous avons cree des jeux
de donnees pour l'atelier 1 ou les jobs sont composes de 4 operations,
puis des jeux de donnees ou les jobs sont composes de 8 operations.
Les details pour les autres ateliers sont consignes dans la gure 4.6.
Pour chacun des ateliers et des types de jobs, nous avons genere 3
types d'aleas, seulement des arr^ets machines (ordonnancement reactif),
seulement des arrivees de jobs (ordonnancement dynamique) et les deux
126
CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF
ensemble. Pour nir, pour chacun des cas precedents, deux instances
ont ete creees, l'une avec un faible nombre d'aleas, et l'autres avec un
nombre plus important.
Pour chacun des cas precedents, nous avons realise 25 instances avec
les m^emes valeurs (nombre de jobs au depart, nombre d'operations par
jobs, etc). Ceci nous permettra de donner des resultats sur la moyenne
des 25 instances et ainsi mieux juger de la qualite des methodes mises
en uvre.
La diversite des problemes que nous proposons a pour but d'etudier
l'in uence des di erents parametres sur les resultats obtenus. Ainsi, on
pourra etudier le comportement des methodes sur des tailles d'ateliers
di erentes, des nombres d'operations variables et aussi sur les aspects
reactifs et dynamiques des ordonnancements.
4.3.2 Resultats et conclusions
Les regles de priorite choisies pour l'experimentation sont les m^emes
que celles des chapitres precedents. A l'arrivee d'un nouveau job dans
l'atelier, la premiere operation est placee dans les les d'attente des
machines pouvant executer celle-ci. Dans le cas d'un arr^et d'une machine, l'operation en cours est stoppee et remise dans les les d'attente
sur les machines disponibles. De la m^eme facon que pour les problemes
precedents, nous ne garderons dans les tableaux de resultats que les
regles donnant la meilleure et la moins bonne des solutions, ainsi que
la moyenne des regles.
Nous presentons maintenant 12 methodes permettant de tester a
la fois les procedures d'agregation, les procedures de reoptimisation
et les reactions aux aleas. L'agregation globale sera testee ainsi que les
agregations iterative et par fonction co^ut. Pour ce qui est des procedures
de reoptimisation, nous utiliserons la permutation, la rea ectation et
la reagregation. En n nous regarderons la reaction aux arr^ets machines
par rea ectation de l'operation en cours et par reagregation des jobs
concernes.
4.3. RE SULTATS NUME RIQUES
!
Types d'instances
127
! Atelier 1 (25 jobs au depart)
! 4 operations par jobs
! Arr^ets de machines (15 ou 50)
! Arrivees de jobs (15 ou 50)
! Arr^ets de machines (8 ou 25) et arrivees de jobs (8 ou 25)
! 8 operations par jobs
! Arr^ets de machines (25 ou 100)
! Arrivees de jobs (25 ou 100)
! Arr^ets de machines (13 ou 50) et arrivees de jobs (13 ou 50)
! Atelier 2 (50 jobs au depart)
! 4 operations par jobs
! Arr^ets de machines (15 ou 50)
! Arrivees de jobs (15 ou 50)
! Arr^ets de machines (8 ou 25) et arrivees de jobs (8 ou 25)
! 8 operations par jobs
! Arr^ets de machines (30 ou 120)
! Arrivees de jobs (30 ou 120)
! Arr^ets de machines (15 ou 60) et arrivees de jobs(15 ou 60)
! Atelier 3 (60 jobs au depart)
! 7 operations par jobs
! Arr^ets de machines (25 ou 100)
! Arrivees de jobs (25 ou 100)
! Arr^ets de machines (13 ou 50) et arrivees de jobs (13 ou 50)
! 12 operations par jobs
! Arr^ets de machines (40 ou 160)
! Arrivees de jobs (40 ou 160)
! Arr^ets de machines (20 ou 80) et arrivees de jobs (20 ou 80)
Fig.
4.6 - Les types d'instances g
enerees
128
CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF
Les methodes sont presentees en fonction de la methode d'agregation, puis de la methode d'amelioration et en n de la maniere de reagir
aux arr^ets de machines :
{ OPT1 :
1. Agregation globale
2. Amelioration par permutations et rea ectations
3. Rea ectation des operations
{ OPT2 :
1. Agregation globale
2. Amelioration par permutations et rea ectations
3. Reagregation des jobs
{ OPT3 :
1. Agregation globale
2. Amelioration par permutations, rea ectations et reagregations
3. Rea ectation des operations
{ OPT4 :
1. Agregation globale
2. Amelioration par permutations, rea ectations et reagregations
3. Reagregation des jobs
{ OPT5 :
1. Agregation iterative
2. Amelioration par permutations et rea ectations
3. Rea ectation des operations
4.3. RE SULTATS NUME RIQUES
129
{ OPT6 :
1. Agregation iterative
2. Amelioration par permutations et rea ectations
3. Reagregation des jobs
{ OPT7 :
1. Agregation iterative
2. Amelioration par permutations, rea ectations et reagregations
3. Rea ectation des operations
{ OPT8 :
1. Agregation iterative
2. Amelioration par permutations, rea ectations et reagregations
3. Reagregation des jobs
{ OPT9 :
1. Agregation par fonction co^ut
2. Amelioration par permutations et rea ectations
3. Rea ectation des operations
{ OPT10 :
1. Agregation par fonction co^ut
2. Amelioration par permutations et rea ectations
3. Reagregation des jobs
{ OPT11 :
1. Agregation par fonction co^ut
2. Amelioration par permutations, rea ectations et reagregations
130
CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF
3. Rea ectation des operations
{ OPT12 :
1. Agregation par fonction co^ut
2. Amelioration par permutations, rea ectations et reagregations
3. Reagregation des jobs
On peut remarquer que dans le cas ou il n'y a pas d'arr^ets machines
dans les aleas, les calculs OPT1 et OPT2, OPT3 et OPT4, OPT5 et
OPT6, OPT7 et OPT8, OPT9 et OPT10, OPT11 et OPT12 sont identiques, car la di erence entre ces calculs provient uniquement du type
de reponses a un arr^et.
Les resultats des tests numeriques sont presentes pour chaque atelier. Pour un atelier donne, un tableau presente un des types d'aleas
consideres dans cette etude, job-shop dynamique pour les arrivees de
jobs uniquement, job-shop reactif pour les arr^ets machines et job-shop
dynamique et reactif pour les deux en m^eme temps.
La premiere colonne du tableau (n ) donne le nombre d'operations
dans la gamme des jobs, la deuxieme donne la quantite d'aleas arrivant
dans l'atelier (P pour peu et B pour beaucoup) (se reporter a la gure
4.6). Les 3 colonnes suivantes donnent les resultats des methodes d'optimisation OPT. Pour ne pas compliquer l'analyse des resultats, nous
donnons uniquement la valeur de la meilleure methode, la valeur de la
plus mauvaise et la moyenne des 12 (ou des 6 dans le cas du job-shop
dynamique). Dans les 3 colonnes suivantes gurent les resultats des
regles de priorite. La derniere colonne contient le pourcentage d'amelioration entre la meilleure methode d'optimisation et la meilleure regle
de priorite.
i
4.3.2.1 Resultats pour l'atelier 1
Le tableau 4.7 presente les resultats obtenus avec des aleas de type
arrivee de jobs. Mis a part pour la premiere serie de donnees ou les
4.3. RE SULTATS NUME RIQUES
131
n
qa
4
8
4
8
P P
B
B
OPT1
881 1534 1341 4803
OPT2
869 1542 1322 4822
OPT3
841 1491 1361 4791
OPT4
842 1502 1354 4788
OPT5
853 1448 1382 4742
OPT6
812 1463 1219 4738
OPT7
791 1442 1228 4699
OPT8
802 1419 1197 4684
OPT9
804 1412 1203 4720
OPT10
741 1399 1198 4610
OPT11
722 1396 1182 4682
OPT12
715 1421 1145 4634
Min
782 1435 1203 4781
Max
905 1698 1411 5428
Moy
842 1582 1341 5154
Min , OPT 9,4 2,8 5,1 3,2
OPT
Fig. 4.7 - Job-shop dynamique, atelier 1
i
meilleures methodes OPT sont performantes, dans les autres cas, la
meilleure regle de priorite n'est que tres legerement moins bonne.
Le tableau 4.8 presente les resultats obtenus avec des aleas de type
arr^ets machines. On constate que les methodes par agregation donnent
des resultats de 5 a 10 % meilleurs que les regles de priorite. Ces resultats sont d'autant meilleurs que le nombre d'operations par jobs est
faible (4 au lieu de 8).
Dans le cas du job-shop dynamique et reactif (tableau de la gure
4.9), ou les aleas sont repartis entre arrivees de jobs et arr^ets machines,
les resultats obtenus sont comparables a ceux obtenus pour le job-shop
reactif. La valeur de la meilleure methode agregative est de 3 a 6 %
inferieure a celle donnee par la meilleure regle de priorite.
132
CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF
n
qa
4
8 4
8
P P B B
OPT1
524 903 728 1212
OPT3
532 848 741 1221
OPT5
494 862 754 1203
OPT7
482 821 692 1170
OPT9
481 834 649 1182
OPT11
465 808 688 1145
Min
512 860 688 1145
Max
603 992 873 1392
Moy
545 922 769 1244
Min , OPT 10,2 6,4 9,3 5,2
OPT
Fig. 4.8 - Job-shop r
eactif, atelier 1
i
Pour l'atelier 1, les resultats obtenus par les methodes agregatives
sont meilleurs que ceux obtenus par les regles de priorite. Il est toutefois
interessant de constater que les methodes OPT obtiennent de meilleurs
resultats dans la resolution de problemes reactifs.
4.3.2.2 Resultats pour l'atelier 2
Le tableau 4.10 contient les resultats obtenus sur l'atelier 2 dans
le cas du job-shop dynamique. On peut remarquer que les methodes
agregatives donnent globalement de meilleurs resultats que les regles
de priorite (de 5 a 11 %). De plus on peut constater que l'on obtient
de meilleurs resultats pour les instances dont le nombre d'aleas est le
plus faible (cf gure 4.6).
D'apres les resultats du tableau 4.11, on peut constater, comme
pour l'atelier 1, que dans le cas d'un job-shop reactif, on obtient les
meilleurs resultats pour les methodes agregatives.
Les resultats obtenus dans le cas d'un job-shop dynamique et reactif
sont comparable a ceux de l'atelier 1. Ils sont presentes dans le tableau
4.3. RE SULTATS NUME RIQUES
n
qa
133
4
8
4
8
P
P
B
B
OPT1
643
1291
1143
2853
OPT2
651
1298
1138
2812
OPT3
650
1302
1108
2821
OPT4
639
1281
1121
2842
OPT5
642
1253
1141
2824
OPT6
621
1248
1122
2831
OPT7
638
1261
1106
2803
OPT8
626
1268
1121
2742
i
OPT9
631
1241
1092
2803
OPT10
623
1234
1097
2752
OPT11
604
1241
1112
2764
OPT12
612
1236
1080
2724
642
1297
1121
2841
748
1402
1262
3287
691
1351
1135
3012
6,2
5,1
3,8
4,3
Min
Max
Moy
Min ,
OPT
OPT
Fig. 4.9 -
Job-shop dynamique et reactif, atelier 1
134
CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF
n
qa
4
8
4
8
P
P
B
B
OPT1
612
1272
992
2198
OPT2
608
1285
978
2213
OPT3
621
1279
980
2212
OPT4
604
1221
982
2212
OPT5
618
1238
961
2239
OPT6
612
1248
955
2213
OPT7
598
1254
953
2164
OPT8
612
1163
947
2203
i
OPT9
604
1204
968
2164
OPT10
582
1173
936
2158
OPT11
591
1198
963
2192
OPT12
563
1204
945
2133
618
1292
986
2242
742
1503
1104
2692
663
1204
1023
2453
9,8
11,1
5,4
5,1
Min
Max
Moy
Min ,
OPT
OPT
Fig. 4.10 -
Job-shop dynamique, atelier 2
4.3. RE SULTATS NUME RIQUES
135
n
qa
4
8
4
8
P
P
B
B
OPT1
489 908 672 1021
OPT3
509 887 651 1014
OPT5
501 872 683 982
OPT7
468 857 642 957
OPT9
460 845 623 964
OPT11
482 839 608 943
Min
514 912 672 1032
Max
682 1098 782 1291
Moy
569 973 687 1129
Min , OPT 11,9 8,7 10,5 9,4
OPT
Fig. 4.11 - Job-shop r
eactif, atelier 2
i
de la gure 4.12.
Dans cet atelier ou le nombre de machines par groupes et plus important (cf 4.5), les methodes agregatives donnent de meilleurs resultats
que pour l'atelier precedent. En e et, le pourcentage d'amelioration
entre la meilleure methode OPT et la meilleure regle de priorite est
plus eleve.
4.3.2.3 Resultats pour l'atelier 3
En ce qui concerne l'atelier 3, le tableau de resultat 4.13 sur le
job-shop dynamique con rme les resultats enregistres pour le job-shop
dynamique de l'atelier 1. Les methodes agregatives, bien que meilleures,
ne dominent pas franchement les regles de priorite.
Comme nous l'avons deja constate pour les ateliers precedents, c'est
pour le job-shop reactif que les methodes OPT donnent les resultats les
meilleurs. Dans ce cas, le pourcentage d'amelioration varie entre 6 et
9 %. Les resultats sont consignes dans le tableau de la gure 4.14.
136
CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF
n
qa
4
8
4
8
P
P
B
B
OPT1
535
1038
742
1769
OPT2
552
1021
754
1781
OPT3
524
997
743
1792
OPT4
551
1005
738
1779
OPT5
523
1024
755
1748
OPT6
534
1032
731
1712
OPT7
542
988
725
1721
OPT8
521
987
706
1705
i
OPT9
511
972
714
1698
OPT10
498
948
712
1672
OPT11
502
930
709
1682
OPT12
491
954
721
1655
543
1021
759
1789
639
1282
903
2024
591
1132
824
1941
10,5
9,8
7,5
8,1
Min
Max
Moy
Min ,
OPT
OPT
Fig. 4.12 -
Job-shop dynamique et reactif, atelier 2
4.3. RE SULTATS NUME RIQUES
n
qa
137
4
8
4
8
P
P
B
B
OPT1
1082
1928
1748
4592
OPT2
1098
1898
1753
4578
OPT3
1102
1904
1751
4524
OPT4
1089
1904
1737
4548
OPT5
1101
1891
1724
4523
OPT6
1101
1879
1742
4492
OPT7
1086
1879
1721
4512
OPT8
1078
1901
1711
4503
i
OPT9
1051
1888
1724
4482
OPT10
1068
1862
1709
4491
OPT11
1053
1881
1712
4459
OPT12
1046
1871
1706
4461
1092
1935
1742
4602
1305
2218
2105
5328
1154
2031
1904
4948
4,4
3,9
2,1
3,2
Min
Max
Moy
Min ,
OPT
OPT
Fig. 4.13 -
Job-shop dynamique, atelier 3
138
CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF
n
qa
4
8
4
8
P P
B
B
OPT1
755 1403 988 1712
OPT3
725 1423 975 1663
OPT5
742 1381 962 1705
OPT7
714 1372 932 1634
OPT9
710 1308 945 1651
OPT11
698 1321 924 1622
Min
762 1421 992 1721
Max
912 1552 1148 2086
Moy
834 1493 1082 1921
Min , OPT 9,1 8,6 7,4 6,1
OPT
Fig. 4.14 - Job-shop r
eactif, atelier 3
i
Pour nir, le tableau 4.15 con rme a nouveau les resultats sur l'atelier 1.
Les resultats obtenus pour cet atelier semble con rmer les resultats
obtenus pour l'atelier 1. Des remarques generales sont faites dans la
section suivante ou les grandes lignes de l'experimentation sont precisees.
4.3.2.4 Remarques generales
En ce qui concerne les types d'agregation, les resultats obtenus aux
chapitres 2 et 3 sont con rmes par les tests presentes plus haut. L'agregation globale, plus rapide que les deux autres, est la moins performante des trois (de 5 a 10 %). L'agregation iterative est plus rapide
que l'agregation par fonction co^ut mais donne des resultats legerement
moins bons (de l'ordre de 2 %).
Pour ce qui est des methodes d'amelioration locale, l'utilisation combinee de la reagregation avec les permutations et les rea ectations ameliore sensiblement les performances des methodes. Ceci etait deja vrai
4.3. RE SULTATS NUME RIQUES
n
qa
139
4
8
4
8
P
P
B
B
1012
1923
1451
3095
OPT2
998
1934
1412
3107
OPT3
1005
1892
1438
3098
OPT4
1022
1872
1423
3056
OPT5
978
1905
1442
3063
OPT6
964
1912
1423
3092
OPT7
982
1864
1421
3087
OPT8
1005
1872
1399
3052
i
OPT1
OPT9
942
1845
1376
3038
OPT10
954
1832
1402
3043
OPT11
963
1824
1398
2962
OPT12
939
1808
1381
3082
1031
1942
1443
3122
1221
2203
1612
3587
1123
2104
1491
3348
9,8
7,4
4,9
5,4
Min
Max
Moy
Min ,
OPT
OPT
Fig. 4.15 -
Job-shop dynamique et reactif, atelier 3
140
CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF
pour les problemes de job-shop statique et deterministe et pour le jobshop generalise.
Pour l'experimentation, nous avons teste deux types de reponses
a l'arr^et d'une machine, la rea ectation des operations concernees par
l'arr^et et la reagregation des jobs. La reagregation donne de meilleurs
resultats que la rea ectation sans toutefois que cela soit signi catif (de
l'ordre de 2 %).
Les resultats obtenus sur les trois types de problemes etudies (jobshop dynamique, reactif et, dynamique et reactif) font appara^tre que
toutes les methodes OPT donnent de meilleurs resultats sur les problemes de type reactif. C'est en e et sur le job-shop reactif que l'ecart
des durees de l'ordonnancement entre les methodes agregatives et les
regles de priorite est le plus important (entre 8 et 10 % selon les ateliers). Par contre, dans le cas du job-shop dynamique, le pourcentage
d'amelioration varie entre 4 et 7 %. Lorsque les aleas sont des deux
types (job-shop dynamique et reactif), le pourcentage varie entre 5 et
10 %.
Pour tester l'in uence de la frequence d'arrivees des aleas, deux
nombres d'aleas ont ete proposes pour chaque type d'instances. On
constate que quand la frequence d'arrivees des aleas est elevee, les
methodes OPT sont moins performantes. L'ecart entre les methodes
agregatives et les regles de priorite se resserre.
L'in uence du nombre d'operations dans les gammes operatoires des
jobs ne semblent pas ^etre tres importante. Les di erences constatees
pour un job-shop reactif de l'atelier 1 (cf tableau 4.8) ne se con rme
pas pour les autres problemes et les autres ateliers.
Pour nir, les methodes agregatives donnent de tres bons resultats
quand le nombre de machines par groupes est le plus eleve (cf 4.10, 4.11
et 4.12). Ceci se voit en comparant les resultats donnes sur les ateliers
1 et 2. Par contre, le nombre de groupes ne semble pas in uer sur les
resultats des methodes OPT (comparaison entre les ateliers 1 et 3).
4.4.
4.4
CONCLUSION
141
Conclusion
L'approche par agregation a ete concue plus particulierement pour
traiter des problemes de job-shop dynamique et reactif. Les methodes
qui en sont issues et qui ont ete presentees dans ce chapitre et les
precedents permettent, dans un premier temps, de trouver des solutions
previsionnelles pour l'ordonnancement de production dans un atelier.
Ce probleme, de type job-shop generalise, est resolu de facon rapide.
Mais l'inter^et principal de l'approche est de reagir rapidement aux aleas
de production pouvant survenir. La reaction a un alea par les methodes
les plus complexes et sur les instances les plus grandes ne prend pas
plus de deux minutes sur une station de travail de type SPARC 10. Les
resultats obtenus sont donc conformes a ce que l'on attend de ce genre
de methodes.
Les methodes proposees jouent beaucoup sur l'a ectation des operations aux machines. Ceci explique tres certainement les bons resultats obtenus sur l'atelier 2. Les methodes fonctionnent d'autant mieux
que le nombre de machines dans les groupes est important. Il faudrait
donc adapter les methodes pour traiter des problemes ou les possibilites
d'a ectation sont plus restreintes. Dans ce cas, l'e ort de calcul pour
l'ordonnancement proprement dit devrait ^etre beaucoup plus important, en utilisant des procedures de type tabou pour les permutations
d'operations par exemple. Ceci serait possible en reduisant le temps de
calcul concernant l'a ectation et la rea ectation.
142
CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF
CONCLUSION
143
Conclusion
Prevoir pour une periode donnee l'organisation et la gestion d'un
atelier de production n'est pas chose facile. Parmi toutes les dicultes rencontrees, l'ordonnancement des jobs sur les di erentes machines
de l'atelier pose un probleme extr^emement complexe. Les algorithmes
developpes ces dernieres annees permettent de resoudre de facon tres
ecace des problemes de petite taille (dix jobs, dix machines). Mais,
des que le nombre de jobs devient trop important (de l'ordre de cent),
l'utilisation de regles de priorite prend le pas sur les autres methodes.
L'approche que nous avons developpee dans cette these a pour but
de proposer une alternative a l'utilisation des regles de priorite. L'objectif de cette approche est le calcul dans un temps le plus court possible d'une solution de qualite superieure a celle donnee par les regles.
Quelques methodes de resolution ont ete presentees, mais d'autres methodes pourront ^etre developpees a partir de cette approche. L'utilisation d'autres fonctions co^ut dans les procedures d'agregation permettrait de mieux tenir compte de la nature du probleme et de l'objectif
poursuivi (rapidite ou optimisation par exemple). Bien qu'en partie
developpe sur des problemes statiques (job-shop statique et deterministe et job-shop generalise), le principe d'agregation trouve sa pleine
justi cation sur les problemes dynamiques et reactifs.
Les machines actuelles sont de plus en plus polyvalentes et peu-
144
CONCLUSION
vent realiser, gr^ace a un ensemble d'outils, plusieurs types d'operations
qui etaient autrefois dediees a une seule. De ce fait, la tendance, pour
les ateliers de production modernes, va vers une reduction du nombre
des types de machines. La polyvalence de ces machines genere des problemes d'a ectation supplementaires. L'approche par agregation permet de gerer ces problemes d'a ectation et, le developpement de methodes de rea ectations multiples (plusieurs operations echangees entre
di erentes machines) permettrait d'ameliorer encore les methodes proposees.
Prevoir l'ordonnancement des operations dans un atelier de production est une chose, la realite de l'atelier en est souvent une autre. Le
deroulement de l'ordonnancement prevu est souvent dicile car assujetti a de nombreux aleas. Dans le modele de job-shop dynamique et
reactif que nous avons traite, deux types d'aleas etaient pris en compte :
l'arrivee aleatoire de jobs et l'arr^et momentanee de machines. Ce suivi
de production est gere par les methodes agregatives dont le but est de
conserver le maximum d'informations de l'ordonnancement previsionnel, tout en prenant en compte les contraintes induites par l'evenement
imprevu. La reaction est rapide et redonne immediatement un ordonnancement previsionnel optimise. Ce souci de vision a long terme de
l'ordonnancement previsionnel a permis une meilleure optimisation que
celle donnee par les regles de priorite utilisees.
Les di erents modeles d'ateliers qui ont servi de support au developpement de l'approche par agregation sont bien s^ur tres simpli es.
Un objectif interessant serait d'adapter les methodes sur des modeles
d'ateliers de production plus complexes tenant compte, par exemple,
de l'outillage des machines, des temps de changements de production,
etc. En n, l'adaptation du principe d'agregation pour gerer un atelier
de production industriel permettrait une reelle evaluation de l'approche
proposee.
145
Bibliographie
[1] Aarts (E. H. L.), Van Laarhoven (P. J. M.), Lenstra (J. K.) et Ulder (N. L. J.). { A computational study of local search algorithms
for job shop scheduling. ORSA Journal on Computing, vol. 6, n
2, 1994.
[2] Adams (J.), Balas (E.) et Zawack (D.). { The shifting bottleneck procedure for the job-shop scheduling. Management Science,
vol. 34, n 3, 1988.
[3] Adiri (I.) et Hefetz (N.). { An ecient algorithm for the twomachine, unit-time, job-shop schedule length problem. Mathematics of Operations Research, vol. 7, 1982.
[4] Aguilera (L. M.). { Ordonnancement de Production avec Co^uts de
Changements. { These de PhD, Institut National Polytechnique
de Grenoble, INPG, 1993.
[5] Aguilera (L. M.), Penz (B.), Song (H.) et Binder (Z.). { Design
and implementation of a scheduling software system. In : System, Man and Cybernetics Conference, IEEE/SMC. Le Touquet,
France, 1993.
[6] Akers (S. B.). { A graphical approach to production scheduling
problems. Operations Research, vol. 4, 1956.
[7] Appelgate (D.) et Cook (W.). { A computational study of jobshop scheduling. ORSA Journal on Computing, vol. 3, 1991.
[8] Ashour (S.), Chiu (K. Y.) et Moore (T. E.). { An optimal schedule
time of a job-shop like disjunctive graph. Networks, vol. 3, 1973.
146
BIBLIOGRAPHIE
[9] Baker (K. R.). { Introduction to Sequencing and Scheduling. {
Wiley, 1974.
[10] Balas (E.). { Machine sequencing via disjunctive graphs : An
implicit enumeration algorithm. Operations Research, vol. 17, n
6, 1969.
[11] Balas (E.). { On the facial structure of scheduling polyhedra.
Mathematical Programming Studies, vol. 24, 1985.
[12] Barker (J. R.) et McMahon (G. B.). { Scheduling the general
job-shop. Management Science, vol. 31, n 5, 1985.
[13] Bellman (R.). { Dynamic Programming. { Princeton University
Press, 1957.
[14] Bensana (E.). { Utilisation de Techniques d'Intelligence Arti cielle pour l'Ordonnancement d'Atelier. { These de PhD, Ecole
Nationale Superieure de l'Aeronautique et de l'Espace, 1987.
[15] Blackstone (J.), Phillips (D.) et Hogg (G.). { A state-of-theart survey of dispatching rules for manufacturing job-shop operations. International Journal of Production Research, vol. 20, n
1, 1982.
[16] Blazewicz (J.), Dror (M.) et Weglarz (J.). { Mathematical programming formulations for machine scheduling: A survey. European Journal of Operational Research, vol. 51, 1991.
[17] Blazewicz (J.), Ecker (K.), Schmidt (G.) et Weglarz (J.). { Scheduling in exible manufacturing systems. { Springer-Verlag, 1993.
[18] Blazewicz (J.), Eiselt (H.), Finke (G.), Laporte (G.) et Weglarz
(J.). { Scheduling tasks and vehicles in a exible manufacturing
system. International Journal of exible manufacturing systems,
vol. 4, n 1, 1991.
[19] Bouma (R. W.). { Job-Shop Scheduling : A Comparison of three
Enumeration Schemes in a Branch and Bound Approach. { These
de PhD, Faculty of Econometrics and Operations Research, Erasmus University, Rotterdam, 1982.
BIBLIOGRAPHIE
147
[20] Bowman (E. H.). { The schedule sequencing problem. Operations
Research, vol. 7, 1959.
[21] Brooks (G. H.) et White (C. R.). { An algorithm for nding
optimal or near optimal solution to the production scheduling
problem. Journal of Industrial Ingineering, vol. 16, n 1, 1965.
[22] Brucker (P.). { An ecient algorithm for the job-shop problem
with two jobs. Computing, vol. 40, 1988.
[23] Brucker (P.) et Jurisch (B.). { A new lower bound for the job-shop
scheduling problem. In : Second International Workshop on Project Management and Scheduling, EURO WG-PMS, Compiegne,
1990.
[24] Brucker (P.) et Schlie (R.). { Job-shop scheduling with multipropose machine. Computing, vol. 45, 1990.
[25] Carlier (J.). { Disjonctions dans les ordonnancements. RAIRO
Recherche Operationnelle, vol. 9, n 2, 1975.
[26] Carlier (J.). { One machine problem. European Journal of Operational Research, vol. 11, 1982.
[27] Carlier (J.). { Problemes d'Ordonnancements a contraintes de
Ressources : Algorithmes et Complexite. { These d'etat, Paris 6,
1984.
[28] Carlier (J.) et Pinson (E.). { An algorithm for solving the jobshop problem. Management Science, vol. 35, 1989.
[29] Carlier (J.) et Pinson (E.). { A practical use of jackson's preemptive schedule for solving the job-shop problem. Annals of Operations Research, vol. 26, 1990.
[30] Conway (R. W.), Maxwell (W. L.) et Miller (L. W.). { Theory of
scheduling. { Addison-Wesley, Reading, Mass, 1967.
[31] Cuninghame Green (R.). { Minimax Algebra. { Springer-Verlag,
Berlin, 1979.
148
BIBLIOGRAPHIE
[32] Davis (L.). { Job-shop scheduling with genetic algorithms. In :
International conference on Genetic Algorithms and their Applications, ed. par Grefenstette (J.). Carnegie Mellon University,
1985.
[33] Dell'Amico (M.) et Trubian (M.). { Applying tabu-search to
the job-shop scheduling problem. Annals of Operations Research,
vol. 41, 1993.
[34] Dorndorf (U.) et Pesch (E.). { Evolution based learning in a
job-shop scheduling environment. { avr 1992. Communication
Personnelle.
[35] Dridi (N.) et Proth (J. M.). { Ordonnancement des t^aches : une
methode basee sur la technologie de groupe. In : Proceedings of
the second international conference on production systems. 1987.
[36] Durand (A.). { Une methode optimale de traitement des contraintes disjonctives dans les problemes d'ordonnancement, application a la construction d'un barrage. R.I.R.O, vol. 1, n 3,
1967.
[37] Erschler (J.) et Esquirol (P.). { Decision-aid in job-shop scheduling : A knowledge based approach. In : IEEE Conference on
Robotics and Automation. San Fransisco, 1986.
[38] Erschler (J.), Fontan (G.) et Merce (C.). { Un nouveau concept de
dominance pour l'ordonnancement de travaux sur une machine.
RAIRO Recherche Operationnelle, vol. 19, n 1, 1985.
[39] Erschler (J.), Roubellat (F.) et Vernhes (J. P.). { Finding some
essential characteristics of the feasible solution for a scheduling
problem. Operations Research, vol. 24, 1976.
[40] Fadil (A.), Aguilera (L. M.), Binder (Z.) et Lemonias (H.). { Jobshop scheduling and production planning assignment. In : International Conference on Industrial Engineering and Production
Management. Mons, Belgique, 1993.
BIBLIOGRAPHIE
149
[41] Falkenauer (E.) et Bou ouix (S.). { A genetic algorithm for jobshop. In : IEEE International Conference on Robotics and Automation. Sacramento, California, 1991.
[42] Fisher (M. L.). { Optimal solution of scheduling problems using
lagrange multipliers : Part 1. Operations Research, vol. 21, 1973.
[43] Fisher (M. L.). { Optimal solution of scheduling problems using
lagrange multipliers : Part 2. In : Symposium on the Theory of
Scheduling and its Applications. { Springer, Berlin, 1973.
[44] Fisher (M. L.). { A dual algorithm for the one-machine scheduling
problem. Mathematical Programming, vol. 11, 1976.
[45] Fisher (M. L.). { The lagrangian relaxation method for solving integer programming problems. Management Science, vol. 27, 1981.
[46] Fisher (M. L.), Lageweg (B. J.), Lenstra (J. K.) et Rinnooy Kan
(A. H. G.). { Surrogate duality relaxation for job-shop scheduling.
Discrete Applied Mathematics, vol. 5, 1983.
[47] Florian (M.), McMahon (G.) et Trepant (P.). { An implicit enumeration algorithm for the machine sequencing problem. Management Science, vol. 17, n 12, 1971.
[48] French (S.). { Sequencing and Scheduling : An Introduction to the
Mathematics of the Job-Shop. { Ellis Horwood Limited, 1982.
[49] Garey (M. R.) et Johnson (D. S.). { Computers and Intractability :
A Guide to the Theory of NP-Completeness. { W. H. Freeman,
1979.
[50] Garey (M. R.), Johnson (D. S.) et Sethi (R.). { The complexity
of ow-shop and job-shop scheduling. Mathematics of Operations
Research, vol. 1, 1976.
[51] Gee (E. S.) et Smith (C. H.). { Selecting allowance policies for
improved job shop performance. International Journal of Production Research, vol. 31, n 8, 1993.
150
BIBLIOGRAPHIE
[52] Geo rion (A. M.). { Lagrangean relaxation for integer programming. Mathematical Programming Studies, vol. 3, 1974.
[53] Gier (R.) et Thompson (G. L.). { Algorithms for solving production scheduling problems. Operations Research, vol. 8, n 4,
1960.
[54] Glover (F.). { Tabu search, part 1. ORSA Journal on Computing,
vol. 1, n 3, 1989.
[55] Glover (F.). { Tabu search, part 2. ORSA Journal on Computing,
vol. 2, n 1, 1990.
[56] Gonzalez (T.) et Sahni (S.). { Flow-shop and job-shop scheduling :
Complexity and approximation. Operations Research, vol. 26,
1978.
[57] GOThA. { Les problemes d'ordonnancement. RAIRO-RO,
vol. 27, n 1, 1993.
[58] Grotschel (M.), Lovasz (L.) et Schrijver (A.). { Geometric Algorithms and Combinatorial Optimization. { Springer-Verlag, Berlin Heidelberg, 1988.
[59] Guinet (A.) et Legrand (M.). { Reduction of job-shop problems
to ow-shop problems with precedence constraints. { 1994. Communication personnelle.
[60] Hax (A. C.) et Candea (D.). { Production and inventory management. { Englewood Cli s, New Jersey, Practice-Hall, Inc,
1984.
[61] Held (M.) et Karp (R. M.). { A dynamic programming approach
to sequencing problems. Journal of SIAM, 1962.
[62] Holland (J. H.). { Adaptation in Natural and Arti cial Systems.
{ The University of Michigan Press, Ann Arbor, 1975.
[63] Hop eld (J.). { Neural networks and physical systems with emergent collective computational abilities. In : Proceeding of the National Academy of Science. 1969.
BIBLIOGRAPHIE
151
[64] Jackson (J. R.). { An extension of Johnson's results on job lot
scheduling. Naval Research Logistic Quarterly, vol. 3, n 3, 1956.
[65] Johnson (S. M.). { Optimal two and three stage production schedules. Naval research Logistic Quarterly, vol. 1, n 1, 1954.
[66] Karsiti (M. N.), Cruz (J. B.) et Mulligan (J. H.). { Simulation
studies of multilevel dynamic job shop scheduling using heuristic
dispatching rules. Journal of Manufacturing Systems, vol. 11, n
5, 1992.
[67] Kirkpatrick (S.). { Optimization by simulated annealing: Quantitative studies. Journal of Statistical Physics, vol. 34, n 5, 1984.
[68] Kirkpatrick (S.), Gelatt (C. D.) et Vecchi (M. P.). { Optimization
by simulated annealing. Science, no220, 1983.
[69] Kubiak (W.), Sethi (S.) et Sriskandarajah (C.). { An ecient
algorithm for a job-shop problem. { 1993. Communication Personnelle.
[70] Lageweg (B. J.), Lenstra (J. K.) et Rinnooy Kan (A. H. G.).
{ Job-shop scheduling by implicit enumeration. Management
Science, vol. 24, n 4, 1977.
[71] Lawler (E. L.), Lenstra (J. K.), Rinnooy Kan (A. H. G.) et
Shmoys (D.) (edite par). { The Traveling Salesman Problem:
A Guided Tour of Combinatorial Optimization. { John Wiley &
Sons, 1987.
[72] Lawler (E. L.) et Wood (D. E.). { Branch and bound methods :
A survey. Operations Research, vol. 14, 1966.
[73] Le Gall (A.) et Roubellat (F.). { Caracterisation d'un ensemble
d'ordonnancements avec contraintes de ressources de type cumulatif. APII, vol. 26, 1992.
[74] Lemonias (H.). { Ordonnancement d'Atelier a T^aches : Une Approche par Decomposition. { These de PhD, Institut National
Polytechnique de Grenoble, 1991.
152
BIBLIOGRAPHIE
[75] Liao (C. J.) et You (C. T.). { An improved formulation for the
job-shop scheduling problem. Journal of Operational Research Society, vol. 43, n 11, 1992.
[76] Lopez (P.), Erschler (J.) et Esquirol (P.). { Ordonnancement de
t^aches sous contraintes : une approche energetique. APII, vol. 26,
1992.
[77] Lourenco (H. R.). { Local optimization and the job-shop scheduling problem. { 1994. Communication personnelle.
[78] Manne (A. S.). { On the job-shop scheduling problem. Operations
Research, vol. 8, 1960.
[79] Matsuo (H.), Suh (C. J.) et Sullivan (R. S.). { A Controlled Search
Simulated Annealing Method for the General Job-Shop Scheduling
Problem. { Rapport technique n 03-44-88, Graduate School of
Business, University of Texas, Austin, 1988.
[80] Mc Culloch (W. S.) et Pitts (W. H.). { A logical calculus of ideas
immanent in nervous activity. Bulletin of Mathematical Biophysics, vol. 3, 1943.
[81] Mitten (L. G.). { Branch and bound methods : General formulation and properties. Operations Research, vol. 18, 1970.
[82] Muth (J. F.) et Thompson (G. L.). { Industrial Scheduling. {
Prentice Hall, Englewood Cli s, New Jersey, 1963.
[83] Nakano (R.) et Yamada (T.). { Conventional genetic algorithm
for job-shop problems. In : Conference on Genetic Algorithms.
San Diego, California, 1991.
[84] Panwalkar (S. S.) et Iskander (W.). { A survey of scheduling
rules. Operations Research, vol. 25, n 1, 1977.
[85] Papadimitriou (C. H.) et Steiglitz (K.). { Combinatorial Optimization : Algorithms and Complexity. { Prentice Hall, Englewood
Cli s, N.J., 1982.
BIBLIOGRAPHIE
153
[86] Penz (B.) et Dupont (L.). { New heuristics for the job-shop
problem. In : International Conference on industrial Engineering
and Production Management. Mons, Belgique, 1993.
[87] Pinson (E.). { Le Probleme de Job-Shop. { These de PhD, Universite Pierre et Marie Curie, 1988.
[88] Portmann (M.-C.). { Methodes de decomposition spatiale et temporelle en ordonnancement de la production. APII, vol. 22, 1988.
[89] Potts (C. N.). { Analysis of a linear programming heuristic for
scheduling unrelated parallel machines. Discrete Applied Mathematics, vol. 10, 1985.
[90] Queyranne (M.). { Structure of a simple scheduling polyhedron.
Mathematical Programming, vol. 58, 1993.
[91] Queyranne (M.) et Wang (Y.). { Single-machine scheduling polyhedra with precedence constraints. Mathematics of Operations
Research, vol. 16, n 1, 1991.
[92] Raman (N.) et Talbot (F. B.). { The job-shop tardiness problem :
A decomposition approach. European Journal of Operational Research, vol. 69, 1993.
[93] Ramasesh (R.). { Dynamic job-shop scheduling : A survey of simulation research. International Journal of Management Science,
vol. 18, n 1, 1990.
[94] Rechenberg (I.). { Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. { Problemata, 1973, FrommannHolzboog edition.
[95] Rinnooy Kan (A. H. G.). { Machine Scheduling Problem : Classi cation, Complexity and Computations. { Nyho , 1976.
[96] Rogers (R. V.) et White (K. P.). { Algebraic, mathematical programming and network models of the deterministic job-shop scheduling problem. IEEE Transactions on Systems, Man, and Cybernetics, vol. 21, n 3, 1991.
154
BIBLIOGRAPHIE
[97] Rosenblatt (F.). { Perceptron simulation experiment. In : Proceeding of the IRE. 1960.
[98] Roy (B.) et Sussman (B.). { Les Problemes d'ordonnancement
avec contraintes disjonctives. { Rapport technique n D. S. 9,
SEMA, Paris, France, 1964.
[99] Schwefel (H.-P.). { Numerische Optimierung von ComputerModellen mittels der Evolutionsstrategie. { Birkhauser Verlag,
1977.
[100] Silver (E. A.), Vidal (V. V.) et de Werra (D.). { A tutorial
on heuristic methods. European Journal of Operational Research,
vol. 5, 1980.
[101] Strusevitch (V. A.). { Two machine super-shop scheduling problem. Journal of Operational Research Society, vol. 42, n 6, 1991.
[102] Tahboub (K. K.) et Odrey (N. G.). { A dioid algebra approach
for modeling the job-shop scheduling problem. { 1994. Communication Personnelle.
[103] Taillard (E.). { Parallel taboo search techniques for the job-shop
scheduling problem. ORSA Journal on Computing, vol. 6, n 2,
1994.
[104] Van Laarhoven (P. J. M.). { Theoretical and Computational Aspects of Simulated Annealing. { These de PhD, Erasmus University, Rotterdam, 1988.
[105] Van Laarhoven (P. J. M.) et Aarts (E. H. L.). { Simulated Annealing : Theory and Applications. { Reidel, Dordrecht, The Netherlands, 1987.
[106] Van Laarhoven (P. J. M.), Aarts (E. H. L.) et Lenstra (J. K.).
{ Job-shop scheduling by simulated annealing. Operations Research, vol. 40, n 1, 1992.
[107] Vancheeswaran (R.) et Townsend (M. A.). { Two-stage heuristic procedure for scheduling job-shops. Journal of Manufacturing
Systems, vol. 12, n 4, 1993.
BIBLIOGRAPHIE
155
[108] Vepsalainen (A. P. J.) et Morton (T. E.). { Priority rules for
job shops with weighted tardiness costs. Management Science,
vol. 33, n 8, 1987.
[109] Vig (M. M.) et Dooley (K. J.). { Dynamic rules for due-date assignment. International Journal of Production Research, vol. 29,
n 7, 1991.
[110] Wagner (H. M.). { An integer linear programming model for
machine scheduling. Naval Research Logistic Quarterly, vol. 6,
1959.
[111] Wein (L. M.) et B. (C. P.). { A broader view of the job-shop
scheduling problem. Management Science, vol. 38, n 7, 1992.
[112] Wein (L. M.) et Ou (J.). { The impact of processing time
knowledge on dynamic job-shop scheduling. Management Science,
vol. 37, n 8, 1991.
[113] Werner (F.) et Winkler (A.). { Insertion techniques for the heuristic solution of the job-shop problem. { 1991. Communication
Personnelle.
[114] Widmer (M.). { Job shop scheduling with tooling constraints: a
tabu search approach. Journal of the Operational Research Society, vol. 42, n 1, 1991.
[115] Zhang (C. S.), Yan (P. F.) et Chang (T.). { Solving job-shop
scheduling problem with priority using neural network. { 1991.
Communication personnelle.
[116] Zhou (D. N.), Cherkassky (V.), Baldwin (T. R.) et Olson (D. E.).
{ A neural network approach to job-shop scheduling. IEEE Transactions on Neural Networks, vol. 2, n 1, 1991.

1227350

1228573

1227365

1227092

1227327

1227243

1229264

1227329

1227270

1227407

1227268

1227218

1228078