Lot sizing and scheduling — Survey and extensions <s> Brief history review <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> Brief history review <s> We present a review of the main “global optimization" methods. The paper comprises one introduction and two parts. In the introduction, we recall some generalities about non linear constraint-less optimization and we list some classifications which have been proposed for the global optimization methods. We then describe, in the first part, various “classical" global optimization methods, most of which available long before the appearance of Simulated Annealing (a key event in this field). There exists plenty of papers and books dealing with these methods, and studying in particular their convergence properties. The second part of the paper is devoted to more recent or atypical methods, mostly issued from combinatorial optimization. The three main methods are “metaheuristics": Simulated Annealing (and derived techniques), Tabu Search and Genetic Algorithms; we also describe three other less known methods. For these methods, theoretical studies of convergence are less abundant in the literature, and the use of convergence results is by far more limited in practice. However, the fitting of some of these techniques to continuous variables problems gave very promising results; that question is not discussed in detail in the paper, but useful references allowing to deepen the subject are given. <s> BIB002 </s> Lot sizing and scheduling — Survey and extensions <s> Brief history review <s> This paper is concerned with the general dynamic lot size model, or generalized Wagner-Whitin model. Let n denote the number of periods into which the planning horizon is divided. We describe a simple forward algorithm which solves the general model in 0n log n time and 0n space, as opposed to the well-known shortest path algorithm advocated over the last 30 years with 0n2 time. ::: ::: A linear, i.e., 0n-time and space algorithm is obtained for two important special cases: a models without speculative motives for carrying stock, i.e., where in each interval of time the per unit order cost increases by less than the cost of carrying a unit in stock; b models with nondecreasing setup costs. ::: ::: We also derive conditions for the existence of monotone optimal policies and relate these to known planning horizon and other results from the literature. <s> BIB003 </s> Lot sizing and scheduling — Survey and extensions <s> Brief history review <s> We consider the n-period economic lot sizing problem, where the cost coefficients are not restricted in sign. In their seminal paper, H. M. Wagner and T. M. Whitin proposed an O(n2) algorithm for the special case of this problem, where the marginal production costs are equal in all periods and the unit holding costs are nonnegative. It is well known that their approach can also be used to solve the general problem, without affecting the complexity of the algorithm. In this paper, we present an algorithm to solve the economic lot sizing problem in O(n log n) time, and we show how the Wagner-Whitin case can even be solved in linear time. Our algorithm can easily be explained by a geometrical interpretation and the time bounds are obtained without the use of any complicated data structure. Furthermore, we show how Wagner and Whitin's and our algorithm are related to algorithms that solve the dual of the simple plant location formulation of the economic lot sizing problem. <s> BIB004 </s> Lot sizing and scheduling — Survey and extensions <s> Brief history review <s> Abstract Batching decisions are one of management's instruments to impact performance of goods-flow systems. There is a vast body of literature on analysis and modeling of batching. This paper aims to provide a structure for batching decisions that can help in positioning batching research and models with respect to issues pertinent to goods-flow management. The basis of the structure is a distinction of batching issues as related to three decision levels: (i) process choice/design, (ii) activity planning (aggregate planning and activity programming), and (iii) activity control. Furthermore, the paper discusses some often heard criticisms of batching analysis. The paper concludes with a little speculation of the authors on the future directions of batching research. <s> BIB005
Research on lot sizing started with the classical economic order quantity (EOQ) model [3, 37, 54] . The assumptions for the EOQ model are a single-level production process with no capacity constraints, which makes the problem become a single-item problem. The demand for that item is assumed to be stationary, i.e. demand occurs continuously with a constant rate. The EOQ model is a continuous time model with an infinite planning horizon. The optimal solution is easy to derive. Since these assumptions appear to be very restrictive, other models have evolved. First to mention is the economic lot scheduling problem (ELSP) BIB001  where capacity restrictions come in. Because scarce resources are usually shared in common by several items, the ELSP is a single-level, multi-item problem. BIB003 and BIB004 . The next generation of models has combined capacitated and dynamic approaches and bothered the community since then. Surveys of lot sizing literature can be found in BIB002 ,  and BIB005 . Also, scheduling was integrated with lot size decisions. This is what our review is about. Section 2 thus presents established single-level models for lot sizing and scheduling as well as new trends. Section 3 discusses continuous time approaches. Multi-level extensions are dealt with in Section 4. Finally, Section 5 provides some suggestions for future research directions.