Multi-Level Lot Sizing and Scheduling : Methods for Capacitated, Dynamic, and Deterministic Models

This book is the outcome of my research in the field of multi­ levellot sizing and scheduling which started in May 1993 at the Christian-Albrechts-University of Kiel (Germany). During this time I discovered more and more interesting aspects ab out this subject and I had to learn that not every promising idea can be thoroughly evaluated by one person alone. Nevertheless, I am now in the position to present some results which are supposed to be useful for future endeavors. Since April 1995 the work was done with partial support from the research project no. Dr 170/4-1 from the "Deutsche For­ schungsgemeinschaft" (D FG). The remaining space in this preface shaH be dedicated to those who gave me valuable support: First, let me express my deep gratitude towards my thesis ad­ visor Prof. Dr. Andreas Drexl. He certainly is a very outstanding advisor. Without his steady suggestions, this work would not have come that far. Despite his scarce time capacities, he never rejected proof-reading draft versions of working papers, and he was always willing to discuss new ideas - the good as weH as the bad ones. He and Prof. Dr. Gerd Hansen refereed this thesis. I am in­ debted to both for their assessment. I am also owing something to Dr. Knut Haase. Since we al­ most never had the same opinion when discussing certain lot sizing aspects, his comments and criticism gave stimulating input.

1 Introduction.- 1.1 Problem Context.- 1.2 Problem Outline and General Issues.- 1.3 Case Descriptions.- 1.3.1 Eastman Kodak Company.- 1.3.2 Owens-Corning Fiberglas Corporation.- 1.4 Current Practice and Motivation.- 1.5 Chapter Synopsis.- 2 Literature Review.- 2.1 Scope of the Review.- 2.2 Contributions of General Interest.- 2.3 Dynamic Demand, Unlimited Capacity.- 2.4 Dynamic Demand, Scarce Capacity.- 2.5 Intermediate Results.- 3 Problem Specifications.- 3.1 Basic Assumptions.- 3.2 Multiple Machines.- 3.3 Problem Insights.- 3.3.1 Complexity Considerations.- 3.3.2 Derived Parameters.- 3.3.3 Another Point of View: Gozinto-Trees.- 3.3.4 Initial Inventory.- 3.3.5 Schedules.- 3.3.6 Lot Splitting.- 3.3.7 Some Valid Constraints.- 3.3.8 Postprocessing.- 3.4 Parallel Machines.- 3.5 Multiple Resources.- 3.6 Partially Renewable Resources.- 4 Instance Generation.- 4.1 Methods.- 4.1.1 Generation of Gozinto-Structures.- 4.1.2 Generation of External Demand.- 4.1.3 Generation of Capacity Limits.- 4.1.4 Generation of Holding and Setup Costs.- 4.1.5 Generating PLSP-PM Instances.- 4.1.6 Generating PLSP-MR Instances.- 4.1.7 Generating PLSP-PRR Instances.- 4.1.8 Some Remarks.- 4.2 Experimental Design for the PLSP-MM.- 4.2.1 Constant Parameters.- 4.2.2 Systematically Varied Parameters.- 4.2.3 Randomly Generated Parameters.- 4.3 A Comparison of Computing Machines.- 5 Lower Bounds.- 5.1 Network Representations.- 5.1.1 A Simple Plant Location Representation.- 5.1.2 Experimental Evaluation.- 5.2 Capacity Relaxation.- 5.2.1 Motivation for Relaxing Capacity Constraints.- 5.2.2 Basic Enumeration Scheme.- 5.2.3 Branching Rules.- 5.2.4 Bounding Rules.- 5.2.5 Experimental Evaluation.- 5.3 Lagrangean Relaxation.- 5.3.1 Experimental Evaluation.- 5.4 Summary of Evaluation.- 6 Multiple Machines.- 6.1 Unsuccessful Attempts.- 6.1.1 LP-Based Strategies.- 6.1.2 Improvement Schemes.- 6.1.3 Data Perturbation.- 6.1.4 Searching in the Method Parameter Space.- 6.2 Common Construction Principles.- 6.3 Randomized Regret Based Sampling.- 6.3.1 An Introduction to Random Sampling.- 6.3.2 Randomized Regret Based Priority Rules.- 6.3.3 Tuning the Method Parameters.- 6.3.4 Modifications of the Construction Scheme.- 6.3.5 An Example.- 6.3.6 Experimental Evaluation.- 6.4 Cellular Automata.- 6.4.1 An Introduction to Cellular Automata.- 6.4.2 Masked Setup State Selection.- 6.4.3 An Example.- 6.4.4 Experimental Evaluation.- 6.5 Genetic Algorithms.- 6.5.1 An Introduction to Genetic Algorithms.- 6.5.2 Problem Representation.- 6.5.3 Setup State Selection Rules.- 6.5.4 Fitness Values.- 6.5.5 Genetic Operators.- 6.5.6 The Working Principle in a Nutshell.- 6.5.7 An Example.- 6.5.8 Experimental Evaluation.- 6.6 Disjunctive Arc Based Tabu Search.- 6.6.1 An Introduction to Tabu Search.- 6.6.2 The Data Structure.- 6.6.3 Tabu Search.- 6.6.4 Intensification of the Search.- 6.6.5 Modifications of the Construction Scheme.- 6.6.6 An Example.- 6.6.7 Experimental Evaluation.- 6.7 Demand Shuffle.- 6.7.1 Basic Ideas.- 6.7.2 The Data Structure.- 6.7.3 Data Structure Manipulations.- 6.7.4 Modifications of the Construction Scheme.- 6.7.5 An Example.- 6.7.6 Experimental Evaluation.- 6.8 Summary of Evaluation.- 6.9 Some Tests with Large Instances.- 7 Parallel Machines.- 7.1 Related Topics: Job Scheduhng.- 7.2 A Demand Shuffle Adaption.- 7.3 Preliminary Experimental Evaluation.- 8 Multiple Resources.- 8.1 Related Topics: Project Scheduling.- 8.2 A Demand Shuffle Adaption.- 8.3 Preliminary Experimental Evaluation.- 9 Partially Renewable Resources.- 9.1 Related Topics: Course Scheduling.- 9.2 A Demand Shuffle Adaption.- 9.3 Preliminary Experimental Evaluation.- 10 Rolling Planning Horizon.- 10.1 Literature Review.- 10.2 Stability Measures.- 10.3 Pitfalls: Initial Inventory.- 11 Method Selection Guidelines.- 11.1 Basic Ideas.- 11.2 Instance Characterization.- 12 Research Opportunities.- 12.1 Extensions.- 12.2 Linkages to Other Areas.- 13 Conclusion.- A Lower Bounds for the PLSP-MM.- A.l LP-Relaxation: PLSP-Model.- A.2 LP-Relaxation: Plant Location Model.- A.3 Capacity Relaxation.- A. 4 Lagrangean Relaxation.- B Upper Bounds for the PLSP-MM.- B. l Randomized Regret Based Sampling.- B.2 Cellular Automaton.- B.3 Genetic Algorithm.- B.4 Disjunctive Arc Based Tabu Search.- B.5 Demand Shuffle.- C PLSP-PM: Demand Shuffle.- D PLSP-MR: Demand Shuffle.- E PLSP-PRR: Demand Shuffle.- List of Tables.- List of Figures.