Production Scheduling

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-José 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
Gérard BEL and Jean-Bernard CAVAILLÉ

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 Hervé 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 NÉRON 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 Guéret 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, Hélène 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