Primal-Dual Algorithms for Deterministic Inventory Problems Retsef Levi∗ Robin Roundy† David B. Shmoys‡ Abstract We consider several classical models in deterministic inventory theory: the single-item lot-sizing problem, the joint replenishment problem, and the multi-stage assembly problem. These inventory models have been studied extensively, and play a fundamental role in broader planning issues, such as the management of supply chains. For each of these problems, we wish to balance the cost of maintaining surplus inventory for future demand against the cost of replenishing inventory more frequently. For example, in the joint replenishment problem, demand for several commodities is specifed over a discrete fnite planning horizon, the cost of maintaining inventory is linear in the number of units held, but the cost incurred for ordering a commodity is independent of the size of the order; furthermore, there is an additional fxed cost incurred each time a non-empty subset of commodities is ordered. The goal is to fnd a policy that satisfes all demands on time and minimizes the overall holding and ordering cost. We shall give a novel primal-dual framework for designing algorithms for these models that signifcantly improve known results in several ways: the performance guarantees for the quality of the solutions improve on or match previously known results; the performance guarantees hold under much more general assumptions about the structure of the costs, and the algorithms and their analysis are signifcantly simpler than previous known results. Finally, our primal-dual framework departs from the structure of previously studied primal-dual approximation algorithms in signifcant ways, and we believe that our approach may fnd application in other settings. More specifcally, we provide 2-approximation algorithms for the joint replenishment problem and for the assembly problem, and solve the single-item lot-sizing problem to optimality. The results for the joint replenishment and the lot-sizing problems also hold for their generalizations with back orders allowed. As a by product of our work, we prove known and new upper bounds on the integrality gap of some LP relaxations of the above mentioned problems. ∗rl227@cornell.edu. School of ORIE, Cornell University, Ithaca, NY 14853. Research supported partially by a grant from Motorola and NSF grant CCR-9912422. †robin@orie.cornell.edu. School of ORIE, Cornell University, Ithaca, NY 14853. Research supported partially by a grant from Motorola, NSF grant DMI-0075627, and the Quer´ ogico y de Estudios Superiores etaro Campus of the Instituto Tecnol´ de Monterrey. ‡shmoys@cs.cornell.edu. School of ORIE and Dept. of Computer Science, Cornell University, Ithaca, NY 14853. Research supported partially by NSF grant CCR-9912422. 1 Introduction In this paper, we consider several classical models in deterministic inventory theory: the single-item lot- sizing problem, the joint replenishment problem (JRP) and the multi-stage assembly problem. These inventory models have been studied extensively over the years, in a number of different settings, and play a fundamental role in broader planning issues, such as the management of supply chains (see, e.g., [3, 14]). We shall consider the variants in which there is a discrete notion of time with a fnite planning horizon, and the demand is deterministic (known in advance) but dynamic, i.e., it varies over the planning horizon. Each of the inventory models that we consider has the following characteristics. There are N commodities (or equivalently, items) that are needed over a planning horizon consisting of T time periods; for each time period and each commodity, there is a demand for a specifed number of units of that commodity. To satisfy these demands, an order may be placed in each time period. For each commodity i ordered, a fxed ordering cost Ki is incurred, which is independent of the number of units ordered from that commodity. The order placed in time period t may be used to satisfy demand in time period t or any subsequent point in time. In addition, the demand in time period t must be satisfed completely by orders that have been placed no later than time period t. (In the inventory literature, these assumptions are usually referred to as “neither back orders nor lost sales are allowed”.) Since the cost of ordering a commodity is independent of the number of units ordered, there is an incentive to place large orders, to meet the demand not just for the current time period, but for subsequent time periods as well. This is balanced by a cost incurred for holding inventory over time periods. We will let hi denote this holding cost, that is, the cost incurred by ordering st one unit of inventory in period s, and using it to meet the demand for item i in period t. We will assume that hi is non-negative and, for each (i, t), is a non-increasing function of s. (Note that in particular, we do not st require subadditivity; we could have that hi >hi + hi for some rj for each edge (i, j) in the tree. Node (or item) 1, the root of the tree, is facing external demands over T time periods (d1, .., dT ). A unit of item i is assembled from one unit of each of its predecessor items in the tree. Thus, any unit of item 1 consists of one unit of each of the other items. We again have an ordering cost and holding cost for each item. We note that the way we model the holding cost is much more general than the most common setting, in which each item i has a linear holding cost, so that the cost of holding one unit from time period s to time period t is equal to (t − s)hi, for some choice of hi > 0 (or to Pt hi in the more general case). By l=sl allowing the more general structure described above, we can capture other important phenomena, such as perishable goods, where the cost of holding an item longer than a specifed interval is essentially infnite. The strength of the general holding cost structure is demonstrated in Section 4.2, where we show how to apply the algorithm to the more general JRP model with backorders. As for the ordering cost, we note that our algorithms are applicable also in the presence of time dependent cost parameters as will be specifed later on. Furthermore, in addition to the (fxed) ordering cost that is independent of the order size, one can incorporate a per-unit ordering cost into the holding cost term (as long as we preserve the monotonicity). In this paper, we describe a unifed novel primal-dual algorithmic framework that provides optimal and near-optimal solutions to the three inventory models described above. Our main result is a 2-approximation algorithm for the joint replenishment problem. By this we mean that for any instance of the problem, our algorithm computes a feasible solution in polynomial-time, with cost that is guaranteed to be no more than twice the optimal cost. The joint replenishment problem is NP-hard [2], but it can be solved in polynomial- time by dynamic programming for a fxed number of commodities, or for a fxed number of time periods [29, 27, 17], (by fxing the times at which joint orders are placed the problem decomposes by item). LP-based techniques have not previously played a signifcant role in the design of approximation algorithms for NP- hard deterministic inventory problems with constant performance guarantee. LP-rounding was applied to a more general problem by Shen, Simchi-Levi, and Teo [24], but this yielded a guarantee of only O(log N + log T ). This absence of results is particularly surprising in light of the fact that it has long been understood that these problems admit integer programming formulations with strong linear programming relaxations, i.e., that provide tight lower bounds (see, e.g., [15, 20, 21]). These formulations are closely related to formulations that have been studied for the facility location problem, which has also been a source of intense study for approximation algorithms. Our performance guarantee improves signifcantly on the results of Joneja [16], who only considered the case where all the cost parameters are fxed over time. His paper claims a 3-approximation algorithm for this problem, but it has been pointed out that the proof is fawed [26]. A somewhat different analysis yields a performance guarantee of 5 [19]. Federgrun and Tzur [9] proposed an interesting dynamic programming-based heuristic for the joint replenishment problem, but they assume that cost and demand parameters are bounded by constants. The single-item lot-sizing problem was shown to be solvable in polynomial time by dynamic programming in the landmark paper of Wagner & Within[28]. Furthermore, Krarup & Bilde [18] showed, in this case, that the facility location-inspired LP has integer optima by means of a primal-dual algorithm, and B´ar´any. Van Roy, and Wolsey [4] gave yet another proof of this by means of an explicitly generated pair of primal and dual optima (that are computed, ironically, via a dynamic programming computation). Finally, Bertsimas, Teo and Vohra [5] gave a proof, which is based on LP rounding. If we consider our joint replenishment algorithm as applied to the special case of the single-item lot-sizing problem (where, since there is only one item, one can merge the joint ordering cost and the individual item ordering cost into one new ordering cost), then we obtain a new, extremely simple, primal-dual optimization algorithm that also proves the integrality property of this LP formulation. Another dual-based optimization algorithm for the single-item lot-sizing problem, has been proposed by Hoessel, Wagelmans and Kolen [12]. However, their algorithm is very different than ours. Finally, with some modifcations, our primal-dual algorithm can also be applied to the assembly problem to yield a 2-approximation algorithm. Here, we achieve the same approximation ratio as Roundy [22], who gave a 2-approximation algorithm (again for the case where all cost parameters are fxed over time) using a non-linear relaxation and ideas borrowed from continuous-time lot-sizing problems. Although we only match the previous performance guarantee, our approach is much simpler, and it yields the performance guarantee under a much more general cost structure. In particular, under our assumptions on the cost structure, it is easy to show that the assembly problem is NP-hard by a reduction from the joint replenishment problem. However, for the variant of the problem considered by Roundy, it is still not known whether it is NP-hard or not [6]. As a byproduct of our work, we prove upper bounds on the integrality gap of the corresponding LP relaxations, the worst-case ratio between the optimal integer and fractional values; for both the JRP and the assembly problem, we prove an upper bound of 2. In [23], we give a family of instances of the JRP, for which the integrality gap is asymptotically 1.23. To understand the relationship between these inventory models and facility location problems, one can view placing an order as opening a facility; the demand points that this order serves correspond to demand points that are served by the open facility. Although these two classes of problems are related, there are also fundamental distinctions between them. For one, the distances implied by this facility location view of inventory problems is asymmetric and does not satisfy the triangle inequality. For facility location problems, the versions with asymmetric cost metric do not admit constant performance guarantee approximation algorithms (see, e.g., [1, 11, 7]), and so it is particularly interesting that the additional structure in these inventory problems is suffcient to obtain good approximation algorithms. Furthermore, we are interested in multi-commodity models; there has been recent work that considers multi-commodity facility location problems but, of course, with a symmetric cost metric [25]. We note that our algorithms have their intellectual roots in the seminal paper of Jain & Vazirani [13], which gives a primal-dual approximation algorithm for the uncapacitated facility location problem. Nonetheless our algorithms depart from their approach in rather signifcant ways, as we shall describe in detail in the next section. We believe that this new approach may fnd applications in other settings. The rest of the paper is organized in the following way. In Section 2 we describe the generic primal-dual algorithm focusing on the JRP case. Then in Section 3 we frst consider the lot-sizing problem as a special case of the JRP and show that the algorithm provides an optimal solution to this special case. In Section 4 we complete the presentation of the algorithm for the JRP case and describe the worst case analysis. We then show how to extend the algorithm for the JRP to the more general case in which back orders are allowed. In Section 5, we describe the modifcations in the algorithm and the analysis for the assembly problem. We conclude with some interesting open questions. 2 A primal-dual framework In this section, we outline the main ideas in our primal-dual framework. We start by giving a high-level description, and then give a more detailed presentation. We shall start by focusing on the JRP. It is straightforward to give an integer programming formulation in which there are 0-1 decision variables that indicate whether the demand for a given commodity in a particular time period is supplied from an order at a specifc time period, as well as 0-1 variables that indicate whether an order is placed in a given time period, and whether a particular commodity is included in that order. We shall defer presenting the details of this formulation and the dual of its LP relaxation, since the main ideas of the algorithm can be presented without any explicit reference to the LPs. Our algorithm works in two phases. In the frst phase of the algorithm we simultaneously construct a feasible dual solution and a feasible primal (integer) solution. Each demand point (i, t) has a dual variable bit, which can be interpreted as a budget. In constructing the dual solution, we use a dual-ascent approach. Each budget (i.e., dual variable bi), is initially 0 and is gradually increased until it is frozen at its fnal value; t that is, we never decrease its value. Unlike the primal-dual algorithm of Jain & Vazirani for the facility location problem (or that of Goemans & Williamson [10] for network design problems), we do not increase the dual variables uniformly. Instead we use a more sophisticated mechanism, which we call a waveform. Consider a wave that starts to move from the end of the planning horizon to the beginning (from period T to 1) and let τ be a continuous variable variable that indicates the current location of the wavefront; initially, τ = T . The budget of any unfrozen demand point is then related to the wavefront location τ. More specifcally, each demand point (i, t) keeps its budget fxed at 0 until the wave reaches period t. Moreover, once the wave crosses time t and as long as the budget bi is not frozen, we keep the budget of (i, t) equal to the holding cost of providing dit from τ ; t that is, bit = dit · hiτt, which, for notational convenience, we shall denote Hτt i (see Figure 2.1). Each demand point is going to offer its budget to all potential orders (i.e., time periods) from which it can be served. When offered to some potential order at time period s (s =1,...,t), the budget bi of demand t point (i, t) is frst used to pay for the holding cost incurred by providing dit from s. The residual budget is °°±°±°±°±°±°±°±°±°±°±°±°±°±°±± contribution wave ¾ to ordering -¾ Hi st - costs at s 1 2 τ s t T -2 T -1 T ¾ budget bi t = Hi τ t - Figure 2.1: The waveform specifcation of the budget bi and its allocation. t then used to pay a share of the item ordering cost Ki with respect to the order s. Once the item ordering cost is completely paid for (by this and other demand points), the residual budget is used to pay a share of the joint ordering cost K0 with respect to s. Each potential order s collects the budgets of all relevant demand points (i.e., demands at time period s or later), trying to pay for its cost. The cost of an order consists of the joint ordering cost K0, the item ordering cost Ki for each item i included in the order, and the holding cost for each demand point provided by the order. Note that each demand point is simultaneously making these offers to multiple potential orders, even though it will ultimately be served by exactly one of them; furthermore, more than one of these orders might be opened, and the extent to which these multiple offers are simultaneously accepted is directly linked to the performance guarantee that we will be able to prove. Once the cost of some joint order s is fully paid for, we are going to temporarily open this joint order. This order at time period s will include exactly those items for which the item ordering cost with respect to s has been fully paid. We then freeze the budgets of all demand points that can be served from that order; that is, all unsatisfed demands for those items ordered in time period s for all time periods s or later. We note that the waveform mechanism ensures that the budget of any frozen demand point is, at minimum, enough to pay for the holding cost incurred by satisfying it from the order at s. This phase ends when all budgets are frozen, providing a feasible dual solution and a feasible solution to the JRP. However, this initial solution is too expensive, since the budget of a demand point might be used to pay for the opening of multiple orders. This leads to the second phase, in which we prune the initial solution to get a cheaper one. For each temporarily opened joint order in some period s, we consider the location τ of the wavefront when s was temporarily opened; let open(s) denote this value, where it is clear that open(s) 1, PNi=1 Pt≥s zst = K0. (Note that we can no longer increase i any variable z without violating the constraint (7).) Then we declare that the joint order in period s is st temporarily opened. In this order at s, we include any item i such that Pt≥s li = Ki. For each such item st i, we freeze the budget of any unfrozen demand point (i, t) with t ≥ s (see also Event 2 above). Event 4 Suppose τ =1. We then open a joint order in period 1. We add to this order all the items i =1, .., N. We then charge the cost of this order to the dual variables of the demand points (i, 1) by setting ii bi := li 11, where li := Ki and z := K0/N (for i =1, .., N). Next we freeze all the unfrozen 1 11 + z 11 11 budgets and terminate. We note that the various events described above are likely to occur at non-integer wavefront locations (i.e., for non-integer values of τ). The procedure continues until all budgets are frozen (i.e., until Event 4 above happens). In case several events happen simultaneously we consider them in an arbitrary order. Let (ˆb, ˆl, zˆ) be the dual solution generated at the end of this phase. It is easily seen that this a feasible dual solution. Moreover, the above procedure also induces a feasible (integer) primal solution, since the budget of each demand point is frozen only when there is a temporarily opened order s (such that s ≤ t) with item i. However, this solution is rather expensive, since the budget of a demand point can be multiply used to pay towards several orders. Next, we discuss the second phase of the algorithm, in which we prune the solution to get a cheaper one in which this overpayment is bounded. More specifcally, for the JRP and the assembly problem, we will show that each demand point contributes to at most two orders in the pruned solution. We frst discuss the simpler special case of the single-item lot-sizing problem (in Section 3) and then discuss the more general model of the JRP (in Section 4). 3 The single-item lot-sizing problem In this section, we show that the primal-dual framework produces an optimal solution to the single-item lot-sizing problem. We start with this model, rather than the JRP, since this allows us highlight the main ideas of the algorithm and its analysis. This lot-sizing problem can be viewed as the special case of the JRP in which N =1 and K0 =0. To simplify our notation, we will only have an ordering cost K and holding costs hst, where we now omit the item index. The primal and dual LPs are also simpler, as follows: XX X T Tt s=1 t=1 s=1 minimize xstHst (P1) K + ys X t s=1 xst ≤ ys,t =1,...,T, s =1, . . . , t, (10) xst,ys ≥ 0,s =1,...,T, t = s, . . . , T. (11) We also get similar dual: =1,t =1,...,T, subject to (9) xst XX T t=1 subject to bt ≤ Hst + lst,t =1,...,T, s =1, . . . , t. (12) T maximize bt (D1) lst ≤ K, s =1,...,T. (13) t=s lst ≥ 0,t =1,...,T, s =1, . . . , t. (14) If one considers the primal-dual framework applied to this setting, the budget bt of any demand point t is allocated (with respect to any order s) to pay for the cost of holding the demand dt from s to t, and then the leftover amount lst is used to pay a share of the ordering cost at s, K. We apply the procedure described in Section 2, but now an order s is temporarily opened as soon as its ordering cost K is fully paid, i.e., when Pt≥s lst = K. Let (ˆb, ˆl) be the dual feasible solution at the end of the frst phase. We next describe the pruning phase. Let R = {s1 =1 0. Observe that for each two orders with intersecting shadow intervals, there exists at least one demand point t that contributes towards both s and r (if s 0. In addition, each demand point should ˆ pay for its holding cost. We use Ht to denote the holding cost incurred by demand point t in (ˆx, yˆ), i.e., Pt Hstxˆst. For each demand point t =1,...,T , let freeze(t) be the location of the wavefront τ when its budget was frozen, i.e., ˆbt = Hfreeze(t),t. We call the interval [freeze(t),t] the active interval of t. This is the interval along which we increased the budget bt. Clearly, the demand point t can contribute only towards temporarily opened orders within its active interval. For each order s outside the interval the holding cost Hst are higher than the budget ˆbt = Hfreeze(t),t, so no share can be pad towards the ordering cost. s=1 Lemma 3.1 For any demand point t =1, .., T , there exists a single order s ∈ R0 that is within its active interval. Proof : We frst show that there exists an order s ∈ R0 within the active interval of t. Let s0 ∈ R be the order that caused the budget of t to be frozen. By defnition of the specifc waveform mechanism we are using, we have that open(s0)= freeze(t). If s0 ∈ R0, then since s0 is in the active interval of t, we are done. 0 Otherwise, there must be some s ∈ R0, with s 0). Let C(s) be the set of contributor items for each st s ∈ R. We start by applying the same procedure we have used in Section 3 for the lot-sizing problem to get a subset R0 ⊆ R of permanently opened joint orders (i.e., we process the orders in R from earliest to latest, retaining the next only if its shadow interval does not intersect the shadow interval of any order already in R0). As before, after this pruning step each demand point (i, t) contributes towards the ordering cost of at most one joint order in R0 (the arguments are identical to the ones in Lemma 3.1). Initially, for each joint order s ∈ R0 , we include all of its contributor items i ∈C(s). We call these orders regular orders. Again using the properties of the waveform mechanism, it is straightforward to show that each demand point (i, t) has at least one joint order s ∈ R0 within its active interval (by a proof nearly identical to this part of Lemma 3.1). However, there is no guarantee that there is a joint order within the active interval of (i, t) that includes item i. Thus, we can not guarantee that each demand point incurs bounded holding cost, and more work is required. We will apply a ‘correction step’ to make sure that each demand point (i, t) will be served from an order within its active interval. This will imply that the holding cost it incurs can be paid by its budget ˆbti . This step is done separately for each item i. Focus on one item i, and fnd the latest demand point (i, t) such that there does not exist a regular order of item i within its active interval. We have already observed that there does exist at least one permanently opened joint order s ∈ R0 within its active interval. Hence, we can add an extra order of item i to the earliest joint order in R0 ∩ [freeze(i, t),t], say s. We shall say that (i, t) is the initiator of the extra order of item i in period s. That is, we indicate that item i was added to s as an extra order to provide (i, t) with a ‘close’ order. This process is repeated on the remaining time horizon [1,s), where again s is the earliest extra order of item i we have placed so far. Similarly, we next search next for the latest positive demand point (i, t) with t ∈ [1,s − 1] and with no appropriate order (with item i) in its active interval. We continue until each demand point (i, t) can be served, by either a regular or extra order, within its active interval (see also fgure 4.3). The same procedure is repeated for each item i. Unlike the lot-sizing case discussed in Section 3, the extra orders that we add in the JRP case are likely to create overpayment, where the budgets of some demand points may be used to pay a share of the item ordering cost of multiple orders. However, by choosing the extra orders to be the earliest possible in the active intervals of the corresponding initiators, we guarantee that each demand point can pay towards at most two orders. This will be made rigorous in the analysis presented below. v vvvvvv active interval > > active interval 1 freeze(i, t0) (i, t0) freeze(i, t) (i, t) T -1 T initiator initiator joint order v regular order extra order -> Figure 4.3: Correction Step for item i. We note that after all the orders are specifed, each demand point (i, t) is satisfed from the latest possible order s ∈ R0 containing item i, and this provides a feasible solution for the JRP. Let (ˆx, yˆ) denote this solution. 4.1 Analysis of the JRP algorithm We will show that the cost of (ˆx, yˆ) can be paid using the dual feasible budgets (ˆb, ˆl, zˆ) such that each demand point (i, t) is charged at most 2ˆbti . For this, we need to introduce a somewhat more involved charging scheme. For the joint and regular orders, we use the contributor items to pay for their joint and item ordering cost, respectively. The joint ordering cost and the item ordering cost of regular orders of each s ∈ R0 is i K0 + X Ki = XX(lˆi +ˆz ). st st i∈C(s) i∈C(s) t≥s This follows from the construction of the algorithm. Now consider an extra order of item i in period s ∈ R0 , and let (i, t) be the initiator of this extra order. Let s0 be the freezing order of (i, t), i.e., the order that caused the budget of (i, t) to freeze. In particular, bi 0 freeze(i, t) ≤ open(s0) (observe that the budget ˆ could have frozen after s was opened as described in t 0 Event 2a in Section 2). We claim that s ≤ s . By defnition, s is the earliest order in R0 ∩ [freeze(i, t),t]. We also know that R0 ∩ [open(s0),s0]=6∅, since either s0 ∈ R0 (i.e., permanently open), or it was eliminated 00 0000 by some earlier order s ∈ R0 , such that open(s0) ≤ s 0. In addition, we will say that (i, t) contributes towards some extra order of st st item i in period s ∈ R0 if ˆli > 0. Observe that each demand point (i, t) can only contribute towards a Ni(s),t joint and a regular order r with r ≤ t and towards an extra order s with Ni(s) ≤ t. We charge demand point (i, t) with what it contributes towards different orders in R0 , as well as the holding cost it incurs in (ˆx, yˆ). Denote this holding cost by Hˆ ti . We now show that, using the above charging scheme, one can pay for the cost of (ˆx, yˆ) such that no demand point is charged more than 2ˆbit. We frst state and prove the following lemma, which is central to our result: Lemma 4.1 Consider any demand point (i, t) and let r1 ∈ R0 be the latest order in R0 , regular or extra, towards which (i, t) contributes. Then, either r1 ∈/ [freeze(i, t),t] or it is the earliest order in R0 ∩ [freeze(i, t),t]. Proof : Assume r1 ∈ [freeze(i, t),t] and consider the following two possible cases: Case 1. The order in period r1 is a regular order of item i. We will argue that open(r1) ≤ freeze(i, t). i We know that i ∈C(r1), and so Pu≥r1 zˆ > 0. By the construction of the waveform, we know that r1,u the demand points of an item can start paying a share of the joint ordering cost only after the item ordering cost is fully paid. Thus, when the order at r1 was temporarily opened, we immediately added item i to that order. Consider the wavefront position τ when the order r1 is opened (i.e., the wavefront is located in open(r1)); if the demand point (i, t) is not frozen prior to this point in the execution of the algorithm (i.e., when τ is larger), it must become frozen now. In other words, open(r1) ≤ freeze(i, t). By the choice of r1, we know that its shadow interval [open(r1),r1] does not contain another order r ∈ R0 . Since [freeze(i, t),r1] ⊆ [open(r1),r1], this implies that r1 is the earliest order in R0 ∩ [freeze(i, t),t]. Case 2. The order in r1 is an extra order of item i. This order has some initiator (i, t∗) with a freezing order Ni(r1). As we have already observed, we must have r1 ≤ Ni(r1) ≤ t (we assume that (i, t) contributes towards r1). In particular, by the waveform properties we know that freeze(i, t∗) ≤ freeze(i, t), since (i, t) was frozen no later than (i, t∗) was (as Ni(r1) ≤ t). However, from the way we add extra orders, we know that the order at r1 is the earliest in R0 within the active interval of the initiator (i, t∗). In other words, R0 ∩ [freeze(i, t∗),r1)= ∅. Given that we already concluded that freeze(i, t∗) ≤ freeze(i, t), the lemma follows. The above lemma has several immediate corollaries: Corollary 4.2 Any demand point (i, t) can contribute towards at most two orders in R0 . Proof : Suppose that (i, t) contributes towards more than one order in R0 , and let r1 >r2 be the two latest such orders. Suppose that r1 < freeze(i, t); in that case, r1 and r2 must both be extra orders of item i (since they do not lie in the active interval of (i, t)). We will argue that (i, t) cannot contribute to both. If (i, t) contributes to r2, then we must have that ˆli N > 0, and so r1 < freeze(i, t) ≤ Ni(r2). But the initiator of r2 is i(r2),t earlier than r1 and hence earlier than Ni(r2), which is its freezing order. Clearly, it is impossible for this to be true. Hence, (i, t) cannot contribute to more than one extra order that precedes its active interval. Hence, r1 ∈ [freeze(i, t),t]. By Lemma 4.1, it follows that r1 is the earliest permanent order in N [freeze(i, t),t] ∩ R0 . Hence, no other order that (i, t) contributes to is within its active interval. Any order to which (i, t) contributes that precedes its active interval is an extra order. But we have already seen that there is at most one such order (namely r2), which completes the proof. Corollary 4.3 Consider a demand point (i, t) and let r1 be the latest order towards which (i, t) contributes some positive share. Then the holding cost that (i, t) incurs in (ˆx, yˆ) is at most Hi (i.e., Hˆ i ≤ Hi ). r1,t tr1,t Proof : Since the algorithm ensures that each demand point (i, t) is satisfed from some order r ∈ R0 within its active interval, the claim follows immediately from Lemma 4.1, since r1 is either the earliest in [freeze(i, t),t] ∩ R0 or r1 < freeze(i, t). We now ready to prove the main theorem: Theorem 4.4 The primal-dual framework yields a 2-approximation algorithm for the JRP. Proof : Consider any demand point (i, t) and let r1 ∈ R0 again be the latest order in (ˆx, yˆ) towards which (i, t) contributes a positive share. If the order in period r1 is a regular order of item i, then (i, t) contributes ˆli + zˆi > 0. If the order at r1 is an extra order of item i, then (i, t) contributes ˆli > 0, where r1,t r1,t i(r1),t N freeze(i, t) ≤ Ni(r1) ≤ t. In either case, this is clearly bounded by ˆbti . Moreover, if (i, t) contributes only to one order, then by Corollary 4.3 Hˆ i ≤ ˆbti , and we can pay for its holding cost and overall contributions t using at most 2ˆbit. Now assume that (i, t) also contributes towards a second (earlier) order r2. By Lemma 4.1, r2 must Hence, (i, t) contributes ˆli be an extra order of item i such that r2 ∈/ [freeze(i, t),t]. > 0 towards i(r2),t r2, where freeze(i, t) ≤ Ni(r2) t). Given a demand dit, we let Bi be the back order cost of providing this demand from an order in period s, where st s>t. As before, we will assume that Bi is non-negative, linear in dit and non-decreasing in s ≥ t for any st fxed (i, t). We will show that our general assumptions on the holding cost imply that this more general case with back orders can be reduced to the previous variant without back orders. Consider now any two consecutive orders of item i, say, in periods s1 j for each edge (i, j) in the tree. Item 1, the root of the tree, is facing external demand over T time periods (d1, .., dT ). This tree defnes the assembly relations between the different items. Each unit of item i is assembled from one unit of each of its direct predecessor items in the tree. This ratio of “one-to-one” is without loss of generality and can be achieved by re-defning the unit of measure of the items if necessary. The tree structure implies that each item is used to directly assemble a single more complex item, as it has a single successor item in the tree. The goal is to satisfy all of the external demands for item 1, d1,...,dT on time with minimum cost. The cost again consists of fxed ordering cost, Ki for each order of item i, and linear item holding cost for carrying inventory of that item over periods, where the holding cost has a similar structure to the one discussed in Section 1. However, each order of item i can be satisfed only from the on-hand inventory of the items from which this item is assembled (i.e., its direct predecessor items in the tree, or an external supplier if this item corresponds to a leaf in the tree). Alternatively, an order of item i placed in period t can be used to satisfy orders of its successor item in period t and in subsequent periods. In other words, in order to provide the demand dt of item 1 in period t, each one of the items in the tree must provide dt units by time t. We let P(i) and S(i), respectively, be the set of all predecessors and successors of item i within the in-tree (both including item i). Furthermore, let P0(i) denote the direct predecessors of item i, and we let σ(i) be its direct successor. Finally, for each item i and each item k ∈P(i), we let pathki be the path from k to i (k>i) in the tree defned above. 5.1 A Linear Program We start by explaining how one can formulate the assembly problem as an integer program with a structure similar to that exploited for the JRP. For this, we need to introduce some well-known results from inventory theory. One well-known result on the assembly problem is the optimality of what is called the class of nested policies (see [8]). In a nested policy, whenever we place an order of item i, we simultaneously place an order for its direct successor item in the tree, item σ(i). In other words, we can assume that we place an order for item i at time period s only if we also place an order for every item j ∈S(i) at the same time period. It is not hard to show that any non-nested policy can be converted to a nested policy with at most the same cost by differing orders of the item with the larger index (for details see [8]). In addition, it is readily verifed that zero inventory ordering (ZIO) policies are optimal for the assembly problem. In ZIO policies we place an order for item i only if the current on-hand inventory of this item is 0. The proof is again by virtue of converting any policy that does not follow the ZIO rule to one that does follow it and has at most the same cost (in this case by decreasing the quantity of one order and increasing the quantity of another). These two properties implies that the assembly problem has also an optimal policy in which for each item, the units that are used to satisfy the demand in period t are provided by single order of item i. In multi-stage models such as the assembly problem, it is often more convenient to consider the echelon inventory level, as opposed to the conventional inventory level discussed so far (which is essentially the on-hand inventory of that item). The echelon inventory level of item i is defned to be the overall number of units of that item in the system, which includes units that are assembled into other items. Thus, the echelon inventory level of item i is equal to the sum of the conventional inventory levels of all its successor items (i.e., j ∈S(i)). Observe that the echelon inventory level of each item i increases only when an order of item i is placed, and decreases only when demand occurs. In other words, it is dependent only on decisions made with respect to item i. Using the echelon inventory concept, we can defne for each item i and s ≤ t, h ¯i a per unit echelon holding cost, st, for ordering a unit of item i in period s that will be used to satisfy the demand of the end product in period t. We will assume that the echelon holding cost parameters have the same monotonicity properties as discussed in Section 1. Following are some comments on the relations between echelon and conventional holding cost. If also assume that the the conventional holding cost is additive, i.e., hist = hi + hti 0t for each i and s ≤ t0 ≤ t st0 (this is essentially the traditional holding cost), then there exists a straightforward cost transformation from conventional to echelon holding cost. Given the conventional holding cost parameters hist, we defne the echelon holding cost parameters as ¯ := hi − Pk∈P0(i) st, i.e., as the marginal additional conventional hi hk st st holding cost due to assembling item i. We assume that h ¯i is non-negative, since otherwise there will no st physical inventory of the predecessor items (it will be cheaper to assemble them immediately). To see why echelon and conventional holding costs both lead to equivalent formulation of the model, consider the demand dt of item 1 in period t, and let s(i) ≤ t be the period in which item i ordered these dt units (i =1,...,N). More specifcally, these units were assembled into item i in period s(i), and then assembled into item σ(i) in period s(σ(i)). Therefore, the conventional holding cost that these units incur at stage i is equal to hi dt. However, by the additivity assumption this is equal to (hi − hi )dt. So the s(i),s(σ(i)) s(i),t s(σ(i)),t overall conventional holding cost incurred is NN N dt X(hi − hi )= dt X(hi − X hk )= dt X h ¯i . s(i),t s(σ(i)),t s(i),t s(i),t s(i),t i=1 i=1 k∈P0(i) i=1 Observe again that each item incurs echelon holding costs that are only a function of the decisions made with respect to item i (at stage i). This decomposition of holding costs to items will be a key property in formulating the LP below. From now own we will assume that the problem is given to us with echelon holding cost parameters h ¯i as discussed above. st Let H ¯ i = h ¯i dt be the overall echelon holding cost of ordering the dt units of item i required to satisfy st st the demand in period t from period s. By relying on properties the ZIO policies and echelon inventories and holding costs stated above, it is straightforward to adapt the linear programming relaxation given in Section 2 to the assembly problem: NT NTt i=1 s=1 i=1 t=1 s=1 XXX XX ¯ i Hi x st st i minimize (P2) Ki + y s t s=1 x i ≤ yj ,i =1,...,N, t =1,...,T, s =1,...,t, j ∈S(i) (16) st s ii x ≥ 0,i =1,...,N, s =1,...,T, t = s, . . . , T. (17) st,ys 0 There no longer is a joint ordering cost, so the variables y are eliminated, along with their terms in s i the objective function, as well as the constraints (3). The binary variable x corresponds to the decision to st order the units of item i that are used to satisfy the demand in period t in period s. The objective function i H ¯ i coeffcient of x is the corresponding echelon holding cost associated with this decision. Finally, one st st i has the constraint that x ≤ ysj for each j ∈S(i) (and for each period s ≤ t). This implies the nestedness st property. It is straightforward to verify that the induced integer program fnds a minimum-cost feasible nested policy, i.e., it fnds an optimal solution for the assembly problem (since nested policies are optimal). Thus, the LP relaxation again provides a lower bound on the cost of each feasible policy. Note that in the i above LP there are many redundant constraints (it would be suffcient to require only x ≤ ysσ(i) . However, st since we are not going to solve the LP, it does not have any impact. On the other hand we get a ”nicer” dual problem: X i x =1,i =1,...,N, t =1,...,T, st subject to (15) NT i=1 t=1 X ¯ iH X bi t maximize subject to (D2) + X z ij st, i =1,...,N, t =1,...,T, s =1, . . . , t. bi t ≤ (18) st j∈S(i) ki z ≤ Ki,i =1,...,N, s =1,...,T. (19) st XX k∈P(i) t≥s ijz≥ 0,st i = 1, . . . , N, t = 1, . . . , T, s = 1, . . . , t, (20) j ∈ S(i) The intuition underlying the dual program is similar to the one in the JRP case. We again think on the variables bi as budgets associated with demand points. However, now a demand point (i, t) corresponds to t the dt units of item i that are assembled into the dt units of the end product (item 1) that satisfy the external demand in period t. The concepts of echelon inventory and echelon holding cost, enable us to treat each such demand point separately. Since the solution is nested, whenever there is an order of item i then in the same period there is an order of each one of the items on the path between i and the root of the tree (i.e., j ∈ pathi1). Hence, each demand point (i, t) will frst pay a share of the item ordering cost of item i towards potential orders in periods {s :≤ t}. However, it may also pay some share of the item ordering cost of items on the path between i and the root of the tree. The variables zij for j ∈S(i) account for these contributions. st 5.2 Primal-Dual Procedure We use a similar procedure to construct the dual solution and the initial feasible (integer) primal solution. In particular, we again use the waveform mechanism, i.e., the budget of each demand point (i, t) is kept at 0 H ¯ i as long as τ ≥ t. Once t ≥ τ and as long as the budget is not unfrozen we maintain the invariant bi = t τt (the echelon holding cost of providing dt units of demand i in period t from τ). We note again that here a demand point (i, t) corresponds to providing dt units of item i to node 1 (i.e., item 1), so as to satisfy the ij ¯ external demand dt. Given a potential order s, the budget bti will be allocated to Hsti + Pj∈S(i) zst. First it will be used to pay for the echelon holding cost incurred by holding dt units of item i in the system from period s to t. Once the budget is suffciently large to pay for the holding cost, and because of the nestedness property, it will possibly contribute a share of the item ordering cost at s towards items j ∈ pathi1. The allocation of these contributions towards item ordering costs is done according to the order of these items on the path from i to 1, i.e., (i, t) may contribute to the item ordering cost in period s of some item j 6= i in S(i) only after the ordering cost in period s of all the items on the path from i to j is already fully paid. ij These contributions are done through the variables z . Of course, we must also maintain, for each item i st ki and each ordering period s, that the total of the shares contributed, Pt≥s Pk∈P(i) zst ≤ Ki (Constraint (19) above). We will temporarily open an order in period s only when the ordering cost of item 1 at s is fully paid. We will add item i to this order only if each item on the path from i to item 1 (i.e., each j ∈ pathi1) has already fully paid for its item ordering cost with respect to s. We now describe the frst phase of the algorithm in detail, focusing on the different events that may occur: Event 1 When the wavefront arrives at s, i.e., τ = s (for s = T,T − 1,..., 2), we identify all unfrozen ii demand points (i, t) with t = s, . . . , T and start increasing the variable z at the same rate as bi (keeping st t bi H ¯ i H ¯ i ii := =+ z ). t τt st st ki Event 2 Suppose that for some item i> 1 and some period s> 1, we have Pk∈P(i) Pt≥s zst = Ki, i.e., the item ordering cost of i in this period is fully paid. (Note that this means that we can no longer to ki continue to increase any of the variables z without violating the constraint (19) of item i.) Then one of the st following cases applies: (a) Suppose that the order in time period s is already temporarily opened (see Event 3 below) and includes all items j ∈S(i) \{i}. Then we add to this order each item k ∈P(i) with a positive contribution ki towards the item ordering cost of item i at s, i.e., the set of items {k ∈P(i): Pt≥s z> 0}. st Note that all of these items have the property that each j ∈ pathki has already fully paid for its item ordering cost Kj with respect to s. For each such item k, we then freeze the budget of any unfrozen demand point (k, t) with t ≥ s. (b) Otherwise, consider the item j ∈S(i) with highest index, such that its item ordering cost is not yet fully paid. Let j0 be that item. Each item that has a positive contribution towards the item ordering cost of item i at s will now start to contribute towards the item ordering cost of that item j0 at s. More kj precisely, let j0 := max{j ∈S(i): Pk∈P(j) Pt≥s zst 0, consider each unfrozen demand point (k, t) with t ≥ s: freeze st ki kj0 the variable z and instead start increasing the variable z (at the same rate as the budget bi). The st stt kj0 variable z accounts for the portion in the budget bk that is used to pay a share towards the ordering st t cost Kj0 of item j0 with respect to s. k1 Event 3 Suppose that for some period s> 1, PNk=1 Pt≥s zst = K1. (Note that we can no longer increase k1 any variable z without violating the constraint (19) with respect to item 1, the root of the tree.) Then we st declare that the order in period s is temporarily opened. We add to this order at s any item i such that each item j ∈S(i) has fully paid for their item ordering cost Kj at s, i.e., that for each item j ∈S(i), we have kj Pk∈P(j) Pt≥s zst = Kj . For each such item i, we freeze the budget of each unfrozen demand point (i, t) with t ≥ s. Event 4 Suppose τ =1. We then open the order in period 1. We add to this order all of the items i =1, .., N. We then charge the cost of this order to the dual variables of the demand points (i, 1) by setting bi ii 1 := z11 := Ki (for i =1, .., N). Next we freeze all of the unfrozen budgets and terminate. The solution (ˆb, zˆ) at the end of this phase is clearly dual feasible with respect to (D2). In addition, the induced primal solution is feasible for the assembly problem and is nested. However, this initial primal solution for the assembly problem is again potentially too expensive because of possible multiple payments, so we need to prune it. 5.3 The Pruning Phase Our goal in the pruning step for the assembly problem is to fnd a cheaper feasible solution which is still nested. To achieve a nested feasible solution we exploit the tree structure and perform the pruning phase in an iterative way, starting at item 1 and then going up the tree. We treat item i only when all of the permanent orders of its successor items are already determined. Since we wish to keep the solution nested, the permanently open orders of item i will be a subset of the permanently open orders of its direct successor item σ(i) that are assumed to be already determined. Let R := {s1 =1 0, or in other wordsPt≥s zˆ > 0. st st We will denote the set of contributor items by C(i, s). The following property of contributor items, which follows from the construction of the algorithm, plays a critical role in the execution of the pruning phase (to be described below) and the analysis of the algorithm. If item k is a contributor of an order of item i in period s, and item l is on the path from k to i, then item l is also a contributor of item i in period s. In other words, if k ∈C(i, s) then pathki ⊆C(i, s). We again use open(s) and the corresponding shadow interval (for each s ∈ R), and freeze(i, t) and the corresponding active interval (for any (i, t)). Here open(s) is the wavefront location when the item ordering cost of item 1 at s was fully paid, and freeze(i, t) is the wavefront location at the time when the budget ˆbi t was frozen, i.e., the frst some when there was some period s ≤ t such that all the item ordering costs of items on pathi1 were fully paid. We start with item 1, and perform the same greedy procedure we used before to compute a subset R0 ⊆ R of permanently opened orders; i.e., we process the orders in R from earliest to latest, retaining the next only if its shadow interval does not intersect the shadow interval of any order already in R0 . For each order s ∈ R0 , we initially add all of the contributor items i ∈C(1,s), and call these regular orders. Next we consider the rest of the items i =2, .., N in a way such that each item i is considered only after σ(i) was considered. Focus now on some item i> 1. Before the pruning step of this item starts, we assume that we have already permanently opened all the orders of its successor item σ(i). Moreover, some of these orders may include item i, exactly those orders for which item i was a contributor item σ(i). As in the JRP case, there is no guarantee that for each demand point (i, t) there already exists a permanently opened order that includes item i within its active interval. We again have to perform a similar ‘correction step’ to the one described for the JRP in Section 4. We start at the end of the planning horizon, i.e. at T , and look for the frst positive demand point, say (i, t), such that currently there does not exist a permanently opened order of item i within its active interval, [freeze(i, t),t]. Let s0 ∈ R be its freezing order. We now consider the earliest permanently opened order in R0 ∩ [freeze(i, t),t] with item σ(i), say s, and add to this order all of the contributor items of the order of i at s0, i.e., items k ∈C(i, s0). Observe that all of these items are parents of item i, and were not yet considered in the pruning phase. We consider only permanently open orders that already include item σ(i) to guarantee the nestedness of the solution. Recall that for each k ∈C(i, s0), it is also the case that each item l on the path from k to i (i.e., l ∈ pathki) is also a contributor item (i.e., l ∈C(i, s0)). We call these orders extra orders. We say that (i, t) and i are the initiator and the initiator item, respectively, of these extra orders in s. We note that in essence these extra orders are equivalent to the extra orders that we have added in pruning phase for the JRP in Section 4. The only difference that now we may add not only an extra order of item i, but a set of extra orders of a subset of parent items of i, namely its contributor items at the freezing order s0 (i.e., items in C(i, s0)). As before, denote s0 := Ni(s). We then continue iteratively on [1,s), until each demand point (i, t) has a permanently open order with item i within its active interval. We now argue why the above procedure is well defned, i.e., that in the active interval of each demand 0 point (i, t) there exists at least one order with item σ(i). Moreover we argue that s ≤ s = Ni(s). Observe that for item i such that σ(i)=1, the arguments are identical to the ones in the JRP case (see Section 4). So, for each i, we can assume by induction that the procedure is well defned for σ(i). Let s0 ∈ R be again the freezing order of (i, t) and consider the demand point (σ(i),s0); we claim that freeze(i, t) ≤ freeze(σ(i),s0). Recall that (i, t) was frozen just when item i was added to the order at s0; hence item σ(i) must have been added to s0 either with item i, or perhaps earlier. In particular, (σ(i),s0) was frozen either with (i, t) or even earlier, i.e., freeze(i, t) ≤ freeze(σ(i),s0). By induction, we know that when (i, t) is considered, we have already ensured that there exists a permanently open order in R0 ∩ [freeze(σ(i),s0),s0] with item σ(i). Since [freeze(σ(i),s0),s0] ⊆ [freeze(i, t),t], we conclude that the procedure described above is indeed well-defned, and that s ≤ s0 . It is now clear that at the end of the pruning phase, we have a feasible nested solution to the assembly problem. Let (ˆx, yˆ) be this solution. Next we will show that the cost of the solution is no more than twice the optimal cost. The idea will be again to show that we can pay for the cost of the solution using the dual budgets, such that each demand point is charged at most ˆbit. 5.4 Analysis of The Assembly Problem We start by describing a charging scheme of how the cost of (ˆx, yˆ) can be paid using the feasible dual budgets (ˆb, zˆ). For each order s ∈ R0 , the items included in this order can be either regular orders or extra orders that were added in the course of the pruning phase. Let I(s) be the set of the initiator items of the extra orders included in s in (ˆx, yˆ). In other words, the set of all items included in and order at s ∈ R0 is partitioned by C(1,s) and {C(j, s): j ∈ I(s)}. We pay for the ordering cost of the regular orders at s, i.e., of items i ∈C(1,s), using Pi∈C(1,s) Ki = Pi∈C(1,s) Pj∈S(i) Pt≥s zˆstij . The equality is correct based on the observation that if for some k ∈P(i) and j ∈S(i) we have k ∈C(i, s) and i ∈C(j, s), then we also have k ∈C(j, s). As for the items in extra orders at s, we can partition them according to their initiator item in I(s). Thus, Kk we have Pi∈I(s) Pk∈C(i,Ni(s)) = Pi∈I(s) Pk∈C(i,Ni(s)) Pl∈pathki Pt≥Ni(s) zˆN kl i(s),t. This is correct based on the construction of the algorithm and the same argument used above for the regular orders. For each demand point (i, t) we say that it contributes towards a regular order in period s ∈ R0 if ij i ∈C(1,s) and Pj∈S(i) zˆ > 0. We say that (i, t) contributes towards extra orders at some s ∈ R0 , if st ik i ∈C(j, Nj (s)) for some 1 0. In addition, each demand point is charged with the echelon holding cost that it incurs in (ˆx, yˆ); denote this cost by Hˆ ti . An important observation is that any demand point (i, t) can only contribute to the opening of orders s ∈ R0 that include item i (either as regular or extra orders). We are now ready to show that, as in the case of the JRP, one can use the above charging scheme to pay for the cost of (ˆx, yˆ) in a way such that no demand point (i, t) is charged more than twice its budget ˆbti . The following are the analogous results to Lemma 4.1 and Corollaries 4.2 and 4.3: Lemma 5.1 Consider each demand point (i, t) and let r1 ∈ R0 be the latest order in R0 , regular or extra, towards which (i, t) contributes. Then, either r1 ∈/ [freeze(i, t),t] or it is the earliest order in R0 ∩ [freeze(i, t),t] with item i. Proof : Assume r1 ∈ [freeze(i, t),t] and consider again the following two possible cases: Case 1. The order of item i in period r1 is a regular order. In particular, we know that i ∈C(1,r1), and so item i was added to the order at s at the moment it was temporarily opened. Thus, (i, t) was frozen at open(r1) or perhaps earlier. This implies that open(r1) ≤ freeze(i, t). We also know that R0 ∩ [open(r1),r1)= ∅ (since we permanently opened r1) and that [freeze(i, t),r1) ⊆ [open(r1),r1). This concludes the proof of the lemma for this case. Case 2. The order of item i in period r1 is an extra order. We know that the extra order at r1 has some initiator (j∗ ,t ∗), where j∗ ∈S(i) is the initiator item. Consider Nj∗ (r1), the freezing order of (j∗ ,t ∗). In particular, we have already seen that r1 ≤ Nj∗ (r1) ≤ t. We claim that freeze(j∗ ,t ∗) ≤ freeze(i, t). Observe that (j∗ ,t ∗) was frozen when item j∗ was added to the order at Nj∗ (r1). However, since i ∈C(j∗ , Nj∗ (r1)), it follows that item i was added to the order at Nj∗ (r1) together with item j∗ . Thus, (i, t) was frozen together with (j∗ ,t ∗) or perhaps earlier, so indeed freeze(j∗ ,t ∗) ≤ freeze(i, t). By the construction of the algorithm, we know that there does not exist an order with item j∗ in R0 ∩ [freeze(j∗ ,t ∗),r1). Since the solution is nested (i.e., if we order item i, we must also order item j∗), there does not exist any order with item i in R0 ∩ [freeze(j∗ ,t ∗),r1). Since we have already concluded that [freeze(i, t),r1) ⊆ [freeze(j∗ ,t ∗),r1), we see that the lemma holds. Corollary 5.2 Each demand point (i, t) can contribute towards at most two orders in R0 . Proof : Suppose that (i, t) contributes towards more than one order in R0 , and let r1 >r2 be the two latest such orders. We will show that it can not be the case that r1 < freeze(i, t). The rest of the proof is identical to that of Corollary 4.2. Suppose that indeed r1 < freeze(i, t); in that case, the orders of item i at r1 and r2 must both be extra orders (since they do not lie in the active interval of (i, t)). Let j∗ ∈S(i) be the initiator item of the order at r2 and let Nj∗ (r2) be the freezing order of the initiator (j∗ ,t ∗). Clearly, Nj∗ (r2) ≤ t ∗ , but we must also have r1 < freeze(i, t) < Nj∗ (r2) (demand point (i, t) contributes towards the order of j∗ at Nj∗ (r2)). This implies that to show a contradiction it is suffcient to show that t ∗ 0. If the order of item i at r1 is an extra order, then (i, t) contributes Pj∈pathi,j∗ zˆNj ∗ (r1),t > 0, where j∗ ∈S(i) is the corresponding initiator item, and freeze(i, t) ≤ Nj∗ (r1) ≤ t. In either case, this is clearly bounded by ˆbti . If (i, t) contributes only towards a single order in R0 , then by Corollary 5.3, the holding cost it incurs is bounded by ˆbi we can pay for its holding cost and its contributions using at most t 2ˆbit. Now assume that (i, t) also contributes towards a second (earlier) order r2. By Lemma 5.1, the order of item i at r2 must be an extra order, such that r2 ∈/ [freeze(i, t),t]. If j0 ∈S(i) is the cor ij responding initiator item of this order, then (i, t) contributes Pj∈pathij0 zˆ > 0 towards r2, and Nj0 (r2),t freeze(i, t) ≤ Nj0 (r2) 1 to be a non-decreasing function of the ordering time. Finally, also in this case we are not able to show whether the analysis is tight. We end the discussion on the assembly problem by mentioning that under our general assumptions on the cost parameters, the variant of the assembly problem we consider is NP-Hard. This can be shown by a simple reduction from the JRP to the 2-stage assembly problem. Given an instance of the JRP, we rescale the demand and the holding cost parameters hi of the items (by inversely proportionate value) so that for st each period t (t =1, .., T ), there is a uniform demand Dt = dit . Each of the items is the predecessor of a common dummy item 0 with ordering cost equal to the joint ordering cost K0, demand Dt, and echelon holding cost equal to 0. This yields an instance of a 2-stage assembly problem, and since we can restrict to nested policies, it is equivalent to the original JRP instance. 6 Conclusions In this paper we have shown a general algorithmic framework of how to generate optimal and near-optimal solutions to a class of classical deterministic inventory models. Although the method is based on LP relaxations, our approximation algorithms do not require the LP’s to be solved. They are used only in the analysis of the algorithms. The algorithms are clearly polynomial- time but there is still work to do so as to get the most effcient implementations. We believe that it would be interesting to test the typical quality of the solutions that our algorithms generate on different inputs and compare them to other known heuristics. A very interesting theoretical open question is related to the approximability of the JRP. The problem is NP-hard but we know of no approximability hardness result and one can not even exclude the existence of a polynomial-time approximation scheme (i.e., one might be able to design a ρ−approximation algorithm for any ρ> 1). We mention again that for the assembly network problem with the traditional holding cost structure, it is not known whether it is NP-hard. Two more specifc open questions are related to the tightness of the analysis of the primal-dual algorithms and the LP relaxations considered in this paper. We have constructed [23] an example in which the integrality gap is 1.21. This implies that using the LP as the only lower bound, one can not hope to prove a performance guarantee better than 1.21. However, there still exists a signifcant gap between the upper bound of 2 and the lower bound of 1.21. Acknowledgments We thank Chaitanya Swamy for stimulating discussions and helpful suggestions. References [1] A. Archer. Inapproximability of the asymmetric facility location and k-median problems. Unpublished manuscript, 2000. [2] E. Arkin, D. Joneja, and R. Roundy. Computational complexity of uncapacitated multi-echelon production planning problems. Operations Research Letters, 8:61–66, 1989. [3] Y. Askoy and S. S. Erenguk. Multi-item inventory models with coordinated replenishment: a survey. International Journal of Operations and Production Management, 8:63–73, 1988. [4] I. B´ar´any, T. J. Van Roy, and L. A. Wolsey. Uncapacitated lot-sizing: the convex hull of solutions. Mathematical Programming Study, 22:32–43, 1984. [5] D. Bertsimas, C. Teo, and R. Vohra. On dependent randomized rounding algorithms. Operations Research Letters, 25:105–114, 1999. [6] M. R. Bussieck, A. Fink, and M. E. L¨ ubbecke. Yet another note on “An effcient zero-one formulation of the multilevel lot-sizing problem”. Technical report, Department of Mathematical Optimization, Braunschweig University of Technology, 1998. [7] J. Chuzhoy, S. Guha, S. Khanna, and J. Naor. Asymmetric k-center is log*n-hard to approximate. Electronic Colloquium on Computational Complexity (ECCC) (038), 2003. [8] W. B. Crowston and M. H. Wagner. Dynamic lot size models for multi-stage assembly systems. Management Science, 20:14–21, 1973. [9] A. Federgrun and M. Tzur. The joint replenishment problem with time-varying parameters: effcient, asymptotic and epsilon-optimal solutions. Operations Research, 42:1067–1087, 1994. [10] M. X. Goemans and D. P. Williamson. A general approximation technique for constrained forest problems. SIAM Journal on Computing, 24:296–317, 1995. [11] E. Halperin, G. Kortsarz, and R. Krauthgamer. Tight lower bounds for the asymmetric k-center problem. Electronic Colloquium on Computational Complexity (ECCC) 10(035), 2003. [12] A. V. Hoesel, A. Wagelmans, and A. Kolen. A dual algorithm for the economic lot-sizing problem. European Journal of Operations Research, 52:315–325, 1991. [13] K. Jain and V. V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. Journal of the ACM 48, pages 274–296, 2001. [14] D. Joneja. Multi-echelon and joint replenishment production and distribution systems with non stationary demand. Technical Report 731, School of OR&IE, Cornell University, 1987. [15] D. Joneja. Planning for joint replenishment and assembly systems with deterministic non-stationary demands. PhD thesis, School of OR&IE, Cornell University, Ithaca, NY, January 1989. [16] D. Joneja. The joint replenishment problem: new heuristics and worst case performance bounds. Operations Research, 38:723–771, 1990. [17] E. P. C. Kao. A multi product dynamic lot size model with individual and joint setup costs. Operations Research, 27:279–289, 1979. [18] J. Krarup and O. Bilde. Plant location, set covering and economic lot sizing: an O(mn) algorithm for structural problems. In Numerische Methoden Bei Optimierungsaufgaben, volume 3, pages 155–180, 1977. [19] R. Levi and R. O. Roundy. A note on Joneja’s joint replenishment problem approximation algorithm. In preparation. [20] P. Raghavan and M. R. Rao. The multi-item lot sizing problem with joint replenishment: a polyhedral approach. Technical Report SOR-91-8, Stern School, NY University, 1991. [21] P. Raghavan and M. R. Rao. Formulations to the multi-item lot sizing problem with joint replenishment. Technical Report SOR-92-19, Stern School, NY University, 1992. [22] R. O. Roundy. Effcient, effective lot-sizing for multi-product, multi-stage production systems. Operations Research, 41:371–386, 1993. [23] R. O. Roundy, R. Levi, and D. B. Shmoys. A lower bound on the integrality gap for a strong IP formulation for the joint replenishment problem. In preparation. [24] Z. J. Shen, D. Simchi-Levi, and C. P. Teo. Approximation algorithms for the single-warehouse multi- retailer problem with piecewise linear cost structures. url: citeseer.nj.nec.com/439759.html. [25] D. B. Shmoys, C. Swamy, and R. Levi. Facility location with service installation costs. In Proceedings of the 15th Annual SIAM-ACM Symposium on Discrete Algorithms, pages 1081–1090, 2004. [26] D. Simchi-Levi, 2002. Private communication. [27] A. F. Veinott. Minimum concave cost solutions of Leontief substitution models of multi-facility inventory systems. Operations Research, 17:262–291, 1969. [28] H. M. Wagner and T. M. Whitin. Dynamic version of the economic lot sizing model. Management Science, 5:89–96, 1958. [29] W. I. Zangwill. A deterministic multi-product, multi-facility production and inventory model. Operations Research, 14:486–507, 1966.