On alternative mixed integer programming formulations and LP-based heuristics for lot-sizing with setup times

We address the multi-item, capacitated lot-sizing problem (CLSP) encountered in environments where demand is dynamic and to be met on time. Items compete for a limited capacity resource, which requires a setup for each lot of items to be produced causing unproductive time but no direct costs. The problem belongs to a class of problems that are difficult to solve. Even the feasibility problem becomes combinatorial when setup times are considered. This difficulty in reaching optimality and the practical relevance of CLSP make it important to design and analyse heuristics to find good solutions that can be implemented in practice. We consider certain mixed integer programming formulations of the problem and develop heuristics including a curtailed branch and bound, for rounding the setup variables in the LP solution of the tighter formulations. We report our computational results for a class of instances taken from literature.     

A Greedy Algorithm for Capacitated Lot-Sizing Problems

We show that the convex hull of the set of feasible solutions of single-item capacitated lot-sizing problem (CLSP) is a base polyhedron of a polymatroid. We present a greedy algorithm to solve CLSP with linear objective function. The proposed algorithm is an effective implementation of the classical Edmonds' algorithm for maximizing linear function over a polymatroid. We consider some special cases of CLSP with nonlinear objective function that can be solved by the proposed greedy algorithm in O ( n ) time.     

Approximation algorithms for deterministic continuous-review inventory lot-sizing problems with time-varying demand

This work deals with the continuous time lot-sizing inventory problem when demand and costs are time-dependent. We adapt a cost balancing technique developed for the periodic-review version of our problem to the continuous-review framework. We prove that the solution obtained costs at most twice the cost of an optimal solution. We study the numerical complexity of the algorithm and generalize the policy to several important extensions while preserving its performance guarantee of two. Finally, we propose a modified version of our algorithm for the lot-sizing model with some restricted settings that improves the worst-case bound.     

The combined cutting stock and lot-sizing problem in industrial processes

Despite its great applicability in several industries, the combined cutting stock and lot-sizing problem has not been sufficiently studied because of its great complexity. This paper analyses the trade-off that arises when we solve the cutting stock problem by taking into account the production planning for various periods. An optimal solution for the combined problem probably contains non-optimal solutions for the cutting stock and lot-sizing problems considered separately. The goal here is to minimize the trim loss, the storage and setup costs. With a view to this, we formulate a mathematical model of the combined cutting stock and lot-sizing problem and propose a solution method based on an analogy with the network shortest path problem. Some computational results comparing the combined problem solutions with those obtained by the method generally used in industry—first solve the lot-sizing problem and then solve the cutting stock problem—are presented. These results demonstrate that by combining the problems it is possible to obtain benefits of up to 28% profit. Finally, for small instances we analyze the quality of the solutions obtained by the network shortest path approach compared to the optimal solutions obtained by the commercial package AMPL.     

Models for capacitated lot-sizing problem with backlogging,setup carryover and crossover

Setup operations are significant in some production environments. It is mandatory that their production plans consider some features, as setup state conservation across periods through setup carryover and crossover. The modelling of setup crossover allows more flexible decisions and is essential for problems with long setup times. This paper proposes two models for the capacitated lot-sizing problem with backlogging and setup carryover and crossover. The first is in line with other models from the literature, whereas the second considers a disaggregated setup variable, which tracks the starting and completion times of the setup operation. This innovative approach permits a more compact formulation. Computational results show that the proposed models have outperformed other state-of-the-art formulation.     

A Lagrangian-based heuristic for the capacitated lot-sizing problem in parallel machines

This paper addresses the capacitated lot-sizing problem involving the production of multiple items on unrelated parallel machines. A production plan should be determined in order to meet the forecast demand for the items, without exceeding the capacity of the machines and minimize the sum of production, setup and inventory costs. A heuristic based on the Lagrangian relaxation of the capacity constraints and subgradient optimization is proposed. Initially, the heuristic is tested on instances of the single machine problem and results are compared with heuristics from the literature. For parallel machines and small problems the heuristic performance is tested against optimal solutions, and for larger problems it is compared with the lower bound provided by the Lagrangian relaxation.     

An MIP-based interval heuristic for the capacitated multi-level lot-sizing problem with setup times

This paper considers the capacitated multi-level lot-sizing problem with setup times, a class of difficult problems often faced in practical production planning settings. In the literature, relax-and-fix is a technique commonly applied to solve this problem due to the fact that setup decisions in later periods of the planning horizon are sensitive to setup decisions in the early periods but not vice versa. However, the weakness of this method is that setup decisions are optimized only on a small subset of periods in each iteration, and setup decisions fixed in early iterations might adversely affect setup decisions in later periods. In order to avoid these weaknesses, this paper proposes an extended relax-and-fix based heuristic that systematically uses domain knowledge derived from several strategies of relax-and-fix and a linear programming relaxation technique. Computational results show that the proposed heuristic is superior to other well-known approaches on solution qualities, in particular on hard test instances.     

A holding cost bound for the economic lot-sizing problem with time-invariant cost parameters

We show that in an optimal solution of the economic lot-sizing problem the total holding cost in an order interval is bounded from above by a quantity proportional to the setup cost and the logarithm of the number of periods in the interval. We present two applications of this result.     

The multi-item capacitated lot-sizing problem with setup times and shortage costs

We address a multi-item capacitated lot-sizing problem with setup times and shortage costs that arises in real-world production planning problems. Demand cannot be backlogged, but can be totally or partially lost. The problem is NP-hard. A mixed integer mathematical formulation is presented. Our approach in this paper is to propose some classes of valid inequalities based on a generalization of Miller et al. [A.J. Miller, G.L. Nemhauser, M.W.P. Savelsbergh, On the polyhedral structure of a multi-item production planning model with setup times, Mathematical Programming 94 (2003) 375–405] and Marchand and Wolsey [H. Marchand, L.A. Wolsey, The 0–1 knapsack problem with a single continuous variable, Mathematical Programming 85 (1999) 15–33] results. We also describe fast combinatorial separation algorithms for these new inequalities. We use them in a branch-and-cut framework to solve the problem. Some experimental results showing the effectiveness of the approach are reported.     

The effects of learning in production and group size on the lot-sizing problem

One of the lot-sizing problem extensions that received noticeable attention in the literature is the one that investigated the effects of learning in production. The studies along this line of research assumed learning to improve with the number of repetitions following a power form. There is evidence also that the group size, i.e., the number of workers learning in a group affects performance (time per unit). This note revisits the problem and modifies it by incorporating the group size, along with cumulative production, as a proxy for measuring performance. Numerical examples are provided to illustrate the behavior of the modified model. The results of the two models are also compared to draw some meaningful insights and conclusions. Although the results favor using a simple univariate learning curve, considering group size when modeling lot-sizing problems can significantly affect the unit production cost.     

Lot-sizing with production and delivery time windows

We study two different lot-sizing problems with time windows that have been proposed recently. For the case of production time windows, in which each client specific order must be produced within a given time interval, we derive tight extended formulations for both the constant capacity and uncapacitated problems with Wagner-Whitin (non-speculative) costs. For the variant with nonspecific orders, known to be equivalent to the problem in which the time windows can be ordered by time, we also show equivalence to the basic lot-sizing problem with upper bounds on the stocks. Here we derive polynomial time dynamic programming algorithms and tight extended formulations for the uncapacitated and constant capacity problems with general costs. For the problem with delivery time windows, we use a similar approach to derive tight extended formulations for both the constant capacity and uncapacitated problems with Wagner-Whitin (non-speculative) costs. We are most grateful for the hospitality of IASI, Rome, where part of this work was carried out. The collaboration with IASI takes place in the framework of ADONET, a European network in Algorithmic Discrete Optimization, contract n MRTN-CT-2003-504438. This text presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors.     

Coordination of dynamic lot-sizing in supply chains

This paper presents a new scheme for the coordination of dynamic, uncapacitated lot-sizing problems in two-party supply chains where parties’ local data are private information and no external or central entity is involved. This coordination scheme includes the following actions: At first, the buyer generates a series of different supply proposals using an extension of her local lot-sizing problem. Then the supplier calculates his cost changes that would result from the implementation of the buyer’s proposals. Based on these information, parties can identify the best proposal generated. The scheme identifies the system-wide optimum in different settings—for instance in a two-stage supply chain where the supplier’s costs for holding a period’s demand in inventory exceed his setup costs.     

An effective heuristic for the CLSP with set-up times

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.     

Single item lot-sizing problem for a warm/cold process with immediate lost sales

We consider the dynamic lot-sizing problem with finite capacity and possible lost sales for a process that could be kept warm at a unit variable cost for the next period t + 1 only if more than a threshold value Q_t has been produced and would be cold, otherwise. Production with a cold process incurs a fixed positive setup cost, K_t and setup time, S_t, which may be positive. Setup costs and times for a warm process are negligible. We develop a dynamic programming formulation of the problem, establish theoretical results on the structure of the optimal production plan in the presence of zero and positive setup times with Wagner–Whitin-type cost structures. We also show that the solution to the dynamic lot-sizing problem with lost sales are generated from the full commitment production series improved via lost sales decisions in the presence of a warm/cold process.     

Lot-sizing on a tree

For the problem of lot-sizing on a tree with constant capacities, or stochastic lot-sizing with a scenario tree, we present various reformulations based on mixing sets. We also show how earlier results for uncapacitated problems involving (Q,S_Q) inequalities can be simplified and extended. Finally some limited computational results are presented.     

The profit maximizing capacitated lot-size (PCLSP) problem

This paper extends the results for capacitated lot-sizing research to include pricing. Based on a few examples, the new version appears to by much easier to solve computationally. The paper, by including price, can modify demand as well as production schedule. Due to model assumptions (form of demand) a feasible solution can be found easily, unlike CLSP.     

MIP modelling of changeovers in production planning and scheduling problems

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.     

Polyhedral analysis for the two-item uncapacitated lot-sizing problem with one-way substitution

We consider a production planning problem for two items where the high quality item can substitute the demand for the low quality item. Given the number of periods, the demands, the production, inventory holding, setup and substitution costs, the problem is to find a minimum cost production and substitution plan. This problem generalizes the well-known uncapacitated lot-sizing problem. We study the projection of the feasible set onto the space of production and setup variables and derive a family of facet defining inequalities for the associated convex hull. We prove that these inequalities together with the trivial facet defining inequalities describe the convex hull of the projection if the number of periods is two. We present the results of a computational study and discuss the quality of the bounds given by the linear programming relaxation of the model strengthened with these facet defining inequalities for larger number of periods.     

Solving the capacitated lot-sizing problem with backorder consideration

In this research, we formulate and solve a type of the capacitated lot-sizing problem. We present a general model for the lot-sizing problem with backorder options, that can take into consideration various types of production capacities such as regular time, overtime and subcontracting. The objective is to determine lot sizes that will minimize the sum of setup costs, holding cost, backorder cost, regular time production costs, and overtime production costs, subject to resource constraints. Most existing formulations for the problem consider the special case of the problem where a single source of production capacity is considered. However, allowing for the use of alternate capacities such as overtime is quite common in many manufacturing settings. Hence, we provide a formulation that includes consideration of multiple sources of production capacity. We develop a heuristic based on the special structure of fixed charge transportation problem. The performance of our algorithm is evaluated by comparing the heuristic solution value to lower bound value. Extensive computational results are presented.     

Dynamic knapsack sets and capacitated lot-sizing

 A dynamic knapsack set is a natural generalization of the 0-1 knapsack set with a continuous variable studied recently. For dynamic knapsack sets a large family of facet-defining inequalities, called dynamic knapsack inequalities, are derived by fixing variables to one and then lifting. Surprisingly such inequalities have the simultaneous lifting property, and for small instances provide a significant proportion of all the facet-defining inequalities. We then consider single-item capacitated lot-sizing problems, and propose the joint study of three related sets. The first models the discrete lot-sizing problem, the second the continuous lot-sizing problem with Wagner-Whitin costs, and the third the continuous lot-sizing problem with arbitrary costs. The first set that arises is precisely a dynamic knapsack set, the second an intersection of dynamic knapsack sets, and the unrestricted problem can be viewed as both a relaxation and a restriction of the second. It follows that the dynamic knapsack inequalities and their generalizations provide strong valid inequalities for all three sets. Some limited computation results are reported as an initial test of the effectiveness of these inequalities on capacitated lot-sizing problems. Received: March 28, 2001 / Accepted: November 9, 2001 Published online: September 27, 2002 RID="★" ID="★" Research carried out with financial support of the project TMR-DONET nr. ERB FMRX–CT98–0202 of the European Union. Present address: Electrabel, Louvain-la-Neuve, B-1348 Belgium. Present address: Electrabel, Louvain-la-Neuve, B-1348 Belgium. Key words. knapsack sets – valid inequalities – simultaneous lifting – lot-sizing – Wagner-Whitin costs