Serial Number:

Julien Bidot

Description

Niveau: Supérieur

• dissertation

Serial Number: 2297 A General Framework Integrating Techniques for Scheduling under Uncertainty by Julien Bidot Automated-production engineer, Ecole Nationale d'Ingénieurs de Tarbes A dissertation presented at Ecole Nationale d'Ingénieurs de Tarbes in conformity with the requirements for the degree of Doctor of Philosophy of Institut National Polytechnique de Toulouse, France Specialty: Industrial Systems 28 November 2005 Submitted to the following committee members: Chairman: Gérard Verfaillie ONERA, France Reviewer: Amedeo Cesta I.S.T.C.–C.N.R., Italy Reviewer: Erik L. Demeulemeester Katholieke Universiteit Leuven, Belgium Reviewer and invited member: Eric Sanlaville LIMOS–Université Blaise Pascal, France Advisor: Bernard Grabot L.G.P.–ENIT, France Academical mentor: Thierry Vidal L.G.P.–ENIT, France Industrial mentor: Philippe Laborie ILOG S.A., France Invited member: J. Christopher Beck University of Toronto, Canada

• doctoral consortium


• groupe de recherche sur l'ordonnancement théorique


• integrating techniques


• automated-production engineer


• always been


• short-time period

Sujets

• Dissertation
• De Backer
• Comment
• Blythe
• Le Pape
• Massimino
• Perron

Informations

• Publié par: profil-nechor-2012
• Nombre de lectures: 31
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Serial Number: 2297
A General Framework Integrating
Techniques for Scheduling under Uncertainty
by
Julien Bidot
Automated-production engineer, Ecole Nationale d’Ingénieurs de Tarbes
A dissertation presented at Ecole Nationale d’Ingénieurs de Tarbes
in conformity with the requirements
for the degree of Doctor of Philosophy
of Institut National Polytechnique de Toulouse, France
Specialty: Industrial Systems
28 November 2005
Submitted to the following committee members:
Chairman: Gérard Verfaillie ONERA, France
Reviewer: Amedeo Cesta I.S.T.C.–C.N.R., Italyer: Erik L. Demeulemeester Katholieke Universiteit Leuven, Belgium
Reviewer and invited member: Eric Sanlaville LIMOS–Université Blaise Pascal, France
Advisor: Bernard Grabot L.G.P.–ENIT, France
Academical mentor: Thierry Vidal L.G.P France
Industrial mentor: Philippe Laborie ILOG S.A., France
Invited member: J. Christopher Beck University of Toronto, CanadaAcknowledgments
Many people have helped me directly or indirectly to achieve this dissertation, making it
better than it otherwise would have been.
Thanks to Philippe Laborie for his guidance, insight, kindness, and availability. It has
been very pleasant to work with him at ILOG. In particular, he has been of great help
to implement algorithms.
Thanks to Thierry Vidal for his constant support, helpful suggestions, and kindness.
He has always trusted me and I have been quite free to organize as I have wanted. I have
appreciated this even if freedom has sometimes meant complex decisions to make.
Thanks to Chris Beck for guiding me and giving me advices all along my Ph.D. thesis
even if he has not always been physically close to me. He has been a precious mentor
during my first six months at ILOG and during my visit at Cork Constraint Computation
Centre (4C).
Thanks to Jérôme Rogerie for his participation in the achievement of this research
work, in particular, during our investigation of potential industrial applications.
I thank Amedeo Cesta, Erik Demeulemeester, and Eric Sanlaville for reviewing my
dissertation given a short-time period. I also thank Gérard Verfaillie for taking part of
my jury.
Thanks to my advisor, Bernard Grabot, for his sustained encouragement. I also thank
the members of the research group “Production Automatisée” for helping me during the
different time periods I have been working in Laboratoire Génie de Production (L.G.P.).
Thanks to Daniel Noyes and the administrative staff of L.G.P. for having hosted me
several times during my Ph.D. thesis.
Thanks to Eugene Freuder and all the members of 4C. They have been hosting me
for three months providing me a stimulating environment contributing to the outcome of
my dissertation.
ThankstoJeremyFrank,mymentorattheCP’03doctoralprogramwhomaderelevant
remarks about my work. Thanks also to Jim Blythe who was my mentor at the ICAPS’03
doctoral consortium.
Thanks to Hassan Aït-Kaci, Emilie Danna, Bruno De Backer, Vincent Furnon, Daniel
Godard, Emmanuel Guéré, Pascal Massimino, Claude Le Pape, Pierre Lopez, Wim Nui-
jten, Laurent Perron, Jean-Charles Régin, Francis Sourd, the members of the French re-
searchgroup“flexibilité” ofGOThA(Groupederecherchesurl’OrdonnancementThéorique
et Appliqué), and many others for their help and wealthy ideas.
Special thanks go to the members of my family for their financial, intellectual, and
emotional support throughout this long and challenging process. Last and not least, I
thank my girlfriend, Hélène, for her love, patience, and encouragement.
Encore une dernière fois, merci à toutes et à tous.
iiiContents
Acknowledgments iii
List of Tables ix
List of Figures xi
Introduction 1
1 State of the Art 5
1.1 What We Do Not Review . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Deterministic Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Task Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.3 Bridging the Gap Between Task Planning and Scheduling . . . . . . 8
1.2.4 Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.5 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 Non-deterministic Domains. . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.1 Uncertainty Sources . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.3 Uncertainty Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3.4 Temporal Extensions of CSPs . . . . . . . . . . . . . . . . . . . . . 24
1.3.5 Task Planning under Uncertainty . . . . . . . . . . . . . . . . . . . 25
1.3.6 Scheduling under Uncertainty . . . . . . . . . . . . . . . . . . . . . 27
1.4 Summary and General Comments . . . . . . . . . . . . . . . . . . . . . . . 35
2 General Framework 37
2.1 Definitions and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.2 Revision Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.2.1 Generalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.2.2 Examples of Revision Techniques in Task Planning and Scheduling 42
2.2.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.3 Proactive Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.3.1 Generalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.3.2 Examples of Proactive Techniques in Task Planning and Scheduling 44
2.3.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.4 Progressive Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.4.1 Generalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.4.2 Examples of Progressive Techniques in Task Planning and Scheduling 48
vvi CONTENTS
2.4.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.5 Mixed Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.5.1 Generalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.5.2 Examples of Mixed Techniques in Task Planning and Scheduling . . 52
2.6 Summary and General Comments . . . . . . . . . . . . . . . . . . . . . . . 53
3 Application Domain 55
3.1 Project Management and Project Scheduling . . . . . . . . . . . . . . . . . 55
3.2 Construction of Dams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.2.1 General Description . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.2.2 Uncertainty Sources . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.2.3 An Illustrative Example . . . . . . . . . . . . . . . . . . . . . . . . 57
3.3 General Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4 Theoretical Model 61
4.1 Model Expressivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.2.1 Scheduling Problem and Schedule Model . . . . . . . . . . . . . . . 64
4.2.2 Generation and Execution Model . . . . . . . . . . . . . . . . . . . 69
4.3 Schedule Generation and Execution . . . . . . . . . . . . . . . . . . . . . . 72
4.4 A Toy Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.5 Summary and General Comments . . . . . . . . . . . . . . . . . . . . . . . 79
5 Experimental System 81
5.1 Scheduling Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.1.1 Costs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.2 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.2.1 Solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.2.2 Controller . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.2.3 World Simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2.4 Resolution Techniques . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2.5 Experimental Parameters and Indicators . . . . . . . . . . . . . . . 89
5.3 Revision-Proactive Approach . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.3.1 Revision Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.3.2 Proactive Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.3.3 Experimental Studies . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.4 Progressive-Proactive Approach . . . . . . . . . . . . . . . . . . . . . . . . 99
5.4.1 When to Try Extending the Current Partial Flexible Schedule? . . 100
5.4.2 How to Select the Subset of Operations to Be Allocated and Ordered?101
5.4.3 How to Allocate and Order the Subset of Operations? . . . . . . . . 105
5.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.6 Summary and General Comments . . . . . . . . . . . . . . . . . . . . . . . 107
6 Future Work 109
6.1 Prototype . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
6.1.1 Experimental