Lot sizing and scheduling — Survey and extensions <s> The discrete lot sizing and scheduling problem <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> The discrete lot sizing and scheduling problem <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> The discrete lot sizing and scheduling problem <s> Changeover costs and times are central to numerous manufacturing operations. These costs arise whenever work centers capable of processing only one product at a time switch from the manufacture of one product to another. Although many researchers have contributed to the solution of scheduling problems that include changeover costs, due to the problem's combinatorial explosiveness, optimization-based methods have met with limited success. In this paper, we develop and apply polyhedral methods from integer programming for a dynamic version of the problem. Computational tests with problems containing one to five products and up to 225 integer variables show that polyhedral methods based upon a set of facet inequalities developed in this paper can effectively reduce the gap between the value of an integer programming formulation of the problem and its linear programming relaxation by a factor of 94 to 100%. These results suggest the use of a combined cutting plane/branch-and-bound procedure as a solution approach. In a test with a five product problem, this procedure, when compared with a standard linear programming-based branch-and-bound approach, reduced computation time by a factor of seven. <s> BIB003 </s> Lot sizing and scheduling — Survey and extensions <s> The discrete lot sizing and scheduling problem <s> Consider a plant that has information about the arrival schedule of its "inputs" over a planning cycle. The plant has parallel production lines for processing multiple types of products. However, changeover cost and changeover time are incurred when a line changes from processing one type of products to a different type of products. We present a dynamic line allocation problem that determines an optimal line allocation so that the total relevant cost changeover and waiting costs is minimized. In this paper we analyze the complexity of the problem and develop three different heuristics for generating near-optimal allocations. <s> BIB004 </s> Lot sizing and scheduling — Survey and extensions <s> The discrete lot sizing and scheduling problem <s> This article presents an extension of a dynamic programming algorithm for scheduling production of multiple items on a single machine with time-varying deterministic demands. The extension handles time-varying deterministic material supply constraints. The algorithm minimizes the sum of changeover and inventory holding costs under two assumptions. First, we assume that in each time period, within the planning horizon, the machine must either be shut down or be producing some one item for the entire time period. Second, we assume that inventory holding costs are the same for all items and are representable as a non-decreasing function. <s> BIB005 </s> Lot sizing and scheduling — Survey and extensions <s> The discrete lot sizing and scheduling problem <s> A new integer linear programming formulation for the discrete lot-sizing and scheduling problem is presented. This polynomial-size formulation is obtained from the model with the natural variables by splitting these variables. Its linear programming relaxation is shown to be tight, by reformulating it as a shortest path problem. The latter also provides a dynamic programming formulation for the discrete lot-sizing and scheduling problem. <s> BIB006 </s> Lot sizing and scheduling — Survey and extensions <s> The discrete lot sizing and scheduling problem <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> BIB007
Subdividing the (macro-) periods of the CLSP into several (micro-)periods leads to the discrete lot sizing and scheduling problem (DLSP). In this subsection we will use the term period for short in order to refer to a micro-period. The fundamental assumption of the DLSP is the so-called 'all-or-nothing' production: Only one item may be produced per period, and, if so, production uses the full capacity. The DLSP is called a small bucket problem BIB002 , because at most one item can be produced per period. Hence, periods in the DLSP model usually correspond to small time slots such as hours or shifts. The decision variables and the parameters for the DLSP are the same as for the CLSP (see Tables 4  and 5 ). Since we consider short periods, it does not make much sense to raise setup costs in every period in which production takes place as it is done in the CLSP. Thus, setup costs should be incurred only if the production of a new lot begins. Note, the production of a lot may last several periods. To model this, we need a new decision variable (see Table 6 ) and a new parameter (see Table 7 ) both representing the setup state in a certain period. Mathematically, the DLSP can now be specified as a mixed-integer programming model:  The objective function as well as most of the constraints equal those of the CLSP. The 'all-or-nothing' assumption comes in via Eq. BIB001 , where in contrast to the CLSP the left-and the right-hand side must be equal. Restrictions (10) make sure that at most one item can be produced per period. In combination with the constraints (9) capacity limits are taken into account. Most authors assume that the capacity does not vary over time, i.e. C1 ..... Cr. The beginning of a new lot is spotted by the inequalities  . The condi-tions (12) define the setup state variables to be binary. Note that in contrast to the CLSP, a non-negativity constraint for the xjt variables is sufficient (see the inequalities (13) ). This is due to the combination of restrictions ( 11 ) and (12) together with the objective (7). Complexity considerations for the DLSP are published in BIB004 BIB006 , BIB005 , BIB003 and BIB007 . Again, let us consider the example in Section 1.4. The DLSP combines phases I-III. However, in the presence of multi-level precedence constraints among the items, the DLSP, when applied level by level, still does not guarantee a feasible solution. The advantage over the CLSP is that minimum lead times, such as transportation time or time for cooling, can easily be taken into account, because of having short time periods in mind. If the CLSP is used as a basis with periods representing, say, weeks, (short) minimum lead times must either be ignored or be overestimated. The latter leads to high total lead times which is certainly not desired.