Modeling Industrial Lot Sizing Problems: A Review
---
paper_title: Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches

paper_content:

Proofs from complexity theory as well as computational experiments indicate that most lot sizing problems are hard to solve. Because these problems are so difficult, various solution techniques have been proposed to solve them. In the past decade, meta-heuristics such as tabu search, genetic algorithms and simulated annealing, have become popular and efficient tools for solving hard combinational optimization problems. We review the various meta-heuristics that have been specifically developed to solve lot sizing problems, discussing their main components such as representation, evaluation neighborhood definition and genetic operators. Further, we briefly review other solution approaches, such as dynamic programming, cutting planes, Dantzig-Wolfe decomposition, Lagrange relaxation and dedicated heuristics. This allows us to compare these techniques. Understanding their respective advantages and disadvantages gives insight into how we can integrate elements from several solution approaches into more powerful hybrid algorithms. Finally, we discuss general guidelines for computational experiments and illustrate these with several examples.
---
paper_title: Sequencing and scheduling : algorithms and complexity

paper_content:

Sequencing and scheduling as a research area is motivated by questions that arise in production planning, in computer control, and generally in all situations in which scarce resources have to be allocated to activities over time. In this survey, we concentrate on the area of deterministic machine scheduling. We review complexity results and optimization and approximation algorithms for problems involving a single machine, parallel machines, open shops, flow shops and job shops. We also pay attention to two extensions of this area: resource-constrained project scheduling and stochastic machine scheduling.
---
paper_title: Inventory Management and Production Planning and Scheduling

paper_content:

THE CONTEXT AND IMPORTANCE OF INVENTORY MANAGEMENT AND PRODUCTION PLANNING AND SCHEDULING. The Importance of Inventory Management and Production Planning and Scheduling. Strategic Issues. Frameworks for Inventory Management and Production Planning and Scheduling. Forecasting. TRADITIONAL REPLENISHMENT SYSTEMS FOR MANAGING INDIVIDUAL--ITEM INVENTORIES. Order Quantities When Demand is Approximately Level. Lot Sizing for Individual Items with Time--Varying Demand. Individual Items with Probabilistic Demand. SPECIAL CLASSES OF ITEMS. Managing the Most Important (Class A) Inventories. Managing Routine (Class C) Inventories. Style Goods and Perishable Items. THE COMPLEXITIES OF MULTIPLE ITEMS AND MULTIPLE LOCATIONS. Coorinated Replenishments at a Single Stocking Point. Supply Chain Management and Multiechelon Inventories. PRODUCTION PLANNING AND SCHEDULING. An Overall Framework for Production Planning and Scheduling. Medium--Range Aggregate Production Planning. Material Requirements Planning and its Extensions. Just--in--Time and Optimized Production Technology. Short--Range Production Scheduling. Summary. Appendices. Indexes.
---
paper_title: Manufacturing Planning and Control Systems

paper_content:

The book is well-known for having the most current coverage available. A "non-numerical" approach is used with thoroughly integrated real applications. The Third Edition will provide complete integration of JIT concepts and techniques, continued use of real-world examples, and improved organization and style. There is more coverage of global factors, human issues, and strategic issues. The book also provides an introduction to production planning and control, as well as coverage of more advanced topics.
---
paper_title: Dynamic Version of the Economic Lot Size Model

paper_content:

(This article originally appeared in Management Science, October 1958, Volume 5, Number 1, pp. 89-96, published by The Institute of Management Sciences.) ::: ::: A forward algorithm for a solution to the following dynamic version of the economic lot size model is given: allowing the possibility of demands for a single item, inventory holding charges, and setup costs to vary over N periods, we desire a minimum total cost inventory management scheme which satisfies known demand in every period. Disjoint planning horizons are shown to be possible which eliminate the necessity of having data for the full N periods.
---
paper_title: A Backlogging Model and a Multi-Echelon Model of a Dynamic Economic Lot Size Production System---A Network Approach

paper_content:

Two dynamic economic lot size production systems are analyzed in this paper, the first being a single product model with backlogging and the second a multi-echelon model. In each model the objective is to find a production schedule that minimizes the total production and inventory costs. ::: ::: A key conceptual difficulty is that the mathematically perplexing problem of minimizing a concave function is being considered. It is shown that both models are naturally represented via single source networks. The network formulations reveal the underlying structure of the models, and facilitate development of efficient dynamic programming algorithms for calculating the optimal production schedules.
---
paper_title: Uncapacitated Lot-Sizing Problems with Start-Up Costs

paper_content:

We consider the uncapacitated economic lot-sizing problem with start-up costs as a mixed integer program. A family of strong valid inequalities is derived for the class as well as a polynomial separation algorithm. It is then shown how equivalent, or possibly stronger, formulations are obtained by the introduction of auxiliary variables. Finally, some limited computational results for a single item model and a multi-item model with changeover costs are reported.
---
paper_title: The discrete lot-sizing and scheduling problem

paper_content:

Abstract The discrete lot-sizing and scheduling problem consists in scheduling several products on a single machine so as to meet the known dynamic demand and to minimize the sum of inventory and setup cost. The planning interval is phased into many short periods, e.g. shifts or days, and setups may occur only at the beginning of a period. A branch-and-bound procedure is presented using Lagrangean relaxation for determining both lower bounds and feasible solutions. The relaxed problems are solved by dynamic programming. Computational results on a personal computer are reported for various examples from the literature with up to 12 products and 122 periods or 3 products and 250 periods. The procedure yields optimal solutions or at least feasible solutions with tight lower bounds in a few minutes. The results are compared with those obtained by solving the usual capacitated lot-sizing problem.
---
paper_title: The capacitated dynamic lot-sizing problem with startup and reservation costs: A forward algorithm solution

paper_content:

Abstract Often in production environments, there are several products available to be processed on a machine. The decisions that must be made are: 1) which product should be processed next, and 2) how much time should elapse before a changeover occurs and a different product is chosen for processing. This problem is known as the multiple product cycling problem . The single product variation of this problem is addressed in this paper. It is assumed that the product to be processed next has already been chosen (decision #1). The second decision concerning production run length must now be determined. In the single product problem, there is a fixed startup cost associated with turning the machine on in a period when the machine was off in the previous period and a fixed reservation cost incurred in each period in which the machine is on. Ending inventory in a period is assessed a holding cost. The relationship of the single product problem to the multiple period problem is as follows. The startup cost is identical to the changeover cost in the multiple product problem. By processing a particular product, other products must wait. This effect is captured by the reservation cost which is the opportunity cost one would incur by having the machine dedicated to processing a particular product. A forward dynamic programming algorithm is presented which uses heuristic rules to detect empirical decision horizons. The entire problem is partitioned into smaller Subproblems which are then easily solved. The subproblems are created by the occurrence of startup regeneration points. These are periods where there is no ending inventory and the following period contains a machine startup. Computational experience is reported which shows that reductions in computational effort (measured in CPU time and the number of nodes in the decision tree evaluated) can be as high as 95 to 99% when using the decision horizon techniques and bounding procedures described in this paper. These results are based on the solution of 28 test problems that were each 20 periods in length. Because a forward algorithm was used, not only were the solutions to the 20-period problems obtained, but the solutions to the one-period problems through 19-period problems were obtained as well. Even though the procedure described in this paper cannot guarantee that it will always find the optimal solution, it did find the optimal solution in every problem tested. By being able to solve the single product problem presented in this paper quickly, the ability to rapidly generate optimal or near optimal solutions to the multiple product problem (which uses the procedure described in this paper as a subroutine) appears closer to realization.
---
paper_title: Discrete Lotsizing and Scheduling by Batch Sequencing

paper_content:

The discrete lotsizing and scheduling problem for one machine with sequence dependent setup times and setup costs is solved as a single machine scheduling problem, which we term the batch sequencing problem. The relationship between the lotsizing problem and the batch sequencing problem is analyzed. The batch sequencing problem is solved with a brauch & bound algorithm which is accelerated by bounding and dominance rules. The algorithm is compared with recently published procedures for solving variants of the DLSP and is found to be more efficient if the number of items is not large.
---
paper_title: A dynamic lot-sizing model with multi-mode replenishments: polynomial algorithms for special cases with dual and multiple modes

paper_content:

Abstract This paper generalizes the classical dynamic lot-sizing model to consider the case where replenishment orders may be delivered by multiple shipment modes. Each mode may have a different lead time and is characterized by a different cost function. The model represents those applications in which products can be purchased through various suppliers or delivered from a single source using various transportation modes with different lead times and costs. The problem is challenging due to the consideration of cargo capacity constraints, i.e., the multiple set-ups cost structure, associated with a replenishment mode. The paper presents several structural optimality properties of the problem and develops efficient algorithms, based on the dynamic programming approach, to find the optimal solution. The special, yet practical, cases of the two-mode replenishment problem analyzed in this paper are analytically tractable, and hence, the respective problems can be solved in polynomial time.
---
paper_title: Rolling-horizon lot-sizing when set-up times are sequence-dependent

paper_content:

The challenging problem of efficient lot sizing on parallel machines with sequence-dependent set-up times is modelled using a new mixed integer programming (MIP) formulation that permits multiple set-ups per planning period. The resulting model is generally too large to solve optimally and, given that it will be used on a rolling horizon basis with imperfect demand forecasts, approximate models that only generate exact schedules for the immediate periods are developed. Both static and rolling horizon snapshot tests are carried out. The approximate models are tested and found to be practical rolling horizon proxies for the exact model, reducing the dimensionality of the problem and allowing for faster solution by MIP and metaheuristic methods. However, for large problems the approximate models can also consume an impractical amount of computing time and so a rapid solution approach is presented to generate schedules by solving a succession of fast MIP models. Tests show that this approach is able to produc...
---
paper_title: Multi-Item Lot Size Scheduling by Heuristic Part I: With Fixed Resources

paper_content:

The multi-item lot size problem has been a formal management issue for some decades. The lot size decision of how much to produce and when usually considers the trade-off between lost productivity from frequent set-ups and short runs and the higher inventory costs arising from longer runs. When the decision must also consider shared limited production resources, the problem becomes complex. ::: ::: The paper is presented in two parts. Part I outlines a heuristic for solving the multi-item lot size problem given fixed production resources. The problem is initially structured as a network of unlimited capacity. An arc-cutting criterion is suggested, successively paring the unconstrained lot size optimum in low-cost increments until a feasible integer solution occurs. ::: ::: In Part II of this 2 part paper, the heuristic is extended to include variable capacity constraints. Computational results for both the fixed and variable capacity configurations and the bibliography conclude the presentation.
---
paper_title: The Joint Replenishment Problem with Time-Varying Costs and Demands: Efficient, Asymptotic and ε-Optimal Solutions

paper_content:

We address the Joint Replenishment Problem (JRP) where, in the presence of joint setup costs, dynamic lot sizing schedules need to be determined for m items over a planning horizon of N periods, with general time-varying cost and demand parameters. We develop a new, so-called, partitioning heuristic for this problem, which partitions the complete horizon of N periods into several relatively small intervals, specifies an associated joint replenishment problem for each of these, and solves them via a new, efficient branch-and-bound method. The efficiency of the branch-and-bound method is due to the use of a new, tight lower bound to evaluate the nodes of the tree, a new branching rule, and a new upper bound for the cost of the entire problem. The partitioning heuristic can be implemented with complexity O(mN2log log N). It can be designed to guarantee an e-optimal solution for any e > 0, provided that some of the model parameters are uniformly bounded from above or below. In particular, the heuristic is asy...
---
paper_title: An effective heuristic for the CLSP with set-up times

paper_content:

The problem of multi-item, single level, capacitated, dynamic lot-sizing with set-up times (CLSP with set-up times) is considered. The difficulty of the problem compared with its counterpart without set-up times is explained. A lower bound on the value of the objective function is calculated by Lagrangian relaxation with subgradient optimisation. During the process, attempts are made to get good feasible solutions (ie. upper bounds) through a smoothing heuristic, followed by a local search with a variable neighbourhood. Solutions found in this way are further optimised by solving a capacitated transshipment problem. The paper describes the various elements of the solution procedure and presents the results of extensive numerical experimentation.
---
paper_title: Minimum Change-Over Scheduling of Several Products on One Machine

paper_content:

Given a finite horizon delivery schedule for n products we wish to schedule production on a single machine to meet deliveries and minimize the number of change-overs of the machine from one product to another. A state space is defined and in it a network is constructed such that the shortest distance through the network corresponds to the minimum number of production change-overs. Certain properties of the optimal path are deduced from the dynamic programming formulation of the shortest route problem, and these properties are utilized in the construction of an algorithm that finds the optimal path. A numerical example illustrates the method.
---
paper_title: Setup cost reduction in the dynamic lot-size model

paper_content:

Abstract Recently, one primary focus of Operations Management has turned to setup reduction because of the growth of Just-in-Time(JIT) manufacturing. Porteus [1] and Billington [2] have developed optimal policies for calculating investment in setup reduction and lot-size in the EOQ model when setup cost is some function of investment. Zangwill [3] has examined the effects of incremental setup cost reductions in the multi-factility dynamic demand environment on costs and zeroinventory facilities. His focus is on obtaining zero-inventory facilities and maximizing savings from lower setup costs without including the cost of such an event. As an extension of these developments, we model the Wagner-Whitin problem with a one-time oportunity to invest in setup reduction. Setup cost is treated as a policy variable and defined as a function of the decision variable representing the annual amortized investment in setup cost reduction. We use an exponential setup reduction function, but speculate that the results also hold for other functions as well. In contrast to Zangwill, we take a direct approach by explicitly finding the optimal investment in setup cost reduction while generating an optimal lot-sizing schedule. Solving a model that incorporates the trade-off between investment and savings results in more realistic solutions. We use a golden section search and the Wagner-Whitin algorithm to obtain solutions for lot-size, setup cost, and the investment in setup reduction. This model is also formulated as a network to better illustrate the interaction between the decision variables. The network formulation can also be exploited to solve the problem with linear programming or network techniques. Finally, we state and prove two theorems that hold for all setup reduction models whether they assume constant or dynamic demand. The first theorem asserts that optimal values for setupt cost and lot-sizes stay fixed over a particular range of holding costs. The second theorem states that the optimal setup cost is independent of initial setup cost.
---
paper_title: Algorithms for Capacitated, Multi-Item Lot-Sizing without Set-Ups

paper_content:

The multi-item lot-sizing problem considered here is concerned with finding the lot sizes over a horizon of discrete time periods to meet known future demand without incurring backlogs, such that the total cost of production and inventory holding is minimized. The capacity constraints arise because the production of each item consumes capacitated production resources at a given rate. Production is assumed to occur without set-ups. The problem is formulated as a capacitated trans-shipment problem. Use of modern, minimum-cost network flow algorithms, coupled with appropriate starting procedures, allows realistically large problem instances to be solved efficiently; thus obviating the need for specialized algorithms based on restrictive assumptions regarding cost structures.
---
paper_title: The Capacitated Lot-Sizing Problem with Linked Lot Sizes

paper_content:

In this paper a new mixed integer programming (MIP) model formulation and its incorporation into a time-oriented decomposition heuristic for the capacitated lot-sizing problem with linked lot sizes (CLSPL) is proposed. The solution approach is based on an extended model formulation and valid inequalities to yield a tight formulation. Extensive computational tests prove the capability of this approach and show a superior solution quality with respect to other solution algorithms published so far.
---
paper_title: A framework for modelling setup carryover in the capacitated lot sizing problem

paper_content:

This paper addresses the single-level capacitated lot sizing problem (CLSP) with setup carryover. Specifically, we consider a class of production planning problems in which multiple products can be produced within a time period and significant setup times are incurred when changing from one product to another. Hence, there might be instances where developing a feasible schedule becomes possible only if setups are carried over from one period to another. We develop a modelling framework to formulate the CLSP with setup times and setup carryovers. We then extend the modelling framework to include multiple machines and tool requirements planning. The need for such a model that integrates both planning and lot sizing decisions is motivated by the existence of a similar problem in a paper mill. We apply the modelling framework to solve optimally, an instance of the paper mill's problem.
---
paper_title: The discrete lot-sizing and scheduling problem with sequence-dependent setup costs

paper_content:

Abstract We consider the problem of scheduling several products on a single machine so as to meet the known dynamic demand and to minimize the sum of inventory costs and sequence-dependent setup costs. The planning interval is subdivided into many short periods, e.g. shifts or days, and any lot must last one or several full periods. We formulate this problem as a travelling salesman problem with time windows and present a new procedure for determining lower bounds using Lagrangean relaxation as well as a heuristic. Computational results for problems with up to 10 products and 150 periods are reported.
---
paper_title: A Dual Ascent Procedure for Multiproduct Dynamic Demand Coordinated Replenishment with Backlogging

paper_content:

This paper describes a mixed-integer programming formulation and dual ascent based branch-and-bound algorithm for the multiproduct dynamic demand coordinated replenishment problem with backlogging. The single sourcing properties of the formulation and the hierarchical structure of the fixed-charge and continuous variables yield an extremely tight linear programming relaxation for the problem. A branch-and-bound algorithm based on Erlenkotter's dual ascent, dual adjustment, and primal construction concepts exploits these properties to obtain an efficient solution procedure. Computational results indicate that the new procedures find optimal solutions in less than five percent of the computational time of the most efficient previous algorithm. The heuristic performance of the procedures also demonstrate their superiority over existing approaches. We solved problems with 12 time periods and 20 products in 0.41 CPU seconds, and heuristic solutions with a worst-case three-percent optimality gap are found in 0.068 CPU seconds. The efficiency and large-scale capability of the procedures make their potential application in inventory requirements planning systems promising.
---
paper_title: A Dynamic Lot Sizing Model with Learning in Setups

paper_content:

This paper considers the dynamic lot sizing problem of H. M. Wagner and T. M. Whitin with the assumption that the total cost of n setups is a concave nondecreasing function of n. Such setup costs could arise from the worker learning in setups and/or technological improvements in setup methods. An efficient dynamic programming algorithm is developed to solve a finite horizon problem and results are presented to find decision/forecast horizons. Several new results presented in the paper have potential use in solving other related problems.
---
paper_title: Production Smoothing of Economic Lot Sizes with Non-Decreasing Requirements

paper_content:

This paper considers the problem of finding a production schedule, in terms of how much to produce in each period, that minimizes the total cost of supplying known market requirements for a single product. The costs include a concave production cost, a concave inventory cost, and a piecewise concave cost of changing the production level from one period to the next. Assuming that there is no backlogging of requirements and that the market requirements are monotone increasing, i.e., not decreasing from period to period, the form of the minimum cost production schedule is obtained. This form is then exploited in a dynamic programming algorithm to provide an efficient means of exactly determining the minimum cost schedule. An interesting calculation reducing theorem is also developed to further enhance the efficiency of the dynamic programming algorithm.
---
paper_title: Lot Sizing and Scheduling with Sequence Dependent Setup Costs and Times and Efficient Rescheduling Opportunities

paper_content:

Abstract This paper deals with lot sizing and scheduling for a single-stage, single-machine production system where setup costs and times are sequence dependent. A large-bucket mixed integer programming (MIP) model is formulated which considers only efficient sequences. A tailor-made enumeration method of the branch-and-bound type solves problem instances optimally and efficiently. The size of solvable cases ranges from 3 items and 15 periods to 10 items and 3 periods. Furthermore, it will become clear that rescheduling can neatly be done.
---
paper_title: Simultaneous lotsizing and scheduling by combining local search with dual reoptimization

paper_content:

Abstract The contribution of this paper is twofold. On the one hand, the particular problem of integrating lotsizing and scheduling of several products on a single, capacitated production line is modelled and solved, taking into account sequence-dependent setup times. Thereby, continuous lotsizes, meeting deterministic dynamic demands, are to be determined and scheduled with the objective of minimizing inventory holding costs and sequence-dependent setup costs. On the other hand, a new general algorithmic approach is presented: A dual reoptimization algorithm is combined with a local search heuristic for solving a mixed integer programming problem. This idea is applied to the above lotsizing and scheduling problem by embedding a dual network flow algorithm into threshold accepting and simulated annealing, respectively. Computational tests show the effectiveness of the new solution method.
---
paper_title: The coordinated replenishment dynamic lot-sizing problem with quantity discounts

paper_content:

Abstract In the classical coordinated replenishment dynamic lot-sizing problem, the primary motivation for coordination is in the presence of the major and minor setup costs. In this paper, a separate element of coordination made possible by the offer of quantity discounts is considered. A mathematical programming formulation for the extended problem under the all-units discount price structure and the incremental discount price structure is provided. Then, using variable redefinitions, tighter formulations are presented in order to obtain tight lower bounds for reasonable size problems. More significantly, as the problem is NP-hard, we present an effective polynomial time heuristic procedure, for the incremental discount version of the problem, that is capable of solving reasonably large size problems. Computational results for the heuristic procedure are reported in the paper.
---
paper_title: The capacitated dynamic lot size problem with variable technology

paper_content:

Traditionally, the technological coefficients in production models were assumed to be fixed. In recent years however, researchers have used the learning curve model to represent nonlinear technological coefficients, and the dynamic lot-sizing problem with learning in setups has received attention. This article extends the research to consider capacity restrictions in the single-level, multi-item case. The research has two goals, first, to analyze the effects of setup learning on a production schedule, and second, to investigate efficient ways of solving the resulting nonlinear integer model. Previously derived algorithms do not address the issue of capacity; thus a heuristic is developed and its solution is compared with the optimal solution, where possible, or to a lower bound solution.
---
paper_title: Capacitated lot-sizing with sequence dependent setup costs

paper_content:

A new model is presented for capacitated lot-sizing with sequence dependent setup costs. The model is solved heuristically with a backward oriented method; the sequence and lot-size decisions are based on a priority rule which consists of a convex combination of setup and holding costs. A computational study is performed where the heuristic is compared with the Fleischmann approach for the discrete lot-sizing and scheduling problem with sequence dependent setup costs.
---
paper_title: Coordinated Capacitated Lot-Sizing Problem with Dynamic Demand: A Lagrangian Heuristic

paper_content:

Coordinated replenishment problems are common in manufacturing and distribution when a family of items shares a common production line, supplier, or a mode of transportation. In these situations the coordination of shared, and often limited, resources across items is economically attractive. This paper describes a mixed-integer programming formulation and Lagrangian relaxation solution procedure for the single-family coordinated capacitated lot-sizing problem with dynamic demand. The problem extends both the multi-item capacitated dynamic demand lot-sizing problem and the uncapacitated coordinated dynamic demand lot-sizing problem. We provide the results of computational experiments investigating the mathematical properties of the formulation and the performance of the Lagrangian procedures. The results indicate the superiority of the dual-based heuristic over linear programming-based approaches to the problem. The quality of the Lagrangian heuristic solution improved in most instances with increases in problem size. Heuristic solutions averaged 2.52% above optimal. The procedures were applied to an industry test problem yielding a 22.5% reduction in total costs.
---
paper_title: Programming of Economic Lot Sizes

paper_content:

This paper studies the planning problem faced by a machine shop required to produce many different items so as to meet a rigid delivery schedule, remain within capacity limitations, and at the same time minimize the use of premium-cost overtime labor. It differs from alternative approaches to this well-known problem by allowing for setup cost indivisibilities. ::: ::: As an approximation, the following linear programming model is suggested: Let an activity be defined as a sequence of the inputs required to satisfy the delivery requirements for a single item over time. The input coefficients for each such activity may then be constructed so as to allow for all setup costs incurred when the activity is operated at the level of unity or at zero. It is then shown that in any solution to this problem, all activity levels will turn out to be either unity or zero, except for those related to a group of items which, in number, must be equal to or less than the original number of capacity constraints. This result means that the linear programming solution should provide a good approximation whenever the number of items being manufactured is large in comparison with the number of capacity constraints.
---
paper_title: Lotsizing and Scheduling on Parallel Machines with Sequence-Dependent Setup Costs

paper_content:

Industrial lotsizing and scheduling pose very difficult analytical problems. We propose an unconventional model that deals with sequence-dependent setup costs in a multiple-machine environment. The sequence-splitting model splits an entire schedule into subsequences, leading to tractable subproblems. An optimization approach based on a column generation/branch and bound methodology is developed, and heuristically adapted to test problems including five real-world problem instances gathered from industry.
---
paper_title: Multiperiod Production Planning Carrying over Set-up Time

paper_content:

Set-ups eat production capacity time and continue troubling production planning, especially on bottlenecks. The shortening of production planning periods to days, shifts or even less has increased the relative length of set-up times against the periods. Yet, many production planning models either ignore set-up times or, paradoxically, split longer multiperiod batches by adding set-ups at breaks between planning periods. The MILP-based capacitated lot-sizing models that include set-up carry-overs, i.e. allow a carry-over of a set-up of a product to the next period in case a product can be produced in subsequent periods, have incorporated fixed set-up fees without consideration of capacity consumed by set-up time. Inspired by production planning in process industries where set-up times still remain substantial, we incorporated set-up time with associated cost in two modifications of carry-over models. Comparison with an earlier benchmark model without set-up carry-over shows that substantial savings can be derived from the fundamentally different production plans enforced by carry-overs. Moreover, we show that heuristic inclusion of carry-overs by removal of set-ups from non-carry-over solutions is inefficient.
---
paper_title: Some Optimum Algorithms for Scheduling Problems with Changeover Costs

paper_content:

We consider a production line that can produce one of n items per day. The demand schedule for all items is known in advance, and all items must be produced on or before their deadlines. We want a production schedule that meets all demand deadlines and minimizes the total changeover cost. The changeover cost has a special structure: it is i one dollar if the production line changes from producing item i to item j and i is less than j, and ii zero if i is greater than or equal to j. We also consider multiple identical production lines with all demands due at the end of every month, and assume that there is exactly enough demand at the end of every month. We obtain optimum production schedules for both the single-line and multiple-line case.
---
paper_title: The capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times

paper_content:

We consider the single machine capacitated lot-sizing and scheduling problem (CLSP) with sequence-dependent setup costs and non-zero setup times, with the additional feature that setups may be carried over from one period to the next, and that setups are preserved over idle periods. We provide an exact formulation of this problem as a mixed-integer program.It is well known that the CLSP is NP-hard. Therefore, we have also developed a heuristic for solving large problem instances. This is coupled with a procedure for obtaining a lower bound on the optimal solution. We carry out a computational study to test the accuracy of several different lower bounding linear relaxations and the approximate solution obtained by the heuristic. In our study, the average deviation of the heuristic solution from the corresponding exact solution depends on the size of the problem and ranges from 10 to 16%. The heuristic is more effective when there are many more products than there are planning periods. This is a desirable property from a practical viewpoint since most firms are likely to implement such a procedure on a rolling horizon basis, solving the problem repeatedly for a few periods at a time.
---
paper_title: A heuristic for production scheduling and inventory control in the presence of sequence-dependent setup times

paper_content:

The consideration of sequence-dependent setup times is one of the most difficult aspects of production scheduling problems. This paper reports on the development of a heuristic procedure to address a realistic production and inventory control problem in the presence of sequence-dependent setup times. The problem considers known monthly demands, variable production rates, holding costs, minimum and maximum inventory levels per product, and regular and overtime capacity limits. The problem is formulated as a Mixed-Integer Program (MIP), where subtour elimination constraints are needed to enforce the generation of job sequences in each month. By relaxing the subtour elimination constraints, the MIP formulation can be used to find a lower bound on the optimal solution. CPLEX 3.0 is used to calculate lower bounds for relatively small instances of this production problem, which are then used to assess the merit of a proposed heuristic. The heuristic is based on a simple short-term memory tabu search method that coordinates linear programming and traveling salesperson solvers in the search for optimal or near-optimal production plans.
---
paper_title: A modified framework for modelling set-up carryover in the capacitated lotsizing problem

paper_content:

In this note, a modified framework to model set-up carryovers in the capacitated lotsizing problem is presented. The proposed framework allows product dependent set-up times and costs to be incorporated. This is an extension of an earlier published work on modelling set-up carryovers for the constant set-up time scenario. An example to illustrate the modified framework is also provided.
---
paper_title: An integrated model for job-shop planning and scheduling

paper_content:

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.
---
paper_title: An economic lot-sizing problem with perishable inventory and economies of scale costs: Approximation solutions and worst case analysis

paper_content:

The costs of many economic activities such as production, purchasing, distribution, and inventory exhibit economies of scale under which the average unit cost decreases as the total volume of the activity increases. In this paper, we consider an economic lot-sizing problem with general economies of scale cost functions. Our model is applicable to both nonperishable and perishable products. For perishable products, the deterioration rate and inventory carrying cost in each period depend on the age of the inventory. Realizing that the problem is NP-hard, we analyze the effectiveness of easily implementable policies. We show that the cost of the best Consecutive-Cover-Ordering (CCO) policy, which can be found in polynomial time, is guaranteed to be no more than (42 5)/7 1.52 times the optimal cost. In addition, if the ordering cost function does not change from period to period, the cost of the best CCO policy is no more than 1.5 times the optimal cost. © 2005 Wiley Periodicals, Inc. Naval Research Logistics 52: 536 -548, 2005.
---
paper_title: Rolling-horizon lot-sizing when set-up times are sequence-dependent

paper_content:

The challenging problem of efficient lot sizing on parallel machines with sequence-dependent set-up times is modelled using a new mixed integer programming (MIP) formulation that permits multiple set-ups per planning period. The resulting model is generally too large to solve optimally and, given that it will be used on a rolling horizon basis with imperfect demand forecasts, approximate models that only generate exact schedules for the immediate periods are developed. Both static and rolling horizon snapshot tests are carried out. The approximate models are tested and found to be practical rolling horizon proxies for the exact model, reducing the dimensionality of the problem and allowing for faster solution by MIP and metaheuristic methods. However, for large problems the approximate models can also consume an impractical amount of computing time and so a rapid solution approach is presented to generate schedules by solving a succession of fast MIP models. Tests show that this approach is able to produc...
---
paper_title: MRP lot sizing with variable production/purchasing costs: formulation and solution

paper_content:

SUMMARY The research on lot sizing is extensive; however, no author in the literature reviewed to date provides an optimal solution algorithm to a prevalent problem which is found in manufacturing. A multi-level, general product-structure, variable-cost model is presented which follows the procedure of a closed-loop material requirements planning (MRP) system, and incorporates many conditions that production and material managers find in practice. A branch and bound (B&B7) algorithm is developed. The efficiency of B&B is derived from effective lower bounds and solution procedures which are determined on the basis of the space-time structure of the MRP lot-sizing problem and its non-convex total-cost function. This path-dependent lower bound is computationally efficient and guarantees an optimal solution. The B&B algorithm is tested on problems and compared to heuristics in the literature.
---
paper_title: Integration of lotsizing and scheduling decisions in a job-shop

paper_content:

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.
---
paper_title: The coordinated replenishment dynamic lot-sizing problem with quantity discounts

paper_content:

Abstract In the classical coordinated replenishment dynamic lot-sizing problem, the primary motivation for coordination is in the presence of the major and minor setup costs. In this paper, a separate element of coordination made possible by the offer of quantity discounts is considered. A mathematical programming formulation for the extended problem under the all-units discount price structure and the incremental discount price structure is provided. Then, using variable redefinitions, tighter formulations are presented in order to obtain tight lower bounds for reasonable size problems. More significantly, as the problem is NP-hard, we present an effective polynomial time heuristic procedure, for the incremental discount version of the problem, that is capable of solving reasonably large size problems. Computational results for the heuristic procedure are reported in the paper.
---
paper_title: Dynamic Lot Sizing with Batch Ordering and Truckload Discounts

paper_content:

This paper studies two important variants of the dynamic economic lot-sizing problem that are applicable to a wide range of real-world situations. In the first model, production in each time period is restricted to a multiple of a constant batch size, where backlogging is allowed and all cost parameters are time varying. Several properties of the optimal solution are discussed. Based on these properties, an efficient dynamic programming algorithm is developed. The efficiency of the dynamic program is further improved through the use of Monge matrices. Using the results developed for the first model, an O(n3log n) algorithm is developed to solve the second model, which has a general form of product acquisition cost structure, including a fixed charge for each acquisition, a variable unit production cost, and a freight cost with a truckload discount. This algorithm can also be used to solve a more general problem with concave cost functions.
---
paper_title: An Efficient Algorithm for Multi-Item Scheduling

paper_content:

A number of resource-allocation problems, including that of multi-item scheduling, may be solved approximately as large linear programs, as in Manne [Management Sci. 4, 115-135 1958]. Dzielinski and Gomory [Management Sci. 11, 874-890 1965] applied the Dantzig-Wolfe decomposition principle to this problem. Here, the problem is attacked directly, using a column generation technique and Dantzig and Van Slyke's generalized upper-bounding method [J. Comp. and Syst. Sci. 1, 213-226 1967]. For problems involving I items and T time periods, one need deal with a basis matrix of dimension only T by T. A lower bound on the optimal cost may be developed, and intermediate solutions all have Manne's integer property loc. cit.. Computational experiments, including an option for pricing out subproblem solutions until none is useful, show a number of iterations to optimality of from one-half to one-ninth the number required by the decomposition principle with work per iteration remaining approximately the same. Extensions of the basic model are also described. These form the core of an automated production-scheduling and inventory-control system, currently being used by a major U. S. manufacturer. Computational experience with this extended model is presented.
---
paper_title: Hybrid heuristics for the capacitated lot sizing and loading problem with setup times and overtime decisions

paper_content:

The capacitated lot sizing and loading problem (CLSLP) deals with the issue of determining the lot sizes of product families/end items and loading them on parallel facilities to satisfy dynamic demand over a given planning horizon. The capacity restrictions in the CLSLP are imposed by constraints specific to the production environment considered. When a lot size is positive in a specific period, it is loaded on a facility without exceeding the sum of the regular and overtime capacity limits. Each family may have a different process time on each facility and furthermore, it may be technologically feasible to load a family only on a subset of existing facilities. So, in the most general case, the loading problem may involve unrelated parallel facilities of different classes. Once loaded on a facility, a family may consume capacity during setup time. Inventory holding and overtime costs are minimized in the objective function. Setup costs can be included if setups incur costs other than lost production capacity. The CLSLP is relevant in many industrial applications and may be generalized to multi-stage production planning and loading models. The CLSLP is a synthesis of three different planning and loading problems, i.e., the capacitated lot sizing problem (CLSP) with overtime decisions and setup times, minimizing total tardiness on unrelated parallel processors, and, the class scheduling problem, each of which is NP in the feasibility and optimality problems. Consequently, we develop hybrid heuristics involving powerful search techniques such as simulated annealing (SA), tabu search (TS) and genetic algorithms (GA) to deal with the CLSLP. Results are compared with optimal solutions for 108 randomly generated small test problems. The procedures developed here are also compared against each other in 36 larger size problems.
---
paper_title: An Algorithm for Single-Item Capacitated Economic Lot Sizing with Piecewise Linear Production Costs and General Holding Costs

paper_content:

We consider the Capacitated Economic Lot Size problem with piecewise linear production costs and general holding costs, which is an NP-hard problem but solvable in pseudo-polynomial time. A straightforward dynamic programming approach to this problem results in an [TeX: $O(n^2 \\bar{c} \\bar{d} )$] algorithm, where [TeX: $n$] is the number of periods, and [TeX: $\\bar d$ and $\\bar c$] are the average demand and the average production capacity over the $n$ periods, respectively. However, we present a dynamic programming procedure with complexity [TeX: $O(n^2 \\bar{q} \\bar{d} )$], where [TeX: $\\bar q$] is the average number of pieces of the production cost functions. In particular, this means that problems in which the production functions consist of a fixed set-up cost plus a linear variable cost are solved in [TeX: $O(n^2 \\bar{d})$] time. Hence, the running time of our algorithm is only linearly dependent on the magnitude of the data. This result also holds if extensions such as backlogging and start-up costs are considered. Moreover, computational experiments indicate that the algorithm is capable of solving quite large problem instances within a reasonable amount of time. For example, the average time needed to solve test instances with 96 periods, 8 pieces in every production function and average demand of 100 units, is approximately 40 seconds on a SUN SPARC 5 workstation.
---
paper_title: Hybrid heuristics for the multi-stage capacitated lot sizing and loading problem

paper_content:

The multi-stage capacitated lot sizing and loading problem (MCLSLP) deals with the issue of determining the lot sizes of product items in serially-arranged manufacturing stages and loading them on parallel facilities in each stage to satisfy dynamic demand over a given planning horizon. It is assumed that regular time capacity decisions have already been made in the tactical level and allocated to the stages, but it is still an important decision problem whether to augment regular time capacity by overtime capacity. Each item may be processed on a technologically feasible subset of existing facilities with different process and setup times on each facility. Since the solution of the MCLSLP requires the design of a powerful algorithm, simulated annealing (SA) and genetic algorithms (GA) are integrated to enhance their individual performances. Furthermore, these global optimisation methods are incorporated into a Lagrangean relaxation scheme, hence creating a hybrid solution methodology. Numerical results obtained using these methods confirm the mutual benefits of integrating different solution techniques.
---
paper_title: Lotsizing and Scheduling on Parallel Machines with Sequence-Dependent Setup Costs

paper_content:

Industrial lotsizing and scheduling pose very difficult analytical problems. We propose an unconventional model that deals with sequence-dependent setup costs in a multiple-machine environment. The sequence-splitting model splits an entire schedule into subsequences, leading to tractable subproblems. An optimization approach based on a column generation/branch and bound methodology is developed, and heuristically adapted to test problems including five real-world problem instances gathered from industry.
---
paper_title: Lot sizing problems with strong set-up interactions

paper_content:

We address the problem of coordinated replenishment of products when the products can be produced only in fixed proportion to each other. Such problems commonly arise in the manufacture of sheet/plate metal parts or die-cast parts. The problem is a variant of the well-known Joint Replenishment Problem. We call this problem the Strong Interaction Problem (SIP). After giving a mathematical formulation of the problem, we show that the general problem is NP-hard. An important variant of the problem, in which products are unique to a family, is shown to be polynomially solvable. We present several lower bounds, an exact algorithm and a heuristic for the problem. Computational testing on randomly generated problems suggests that our exact algorithm performs very well when compared with a commercially available integer programming solver. The heuristic method also gives good solutions.
---
paper_title: Inventory replenishment model: lot sizing versus just-in-time delivery

paper_content:

Motivated by a practical industrial problem where a manufacturer stipulates a minimum order from each buyer but where a local dealer promises the buyer a just-in-time delivery with a slightly higher unit cost, this paper uses a dynamic lot-sizing model with a stepwise cargo cost function and a minimum order amount constraint to help the buyer select the supplier with minimum total cost.
---
paper_title: An economic lot-sizing problem with perishable inventory and economies of scale costs: Approximation solutions and worst case analysis

paper_content:

The costs of many economic activities such as production, purchasing, distribution, and inventory exhibit economies of scale under which the average unit cost decreases as the total volume of the activity increases. In this paper, we consider an economic lot-sizing problem with general economies of scale cost functions. Our model is applicable to both nonperishable and perishable products. For perishable products, the deterioration rate and inventory carrying cost in each period depend on the age of the inventory. Realizing that the problem is NP-hard, we analyze the effectiveness of easily implementable policies. We show that the cost of the best Consecutive-Cover-Ordering (CCO) policy, which can be found in polynomial time, is guaranteed to be no more than (42 5)/7 1.52 times the optimal cost. In addition, if the ordering cost function does not change from period to period, the cost of the best CCO policy is no more than 1.5 times the optimal cost. © 2005 Wiley Periodicals, Inc. Naval Research Logistics 52: 536 -548, 2005.
---
paper_title: Warehouse space capacity and delivery time window considerations in dynamic lot-sizing for a simple supply chain

paper_content:

Abstract This paper studies a single item, two-echelon dynamic lot-sizing model with delivery time windows, early shipment penalties, and warehouse space capacity constraints. The two-echelon system consists of a warehouse and a distribution center. The underlying problem is motivated by third party logistics and vendor managed inventory applications in the computer industry where delivery time windows are typically specified by the distribution center under the terms of a supply contract. The capacity of the warehouse is limited. This constraint should be considered explicitly because the finished products are expensive items (such as computer equipment and peripherals), and they have to be stored in the warehouse in an appropriate climate before they are shipped to the distribution center. Studying the optimality properties of the problem, the paper provides a polynomial time algorithm for computing its solution. The optimal solution includes: (i) the replenishment plan specifying “when, and in what quantities, to replenish the stock at the third-party warehouse,” and (ii) the dispatch plan specifying “when, and in what quantities, to release an outbound shipment to the distribution center, and in which order to satisfy the demands.” The algorithm is based on dynamic programming and requires O(T3) computational complexity.
---
paper_title: Lot sizing for a product subject to obsolescence or perishability

paper_content:

Abstract This paper presents a stochastic dynamic programming model for determining the optimal ordering policy for a perishable or potentially obsolete product so as to satisfy known time-varying demand over a specified planning horizon. We have considered random life time perishability where, at the end of each discrete period, the total remaining inventory either becomes worthless or remains usable for at least the next period. Two approximate solution methods are shown. The optimal and heuristic methods are compared on a large set of test problems and their performance as a function of various problem parameters is analyzed.
---
paper_title: Bounded Production and Inventory Models with Piecewise Concave Costs

paper_content:

An n period single-product single-facility model with known requirements and separable piecewise concave production and storage costs is considered. It is shown using network flow concepts that for arbitrary bounds on production and inventory in each period there is an optimal schedule such that if, for any two periods, production does not equal zero or its upper or lower bound, then the inventory level in some intermediate period equals zero or its upper or lower bound. An algorithm for searching such schedules for an optimal one is given where the bounds on production are -∞, 0 or ∞. A more efficient algorithm assumes further that inventory bounds satisfy “exact requirements.”
---
paper_title: Minimum Concave-Cost Solution of Leontief Substitution Models of Multi-Facility Inventory Systems

paper_content:

The paper shows that a broad class of problems can be formulated as minimizing a concave function over the solution set of a Leontief substitution system. The class includes deterministic single- and multi-facility economic lot size, lot-size smoothing, warehousing, product-assortment, batch-queuing, capacity-expansion, investment consumption, and reservoir-control problems with concave cost functions. Because in such problems an optimum occurs at an extreme point of the solution set, we can utilize the characterization of the extreme points given in a companion paper to obtain most existing qualitative characterizations of optimal policies for inventory models with concave costs in a unified manner. Dynamic programming recursions for searching the extreme points to find an optimal point are given in a number of cases. We only give algorithms whose computational effort increases algebraically (instead of exponentially) with the size of the problem.
---
paper_title: A new characterization for the dynamic lot size problem with bounded inventory

paper_content:

In this paper, we address the dynamic lot size problem with storage capacity. As in the unconstrained dynamic lot size problem, this problem admits a reduction of the state space. New properties to obtain optimal policies are introduced. Based on these properties a new dynamic programming algorithm is devised. Superiority of the new algorithm to the existing procedure is demonstrated. Furthermore, the new algorithm runs in O(T) expected time when demands vary between zero and the storage capacity. Computational results are reported for randomly generated problems.
---
paper_title: Transshipment through crossdocks with inventory and time windows

paper_content:

The supply chain between manufacturers and retailers always includes transshipments through a network of locations. A major challenge in making demand meet supply has been to coordinate transshipment activities across the chain aimed at reducing costs and increasing service levels in the face of a range of factors, including demand fluctuations, short lead times, warehouse limitations and transportation and inventory costs. The success in implementing push-pull strategies, when firms change from one strategy to another in managing the chain and where time lines are crucial, is dependent on adaptive transshipment scheduling. Yet again, in transshipment through crossdocks, where just-in-time objectives prevail, precise scheduling between suppliers, crossdocks and customers is required to avoid inventory backups or delays.
---
paper_title: Warehouse space capacity and delivery time window considerations in dynamic lot-sizing for a simple supply chain

paper_content:

Abstract This paper studies a single item, two-echelon dynamic lot-sizing model with delivery time windows, early shipment penalties, and warehouse space capacity constraints. The two-echelon system consists of a warehouse and a distribution center. The underlying problem is motivated by third party logistics and vendor managed inventory applications in the computer industry where delivery time windows are typically specified by the distribution center under the terms of a supply contract. The capacity of the warehouse is limited. This constraint should be considered explicitly because the finished products are expensive items (such as computer equipment and peripherals), and they have to be stored in the warehouse in an appropriate climate before they are shipped to the distribution center. Studying the optimality properties of the problem, the paper provides a polynomial time algorithm for computing its solution. The optimal solution includes: (i) the replenishment plan specifying “when, and in what quantities, to replenish the stock at the third-party warehouse,” and (ii) the dispatch plan specifying “when, and in what quantities, to release an outbound shipment to the distribution center, and in which order to satisfy the demands.” The algorithm is based on dynamic programming and requires O(T3) computational complexity.
---
paper_title: Production Smoothing of Economic Lot Sizes with Non-Decreasing Requirements

paper_content:

This paper considers the problem of finding a production schedule, in terms of how much to produce in each period, that minimizes the total cost of supplying known market requirements for a single product. The costs include a concave production cost, a concave inventory cost, and a piecewise concave cost of changing the production level from one period to the next. Assuming that there is no backlogging of requirements and that the market requirements are monotone increasing, i.e., not decreasing from period to period, the form of the minimum cost production schedule is obtained. This form is then exploited in a dynamic programming algorithm to provide an efficient means of exactly determining the minimum cost schedule. An interesting calculation reducing theorem is also developed to further enhance the efficiency of the dynamic programming algorithm.
---
paper_title: Mathematical Programming Models and Formulations for Deterministic Production Planning Problems.

paper_content:

We study in this lecture the literature on mixed integer programming models and formulations for a specific problem class, namely deterministic production planning problems. The objective is to present the classical optimization approaches used, and the known models, for dealing with such management problems.We describe first production planning models in the general context of manufacturing planning and control systems, and explain in which sense most optimization solution approaches are based on the decomposition of the problem into single-item subproblems.Then we study in detail the reformulations for the core or simplest subproblem in production planning, the single-item uncapacitated lot-sizing problem, and some of its variants. Such reformulations are either obtained by adding variables - to obtain so called extended reformulations - or by adding constraints to the initial formulation. This typically allows one to obtain a linear description of the convexh ull of the feasible solutions of the subproblem. Such tight reformulations for the subproblems play an important role in solving the original planning problem to optimality.We then review two important classes of extensions for the production planning models, capacitated models and multi-stage or multi-level models. For each, we describe the classical modeling approaches used. Finally, we conclude by giving our personal view on some new directions to be investigated in modeling production planning problems. These include better models for capacity utilization and setup times, new models to represent the product structure - or recipes - in process industries, and the study of continuous time planning and scheduling models as opposed to the discrete time models studied in this review.
---
paper_title: A Backlogging Model and a Multi-Echelon Model of a Dynamic Economic Lot Size Production System---A Network Approach

paper_content:

Two dynamic economic lot size production systems are analyzed in this paper, the first being a single product model with backlogging and the second a multi-echelon model. In each model the objective is to find a production schedule that minimizes the total production and inventory costs. ::: ::: A key conceptual difficulty is that the mathematically perplexing problem of minimizing a concave function is being considered. It is shown that both models are naturally represented via single source networks. The network formulations reveal the underlying structure of the models, and facilitate development of efficient dynamic programming algorithms for calculating the optimal production schedules.
---
paper_title: Dynamic lot-sizing model with demand time windows and speculative cost structure

paper_content:

We consider a deterministic lot-sizing problem with demand time windows, where speculative motive is allowed. Utilizing an untraditional decomposition principle, we provide an optimal algorithm that runs in O(nT^3) time, where n is the number of demands and T is the length of the planning horizon.
---
paper_title: A model for parallel machine replacement with capacity expansion

paper_content:

Abstract This paper considers an environment where several identical machines are used to meet product/service demands. It is assumed that the product/service demand is growing over time and therefore new machines will be purchased for capacity expansion. Also, older machines are assumed to be more expensive to operate than newer machines; and at some time, it may be economical to replace older machines by newer ones. There may be economies of scale in purchase of new machines. This paper develops an integrated model to find an optimal purchase schedule of new machines to meet both the capacity expansion and the machines replacement requirements. An optimal algorithm and an effective heuristic are developed. Our computational results show that the heuristic is close to optimal.
---
paper_title: Operations Research and Capacity Expansion Problems: A Survey

paper_content:

Planning for the expansion of production capacity is of vital importance in many applications within the private and public sectors. Examples can be found in heavy process industries, communication networks, electrical power services, and water resource systems. In all of these applications, the expansion of production capacity requires the commitment of substantial capital resources over long periods of time. Capacity expansion planning consists primarily of determining future expansion times, sizes, and locations, as well as the types of production facilities. Since the late 1950s, operations research methodology has been used to develop various models and solution approaches suitable for different applications. In this paper, we attempt to unify the existing literature on capacity expansion problems, emphasizing modeling approaches, algorithmic solutions, and relevant applications. The paper includes an extensive list of references covering a broad spectrum of capacity expansion problems.
---
paper_title: A Lagrangean-based heuristic for multi-plant, multi-item, multi-period capacitated lot-sizing problems with inter-plant transfers

paper_content:

This paper addresses scheduling of lot sizes in a multi-plant, multi-item, multi-period, capacitated environment with inter-plant transfers. A real-world problem in a company manufacturing steel rolled products provided motivation to this research. A Lagrangean-based approach, embedded with a lot shifting-splitting-merging routine, has been used for solving the multi-plant, capacitated lot-sizing problem. A "good" solution procedure developed by Sambasivan (Ph.D. Dissertation, University of Alabama, Tuscaloosa, 1994) has been used for solving the relaxed problem. About 120 randomly generated instances of the problem have been solved and it has been found that Lagrangean-based approach works quite "efficiently" for this problem.
---
paper_title: Integrated Production, Distribution, and Inventory Planning at Libbey-Owens-Ford

paper_content:

FLAGPOL, a large-scale linear-programming model of the production, distribution, and inventory operations in the flat glass business of Libbey-Owens-Ford deals with four plants, over 200 products, and over 40 demand centers in a 12-month planning horizon. Annual savings from a variety of sources are estimated at over $2,000,000.
---
paper_title: Using Lagrangean Techniques to Solve Hierarchical Production Planning Problems

paper_content:

This paper proposes and tests a procedure for decomposing a large scale production planning problem modeled as a mixed-integer linear program. We interpret this decomposition in the context of Hax and Meal's hierarchical framework for production planning. The procedure decomposes the production planning problem into two subproblems which correspond to the aggregate planning subproblem and a disaggregation subproblem in the Hax-Meal framework. The linking mechanism for these two subproblems is an inventory consistency relationship which is priced out by a set of Lagrange multipliers. The best values for the multipliers are found by an iterative procedure which may be interpreted as a feedback mechanism in the Hax-Meal framework. At each iteration, the procedure finds both a lower bound on the optimal value to the production planning problem and a feasible solution from which an upper bound is obtained. Our computational tests show that the best feasible solution found from this procedure is very close to optimal. For thirty-six test problems the percentage deviation from optimality never exceeds 4.4%, and the average percentage deviation is 2.2%. In addition, these best feasible solutions dominate the corresponding solutions obtained by a hierarchical procedure.
---
paper_title: Dynamic Capacity Expansion Problem with Deferred Expansion and Age-Dependent Shortage Cost

paper_content:

Deferring capacity expansion may be a cost effective decision when there is anticipation of cheaper capacity in the near future and/or the current demand is too low to justify an immediate expansion. This paper studies a finite-horizon capacity expansion problem (CEP) with deferred capacity expansion. The operating cost and the cost of holding unused capacity in each period depend on the time when the capacity is acquired, and the shortage cost depends on the time when the shortage occurred. Our model is a generalization of the Wagner-Whitin formulation of the CEP and an extension (with deferred expansion) of two other polynomially solvable CEPs in the literature. We explore structural properties of the problem and develop an efficient dynamic programming algorithm to solve the problem in polynomial time.
---
paper_title: Aggregate production planning — A survey of models and methodologies

paper_content:

Abstract Aggregate production planning (APP) involves the simultaneous determination of company's production, inventory and employment levels over a finite time horizon. Its objective is to minimize the total relevant costs while meeting non-constant, time varying demand, assuming fixed sales and production capacity. Despite numerous and varied solution techniques few have been implemented in industry. One problem with their implementation could be that little literature exists, outside of cursory textbook presentations and state-of-the-art summaries in 1967 and 1972 by Silver, which specifically summarizes the existing APP techniques into a simple classification scheme. In this paper we present a classification scheme that categorizes the literature on APP since early 1950, summarizing the various existing techniques into a framework depending upon their ability to either produce an exact optimal or near-optimal solution. The research literature that we compiled consisted of 140 journal articles and 14 books. The articles came from 17 different journals. It is intended to facilitate practitioners and researchers in finding the source work for existing methodologies, and to assist them in determining the suitability for implementation to their particular manufacturing problem and also to identify those areas that might require additional investigation and research.
---
paper_title: Coordination of production and distribution planning

paper_content:

Abstract This paper is a computational study to investigate the value of coordinating production and distribution planning. The particular scenario we consider concerns a plant that produces a number of products over time and maintains an inventory of finished goods at the plant. The products are distributed by a fleet of trucks to a number of retail outlets at which the demand for each product is known for every period of a planning horizon. We compare two approaches to managing this operation, one in which the production scheduling and vehicle routing problems are solved separately, and another in which they are coordinated within a single model. The two approaches are applied to 132 distinct test cases with different values of the basic model parameters, which include the length of the planning horizon, the number of products and retail outlets, and the cost of setups, inventory holding and vehicle travel. The reduction in total operating cost from coordination ranged from 3% to 20%. These results indicate the conditions under which companies should consider the organizational changes necessary to support coordination of production and distribution.
---
paper_title: A deterministic model for planning production quantities in a multi-plant, multi-warehouse environment with extensible capacities

paper_content:

Abstract We have developed a deterministic model for planning production and transportation quantities in multi-plant and multi-warehouse environment with extensible capacities. The model determines a production mix that maximizes total profit over a finite planning horizon. When production cannot meet demand due to lack of adequate resources, the model allows shortfalls to be met through subcontracting or the use of inventory. However, it does not allow subcontracting when adequate resources are available. When solved, the model produces the quantity of each product to be: (1) produced at each plant, (2) transported from each plant to each warehouse, (3) subcontracted at each warehouse, and (4) kept in inventory at each warehouse. Furthermore, it identifies the warehouses that need extensions at any period and the corresponding amounts of extensions needed. We also develop a procedure for reducing the size of the zero–one MILP problem that can be obtained during any application of the model. Numerical examples given to illustrate the model and to compare the full and the reduced versions of the model show that the model works well and that both the full and the reduced versions produce exactly the same results. Finally, we discuss the assumptions underlining the model and highlight the approaches that can be taken to eliminate or, at least, prevent errors that are associated with violations of the assumptions.
---
paper_title: A Dynamic Model for Inventory Lot Sizing and Outbound Shipment Scheduling at a Third-Party Warehouse

paper_content:

This paper presents a model for computing the parameters of an integrated inventory replenishment and outbound dispatch scheduling policy under dynamic demand considerations. The optimal policy parameters specify (i) how often and in what quantities to replenish the stock at an upstream supply chain member (e.g., a warehouse), and (ii) how often to release an outbound shipment to a downstream supply-chain member (e.g., a distribution center). The problem is represented using a two-echelon dynamic lot-sizing model with pre-shipping and late-shipping considerations, where outbound cargo capacity constraints are considered via a stepwise cargo cost function. Although the paper is motivated by a third-party warehousing application, the underlying model is applicable in the general context of coordinating inventory and outbound transportation decisions. The problem is challenging due to the stepwise cargo cost structure modeled. The paper presents several structural properties of the problem and develops a polynomial time algorithm for computing the optimal solution.
---
paper_title: The Dynamic Lot-Size Model with Stochastic Lead Times

paper_content:

Optimal solutions for the dynamic lot-sizing problem with deterministic demands but stochastic lead times are "lumpy." If lead time distributions are arbitrary except that they are independent of order size and do not allow orders to cross in time, then each order in an optimal solution will exactly satisfy a consecutive sequence of demands, a natural extension of the classic results by Wagner and Whitin. If, on the other hand, orders can cross in time, then optimal solutions are still "lumpy" in the sense that each order will satisfy a set, not necessarily consecutive, of the demands. An example shows how this characterization can be used to find a solution to a problem where interdependence of lead times is critical. This characterization of optimal solutions facilitates dynamic programming approaches to this problem.
---
paper_title: Plant co-ordination in pharmaceutics supply networks

paper_content:

The production of active ingredients in the chemical-pharmaceutical industry involves numerous production stages with cumulative lead times of up to two years. Mainly because of rigorous purity requirements and the need of extensive cleaning of the equipment units, production is carried out in campaigns, i.e. multiple batches of the same product type are produced successively before changing to another product type. Each campaign requires a specific configuration of equipment units according to the recipes of the particular chemical process. In the chemical-pharmaceutical industry, production stages are often assigned to different locations, even different countries. Hence the co-ordination of plant operations within the resulting multi-national supply network is of major importance. A key issue is the co-ordination of campaign schedules at different production stages in the various plants. In practice, it is almost impossible to determine exact optimal solutions to the corresponding complex supply network problem with respect to overall logistics costs. In order to reduce the required computational effort, we introduce several aggregation schemes and a novel MILP model formulation which is based on a continuous representation of time. Moreover, we propose an iterative near-optimal solution procedure which can be successfully applied to even exceptionally large real life problem instances. The applicability of the approach suggested is shown using a case study from industry.
---
paper_title: Operational production planning in a chemical manufacturing environment

paper_content:

Abstract This paper develops a heuristic for operational production planning in a chemical processing environment, characterized by a single bottleneck machine, fixed batch sizes, sequence-dependent setup times, as well as production and storage capacity constraints. The algorithm aims at pre-producing future production requirements in order to reduce the total relevant cost, consisting of inventory holding costs and opportunity costs due to setups between production runs. The procedure takes care of lot-sizing, but also determines pretty good production sequences per period according to an approximate traveling salesman algorithm. A numerical example is given in which production lot-sizes and production sequences are determined for 15 products over a 20 week planning horizon under tight capacity conditions.
---
paper_title: A model for lot sizing and sequencing in process industries

paper_content:

Abstract Scheduling in process industries is exceedingly challenging, due to the high capital intensity, relatively long and sequence-dependent setup times, and extremely limited capacity resources that are found in these industries. As a result, it is important to simultaneously consider lot sizing and sequencing factors in the development of a production schedule. This paper presents a mixed integer linear programming model for scheduling production in process industries that embodies the economic trade-offs encompassed in three avenues of research: capacitated lot sizing, flowshop scheduling and sequencing with sequence-dependent setup times. The model is used to schedule production Tor a problem representative of those found in the food processing industry. The corresponding schedule is then compared with approaches that consider lot sizing and sequencing as independent decisions and it is shown that decomposing the scheduling problem into smaller subproblems can result in the generation of infeasible...
---
paper_title: A tabu search heuristic for scheduling the production processes at an oil refinery

paper_content:

In this paper we present a tabu search heuristic which can be used for scheduling the production at an oil refinery. The scheduling problem is to decide which production modes to use at the different processing units at each point in time. The problem is a type of lot-sizing problem where costs of changeovers, inventories and production are considered. In the suggested tabu search heuristic we explore the use of variable neighbourhood, dynamic penalty and different tabu lists. Computational results are presented for different versions of the heuristic and the results are compared to the best-known lower bound for a set of scheduling scenarios.
---
paper_title: A Coordinated Production Planning Model with Capacity Expansion and Inventory Management

paper_content:

Motivated by a problem faced by a large manufacturer of a consumer product, we explore the interaction between production planning and capacity acquisition decisions in environments with demand growth. We study a firm producing multiple items in a multiperiod environment where demand for items is known but varies over time with a long-term growth and possible short-term fluctuations. The production equipment is characterized by significant changeover time between the production of different items. While demand growth is gradual, capacity additions are discrete. Therefore, periods immediately following a machine purchase are characterized by excess machine capacity. We develop a mathematical programming model and an effective solution approach to determine the optimal capacity acquisition, production and inventory decisions over time. Through a computational study, we show the effectiveness of the solution approach in terms of solution quality and investigate the impact of product variety, cost of capital, and other important parameters on the capacity and inventory decisions. The computational results bring out some key insights--increasing product variety may not result in excessive inventory and even a substantial increase in set-up times or holding costs may not increase the total cost over the horizon in a significant manner due to the ability to acquire additional capacity. We also provide solutions and insights to the real problem that motivated this work.
---
paper_title: A Lagrangean-based heuristic for multi-plant, multi-item, multi-period capacitated lot-sizing problems with inter-plant transfers

paper_content:

This paper addresses scheduling of lot sizes in a multi-plant, multi-item, multi-period, capacitated environment with inter-plant transfers. A real-world problem in a company manufacturing steel rolled products provided motivation to this research. A Lagrangean-based approach, embedded with a lot shifting-splitting-merging routine, has been used for solving the multi-plant, capacitated lot-sizing problem. A "good" solution procedure developed by Sambasivan (Ph.D. Dissertation, University of Alabama, Tuscaloosa, 1994) has been used for solving the relaxed problem. About 120 randomly generated instances of the problem have been solved and it has been found that Lagrangean-based approach works quite "efficiently" for this problem.
---
paper_title: Multi-Item, Multi-Period Production Planning with Uncertain Demand

paper_content:

We provide a formulation and solution algorithm for the finite-horizon capacitated production planning problem with random demand for multiple products. Using Lagrangian relaxation, we develop a subgradient optimization algorithm to solve this formulation. We also provide some computational results that indicate this approach works well for rolling-horizon planning compared with the rolling-horizon performance of the corresponding optimal finite-horizon solution. The advantage of our approach is that realistic problem instances can be solved quickly while optimal solutions to such instances are computationally intractable.
---
paper_title: Requirements Planning with Pricing and Order Selection Flexibility

paper_content:

Past requirements-planning research has typically assumed that the firms demands are determined prior to production planning. In contrast, we explore a single-stage planning model that implicitly decides, through pricing decisions, the demand levels the firm should satisfy in order to maximize contribution to profit. We briefly discuss solution methods and properties for these problems when production capacities are unlimited. The key result of this work is a polynomial-time solution approach to the problem under time-invariant finite production capacities and piecewise-linear and concave revenue functions in price.
---
paper_title: Solving Planning and Design Problems in the Process Industry Using Mixed Integer and Global Optimization

paper_content:

This contribution gives an overview on the state-of-the-art and recent advances in mixed integer optimization to solve planning and design problems in the process industry. In some case studies specific aspects are stressed and the typical difficulties of real world problems are addressed.Mixed integer linear optimization is widely used to solve supply chain planning problems. Some of the complicating features such as origin tracing and shelf life constraints are discussed in more detail. If properly done the planning models can also be used to do product and customer portfolio analysis.We also stress the importance of multi-criteria optimization and correct modeling for optimization under uncertainty. Stochastic programming for continuous LP problems is now part of most optimization packages, and there is encouraging progress in the field of stochastic MILP and robust MILP.Process and network design problems often lead to nonconvex mixed integer nonlinear programming models. If the time to compute the solution is not bounded, there are already a commercial solvers available which can compute the global optima of such problems within hours. If time is more restricted, then tailored solution techniques are required.
---
paper_title: The multiscenario lot size problem with concave costs

paper_content:

Abstract The dynamic single-facility single-item lot size problem is addressed. The finite planning horizon is divided into several time periods. Although the total demand is assumed to be a fixed value, the distribution of this demand among the different periods is unknown. Therefore, for each period the demand can be chosen from a discrete set of values. For this reason, all the combinations of the demand vector yield a set of different scenarios. Moreover, we assume that the production/reorder and holding cost vectors can vary from one scenario to another. For each scenario, we consider as the objective function the sum of the production/reorder and the holding costs. The problem consists of determining all the Pareto-optimal or non-dominated production plans with respect to all scenarios. We propose a solution method based on a multiobjective branch and bound approach. Depending on whether shortages are considered or not, different upper bound sets are provided. Computational results on several randomly generated problems are reported.
---
paper_title: An integrated production-inventory-marketing model for deteriorating items

paper_content:

Generally, inventory control policies for deteriorating items are very sensitive to different marketing policies especially in chemical, food and pharmaceutical industries. Realizing the importance of such inventory policies in practice, an integrated production-inventory-marketing model is developed for determining the economic production quantity (EPQ) and economic order quantity (EOQ) for raw materials in a multi-stage production system. This model considers the effect of different marketing policies such as the price per unit product and the advertisement frequency on the demand of a perishable item. A search method is employed to determine the values of EPQ and EOQ which would result in the maximum total net profit.
---
paper_title: MIP modelling of changeovers in production planning and scheduling problems

paper_content:

The goal here is to survey some recent and not so recent work that can be used to improve problem formulations either by a priori reformulation, or by the addition of valid inequalities. The main topic examined is the handling of changeovers, both sequence-independent and -dependent, in production planning and machine sequencing, with in the background the question of how to model time. We first present results for lot-sizing problems, in particular the interval submodular inequalities of Constantino that provide insight into the structure of single item problems with capacities and start-ups, and a unit flow formulation of Karmarkar and Schrage that is effective in modelling changeovers. Then we present various extensions and an application to machine sequencing with the unit flow formulation. We terminate with brief sections on the use of dynamic programming and of time-indexed formulations, which provide two alternative approaches for the treatment of time. (C) 1997 Elsevier Science B.V.
---
paper_title: Mathematical Programming Models and Formulations for Deterministic Production Planning Problems.

paper_content:

We study in this lecture the literature on mixed integer programming models and formulations for a specific problem class, namely deterministic production planning problems. The objective is to present the classical optimization approaches used, and the known models, for dealing with such management problems.We describe first production planning models in the general context of manufacturing planning and control systems, and explain in which sense most optimization solution approaches are based on the decomposition of the problem into single-item subproblems.Then we study in detail the reformulations for the core or simplest subproblem in production planning, the single-item uncapacitated lot-sizing problem, and some of its variants. Such reformulations are either obtained by adding variables - to obtain so called extended reformulations - or by adding constraints to the initial formulation. This typically allows one to obtain a linear description of the convexh ull of the feasible solutions of the subproblem. Such tight reformulations for the subproblems play an important role in solving the original planning problem to optimality.We then review two important classes of extensions for the production planning models, capacitated models and multi-stage or multi-level models. For each, we describe the classical modeling approaches used. Finally, we conclude by giving our personal view on some new directions to be investigated in modeling production planning problems. These include better models for capacity utilization and setup times, new models to represent the product structure - or recipes - in process industries, and the study of continuous time planning and scheduling models as opposed to the discrete time models studied in this review.
---
paper_title: Planning and scheduling in the process industry

paper_content:

Since there has been tremendous progress in planning and scheduling in the process industry during the last 20 years, it might be worthwhile to give an overview of the current state-of-the-art of planning and scheduling problems in the chemical process industry. This is the purpose of the current review which has the following structure: we start with some conceptional thoughts and some comments on special features of planning and scheduling problems in the process industry. In Section 2 the focus is on planning problems while in Section 3 different types of scheduling problems are discussed. Section 4 presents some solution approaches especially those applied to a benchmark problem which has received considerable interest during the last years. Section 5 allows a short view into the future of planning and scheduling. In the appendix we describe the Westenberger-Kallrath problem which has already been used extensively as a benchmark problem for planning and scheduling in the process industr y.
---
paper_title: An Empirical Investigation of Costs in Batching Decisions

paper_content:

This paper examines the use of costs and cost functions to model lot-sizing decisions in batch manufacturing. The cost functions used to model a wide variety of manufacturing systems are typically derived from average cost models of unconstrained inventory problems. The use of setups and average inventories as the basis for modeling the economics of a typical batch manufacturing cell is shown to be inadequate. An alternative physical model that focuses on lead times provides a model that more closely represents the underlying value of such a cell.
---
paper_title: Aclips: a Capacity and Lead Time Integrated Procedure for Scheduling

paper_content:

We propose a general hierarchical procedure to address real-life job shop scheduling problems. The shop typically produces a variety of products, each with its own arrival stream, its ow route through the shop and a given customer due date. The procedure first determines the manufacturing lot sizes for each product. The objective is to minimize the expected lead time, and therefore we model the production environment as a queueing network. Given these lead times, release dates are set dynamically. This in turn creates a time window for every manufacturing order in which the various operations have to be sequenced. The sequencing logic is based on an Extended Shifting Bottleneck Procedure. These three major decisions are next incorporated into a four-phase, hierarchical, operational implementation scheme. A small numerical example is used to illustrate the methodology. The final objective however is to develop a procedure that is useful for large, real-life shops. We therefore report on a real-life application.
---
paper_title: A comparison of two lot sizing-sequencing heuristics for the process industry

paper_content:

Abstract Two heuristics for operational production planning in a chemical processing environment are compared, characterized by a single bottleneck machine, fixed batch sizes, sequence-dependent setup-times, as well as production and storage constraints. Performance of both heuristics is measured by means of simulation experiments in which the planning horizon is partially frozen and rolled a number of times, as would be the case in practical applications. Furthermore, demand uncertainty is simulated as well as the variability among setup times. The performance measure used is the total cost for executing a particular production plan over its entire planning horizon.
---
paper_title: On formulations of the stochastic uncapacitated lot-sizing problem

paper_content:

We consider two formulations of a stochastic uncapacitated lot-sizing problem. We show that by adding (@?,S) inequalities to the one with the smaller number of variables, both formulations give the same LP bound. Then we show that for two-period problems, adding another class of inequalities gives the convex hull of integral solutions.
---
paper_title: Campaign planning for multi-stage batch processes in the chemical industry

paper_content:

Inspired by a case study from industry, the production of special chemical products is considered. In this industrial environment, multi-purpose equipment is operated in batch mode to carry out the diverse processing tasks. Often, extensive set-up and cleaning of the equipment are required when production switches between different types of products. Hence, processes are scheduled in campaign mode, i.e. a number of batches of the same type are processed in sequence. The production of chem ical products usually involves various stages with significant cumulative lead times. Typically, these production stages are assigned to different plants. A hierarchical modelling approach is presented which co-ordinates the various plant operations within the entire supply network. In the first stage, the length of the campaigns, their timing, the corresponding material flows, and equipment requirements have to be determined. At this stage, an aggregation scheme based on feasibility constraints is employed in order to reflect the limited availability of the various types of production equipment. The second stage consists of an assignment model, which allocates the available equipment units between the production campaigns determined in the first stage of the solution procedure. In the third stage, resource conflicts are resolved, which may occur if clean-out operations and minimal campaign lengths have to be considered. The proposed hierarchical approach allows a more compact model formulation compared to ot her approaches known from the literature. As a result, a very efficient and flexible solution approach is obtained. In particular, commercially available standard solvers can be used to solve a wide range of campaign planning problems arising in the chemical industry.
---

Title: Modeling Industrial Lot Sizing Problems: A Review

Section 1: Introduction
Description 1: Introduce the topic of lot sizing models, their classification, relevance, and objectives of the review.

Section 2: The single-item uncapacitated lot sizing problem
Description 2: Discuss the simplest form of dynamic lot sizing with the key variables and constraints associated with this model.

Section 3: Capacitated Multi-Item Lot Sizing Problem (CLSP)
Description 3: Elaborate on the complexities introduced with capacitated multi-item lot sizing models, and different lot sizing problems like the CSLP, DLSP, etc.

Section 4: Further Extensions of Lot Sizing Models
Description 4: Provide an overview of further extensions to lot sizing models, covering expanded topics in setups, production, inventory, demand, and integration with other planning stages.

Section 5: Extension on the set ups
Description 5: Cover extended considerations in lot sizing models related to setups, such as coordinated replenishment and carry-over setups.

Section 6: Extensions on the Production
Description 6: Discuss additional production-related extensions including batch production, sequence-dependent setup costs, and integration with scheduling.

Section 7: Extensions on the inventory
Description 7: Explore how inventory constraints and perishability are treated in advanced lot sizing models.

Section 8: Extension on the demand
Description 8: Address how demand variability, backlogging, and speculative cost structures are incorporated into lot sizing models.

Section 9: Time Horizon
Description 9: Explain the implications of using a rolling horizon approach in lot sizing and how it affects planning and outcomes.

Section 10: Tactical and strategic models
Description 10: Discuss the integration of lot sizing models with higher-level tactical and strategic production planning decisions.

Section 11: Conclusions and New Research Directions
Description 11: Summarize the insights gained from the review and suggest new areas where further research could be directed.