Lot sizing and scheduling — Survey and extensions <s> The proportional lot sizing and scheduling problem <s> Abstract This paper presents a mixed-integer program for the dynamic lot sizing and scheduling problem in a multi-level, single-machine environment. It turns out that in contrast to single-level problems the integration of initial inventory is a crucial aspect if generality should not be lost. It is shown how problem instances can efficiently be solved to suboptimality by using a so-called randomized regret based heuristic. <s> BIB001 </s> Lot sizing and scheduling — Survey and extensions <s> The proportional lot sizing and scheduling problem <s> 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. <s> BIB002
A shortcoming of the CSLP model is that, if the capacity of a period is not used in full, the remaining capacity is left unused. An attempt to avoid this is the proportional lot sizing and scheduling problem (PLSP). Roughly speaking, the basic idea of the PLSP is to use remaining capacity for scheduling a second item in the particular period. If two items are produced in a period, it must be clear in which order these items are to be produced. This is accomplished by interpreting the setup state decision variables Yjt in the following manner: Yjt is the setup state of the machine at the end of a period. The underlying assumption of the PLSP is that the setup state can be changed at most once per period. Production in a period may take place if the machine is properly set up either at the beginning or at the end of the period. Hence, at most two items may be produced per period. To give a formal specification of the PLSP, we use the decision variables and the parameters of the DLSP. A mixed-integer programming model for the PLSP can be formulated as follows:  While the objective function and most of the constraints equal the CSLP model, we should explain what is new. The inequalities (23) make sure that production of an item in a certain period can only take place if the machine is properly set up either at the beginning of Operational Research 99 (1997) 221-235 227 or at the end of that period. Since more than one item may be produced per period, (24) BIB001 ,  and BIB002 .