Production Scheduling

The performance of an company depends both on its technological expertise and its managerial and organizational effectiveness. Production management is an important part of the process for manufacturing firms. The organization of production relies in general on the implementation of a certain number of basic functions, among which the scheduling function plays an essential role. This title presents recently developed methods for resolving scheduling issues. The basic concepts and the methods of production scheduling are introduced and advanced techniques are discussed, providing readers with a comprehensive and accessible guide to employing this process.

Table of Contents:
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