Lot sizing and scheduling — Survey and extensions <s> Further research opportunities <s> This paper deals with an identical multiprocessor, multiproduct, lot-size scheduling problem under deterministic conditions. The problem is an extension of the single-processor ELSP problem. The objective is to minimize the average production and inventory costs per unit time subject to constraints of no shortages and no interference among the products. A mathematical formulation for the problem is given. A heuristic procedure, which extends the Common Cycle approach for a single processor, is suggested and computational results are reported. Upper and Lower bounds are developed and used to measure the effectiveness of the procedure. <s> BIB001 </s> Lot sizing and scheduling — Survey and extensions <s> Further research opportunities <s> Abstract A simple class of heuristic algorithms for discrete dynamic lot size problems with backlogging is presented which can be easily implemented by eyeballing comparisons of the demand sequence with a fixed two sided sequence of cut-off values. Encouraging computational results of two specific interesting cases of such heuristics are reported. Other two-way heuristics are suggested. <s> BIB002 </s> Lot sizing and scheduling — Survey and extensions <s> Further research opportunities <s> We are concerned with a discrete-time undiscounted dynamic lot size model in which demand and cost parameters are constant for an initial few periods. As our main result, we obtain an upper bound on the number of these periods which guarantees the optimality of the Economic Order Quantity EOQ as the size of the production lot to be produced in the first period. The upper bound is given and the optimality holds for every problem with an horizon not less than the upper bound and for the infinite horizon problem. The data beyond the upper bound are allowed to be specified arbitrarily. In the context of forecast horizon theory, we obtain conditions for a finite forecast horizon to exist in the undiscounted dynamic lot size model. Furthermore, existence results for forecast horizons in an undiscounted optimization problem are obtained for the first time in this paper. <s> BIB003 </s> Lot sizing and scheduling — Survey and extensions <s> Further research opportunities <s> This paper finds a tight bound on the error introduced in the dynamic lot size model with backlogging when it is truncated by planning for the interval of time for which data are actually known, rather than for the natural planning interval. <s> BIB004 </s> Lot sizing and scheduling — Survey and extensions <s> Further research opportunities <s> Abstract Two approaches for modifying existing dynamic lot sizing heuristics to incorporate backlogging are presented. Extensive simulation experiments are designed to compare their relative performance with the recently published two-way eyeballing heuristics (TWEH) for lot sizing with backlogging. Dominant heuristics are identified for different cost and demand conditions. TWEH is the simplest algorithm with good performance. <s> BIB005 </s> Lot sizing and scheduling — Survey and extensions <s> Further research opportunities <s> In this paper the Discrete Lotsizing and Scheduling Problem (DLSP) with setup times is considered. DLSP is the problem of determining the sequence and size of production batches for multiple items on a single machine. The objective is to find a minimal cost production schedule such that dynamic demand is fulfilled without backlogging. DLSP is formulated as a Set Partitioning Problem (SPP). We present a dual ascent and column generation heuristic to solve SPP. The quality of the solutions can be measured, since the heuristic generates lower and upper bounds. Computational results on a personal computer show that the heuristic is rather effective, both in terms of quality of the solutions as well as in terms of required memory and computation time. <s> BIB006 </s> Lot sizing and scheduling — Survey and extensions <s> Further research opportunities <s> Abstract This paper is a computational study to investigate the value of coordinating production and distribution planning. The particular scenario we consider concerns a plant that produces a number of products over time and maintains an inventory of finished goods at the plant. The products are distributed by a fleet of trucks to a number of retail outlets at which the demand for each product is known for every period of a planning horizon. We compare two approaches to managing this operation, one in which the production scheduling and vehicle routing problems are solved separately, and another in which they are coordinated within a single model. The two approaches are applied to 132 distinct test cases with different values of the basic model parameters, which include the length of the planning horizon, the number of products and retail outlets, and the cost of setups, inventory holding and vehicle travel. The reduction in total operating cost from coordination ranged from 3% to 20%. These results indicate the conditions under which companies should consider the organizational changes necessary to support coordination of production and distribution. <s> BIB007 </s> Lot sizing and scheduling — Survey and extensions <s> Further research opportunities <s> Abstract This paper deals with lot sizing and scheduling for a single-stage, single-machine production system where setup costs and times are sequence dependent. A large-bucket mixed integer programming (MIP) model is formulated which considers only efficient sequences. A tailor-made enumeration method of the branch-and-bound type solves problem instances optimally and efficiently. The size of solvable cases ranges from 3 items and 15 periods to 10 items and 3 periods. Furthermore, it will become clear that rescheduling can neatly be done. <s> BIB008 </s> Lot sizing and scheduling — Survey and extensions <s> Further research opportunities <s> 1 Introduction.- 1.1 Motivation of the Planning Problem.- 1.2 Background and Related Work.- 1.3 Case Description.- 1.4 Chapter Synopsis.- 2 Description of the Problems.- 2.1 Batching Types and Literature Review.- 2.2 Notation, Basic Definitions and [?/?/?] Descriptor.- 2.3 Single-Machine Case.- 2.4 Multi-Level Product Structures and Parallel Machines.- 2.5 Complexity Analysis.- 2.6 Structural Properties.- 2.7 Instance Generator.- 3 Single-Machine Case.- 3.1 Basic Enumeration Scheme.- 3.2 Item Availability - Preemptive Batching.- 3.2.1 Branch&Bound.- 3.2.2 Dynamic Programming.- 3.2.3 Construction and Improvement.- 3.2.4 Computational Results.- 3.3 Item Availability - Nonpreemptive Batching.- 3.3.1 Branch&Bound.- 3.3.1.1 Minimum Cost Schedule of a Sequence.- 3.3.1.2 Dominance Rules.- 3.3.2 Genetic Algorithm for Sequence Independent Setups.- 3.3.3 Computational Results.- 3.4 Batch Availability.- 3.4.1 Branch&Bound.- 3.4.1.1 Late Schedule of a Sequence.- 3.4.1.2 Dominance Rule.- 3.4.2 Genetic Algorithm for Sequence Independent Setups.- 3.4.3 Computational Results.- 3.4.4 Genetic Algorithm for the Flow-Shop Case.- 4 Discrete Lotsizing and Scheduling.- 4.1 Discrete Lotsizing and Scheduling Problem.- 4.2 Equivalence of DLSP and BSP.- 4.3 Comparison with Variants of the DLSP.- 4.3.1 Sequence Independent Setup Times and Costs (SISTSC).- 4.3.2 Sequence Dependent Setup Costs (SDSC).- 4.3.3 Sequence Dependent Setup Times and Costs (SDSTSC).- 4.3.4 Single-Level Batch Availability (BA).- 4.3.5 Two-Level Batch Availability (BA2LV).- 4.4 Conclusions.- 5 Multi-Level and Parallel Machine Case.- 5.1 Multi-Level Case.- 5.1.1 Single-Machine.- 5.1.2 Multi-Machine.- 5.1.3 Preliminary Computational Results.- 5.2 Parallel Machines.- 6 Artificial Intelligence Approaches.- 6.1 Introduction.- 6.2 Model Formulations.- 6.3 Performance Comparison.- 6.4 Conclusions.- 7 Summary and Future Work.- Appendix A Setup Matrices for the Instance Generator.- List of Notation.- List of Abbreviations.- List of Figures.- List of Tables. <s> BIB009 </s> Lot sizing and scheduling — Survey and extensions <s> Further research opportunities <s> A new model is presented for capacitated lot-sizing with sequence dependent setup costs. The model is solved heuristically with a backward oriented method; the sequence and lot-size decisions are based on a priority rule which consists of a convex combination of setup and holding costs. A computational study is performed where the heuristic is compared with the Fleischmann approach for the discrete lot-sizing and scheduling problem with sequence dependent setup costs. <s> BIB010 </s> Lot sizing and scheduling — Survey and extensions <s> Further research opportunities <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> BIB011 </s> Lot sizing and scheduling — Survey and extensions <s> Further research opportunities <s> Abstract In this paper we consider the Discrete Lotsizing and Scheduling Problem with sequence dependent set-up costs and set-up times (DLSPSD). DLSPSD contains elements from lotsizing and from job scheduling, and is known to be NP-Hard. An exact solution procedure for DLSPSD is developed, based on a transformation of DLSPSD into a Travelling Salesman Problem with Time Windows (TSPTW). TSPTW is solved by a novel dynamic programming approach due to Dumas et al. (1993). The results of a computational study show that the algorithm is the first one capable of solving DLSPSD problems of moderate size to optimality with a reasonable computational effort. <s> BIB012 </s> Lot sizing and scheduling — Survey and extensions <s> Further research opportunities <s> Industrial lotsizing and scheduling pose very difficult analytical problems. We propose an unconventional model that deals with sequence-dependent setup costs in a multiple-machine environment. The sequence-splitting model splits an entire schedule into subsequences, leading to tractable subproblems. An optimization approach based on a column generation/branch and bound methodology is developed, and heuristically adapted to test problems including five real-world problem instances gathered from industry. <s> BIB013 </s> Lot sizing and scheduling — Survey and extensions <s> Further research opportunities <s> In a multiproduct, parallel machine environment, it may be beneficial to dedicate one or more of the machines to a single product for consecutive time periods. However, previous lot-sizing and scheduling models usually do not allow for such short-term dedication. This paper presents a mixed-integer programming model that allows for short-term dedication in scheduling parallel machines serving multiple products with dynamic demands. It also describes a Lagrangian-based algorithm for solving such scheduling problems. ::: ::: ::: ::: An experiment verifies the effectiveness of the algorithm and demonstrates the importance of allowing for short-term dedication. Capacity utilization, one of six factors investigated, greatly affects the use of dedication. A strong interaction effect between the number of machines and the number of products is also seen with respect to the usefulness of short-term dedication. A measure of estimated production frequency incorporates these two factors along with magnitudes of periodic demands. This measure has a strong relationship with the amount of short-term dedication used in solutions. Operations managers employing parallel machines could use the experimental results in deciding whether to use short-term dedication to reduce costs. <s> BIB014
Ongoing research tries to incorporate additional real-world aspects into lot sizing and scheduling models and methods. Quite important are the consideration of positive setup times BIB006 32, BIB008 BIB009 BIB012 and sequence dependencies [ 30, 32, 43, 44, BIB010 BIB008 BIB009 BIB013 BIB012 . Another challenging subject is represented by lot sizing and scheduling with parallel machines BIB014 BIB001 BIB013 BIB011 97, 98] . Also, backlogging attracts increasing research interest, but most authors stick to the WW problem BIB002 39, 49, BIB005  . Taking into account that planning in practice has to be done on a rolling horizon basis is yet another topic worth attacking. Again, the uncapacitated type of problem is the matter of concern in most cases BIB003  BIB004 40, 41, 87] , and an open gap remains for capacitated lot sizing and scheduling BIB011 . Apparently, lot sizing and scheduling interacts with other planning activities in a firm, e.g. distribution planning, cutting and packing, and project scheduling BIB011 . The coordination of these planning tasks is thus a must in order to avoid high transaction costs. However, research has almost neglected the problem of coordination and provides no advice (as an exception, see BIB007 , where production and distribution planning is coordinated). Since making use of cost saving opportunities is a vital aspect in the presence of competition, solving coordination problems is probably the most crucial goal for future work.