Production Scheduling

Pierre Lopez is a researcher within the Laboratory for Analysis and Architecture of Systems at the French National Center for Scientific Research (LAAS-CNRS). He is also head of the MOGISA group (Modeling, Optimization and Integrated Management of Systems of Activities). François Roubellat is also a researcher within LAAS-CNRS. His research is focused on Decision Support Systems for activity scheduling with resource constraints.

• Preface xiiiChapter 1. Statement of Production Scheduling 1François ROUBELLAT and Pierre LOPEZChapter 2. Basic Concepts and Methods in Production Scheduling 5Patrick ESQUIROL and Pierre LOPEZ2.1. Introduction 52.2. Basic scheduling concepts 62.2.1. Tasks 62.2.2. Resources 72.2.3. Modeling 72.2.4. Resolution methods 122.2.5. Representation of solutions 152.3. Project scheduling 152.3.1. Modeling 162.3.2. Resolution 172.4. Shop scheduling 202.4.1. Introduction 202.4.2. Basic model 202.4.3. One-machine problem 212.4.4. Parallel machine problems 222.4.5. Flow shop 242.4.6. Job shop 262.5. Conclusion 292.6. Bibliography 29Chapter 3. Metaheuristics and Scheduling 33Marino WIDMER, Alain HERTZ and Daniel COSTA3.1. Introduction 333.2. What is a combinatorial optimization problem? 343.3. Solution methods for combinatorial optimization problems 343.4. The different metaheuristic types 363.4.1. The constructive approach 363.4.2. Local search approach 373.4.3. The evolutionary approach 483.4.4. The hybrid approach 543.5. An application example: job shop scheduling with tooling constraints 553.5.1. Traditional job shop modeling 573.5.2. Comparing both types of problems 593.5.3. Tool switching 603.5.4. TOMATO algorithm 613.6. Conclusion 623.7. Bibliography 63Chapter 4. Genetic Algorithms and Scheduling 69Marie-Claude PORTMANN and Antony VIGNIER4.1. Introduction 694.1.1. Origin of genetic algorithms 694.1.2. General principles of genetic algorithms 694.1.3. Schema theorem 724.1.4. Chapter presentation 734.2. One-machine problems 734.2.1. Example 1: total time and setup times 734.2.2. Example 2: sum of weighted tardiness 794.2.3. Example 3: sum of weighted tardiness and setup times 834.3. Job shop problems 854.4. Hybrid flow shop 894.4.1. Specific case: one-stage total duration problem 894.4.2. General case: k stages total duration problem 934.5. Hybrid genetic algorithms 994.5.1. Hybridization with other metaheuristics 994.5.2. Hybridization with combinatorial optimization methods 1004.6. Conclusion 1004.7. Bibliography 101Chapter 5. Constraint Propagation and Scheduling 103Patrick ESQUIROL, Pierre LOPEZ and Marie-José HUGUET5.1. Introduction 1035.1.1. Problem and chapter organization 1035.1.2. Constraint propagation 1045.1.3. Scheduling problem statement 1065.1.4. Notations 1065.2. Time constraint propagation 1075.2.1. Introduction 1075.2.2. Definition 1075.2.3. Simple temporal problems 1085.2.4. General temporal problems 1105.3. Resource constraint propagation 1125.3.1. Characterization of conflicts 1135.3.2. Deductions based on critical sets and MDSs 1175.3.3. Deductions based on the energetic balance 1225.4. Integration of propagation techniques in search methods 1275.4.1. General improvement techniques of chronological backtracking 1285.4.2. Heuristics for variable and value ordering 1295.4.3. Strategies for applying propagation rules 1305.4.4. Use of a backtracking algorithm 1305.5. Extensions 1315.5.1. Preemptive problems 1315.5.2. Consideration of allocation constraints 1325.6. Conclusion 1335.7. Bibliography 134 Chapter 6. Simulation Approach 139Gérard BEL and Jean-Bernard CAVAILLÉ6.1. Introduction 1396.2. Heuristic resolution (greedy) procedures 1406.2.1. Limits of the basic method 1406.2.2. Manual development procedures of projected scheduling 1416.2.3. Job placement procedure 1416.2.4. Example 1426.2.5. Operation placement procedure 1436.3. Simulation approach 1456.3.1. Discrete event models 1456.3.2. Discrete event simulation 1486.4. Using the simulation approach for the resolution of a scheduling problem 1516.4.1. Determination of projected schedule 1516.4.2. Dynamic scheduling 1536.4.3. Using simulation for decision support 1536.5. Priority rules 1556.5.1. Introduction 1556.5.2. Description of priority rules 1556.5.3. Experimentation conditions 1576.5.4. Main results 1606.6. Information technology tools 1626.6.1. Scheduling software 1626.6.2. Simulation languages 1636.7. Conclusion 1636.8. Bibliography 164Chapter 7. Cyclic Production Scheduling 167Jean-Claude GENTINA, Ouajdi KORBAA and Hervé CAMUS7.1. Introduction 1677.2. Cyclic scheduling problem classifications 1697.2.1. Electroplating robot problem (HSP) 1697.2.2. FMS cyclic scheduling problem 1697.3. Problem positioning 1737.4. Presentation of tools used 1757.4.1. Modeling using Petri nets 1757.4.2. Dual Gantt chart 1777.4.3. Resource availability interval 1787.4.4. Operation placement policies in cyclic scheduling 1807.5. Algorithm principle 1837.6. Extension of cyclic strategies 1857.7. Conclusion and prospects 1887.8. Bibliography 189Chapter 8. Hoist Scheduling Problem 193Christelle BLOCH, Marie-Ange MANIER, Pierre BAPTISTE, and Christophe VARNIER8.1. Introduction 1938.2. Physical system and production constraints 1948.2.1. Tanks 1958.2.2. Hoists 1968.2.3. Carriers 1988.3. Hoist scheduling problems 1988.3.1. General presentation 1988.3.2. Static scheduling problems 1998.3.3. Dynamic scheduling problems 2008.3.4. Classification and brief state of the art 2018.4. Modeling and resolution 2058.4.1. Notations 2058.4.2. CHSP resolution: basic problem 2068.4.3. Extensions 2188.4.4. Multi-product case 2208.5. Resolution of other problems presented 2208.5.1. Optimization of temporary phases 2208.5.2. Job scheduling at line arrival 2218.5.3. DHSP resolution 2228.5.4. RHSP resolution 2248.6. Conclusion 2248.7. Bibliography 2258.8. Appendix: Notation 230Chapter 9. Shop Scheduling with Multiple Resources 233Jean-Charles BILLAUT, Jacques CARLIER, Emmanuel NÉRON and Antoine OLIVER9.1. Introduction 2339.2. Hybrid flow shop scheduling problem 2349.2.1. A few manufacturing cases 2359.2.2. State of the art survey 2379.2.3. Notation and mathematical model 2389.2.4. Heuristic canonical methods 2399.2.5. An exact method 2419.2.6. Extensions of the traditional hybrid flow shop problem 2479.3. RCPSP: presentation and state of the art 2489.3.1. A simple model including shop problems 2499.3.2. Main exact methods for the RCPSP 2509.3.3. Results and fields of application of methods 2589.4. Conclusion 2609.5. Bibliography 261Chapter 10. Open Shop Scheduling 271Christian PRINS10.1. General overview 27110.2. The open shop problem 27210.2.1. Open shop in relation to other shop problems 27210.2.2. An example 27310.2.3. A few real open shop examples 27410.3. Complexity of open shop problems 27510.3.1. Overview 27510.3.2. Polynomial geometric methods 27510.3.3. The polynomial m = 2 case 27610.3.4. The boundary m = 3 case 27710.3.5. Special open shops 27710.4. The preemptive case (operations executable multiple times) 27710.4.1. Gonzalez and Sahni algorithm 27710.4.2. An example 27810.5. Simple heuristics (excluding metaheuristics) 28010.5.1. Introduction 28010.5.2. Performance guarantees 28110.5.3. List heuristics 28110.5.4. Matching heuristics 28310.6. The disjunctive model and shop problems 28510.6.1. Disjunctive model review 28510.6.2. Disjunctive model and shop problems 28610.6.3. Example of open shop disjunctive model 28610.6.4. Disjunctive model properties 28710.7. Metaheuristics for the open shop 28810.7.1. Known traditional neighborhoods for job shop 28810.7.2. Tabu search and simulated annealing methods for open shop. 28810.7.3. Population-based algorithms and neural networks 28810.8. Exact methods for open shop 28910.8.1. Brucker et al. branch-and-bound method 28910.8.2. More recent improvements 29010.9. Algorithm comparison 29010.9.1. Uniform processing times 29010.9.2. Taillard examples 29210.9.3. Difficult Brucker and Guéret and Prins tests 29310.10. Open shop problems in satellite telecommunications 29410.10.1. TDMA systems principle 29410.10.2. Pure open shop cases 29510.10.3. Preemptive case complications 29610.10.4. Generalization of the basic open shop 29610.11. Conclusion 29710.12. Bibliography 297Chapter 11. Scheduling Under Flexible Constraints and Uncertain Data: The Fuzzy Approach 301Didier DUBOIS, Hélène FARGIER and Philippe FORTEMPS11.1. Introduction 30111.2. Basic notions on the fuzzy approach to uncertainty and constraints 30311.2.1. Possibility theory 30311.2.2. Fuzzy arithmetic 30511.2.3. Fuzzy interval comparison 30611.2.4. Possibilistic utility 30711.3. Scheduling under flexible constraints 30811.3.1. The fuzzy PERT problem: flexible constraints 30911.3.2. Limited resources: flexible constraints and fuzzy rules 31411.4. Scheduling with ill-known execution times 31711.4.1. Critical paths under ill-known execution times: difficulties 31811.4.2. Critical paths with interval execution times 32011.4.3. Critical paths with fuzzy execution times 32211.4.4. Limited resources: approach by fuzzy interval comparison 32311.5. Flexible constraint scheduling and ill-known task execution times 32511.6. Conclusion: the potential contribution of possibility theory in scheduling 32811.7. Bibliography 329Chapter 12. Real-Time Workshop Scheduling 333Christian ARTIGUES and François ROUBELLAT12.1. Introduction 33312.2. Interest and problem positioning 33312.2.1. The context of on demand production workshops 33312.2.2. The different approaches to real-time workshop scheduling 33412.2.3. An original approach 33712.3. Modeling and dynamic of scheduling problem considered 33812.3.1. Resources 33912.3.2. Production operations 34012.3.3. Setup operations 34112.4. Decisions, events and constraints 34512.5. Models for off-line and on-line scheduling 34612.5.1. Groups of interchangeable operations 34712.5.2. Operation-on-node graphs 34812.5.3. Generic graph methods 35312.6. Off-line scheduling method 35512.6.1. Gradual construction of a feasible initial sequence of groups 35512.6.2. Search for eligibility by iterative improvement of the sequence 35612.7. Real-time scheduling method, interactive decision support system 35612.7.1. Decision support system organization 35712.7.2. Eligibility control 35812.7.3. Decision support in an eligible sequence context 35912.7.4. Decision support for retrieving eligibility 36012.7.5. Decision and negotiation support between decision centers outside the planned context 36012.8. Conclusion 36112.9. Bibliography 362List of Authors 367Index 371