Preface xiii
Chapter 1. Statement of Production Scheduling 1
François ROUBELLAT and Pierre LOPEZ
Chapter 2. Basic Concepts and Methods in Production Scheduling 5
Patrick ESQUIROL and Pierre LOPEZ
2.1. Introduction 5
2.2. Basic scheduling concepts 6
2.2.1. Tasks 6
2.2.2. Resources 7
2.2.3. Modeling 7
2.2.4. Resolution methods 12
2.2.5. Representation of solutions 15
2.3. Project scheduling 15
2.3.1. Modeling 16
2.3.2. Resolution 17
2.4. Shop scheduling 20
2.4.1. Introduction 20
2.4.2. Basic model 20
2.4.3. One-machine problem 21
2.4.4. Parallel machine problems 22
2.4.5. Flow shop 24
2.4.6. Job shop 26
2.5. Conclusion 29
2.6. Bibliography 29
Chapter 3. Metaheuristics and Scheduling 33
Marino WIDMER, Alain HERTZ and Daniel COSTA
3.1. Introduction 33
3.2. What is a combinatorial optimization problem? 34
3.3. Solution methods for combinatorial optimization problems 34
3.4. The different metaheuristic types 36
3.4.1. The constructive approach 36
3.4.2. Local search approach 37
3.4.3. The evolutionary approach 48
3.4.4. The hybrid approach 54
3.5. An application example: job shop scheduling with tooling constraints 55
3.5.1. Traditional job shop modeling 57
3.5.2. Comparing both types of problems 59
3.5.3. Tool switching 60
3.5.4. TOMATO algorithm 61
3.6. Conclusion 62
3.7. Bibliography 63
Chapter 4. Genetic Algorithms and Scheduling 69
Marie-Claude PORTMANN and Antony VIGNIER
4.1. Introduction 69
4.1.1. Origin of genetic algorithms 69
4.1.2. General principles of genetic algorithms 69
4.1.3. Schema theorem 72
4.1.4. Chapter presentation 73
4.2. One-machine problems 73
4.2.1. Example 1: total time and setup times 73
4.2.2. Example 2: sum of weighted tardiness 79
4.2.3. Example 3: sum of weighted tardiness and setup times 83
4.3. Job shop problems 85
4.4. Hybrid flow shop 89
4.4.1. Specific case: one-stage total duration problem 89
4.4.2. General case: k stages total duration problem 93
4.5. Hybrid genetic algorithms 99
4.5.1. Hybridization with other metaheuristics 99
4.5.2. Hybridization with combinatorial optimization methods 100
4.6. Conclusion 100
4.7. Bibliography 101
Chapter 5. Constraint Propagation and Scheduling 103
Patrick ESQUIROL, Pierre LOPEZ and Marie-Jose HUGUET
5.1. Introduction 103
5.1.1. Problem and chapter organization 103
5.1.2. Constraint propagation 104
5.1.3. Scheduling problem statement 106
5.1.4. Notations 106
5.2. Time constraint propagation 107
5.2.1. Introduction 107
5.2.2. Definition 107
5.2.3. Simple temporal problems 108
5.2.4. General temporal problems 110
5.3. Resource constraint propagation 112
5.3.1. Characterization of conflicts 113
5.3.2. Deductions based on critical sets and MDSs 117
5.3.3. Deductions based on the energetic balance 122
5.4. Integration of propagation techniques in search methods 127
5.4.1. General improvement techniques of chronological backtracking 128
5.4.2. Heuristics for variable and value ordering 129
5.4.3. Strategies for applying propagation rules 130
5.4.4. Use of a backtracking algorithm 130
5.5. Extensions 131
5.5.1. Preemptive problems 131
5.5.2. Consideration of allocation constraints 132
5.6. Conclusion 133
5.7. Bibliography 134
Chapter 6. Simulation Approach 139
Gerard BEL and Jean-Bernard CAVAILLE
6.1. Introduction 139
6.2. Heuristic resolution (greedy) procedures 140
6.2.1. Limits of the basic method 140
6.2.2. Manual development procedures of projected scheduling 141
6.2.3. Job placement procedure 141
6.2.4. Example 142
6.2.5. Operation placement procedure 143
6.3. Simulation approach 145
6.3.1. Discrete event models 145
6.3.2. Discrete event simulation 148
6.4. Using the simulation approach for the resolution of a scheduling problem 151
6.4.1. Determination of projected schedule 151
6.4.2. Dynamic scheduling 153
6.4.3. Using simulation for decision support 153
6.5. Priority rules 155
6.5.1. Introduction 155
6.5.2. Description of priority rules 155
6.5.3. Experimentation conditions 157
6.5.4. Main results 160
6.6. Information technology tools 162
6.6.1. Scheduling software 162
6.6.2. Simulation languages 163
6.7. Conclusion 163
6.8. Bibliography 164
Chapter 7. Cyclic Production Scheduling 167
Jean-Claude GENTINA, Ouajdi KORBAA and Herve CAMUS
7.1. Introduction 167
7.2. Cyclic scheduling problem classifications 169
7.2.1. Electroplating robot problem (HSP) 169
7.2.2. FMS cyclic scheduling problem 169
7.3. Problem positioning 173
7.4. Presentation of tools used 175
7.4.1. Modeling using Petri nets 175
7.4.2. Dual Gantt chart 177
7.4.3. Resource availability interval 178
7.4.4. Operation placement policies in cyclic scheduling 180
7.5. Algorithm principle 183
7.6. Extension of cyclic strategies 185
7.7. Conclusion and prospects 188
7.8. Bibliography 189
Chapter 8. Hoist Scheduling Problem 193
Christelle BLOCH, Marie-Ange MANIER, Pierre BAPTISTE, and Christophe VARNIER
8.1. Introduction 193
8.2. Physical system and production constraints 194
8.2.1. Tanks 195
8.2.2. Hoists 196
8.2.3. Carriers 198
8.3. Hoist scheduling problems 198
8.3.1. General presentation 198
8.3.2. Static scheduling problems 199
8.3.3. Dynamic scheduling problems 200
8.3.4. Classification and brief state of the art 201
8.4. Modeling and resolution 205
8.4.1. Notations 205
8.4.2. CHSP resolution: basic problem 206
8.4.3. Extensions 218
8.4.4. Multi-product case 220
8.5. Resolution of other problems presented 220
8.5.1. Optimization of temporary phases 220
8.5.2. Job scheduling at line arrival 221
8.5.3. DHSP resolution 222
8.5.4. RHSP resolution 224
8.6. Conclusion 224
8.7. Bibliography 225
8.8. Appendix: Notation 230
Chapter 9. Shop Scheduling with Multiple Resources 233
Jean-Charles BILLAUT, Jacques CARLIER, Emmanuel NERON and Antoine OLIVER
9.1. Introduction 233
9.2. Hybrid flow shop scheduling problem 234
9.2.1. A few manufacturing cases 235
9.2.2. State of the art survey 237
9.2.3. Notation and mathematical model 238
9.2.4. Heuristic canonical methods 239
9.2.5. An exact method 241
9.2.6. Extensions of the traditional hybrid flow shop problem 247
9.3. RCPSP: presentation and state of the art 248
9.3.1. A simple model including shop problems 249
9.3.2. Main exact methods for the RCPSP 250
9.3.3. Results and fields of application of methods 258
9.4. Conclusion 260
9.5. Bibliography 261
Chapter 10. Open Shop Scheduling 271
Christian PRINS
10.1. General overview 271
10.2. The open shop problem 272
10.2.1. Open shop in relation to other shop problems 272
10.2.2. An example 273
10.2.3. A few real open shop examples 274
10.3. Complexity of open shop problems 275
10.3.1. Overview 275
10.3.2. Polynomial geometric methods 275
10.3.3. The polynomial m = 2 case 276
10.3.4. The boundary m = 3 case 277
10.3.5. Special open shops 277
10.4. The preemptive case (operations executable multiple times) 277
10.4.1. Gonzalez and Sahni algorithm 277
10.4.2. An example 278
10.5. Simple heuristics (excluding metaheuristics) 280
10.5.1. Introduction 280
10.5.2. Performance guarantees 281
10.5.3. List heuristics 281
10.5.4. Matching heuristics 283
10.6. The disjunctive model and shop problems 285
10.6.1. Disjunctive model review 285
10.6.2. Disjunctive model and shop problems 286
10.6.3. Example of open shop disjunctive model 286
10.6.4. Disjunctive model properties 287
10.7. Metaheuristics for the open shop 288
10.7.1. Known traditional neighborhoods for job shop 288
10.7.2. Tabu search and simulated annealing methods for open shop. 288
10.7.3. Population-based algorithms and neural networks 288
10.8. Exact methods for open shop 289
10.8.1. Brucker et al. branch-and-bound method 289
10.8.2. More recent improvements 290
10.9. Algorithm comparison 290
10.9.1. Uniform processing times 290
10.9.2. Taillard examples 292
10.9.3. Difficult Brucker and Gueret and Prins tests 293
10.10. Open shop problems in satellite telecommunications 294
10.10.1. TDMA systems principle 294
10.10.2. Pure open shop cases 295
10.10.3. Preemptive case complications 296
10.10.4. Generalization of the basic open shop 296
10.11. Conclusion 297
10.12. Bibliography 297
Chapter 11. Scheduling Under Flexible Constraints and Uncertain Data: The Fuzzy Approach 301
Didier DUBOIS, Helene FARGIER and Philippe FORTEMPS
11.1. Introduction 301
11.2. Basic notions on the fuzzy approach to uncertainty and constraints 303
11.2.1. Possibility theory 303
11.2.2. Fuzzy arithmetic 305
11.2.3. Fuzzy interval comparison 306
11.2.4. Possibilistic utility 307
11.3. Scheduling under flexible constraints 308
11.3.1. The fuzzy PERT problem: flexible constraints 309
11.3.2. Limited resources: flexible constraints and fuzzy rules 314
11.4. Scheduling with ill-known execution times 317
11.4.1. Critical paths under ill-known execution times: difficulties 318
11.4.2. Critical paths with interval execution times 320
11.4.3. Critical paths with fuzzy execution times 322
11.4.4. Limited resources: approach by fuzzy interval comparison 323
11.5. Flexible constraint scheduling and ill-known task execution times 325
11.6. Conclusion: the potential contribution of possibility theory in scheduling 328
11.7. Bibliography 329
Chapter 12. Real-Time Workshop Scheduling 333
Christian ARTIGUES and François ROUBELLAT
12.1. Introduction 333
12.2. Interest and problem positioning 333
12.2.1. The context of on demand production workshops 333
12.2.2. The different approaches to real-time workshop scheduling 334
12.2.3. An original approach 337
12.3. Modeling and dynamic of scheduling problem considered 338
12.3.1. Resources 339
12.3.2. Production operations 340
12.3.3. Setup operations 341
12.4. Decisions, events and constraints 345
12.5. Models for off-line and on-line scheduling 346
12.5.1. Groups of interchangeable operations 347
12.5.2. Operation-on-node graphs 348
12.5.3. Generic graph methods 353
12.6. Off-line scheduling method 355
12.6.1. Gradual construction of a feasible initial sequence of groups 355
12.6.2. Search for eligibility by iterative improvement of the sequence 356
12.7. Real-time scheduling method, interactive decision support system 356
12.7.1. Decision support system organization 357
12.7.2. Eligibility control 358
12.7.3. Decision support in an eligible sequence context 359
12.7.4. Decision support for retrieving eligibility 360
12.7.5. Decision and negotiation support between decision centers outside the planned context 360
12.8. Conclusion 361
12.9. Bibliography 362
List of Authors 367
Index 371
