Lot sizing and scheduling — Survey and extensions <s> Nt <s> The ELSP is a time-honored problem that "has been around" since 1915. It is the problem of accommodating cyclical production patterns when several products are made on a single facility. Recent contributions to its resolution resulted in either analytical approaches to a restricted problem, or heuristic approaches to the entire problem. This paper reviews critically the various contributions to the problem, and extends the analysis in the following four directions: (a) An improved analytical approach, (b) A test for feasibility, (c) A systematic means for escape from infeasibility, and (d) A procedure for the determination of a basic period for a given set of multipliers to achieve a feasible schedule. <s> BIB001 </s> Lot sizing and scheduling — Survey and extensions <s> Nt <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> Nt <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> BIB003 </s> Lot sizing and scheduling — Survey and extensions <s> Nt <s> In many practical situations, batching of similar jobs to avoid set-ups is performed whilst constructing a schedule. On the other hand, each job may consist of many identical items. Splitting a job often results in improved customer service or in reduced throughput time. Thus, implicit in determining a schedule is a lot-sizing decision which specifies how a job is to be split. This paper proposes a general model which combines batching and lot-sizing decisions with scheduling. A review of research on this type of model is given. Some important open problems for which further research is required are also highlighted. <s> BIB004 </s> Lot sizing and scheduling — Survey and extensions <s> Nt <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> BIB005 </s> Lot sizing and scheduling — Survey and extensions <s> Nt <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> BIB006
Maximum number of lots in period t. to denote the first position in period t, and to denote the last position in period t. N = y]tr__l Nt is the total number of positions and thus the maximum number of lots that can be built. As we will see, restricting the number of lots per period is purely motivated by modeling concerns, and research on large bucket models without such assumptions is worthwhile. If, however, the parameters Nt are chosen to be large numbers, the restriction is of theoretical interest only. For procedures to be developed it remains to prove that they show good performance not only for small values Nt. The decision variables are basically the same as for the DLSP. To be formally correct, we give a precise definition in Table 9 . A mixed-integer programming model for the GLSP can now be given as follows: Min E E sjXjn "~-E E hjljt BIB003 j=l n=l j-I t=l subject to Again, the objective (29) is to minimize the total sum of setup and holding costs. Eq. (30) gives the inventory balances. Note, a particular item may be produced at several positions in a period. Inequalities  guarantee that, if a lot for item j is scheduled at position n, the machine is in the correct setup state. Capacity restrictions are incorporated via constraints (32). The restrictions (33) enforce a unique setup state. The position at which a setup must take place is determined with the inequalities (34). The conditions BIB001 are the binary conditions for the setup state variables and restrictions BIB002 and (37) are the nonnegativity constraints. Other GLSP papers than [44] are not published yet. However, this reference discusses two model variants and three variants of a heuristic for the GLSP. Note, if we have Nt = 1 for all t = 1 ..... T, then the GLSP equals the CSLP. In the context of the example discussed in Section 1.4, the GLSP can be seen to integrate phases I-III. Since the GLSP is formulated for a single-level gozinto structure only, solution procedures for this problem may be applied level by level in the case of multi-level gozinto structures. As for all other singlelevel approaches, this does not guarantee feasible solutions. Furthermore, the GLSP is a large bucket model and thus the problem associated with incorporating l.,'tinimum lead times is back again. Table 11 Parameters for the BSP Away from discrete time models, a continuous time axis (as it is used in the EOQ and ELSP models) may be used for dynamic demand conditions as well. Ref. BIB004 stresses the close relationship between scheduling (as described in BIB005 ,  and BIB006 ) and lot sizing and scheduling.