Lot sizing and scheduling — Survey and extensions <s> of Operational Research 99 (1997) 221-235 <s> In this paper we study the computational complexity of the capacitated lot size problem with a particular cost structure that is likely to be used in practical settings. For the single item case new properties are introduced, classes of problems solvable by polynomial time algorithms are identified, and efficient solution procedures are given. We show that special classes are NP-hard, and that the problem with two items and independent setups is NP-hard under conditions similar to those where the single item problem is easy. Topics for further research are discussed in the last section. <s> BIB001 </s> Lot sizing and scheduling — Survey and extensions <s> of Operational Research 99 (1997) 221-235 <s> Mixed-integer programming models are typically not used to solve realistic-sized production scheduling problems because they require exorbitant solution times. We impose a useful taxonomy on production scheduling problems and develop alternative formulations for a wide variety of problems within the taxonomy. The linear programming relaxation of the new models is very effective in generating bounds. We show that these bounds are equal to those that could be generated using Lagrangian relaxation or column generation. The linear programming bounds increase in effectiveness as the problems become larger. Perhaps of greatest significance is that practitioners can obtain our results using only standard “off-the-shelf” codes such as LINDO or MPSX/370. We report computational experience in several computing environments (hardware and software) on problems with up to 200 products and 10 time periods (2000 0-1 variables). <s> BIB002 </s> Lot sizing and scheduling — Survey and extensions <s> of Operational Research 99 (1997) 221-235 <s> The multi-item single-level capacitated lot-sizing problem consists of scheduling N different items over a horizon of T periods. The objective is to minimize the sum of set-up and inventory-holding costs over the horizon, subject to a capacity restriction in each period. Different heuristic approaches have been suggested to solve this difficult mathematical problem. So far, only a few limited attempts have been made to analyse and compare these approaches. The paper can be divided into two main parts. The first part shows that current heuristics can be classified in two different categories: single-resource heuristics, which are special-purpose methods, and mathematical-programming-based heuristics, which can usually deal with more general problem environments. The second part is devoted to an extensive computational review. The general idea is to find relationships between the performance of the heuristic and the computational burden involved in finding the solution. Based on these computational results, suggestions can be given with respect to the usefulness of the various heuristics in different industrial settings. <s> BIB003 </s> Lot sizing and scheduling — Survey and extensions <s> of Operational Research 99 (1997) 221-235 <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> BIB004 </s> Lot sizing and scheduling — Survey and extensions <s> of Operational Research 99 (1997) 221-235 <s> The multi-item capacitated lot-sizing problem consists of determining the magnitude and the timing of some operations of durable results for several items in a finite number of processing periods so as to satisfy a known demand in each period. We show that the problem is strongly NP-hard. To explain why one of the most popular among exact and approximate solution methods uses a Lagrangian relaxation of the capacity constraints, we compare this approach with every alternate relaxation of the classical formulation of the problem, to show that it is the most precise in a rigorous sense. The linear relaxation of a shortest path formulation of the same problem has the same value, and one of its Lagrangian relaxations is even more accurate. It is comforting to note that well-known relaxation algorithms based on the traditional formulation can be directly used to solve the shortest path formulation efficiently, and can be further enhanced by new algorithms for the uncapacitated lot-sizing problem. An extensive computational comparison between linear programming, column generation and subgradient optimization exhibits this efficiency, with a surprisingly good performance of column generation. We pinpoint the importance of the data characteristics for an empirical classification of problem difficulty and show that most real-world problems are easier to solve than their randomly generated counterparts because of the presence of initial inventories and their large number of items. <s> BIB005 </s> Lot sizing and scheduling — Survey and extensions <s> of Operational Research 99 (1997) 221-235 <s> Abstract This paper discusses set partitioning and column generation heuristics for the multi item single level capacitated dynamic lotsizing problem. Most previous research efforts reported in literature use the single item uncapacitated problem solutions as candidate plans. In this paper a different approach is proposed in which candidate plans are also generated by some well-known multi item capacitated dynamic lotsizing heuristics. The LP relaxation of a set partitioning model is solved and rounded to obtain an integer solution. A number of heuristics are subsequently applied to improve upon this initial solution. Heuristics are also used to convert the possibly fractional solution from the column generation step to a feasible integer one. Our methods are compared with other common sense heuristics. Computational experience shows that our methods perform best for problems with fewer periods than items, but are quite good on average. <s> BIB006 </s> Lot sizing and scheduling — Survey and extensions <s> of Operational Research 99 (1997) 221-235 <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> BIB007 </s> Lot sizing and scheduling — Survey and extensions <s> of Operational Research 99 (1997) 221-235 <s> In this paper, we develop a Lagrangean relaxation-based heuristic procedure to generate near-optimal solutions to very-large-scale capacitated lot-sizing problems CLSP with setup times and limited overtime. Our computational results show that large problems involving several thousand products and several thousand 0/1 integer variables can be solved in a reasonable amount of computer time to within one percent of their optimal solution. The proposed procedure is general enough to be applied directly or with slight modification to real-life production problems. <s> BIB008 </s> Lot sizing and scheduling — Survey and extensions <s> of Operational Research 99 (1997) 221-235 <s> Abstract Development of new models and solution procedures for production planning has been of research interest for several decades. Implementation of these models has resulted in lower production costs by reducing inventories, number of setups and labor costs. In this paper, we develop several optimal/near-optimal procedures for the Capacitated Lot-Sizing and Scheduling Problem (CLSP) with setup times, limited regular time and limited overtime. We formulate a mixed-integer linear programming model of the problem and solve it by Lagrangean relaxation. We experiment with alternative Lagrangean relaxations and develop new procedures to solve these relaxations. Overall, the capacity constraints relaxation seems to be superior to the demand constraints relaxation. Our results show that large problems can be solved in reasonable computer times and within one-percent accuracy of the optimal solutions. We solved 99 × 8 (i.e., 99 items and 8 periods), 50 × 12 and 50 × 8 problems in 30.61, 36.25 and 12.65 seconds of CDC Cyber 730 computer time, respectively. Our procedures are general enough to be applied directly or with slight modifications in real-life production settings. <s> BIB009 </s> Lot sizing and scheduling — Survey and extensions <s> of Operational Research 99 (1997) 221-235 <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> BIB010 </s> Lot sizing and scheduling — Survey and extensions <s> of Operational Research 99 (1997) 221-235 <s> Abstract In this paper a framework for a new heuristic approach for solving the single level multi-item capacitated dynamic lot sizing problem is presented. The approach uses an iterative item-by-item strategy for generating solutions to the problem. In each iteration a set of items are scheduled over the planning horizon and the procedure terminates when all items are scheduled. An algorithm that implements this approach is developed in which in each iteration a single item is selected and scheduled over the planning horizon. Each item is scheduled by the solution of a bounded single item lot sizing problem where bounds on inventory and production levels are used to ensure feasibility of the overall problem. The performance of this algorithm is compared to some well-known heuristics over a set of test problems. The computational results demonstrated that on the average our algorithm outperforms other algorithms. The suggested algorithm especially appears to outperform other algorithm for problems with many periods and few items. In the literature these problems are considered as hard. <s> BIB011 </s> Lot sizing and scheduling — Survey and extensions <s> of Operational Research 99 (1997) 221-235 <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> BIB012 </s> Lot sizing and scheduling — Survey and extensions <s> of Operational Research 99 (1997) 221-235 <s> A job shop consists of a set of different machines that perform operations on jobs. Each job has a specified processing order through the machines, i.e. a job is composed of an ordered list of operations each of which is determined by the machine required and the processing time on it. There are no precedence constraints among operations of different jobs. Operations can not be interrupted (non-preemption) and each machine can handle only one job at a time. Consequently, each job can be performed on only one machine at a time. The operation sequences on the machines are unknown and have to be determined in order to minimize the makespan, i. e. the time required to complete all jobs. <s> BIB013 </s> Lot sizing and scheduling — Survey and extensions <s> of Operational Research 99 (1997) 221-235 <s> This book on scheduling covers theoretical models as well as scheduling problems in the real world. Author Michael Pinedo also includes a CD that contains slide-shows from industry and movies dealing with implementations of scheduling systems. The book consists of three parts. The first part focuses on deterministic scheduling with the associated combinatorial problems. The second part covers probabilistic scheduling models. In this part it is assumed that processing times and other problem data are not known in advance. The third part deals with scheduling in practice. It covers heuristics that are popular with practitioners and discusses system design and development issues. Each chapter contains a series of computational and theoretical exercises. This book is of interest to theoreticians and practitioners alike. Graduate students in operations management, operations research, industrial engineering and computer science will find the book to be an accessible and invaluable resource. Scheduling will serve as an essential reference for professionals working on scheduling problems in manufacturing and computing environments. Michael Pinedo is the Julius Schlesinger Professor of Operations Management at New York University. <s> BIB014
Using this notation, the CLSP can formally be couched as a mixed-integer programming model: Pjqjt<~Ctxjt, The objective ( 1 ) is to minimize the sum of setup and holding costs. Eq. (2) represents the inventory balances. Due to the restrictions (3), production of an item can only take place if the machine is set up for that particular item. Constraints (4) are the capacity constraints. The setup variables are defined to be binary (5) and the inequalities (6) are the nonnegativity conditions. The CLSP is called a large bucket problem BIB002 , because several items may be produced per period. Such a period typically represents a time slot of, say, one week in the real world. The planning horizon usually is less than six months. Solving the CLSP optimally is known to be NPhard BIB001 45] . If positive setup times are incorpo-rated into the model, the feasibility problem is NPcomplete BIB007 . Hence, there are only a few attempts to solve the CLSP optimally  BIB005 BIB002 47] . Many authors have developed heuristics BIB006 BIB008 BIB009 57, BIB011 BIB003 . Scheduling decisions are, however, not integrated into the CLSP. The usual approach therefore is to solve the CLSP first, and to solve a scheduling problem for each period separately afterwards. A review of the scheduling literature can be found in BIB013 ,  and BIB014 . A recent attempt to hierarchically integrate lot sizing and scheduling is described in BIB012 ,  and BIB010 . Let us return to the example given in Section 1. BIB004 . If we would use a solution procedure for the CLSP during phase I, the problem of capacity violations would vanish and phase II would no longer be necessary. However, due to the multi-level gozinto structure it is easy to figure out an example where the CLSP is used on a level by level basis and does not yield a feasible solution. Also, phase IH, which is the scheduling phase, is not integrated. Table 6 A new decision variable for the DLSP