Lot sizing and scheduling — Survey and extensions <s> Multi-level lot sizing and scheduling <s> Recently there has been a flurry of research in the area of production planning for multi-echelon production-distribution systems with deterministic non-stationary demands and no capacity constraints. A variety of algorithms have been proposed to optimally solve these problems, with varying success. This paper investigates the issue of computational complexity of the problem for all commonly studied product structures, i.e. the single item, the serial system, the assembly system, the one-warehouse-N-retailer system, the distribution system, the joint replenishment system, and the general production-distribution system. Polynomial time algorithms are available for the single-item, serial and assembly systems. We prove that the remaining problems are NP-complete. <s> BIB001 </s> Lot sizing and scheduling — Survey and extensions <s> Multi-level lot sizing and scheduling <s> This paper presents a zero-one linear formulation of the multilevel lot-sizing problem for materials requirement planning systems without capacity constraints. The model is an efficient statement of the problem and has a structure that is particularly convenient for research work. In addition, it is demonstrated that the relaxed linear programming solution to this formulation will always be integer. The results of a rather large computational history are reported along with a variable reduction methodology that allows for the solution of reasonably sized research problems. <s> BIB002 </s> Lot sizing and scheduling — Survey and extensions <s> Multi-level lot sizing and scheduling <s> We consider two classes of multi-item lot-sizing problems. The first is a class of single stage problems involving joint machine capacity constraints and/or start up costs, and the second is a class of multistage problems with general product structure. ::: ::: The problems are solved as mixed integer programs based on i an appropriate choice of the initial problem formulation and ii the addition of cuts which are generated automatically by a mathematical programming system MPSARX. Our results extend and complement those of Karmarkar and Schrage 1985, Afentakis and Gavish 1986, Eppen and Martin 1987 and Van Roy and Wolsey 1987. A major advantage of this approach is its robustness or flexibility. By using just a matrix generator and a mathematical programming system with automatic cut generation routines we can formulate and solve model variants without incurring the costs of adapting an algorithm. <s> BIB003 </s> Lot sizing and scheduling — Survey and extensions <s> Multi-level lot sizing and scheduling <s> Abstract This paper presents a heuristic approach to finding the least cost MRP schedule when end products and their components are produced under a single aggregate capacity constraint. A multi-phase algorithm first obtains a feasible solution. It then proceeds to develop better cost solutions by making controlled changes to the initial feasible schedule. The best cost solutions found by the algorithm differ, on the average, by less than 1% from the corresponding best known solutions. For small problems, the average computation time is about 1 60 - th of that requireed by an exact integer programming model. <s> BIB004 </s> Lot sizing and scheduling — Survey and extensions <s> Multi-level lot sizing and scheduling <s> Abstract This paper presents the first heuristics capable of solving multilevel lotsizing problems with capacity constraints on more than one level. Moreover, the form of the heuristics is quite general so that they can easily be extended to solve a variety of problems. If one wants to solve these problems on a routine basis in a real environment one needs to find fast and easy algorithms. However, we show that for certain problem classes this is a very difficult task, far more difficult than has been suggested in the literature. For problems with setup times we show that finding a feasible solution is NP-complete. Even without setup times testing for feasibility can be very difficult. Just how time consuming such heuristics must be is demonstrated. This leaves little chance to build fast and easy heuristics except for the most simple cases. Our exploration of the complexity issues points to mathematical programming as a potential source of heuristics for these problems. This paper presents a new and general approach based on rounding an LP solution for the problem without setup times. The methods use different information and patterns evident in the LP solution are explored. The approach is tested on a large set of problems. The main contributions of this paper are the way in which we distinguish between the easy and hard lotsizing problems, the LP-based heuristics and the test set of capacitated multilevel lotsizing problems. <s> BIB005 </s> Lot sizing and scheduling — Survey and extensions <s> Multi-level lot sizing and scheduling <s> This paper deals with multi-item capacitated lotsizing in a serial production environment under dynamic demand conditions. The primary objective of this research is to investigate the performance of simple level-by-level heuristics. A problem classification is proposed to distinguish between easy problems and harder ones for which no simple heuristics can be developed. It is shown how simple algorithms can be constructed for the easier problems using a level-by-level approach. These heuristics are the first of their kind for this problem. They are compared with the optimal solution for a set of test problems. The results show that for some problem classes strategies which are frequently used in practice may result in rather poor schedules. <s> BIB006 </s> Lot sizing and scheduling — Survey and extensions <s> Multi-level lot sizing and scheduling <s> A simple heuristic is proposed for multi-level lot-sizing problems where there is a bottleneck. Previous methods to solve this problem have formulated the problem as an integer programming problem and solved the problem using a Lagrangian relaxation embedded within the branch and bound procedure. In this paper we suggest that items to be produced can be grouped into two types and a simple but efficient heuristic can be used to determine the production quantities required. A program was developed to compute production levels and was found to require only a small fraction of the computer time required by the full integer programming approach, and to produce solutions of reasonable quality. The heuristic is simple to implement. <s> BIB007 </s> Lot sizing and scheduling — Survey and extensions <s> Multi-level lot sizing and scheduling <s> We consider an integrated job-shop planning and scheduling model. To solve the problem we use a multi-pass decomposition approach which alternates between solving a planning problem with a fixed sequence of products on the machines, and a job-shop scheduling problem for a fixed choice of the production plan. The generated production plans are feasible i.e., there exists at least one feasible schedule to realize that plan. Quality of the solution is investigated and numerical results are presented. <s> BIB008 </s> Lot sizing and scheduling — Survey and extensions <s> Multi-level lot sizing and scheduling <s> We consider a multistage, multiproduct production/inventory system in discrete time. When an order is placed for a component it is instantly delivered, and the required amounts of the components consumed in producing the given component are simultaneously withdrawn from their respective inventories. External demand occurs for a single component. We assume that the external demand for the component is nonconstant, deterministic, and must be met without backlogging. We propose two new cluster-based heuristics for this problem. We will show that the first of these heuristics has a worst-case relative cost that is between 1.44 and 2, and the second of these heuristics has a worst-case relative cost of 2. Computational tests indicate that, on the average, these heuristics are within 0.7% and 1.3% of optimal, respectively, and that their performance is very insensitive to the size of the system and to other input parameters. <s> BIB009 </s> Lot sizing and scheduling — Survey and extensions <s> Multi-level lot sizing and scheduling <s> Multilevel lotsizing is one of the most challenging subjects in production planning, especially in the presence of capacity constraints. In this paper we investigate lotsizing heuristics for assembly production systems with a bottleneck. More specifically, we discuss heuristics based on Linear Programming (LP), and compare the performance of these heuristics with the performance of approaches based on simulated annealing and tabu search techniques.A comparison of the three heuristics on a set of test problems shows that simulated annealing and tabu search perform well compared to pure LP-based heuristics, but the effectiveness of the latter heuristics can be improved by combining them with elements from simulated annealing and tabu search. <s> BIB010 </s> Lot sizing and scheduling — Survey and extensions <s> Multi-level lot sizing and scheduling <s> This paper reports on our experiments with statistical search methods for solving lotsizing problems in production planning. In lotsizing problems the main objective is to generate a minimum cost production and inventory schedule, such that (i) customer demand is satisfied, and (ii) capacity restrictions imposed on production resources are not violated. We discuss our experiences in solving these, in general NP-hard, lotsizing problems with popular statistical search techniques like simulated annealing and tabu search. The paper concludes with some critical remarks on the use of statistical search methods for solving lotsizing problems. <s> BIB011 </s> Lot sizing and scheduling — Survey and extensions <s> Multi-level lot sizing and scheduling <s> In modelling general multifacility, capacitated lotsizing problems structures of the single end-item (single product) assembly line type quite frequently emerge. On higher aggregated levels of production planning this may be the case, because assembly line structures in many instances provide sufficiently close approximations of actually more general production environments. On more detailed levels of production planning (material requirements planning) single product assembly line structures can be found mainly for two reasons: First, because the lotsizing problem under consideration simply happens to exhibit exactly this structure. Second, because the general structure of numerous MRP-problems contains substructures, which can be formulated as single product assembly line problems. It would seem therefore rather promising to examine this type of problem in greater detail since many actual applications could be expected to benefit from improved solution procedures. <s> BIB012 </s> Lot sizing and scheduling — Survey and extensions <s> Multi-level lot sizing and scheduling <s> Abstract In this paper, we consider an integrated model for job-shop lotsizing and scheduling in order to determine a feasible plan, i.e., a plan with at least one feasible schedule. Our method consists in alternatively solving problems at two different levels, one in which lotsizes are computed for a given sequence of jobs on each machine, and one in which a sequence is computed given fixed lotsizes. Different approaches are investigated, and computational results are reported. <s> BIB013 </s> Lot sizing and scheduling — Survey and extensions <s> Multi-level lot sizing and scheduling <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> BIB014 </s> Lot sizing and scheduling — Survey and extensions <s> Multi-level lot sizing and scheduling <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> BIB015 </s> Lot sizing and scheduling — Survey and extensions <s> Multi-level lot sizing and scheduling <s> Where standard MLP-solvers fail to compute optimum objective function values for certain MLP-model formulations, lower bounds may be used as a point of reference for evaluating heuristics. In this paper, we compute lower bounds for the multi-level proportional lot sizing and scheduling problem with multiple machines (PLSP-MM). Four approaches are compared: Solving LP-relaxations of two different model formulations, solving a relaxed MLP-model formulation optimally, and solving a Lagrangean relaxation. Keywords: <s> BIB016 </s> Lot sizing and scheduling — Survey and extensions <s> Multi-level lot sizing and scheduling <s> Abstract The multiple stage production planning problem addresses any system of inventoriable stocks related by precedence requirements. Such a system could involve fabrication of finished goods from component parts, transportation of assemblies between facilities, or both, as growing interest in supply chain management suggests there may no longer be a useful distinction between the production planning and distribution planning problem. Yet most previous efforts to develop effective planning algorithms have relied on the direct or adapted application of known single item lot sizing techniques, implicitly framing any multiple stage system as a direct extension of the single item lot sizing problem. Considering the latter is better described as a special case of the former, the purpose of this paper is to propose and evaluate a highly adaptable production planning heuristic developed explicitly for the multiple stage problem. Multiple stage production planning typifies any system in which the scheduling of some production stage may place demands on necessary predecessor stages, or constrain the schedules of successor stages. This paper considers detailed material planning, or lot sizing, in a multiple stage, dynamic demand environment. A new heuristic method for developing such production schedules is introduced, based on a structured neighborhood search approach to these problems. An efficient lower bounding technique is also presented, employing Lagrangian relaxation and an alternate approach to the mathematical formulation of a multiple stage planning problem. This technique was employed to find lower bounds on all numerical experiments. The scope of the investigation, with respect to the number of improved heuristic methods included for comparison, is among the broadest in the literature. The new heuristic performed consistently better than other methods, producing solutions which were within an average of 1% of optimal. <s> BIB017
All approaches reviewed so far are for the singlelevel case only. In most real-world situations, however, we face complex multi-level gozinto structures, and thus need solution procedures capable of dealing with these. As a consequence, multi-level lot sizing has attracted research interest. An extensive review of the literature is given in BIB014 . Many BIB002 , BIB003 , BIB009 , [97] and BIB017 .A sensitivity analysis is done in  and [ 112] , and complexity results for uncapacitated, multi-level lot sizing are provided in BIB001 . Most authors who consider capacitated, multi-level lot sizing make restrictive assumptions. Refs. BIB015 ,  , BIB010 , BIB004 , [97] and BIB011 , for example, take only a single bottleneck machine into account. Refs. BIB005 , BIB006 , BIB012 and BIB007 The literature on multi-level lot sizing and scheduling is sparse. An hierarchical integration of some lot sizing and some scheduling procedures is discussed in BIB013 ,  , BIB008 and [106] . The only work where multi-level lot sizing and scheduling is done simultaneously under quite general assumptions such as general gozinto structures and multiple machines is documented in BIB016 - BIB014 . In these references, the multilevel PLSP is tackled. To give a formal specification of the multi-level PLSP, we use the same decision variables as for the single-level PLSP. Some of the single-level PLSP parameters are used again, some must be redefined, and some parameters are new. To avoid confusion, we list all multi-level PLSP parameters in Table 12 . The following mixed-integer model gives a precise specification for the multi-level PLSP: Research on several variants of the multi-level PLSP is summarized in BIB014 . It can be proven that the (multi-level) DLSP and the (multi-level) CSLP are special cases of the (multi-level) PLSP. Compared to the DLSP, for instance, the PLSP is a much more thorny problem, because it lacks 'nice' properties. However, efficient heuristics for the multi-level PLSP do already exist and justify more research effort. The multi-level PLSP integrates phases I-III from the example in Section 1. BIB001 . In contrast to the abovementioned models, it additionally pays attention to multi-level gozinto structures. Thus, the multi-level PLSP is a promising candidate for replacing traditional MRP II logic.  The objective function and most of the constraints equal those in the single-level PLSP model. Hence, we