|
Article Excerpt
The main result of this paper is an O([n.sup.3]) algorithm for the single-item lot-sizing problem with constant batch size and backlogging. We consider a general number of installable batches, i.e., in each time period t we may produce up to [m.sub.t] batches, where the [m.sub.t] are given and time-dependent. This generalizes earlier results as we consider backlogging and a general number of maximum batches. We also give faster algorithms for three special cases of this general problem. When backlogging is not allowed and the costs satisfy the Wagner-Whitin property, the problem is solvable in O([n.sup.2] log n) time. When the production in each period is required to be either zero or equal to the installed capacity, it is possible to solve the problem with and without backlogging in O([n.sup.2]) and O(n log n) time, respectively.
Key words: capacitated lot-sizing; complexity
1. Introduction. In the single-item lot-sizing problem, there is a demand for a single item in n consecutive time periods. The demand in period t may be satisfied from production in period t or from stock at the end of period t- 1. Depending on the problem, it may also be satisfied from backlog in period t. The production in each period is limited by the installed capacity. The installed capacity is a multiple of the batch size, and the maximum number of batches that can be installed in each period is given and is time-dependent. A problem is uncapacitated if one batch in any period t is sufficient to allow production in that period to satisfy all demand that can be satisfied from t, and capacitated otherwise. A problem is called discrete if the production is equal to the installed capacity, i.e., the production is in full batches. The cost associated with a production plan is divided between the production cost, the holding cost, and the backlogging cost in each period. There is also a cost associated with installing capacity. In this work, we assume that all these costs are linear.
This problem and its variants are known under different names: economic lot-sizing with backlogging, multiple set-up problem with dynamic demand, truckload discount schedule. There is a huge literature on special cases, variants, or more general problems than the one just outlined. Below, we review the most relevant work.
Several authors show that the uncapacitated, no backlogging, version of the model described above is solvable in O(n log n) time for general linear cost functions and O(n) time if the costs satisfy the so called Wagner-Whitin property (Aggarwal and Park [1], Federgruen and Tzur [8], Wagelmans et al. [28]). This improves on the O([n.sup.2]) algorithm from the seminal paper of Wagner and Whitin [29]. Then, van Hoesel et al. [25] extend this complexity bound to the same problem with backlogging.
For capacitated problems Florian et al. [12] and Bitran and Yanasse [4] have shown that the general problem without backlogging is NP-Hard, even under various assumptions on the costs or when the problem is discrete. When at most one batch per period can be produced, Van Hoesel and Wagelmans [23] give fully polynomial approximation schemes for this problem. Assuming nonincreasing setup and production costs, and nondecreasing batch sizes, the problem can still be solved in polynomial time, see Chung and Lin [6].
Most authors have considered the case when the batch size is constant over time and the number of batches that can be produced in unlimited. When backlogging is not allowed, Pochet and Wolsey [19] show that the problem is solvable in O([n.sup.3]) time, improving on an earlier O([n.sup.5]) algorithm of Lippman [16]. Lee [14] considers a variant of this problem where there is a fixed cost when installing capacity, and the other costs satisfy the Wagner-Whitin property. He gives an O([n.sup.4]) time algorithm, which has been recently improved to O([n.sup.3]) by Lee et al. [15]. This last bound is achieved as a special case of a more general algorithm for a two-level problem where backlogging is allowed. Stochastic lead times are treated by Alp et al. [3]. Assuming time-independent production, holding and backlogging costs, they can solve the problem in O(n[C.sup.3]) where C is the batch size. More general production costs structure lead to NP-Hard problems. An important example is the modified all-unit cost function, a piecewise linear nondecreasing function for which the cost per unit is nonincreasing. Chan et al. [5] prove that the cost of the best zero-inventory ordering policy is at most 4/3 the optimum cost.
The case when the number of batches that can be produced in a period is bounded has received less attention. Van Hoesel and Wagelmans [22] give an O([n.sup.3]) algorithm for the case when at most one batch can be produced in each period and backlogging is not allowed, improving on an O([n.sup.4]) algorithm of Florian and Klein [11].
The literature on the discrete lot-sizing problem mostly focusses on the problems with startup times or costs, see Fleischmann [9, 10], van Hoesel et al. [24], van Eijl [20], van Eijl and van Hoesel [21]. Lasdon and Terjung [13] consider backlogging and setup times. Recently, Miller and Wolsey [17] studied formulations for the discrete lot-sizing problem with backlogging and/or initial stock, and batch size constant over time. In particular, for the single-item case with either backlogging or initial stock, but not both, they provide linear-programming formulations of polynomial size. This implies that these two problems are solvable in polynomial time.
The main result of this paper is to provide an O([n.sup.3]) algorithm for the general problem outlined in the first paragraph when the batch size is constant over time and all costs are linear. To the best of the author's knowledge, this is the first time that the two following features are considered:
* a bounded number of batches (even all-ones) together with backlogging,
* time-dependent bounds on the number of batches for any lot-sizing problem.
This problem directly generalizes these studied in Pochet and Wolsey [19] and van Hoesel and Wagelmans [22]. Thus, we provide an algorithm of the same time complexity for a more general problem. We also give faster algorithms for three special cases. When no backlogging is allowed and the costs satisfy the Wagner-Whitin property the problem is solvable in O([n.sup.2] log n). In the discrete case it is possible to solve the problem with and without backlogging in O([n.sup.2]) and O(n log n), respectively.
From the practitioner's point of view, backlogging and time-dependent limits on the installable capacity are important modelling features. Backlogging is current practice in production environments where holding costs are high and/or setting up capacity is expensive. Time-dependent limits on the installable capacity is necessary, for example, to account for the variability of the maximum production time in different periods (day and nights, weekdays and weekends, ...).
In addition, the problem considered regularly appears as a substructure in more complex production planning problems involving multiechelon, resource constraints,.... To apply a decomposition approach (e.g. Lagrangean relaxation), one needs to repeatedly solve instances of LSB. The companion papers Van Vyve [26, 27] describe extended linear-programming formulations and facet-defining inequalities for LSB and its relaxations.
The algorithms presented in this paper have theoretical interest as well. We show how to implement a greedy algorithm for a particular matroid problem in O(n log n), instead of the general O([n.sup.2]) bound. Moreover, we show that a greedy algorithm still solves a problem that can be viewed as a matroid problem in which circuits are allowed but penalized.
This paper is organized as follows. We begin by reviewing some standard complexity results that we use in this paper in [section]2. The notation is also introduced. The rest of the paper is divided in two main sections. Section 3 deals with problems without backlogging, while problems involving backlogging are treated in [section]4. Each of these two sections is similarly divided into three subsections. The first one introduces building blocks useful for the next two subsections. The second and the third study the discrete case and the general case, respectively. Finally, we discuss the results obtained and open questions.
2. Preliminaries. In this section, we introduce the notation and present some useful known results. Let n be the length of the planning horizon. We normalize the batch size to 1, so that it will never appear in the models that we will consider. For each period t [member of] {1 ..., n} the following data is given:
* [d.sub.t]: demand in period t,
* [m.sub.t]: maximum number of installable batches in period t,
* [P'.sub.t]: unit production cost in period t,
* [f'.sub.t]: unit set-up cost in period t,
* [h'.sub.t]: unit holding cost in period t (defined also for t = 0),
* [g'.sub.t]: unit backlogging cost in period t (defined also for t = 0). We suppose that all data is rational and that [m.sub.t] are nonnegative integers. We also define the unit vector et = {0, 0, ..., 0, 1, 0, ..., 0}, where the one is in position t. For ease of presentation, we will often index d, m, or e by intervals or (multi-)sets. This denotes the sum over the indexing interval or set. For example, [d.sub.k, l] = [[summation].sup.l.sub.t=k][d.sub.t] and [e.sub.s] = [[summation].sub.t[member of]S] [e.sub.t]s, where S [subset or equal to] {1, ..., n}. Note that S may be a multiset, i.e., it may contain the same element several times. Finally, [(x).sup.+] and [??]x[??] denote max(x, O) and the ceiling function, respectively.
We model the different problems as mixed integer programs using the following variables defined for each period t [member of] {1, ..., n}:
* [x.sub.t]: production in t,
* [y.sub.t]: number of batches that are installed in t,
* [s.sub.t]: stock at the end of t (defined also for t = 0),
* [r.sub.t]: backlog in t from later periods (defined also for t = 0).
This leads to the following formulation of the lot-sizing problem with backlogging and constant batch size (denoted by LSB):
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (1)
[s.sub.t-1] + [r.sub.1] + [x.sub.t] = [d.sub.t] + [r.sub.t-1] + [s.sub.t] 1 [less than or equal to] t [less than or equal to] n, (2)
[x.sub.t] [less than or equal to] [y.sub.t] 1 [less than or equal to] t [less than or equal to] n, (3)
[x.sub.t] [greater than or equal to] 1 [less than or equal to] t [less than or equal to] n, (4)
[s.sub.t], [r.sub.t] [greater than or equal to] [less than or equal to] t [less than or equal to] n, (5)
[y.sub.t] [member of] {0, 1, ..., [m.sub.t]} 1 [less than or equal to] t [less than or equal to] n, (6)
This is the problem considered in [section]4.3. All other problems will be defined as special cases. The following results are well-known and will be used later.
PROPOSITION 2.1. [(x + a + b).sup.+] - [(x + a).sup.+] [greater than or equal to] [(x + b).sup.+] - [(x).sup.+] for any a, b [greater than or equal to] and x [member of] R.
PROOF. The result follows from the convexity of x [??] [(x).sup.+].
PROPOSITION 2.2. If a function f defined on the interval of integers [a, b] is nondecreasing and can be evaluated in constant time, then, for any y, one can find the values
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],
and the corresponding values of x in O(log(b- a)) time by binary search.
PROPOSITION 2.3 (WAGNER AND WHITIN [29]). Let the cost [phi](a, b) of the interval [a, b] be given for all integers a and b satisfying 1 < [less than or equal to] a [less than or equal to] b [less than or equal to] n. The problem of partitioning the interval of integers [1, n] into subintervals with minimum cost is solvable in O([n.sup.2]) time by dynamic programming.
In the rest of this paper, we will denote by PARTITION-INT([phi]) the function which computes the cost of this optimal partition.
Given a finite set N = {1, ..., n} and a nondecreasing submodular function F on N with F([empty set]) = 0, the polytope
P(F) = {y [member of][R.sup.n.sub.+]|[summation over (i[member of]S)][y.sub.i][less than or equal to] F(S) for S[not subset] N
is the polymatroid associated with (N, F). The optimization problem OPT(N, F) associated to the matroid is:
min [n.summation over (i=1)][f.sub.i][y.sub.i],
y [member of] P(F),
[y.sub.i][less than or equal to][m.sub.i], i = 1, ..., n.
It is well-known that the greedy algorithm solves OPT(N, F) (Nemhauser and Wolsey [18]). Another property that we will need makes...
|
