The Multi-Item Joint Replenishment Problem with Volume-Sensitive Transportation Costs and Container Constraints Nejib Ben-Kheder American Airlines Decision Technologies P.O. Box 619616 Dallas-Fort Worth Airport, TX 75261-9616 Candace A. Yano Department of Industrial & Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 August 1990

The Multi-Item Joint Replenishment Problem with Volume-Sensitive Transportation Costs and Container Constraints Abstract We address the problem of scheduling the delivery of multiple items from a single supplier to a manufacturer. The items are packaged into containers and the containers are shipped by truck. There is a fixed charge per truck shipment, and inventory holding costs are charged on end-of-period inventory. We seek to minimize the sum of transportation and inventory costs. The problem is a combination of a binpacking problem and a multi-item joint replenishment problem. We first investigate the single-item case, for which an optimal algorithm is constructed. Then we present a variety of heuristics which start with the solution from the problem in which container constraints are relaxed. On the basis of results for a variation of the singleitem problem, this initial solution is adapted to satisfy container constraints while considering the impact on transportaion costs. One of the heuristics is shown to perform consistently well in a series of computational tests. Keywords: Inventory —Multi-Item Transportation

1. Introduction We consider the problem of scheduling the delivery of multiple components (items) from a single supplier, over a finite horizon, to meet the requirements for each component at an assembly facility. Each component is loaded into a container of a specific type and size, and the containers are shipped by truck from the supplier to the assembler. The delivery schedule must specify the timing and contents of each shipment (number of trucks per delivery day, assignment of containers to trucks, and number of items in each container). The problem is solved in a just-in-time (JIT) context. The adoption of JIT principles in the purchasing process has led to supply networks with relatively few direct suppliers, each one delivering a range of items. This is especially evident in the U.S. automobile industry, which motivated our study. JIT also has resulted stin a change in the ordering cost structure. Order processing costs have been reduced through the use of long-term supply contracts and electronic ordering. Consequently, a volume-sensitive transportation cost has become the main component of the ordering cost. Because of these costs, however, U.S. manufacturers must address the question of how JIT should be implemented in dealing with their suppliers. Typically, a U.S. automobile assembly facility uses three different strategies for coordinating inbound freight. For low volume suppliers, there may be direct, less-thantruckload shipments. Alternatively, shipments from several suppliers may be consolidated by using "milk runs" in which a vehicle stops at several suppliers before arriving at the assembly facility. For medium-volume suppliers that produce components for several assembly facilities, it is common to arrange for full truckload shipments into a break-bulk facility. At this point, the components are sorted by destination and mixed truckload shipments of components are shipped to each assembly facility. For high-volume suppliers, direct shipments to the assembly facility are arranged. In all of these cases, it has become quite common to establish transportation contracts, normally with common carriers, to transport the freight. These contracts specify the origin and destination, the day of the week, and the time of delivery (or a time window) for each shipment. Because these contracts specify only truck movements, the contracted price is normally based on the distance and/or time for each trip, and not on the volume of freight in each truck. In this paper, we investigate the problem of finding delivery schedules for high-volume suppliers with direct shipments to the assembly facility. In many instances, the components from these suppliers, as a group, constitute a significant portion of both the physical volume and dollar value of the inbound freight. Moreover, much of the transportation cost is -1

attributable to these components. Examples of these components include engines, transmissions, stamped metal body parts, instrument panels, and tires. We seek to find a delivery schedule that achieves the best tradeoff between the cost of transportation, which exhibits economies of scale, and the cost of inventory. The solutions can be used to schedule deliveries in the short term. They also can be used to establish longer-term repeating delivery schedules and associated transportation contracts in companies with stable usage rates. Finally, they can be used to assess the benefits of using closer suppliers or different container sizes. In the next section, we present our assumptions and a formulation of the problem. 2. Problem Formulation Assumptions The model is based on the following assumptions: 1. Time is divided into discrete time periods of equal duration. For simplicity, we will assume a period is one day. 2. A finite horizon is considered, but the finite horizon schedule can repeat indefinitely. 3. The individual item demands are deterministic but may vary over time. Near-term demands generally exhibit this property in actual applications. 4. No backordering is allowed. The requirement for any period t must be on hand (at the assembly facility) by the beginning of period t. This assumption is a consequence of the high cost of rescheduling the assembly facility in response to component shortages, or the opportunity cost of a lost sale if the assembly facility is operating at capacity and the assembly line is idled because of the shortage. 5. The delivery lead times are deterministic and constant over time, and therefore, without loss of generality, equal to zero. Most common carriers are able to estimate these lead times quite accurately on the basis of experience. 6. There is no initial inventory and no inventory is left at the end of the final period. This permits us to repeat the schedule indefinitely. 7. The order quantities are itexpressed as an integer number of containers, but the containers may be partially loaded. 8. The containers fit into a truck as long as their total volume does not exceed a specified fraction of the truck volume. If the containers are standardized and designed to fit together well in the trailer, this assumption is realistic. Even if the containers are not standardized, -2

it is usually possible to estimate the effective capacity of a truck trailer. We also assume that the effective capacity of a truck trailer is known for any given supplier. We will refer to it as a truckload. The costs incurred are of two types: a. Inventory holding cost: A cost of Hj per unit (full container) of item j is charged on end-ofperiod inventory. Partially loaded containers are charged pro rata. b. Transportation cost: There is a fixed charge K for each truck shipped. There are no economies of scale from shipping more than one truck on any route on any given day. Any discounts attributable to the contract are considered to be subsumed in the contracted prices. These assumptions are consistent with the circumstances described earlier. Notation The input data for the model are: Djt: demand for item j in period t ( fraction of a container or number of containers) Hj: inventory holding cost per container of item j per period Vj: volume of item j container (fraction of a truckload) K: fixed charge per truck shipped T: planning horizon (number of periods) N: total number of items M: upper bound on the number of trucks used in one period The decision variables for the model are: Xjtm: number of item j containers delivered in period t by truck m Yjt: total number of item j containers delivered in period t Ijt: inventory of item j at the end of period t Fjt: fraction of item j container left empty in period t Note that in an optimal solution, at most one container of each item is partially empty in any shipment. If two (or more) containers are partially empty, it is possible to consolidate the same units into as few containers as possible, possibly reducing transportation costs. -3

A mathematical formulation The multi-item joint replenishment (MIJR) problem with volume-sensitive (VS) transportation cost and container (C) restrictions, MIJR-VSC, can be formulated as: T N T M N Min Z= I E HjIjt + I X K6[E Xjtm] (1) t=1 j= t=l m=l j=l subject to Ijt = Yjt - Fjt + Ijt- - Djt, t=1,.,T;j=1,..N; (2) Vj Xjtm < 1, t=1,..,T; m=1,..,M; (3) J=l M Xjtm = Yjt, t=,..,T;j=1,..N; (4) m=1 Fjt Min ( 1, Y), t=l,.,T; j=1,.N; (5) IjT = Ijo =, =..,N; (6) Yjt, Ijt, Fjt 20, t=l,.,T;j=1,..N; (7) Xjtm integer, t=1,.,T;j=1,..N; m=1,..,M; (8) t 1 ifu>0 where 5[u] = if u>O where 5[u]= [^ if> otherwise. The first term in the objective function is the linear inventory holding cost. The inventory of item j in period t, Ijt, is given by the inventory balance equation in (2). It is a function of the actual quantity of item j shipped in period t, i.e., Yjt - Fjt, not the number of containers. The second term in (1) is the transportation cost. It is proportional to the number of trucks shipped, which is a function of the total volume of containers delivered, regardless of whether these containers are full. Constraints (3) are the truck capacity constraints. Constraints (4) give the total number of containers delivered for each item in each period. Constraints (5) ensure that the empty portion of the container is less than 1, and is zero when that item is not delivered. Constraints (6) correspond to the assumption that the initial and final inventory are zero. Constraints (7) are the non-negativity constraints and ensure that no backlogging is allowed. Finally, constraints (8) restrict the number of containers to integer values. MIJR-VSC can be formulated as a mixed integer program (MIP) by rewriting the transportation cost in terms of 0-1 variables. Problems of realistic size would have thousands of integer variables and therefore would require exorbitant solution times if they were solved optimally by general MIP codes. We seek to find good solution procedures that take advantage of the special structure of the problem. -4

The complexity of MIJR-VSC stems from the fact that it contains features of both the multi-item joint replenishment (MIJR) problem and the bin-packing (BP) problem. Indeed, the problem can be approached as a lot-sizing problem, where we decide when and how much of each item to deliver in each period, and in which the computation of the ordering cost is itself an optimization problem, where we fit containers into trucks to minimize the number of trucks. Both subproblems are known to be difficult to solve optimally. The MIJR problem, with a fixed joint ordering cost andwith an individual ordering cost associated with each item is reported to be NP-complete by Joneja (1987). A special instance of our problem, where the unit inventory holding costs are equal to zero, can be stated as "Given N items of sizes V1,..,VN, where 0 < Vj < 1, 1 <j <N, what is the minimum number of unit size bins needed to pack Qj units of each item j, 1 < j < N?". In our problem, Qj represents the number of item j containers to be delivered over the planning horizon. This problem is equivalent to the one dimensional bin-packing problem, which is known to be NP-hard (Garey and Johnson 1979). These results imply that it is unlikely that any computationally efficient optimal algorithm can be developed. Our approach to MIJR-VSC is a combination of two heuristic procedures, both of which explicitly consider the volume-sensitive nature of the tranportation cost. We briefly describe the two approaches, and then explain how we combine them. One approach to solve this problem is to approximate the transportation cost by ignoring the integrality of the containers. The item demands as well as the order quantities are expressed as fractions of a truckload. The resulting problem can be viewed as a "continuous" version of the original problem. It differs from the traditional MIJR problems in the structure of the ordering cost, which here is volume-sensitive. Ben-Kheder and Yano (1989a) characterize the solution to this relaxed problem and develop an optimal algorithm as well as a simple heuristic to solve it. Once the solution to this problem is obtained, the container decisions are carefully rounded to provide a good solution to the original problem. An alternate approach is to solve a sequence of single-item lot-sizing problems, each with a modified transportation cost. At each stage, the lot sizes for one item are decided using a transportation cost function that recognizes the availability of "free" capacity if a truck is required by the items assigned earlier, but its capacity is not fully utilized. The critical decision in this heuristic is how to sequence the items. Our heuristic combines the two approaches. First, we relax the integrality constraint on the number of containers. The transportation cost can then be written as an explicit function of the order quantities. We use this approximation to determine the lot sizes (in truckloads), which may represent fractional numbers of containers. A portion of the delivery quantity is fixed by rounding the non-integral values down to the nearest integer. The remaining -5

demand is assigned by a sequential procedure, item by item, where the items are ranked according to some importance measure. At each step, we solve a single-item lot-sizing problem to determine when to deliver the unsatisfied demand. We consider the inventory cost and a modified transportation cost that takes into account the truck volume remaining after loading the lot sizes of the previously assigned items. The remainder of this paper is organized as follows. First, we discuss the single-item problem. We characterize the optimal solution and give an O(T3) algorithm to solve the problem optimally. Then, we discuss a generalization of these results to the case where the transportation cost function varies with time. A pseudopolynomial algorithm is presented. Next, we address the multi-item problem. We suggest a number of heuristics, and focus on the one outlined in our preliminary discussion. We conclude with results of a series of computational experiments that demonstrate both the efficiency and robustness of our heuristic and its ability to handle large problems on a routine basis. 3. The Single-Item Problem The single-item (SI) dynamic lot-sizing problem with volume-sensitive (VS) ordering cost (SIVS), was first introduced by Lippman (1969). In his model, the cost associated with each truck is a non-decreasing concave function of the amount delivered by that truck. He shows that such a function is subadditive on [O,+oo), i.e., c(u+v) < c(u) + c(v) for u,v > 0 where c is the cost function. He uses the subadditivity property to characterize the optimal solution to his problem. He proves that there is an optimal schedule X such that: 1. an integer number of full trucks is ordered in periods with positive initial inventory, and 2. the inventory held at the end of each period is less than a truckload. He exploits these results to develop a Wagner-Whitin type algorithm which is O(T3). All quantities in Lippman's model are expressed as a fraction of a truckload, which once converted to the actual number of items may result in fractional values. This discrepancy is corrected in our model, where we restrict the order quantities to be an integer number of containers and allow the containers to be partially loaded to account for the fact that the demand (and therefore shipment quantities) may not be an integer number of containers. In the remainder of this section, we will first show that the solution to the BP component of the problem is trivial in the single-item case, yielding a simpler formulation. We then extend Lippman's result to the single-item problem with container constraints and present an 0(T3) solution procedure. For simplicity, we suppress the item subscript in this section. -6

Problem Analysis Let Q be the unique integer such that QV < 1 < (Q+1)V, i.e., Q is the maximum number of containers that fit into a truck. Consider a solution (Yt) to the single-item problem, and let L = rYt/Ql, i.e., the minimum number of trucks needed to ship Yt containers in period t. Clearly, an optimal assignment of containers to trucks is to assign Q containers each to trucks 1 through L-1 and to assign the remaining containers to the Lth truck. As a result, the transportation cost in period t, TCt, can be expressed in terms of the total number of containers, Yt, and the maximum number of containers that fit into the truck, Q. Thus, TCt = K S (Xtm) = KF Xtm/Q] = KYt/Q. m=1 m=1 The truck index m can be omitted and consequently also constraints (4), as well as the truck capacity constraints (3). SIVS can be formulated as: Min H It + KrYt/Q (9) t=1 t=1 subject to Yt-Ft+ It - It=Dt, t=l,..,T; (10) Ft<Min 1, Yt}, t=l,.,T; (11) IT = Io = 0; (12) It, Ft >, t=l,..,T; (13) Yt integer, t=1,..,T. (14) For a given Q, the transportation cost remains unchanged for all container volumes V such that 1/(Q+1) < V < 1/Q. Therefore, we will assume without loss of generality that V=1/Q for some integer Q. Characterization of the optimal solution Theorem 1: Let Y be an optimal delivery schedule. Then It-1 Ft = 0, V t Proof: See Appendix. Theorem 1 states that in any period t, 1<t<T, either the containers are full, or the initial inventory is zero. This result is quite intuitive. If the containers are partially loaded then the order in period t can be increased with no additional ordering charge and an order in an earlier period can be decreased, reducing the cost of holding inventory in earlier periods. Theorem 2: Let Y be an optimal delivery schedule. Then It < Q, V t Proof: See Appendix. -7

Theorem 2 states that less than a truckload of inventory is held at the end of each period. This result is also intuitive. If a full truckload is not needed until period t+1, then by delaying its delivery from period t to period t+1, the inventory cost is decreased, while the transportation cost is unaltered. Theorem 3: Let Y be an optimal delivery schedule. Then It-i( Yt mod Q) = 0, V t Proof: See Appendix. Theorem 3 asserts that the shipment, if any, consists of one or more full trucks in each period with positive initial inventory. Based on the results of Theorems 1, 2, and 3, we have developed a DP procedure similar to Lippman's procedure for the "continuous" case. We solve a shortest path problem with T nodes and T2 arcs. An arc (u,v) links two consecutive regeneration points u and v (u<v). The computation of the arc cost, Cuv, is achieved by a backward inductive scheme based on properties of the optimal solution (see Ben-Kheder and Yano 1989b). The amount of work required to compute Cuv is shown to be O(T), so the procedure for the single-item problem is O(T3). Next, we investigate how to adapt the single-item solution to a good solution in a multi-item context. One possible approach to the multi-item problem, MIJR-VSC, is to ignore the interdependencies among items and solve the single-item problems independently. This approach, while computationally simple, can yield substantial cost penalties, since it does not consider the economies of jointly ordering the items. One possible improvement on this simplistic approach is to partially coordinate the decisions among the items by an appropriate modification of the costs. The interaction among items is reflected principally in the volume-sensitive transportation cost. Assume that the solution for a given set of items is known, and that we have assigned the containers to trucks in each time period by some binpacking rule. For a given period, t, there is a positive volume slack, Smt, for each partially loaded truck, m. Let j be the item to be scheduled next. Let Vj be the volume of an item j container. Also let Qjt~ = Smt /Vj, which represents the number of item j containers m=l that can be delivered in period t with no additional transportation charge. We adjust the transportation cost accordingly, i.e., te cost of tansporting Yti costsntainers of item j is set equal to K max ( 0, r(Yjt - Qjt~ )/Qjl where Qj = Ll/Nj J is the maximum number of item j containers that fit into a truck. The resulting transportation cost function is time varying. Theorem 2 and Theorem 3 do not hold in this case, so the algorithm discussed in Section 3 needs to be modified to handle time-varying costs, as described in the next section. -8

4. The Single-Item Problem with Time Varying Transportation Cost This problem is a variant of SIVS, where the transportation cost, Ct, is volume-sensitive as well as time-varying. We denote by QtO the number of containers free of charge (FOC) in period t. The single-item problem with volume- and time-sensitive transportation cost can be stated mathematically as: Min HIt + Ct[Yt (15) t=1 t=1 subject to (10) through (14) where Ct[Yt]= K Max { 0, R(Yt - Qto)/Q1 ) is the volume sensitive cost shown in Figure 3.1 Transportation cost 3K 2K K _shipment volume o Q+Q 2Q+Qt 3Q+Q (in containers) Qt t Figure 1: Modified transportation cost in period t We extend the results for SIVS to the problem with volume-sensitive, time-varying transportation costs, SIVTS (short for single-item, volume and time sensitive). Theorem 1 still holds for the same intuitive reasons. Theorem 2 must be altered because it might be more economical to group deliveries in periods with FOC transportation. Theorem 3 needs to be restated to account for the FOC volume in each period. Theorems 2 and 3 are modified below. Theorem 4: Let Y be an optimal delivery schedule. Then Yt >Qt~ ==> It < Q, V t. Proof: See Appendix. Theorem 4 states that if the delivery in period t exceeds the number of FOC containers then less-than-a truckload of inventory is held in period t. Theorem 5: Let Y be an optimal schedule. Then It-1 [(Yt-Qt 0) Mod Q] Yt = 0, V t Proof: See Appendix. -9

Theorem 5 asserts that if a delivery occurs in period t, then either the initial inventory is zero, or the delivery quantity is equal to the number of FOC containers, plus an integer number of full trucks. In the following corollary, the number of trucks in a period t, kt, is shown to be restricted for any regeneration interval. Corollary 5.1: Let (Yu+i,..,Yt-l) be a partial solution in the regeneration interval [u+1l,v]. Then there exists at most one positive integer value kt, for which Yt = Qt~+ ktQ > 0 and (Yu+l,..,Yt-l,Yt) is a partial solution. Proof: See Appendix. Corollary 5.1 restricts the number of possible solutions in each period, which is an important factor in reducing the complexity of our solution procedure. Solution procedure We use the same DP structure as for the basic single-item problem, but a more elaborate procedure is needed to compute the arc costs. Let u and v be two consecutive regeneration points, and Y be an optimal delivery schedule. Then the following properties hold: 1. By Theorem 1, Ft=0 for all except the first period in the regeneration interval and Fu+i = f = Fr Dt 1- Dt, which is the number of container units shipped in excess of the t=u+1 t=u+l number of container units required during the time interval [u+ 1,v]. All the containers are full, except possibly one container in period u+1, which has a fraction f of a container of unfilled space. 2. By Theorem 5, Yt, u+1 < t <v, is equal either to zero, or to Qt~+ktQ for some integer kt. 3. Let St and Rt be the total quantity shipped and required, respectively, over the time interval [u+l,t]. Assume Stli is known. Then by Corollary 5.1, if Yt > 0, there is a unique integer kt such that Yt = Qt~+ ktQ, i.e., Max ( 0, F(Rt - St-l - QtO)/Ql }, as derived in the proof of Corollary 5.1. This characterization of the optimal solution in a regeneration interval suggests the following DP procedure to compute Cuv Computation of Cuv The stage variables are the time periods u+l,..,v. At stage t, the state St is the total number of containers delivered from period u+1 up to and including period t. The quantities -10

Rt, u+1 < t < v, and f are as defined above. Then for an admissible state St, the end-of-period inventory, I(St), is equal to St - f- Rt. The DP recursion formula is given by: g(St) = H I(St) + Min ( g(St+l), g(St+1+Qt+li+ kt+lQ)+ kt+l K) for St e At (16) and g(Sv) = 0 for Sv E Av where At, u+1 <t<v, is the set of admissible states in period t. There are at most two admissible ways to reach a state St from stage t+1. Either no delivery occurs in period t+1, which is only feasible if St - f Rt+l, or we deliver Qt+10 containers plus kt+i full trucks, where kt+i = Max ( 0, F(Rt+l - (St - f) - Qt+1~)/Ql}. In determining g(St) in (16), we choose between these two delivery policies. A state St is admissible at stage t if: 1. it results in positive inventory at the end of period t, i.e., St - f> Rt, and 2. it is less than the maximum number of containers required during the time interval [u+l,v], Quv, which is equal to FRy 1. Observe that Av=(Quv), and that I At I < Quv for u <t<v. In the first period of the regeneration interval, a tighter upper bound on Su+1 can be obtained from Theorem 4. If Su+1 > Qu+10 then Iu+1 = Su+1 - f - Du+1 < Q (by Theorem 4), which implies that Su+1 < max (Qu+10, rQ+(f+Du+i)1}. Once g(Su+1 ) is computed for Su+1 in Au+i, Cuv is obtained from: Cuv = Min I g(Su+l ) + K k(Su+l ), Su+i e Au+1) (17) where k(Su+i) is the number of trucks needed to deliver the Su+1 containers in excess of the Qu+10 FOC containers, i.e., k(Su+l) = Max ( 0, F(Su+1 -Qu+l~)/Ql}. Computational complexity The value at each node in the shortest path network is determined by comparing the two costs, as stated in (16). Let L = Maxv>u (Quv), be an upper bound on the number of containers needed in a regeneration interval. Then the total number of nodes in the DP computation of Cuv is bounded by LT. Therefore, the computational effort required by our two DP procedures combined is O(LT3), which is polynomial if L is bounded above by a polynomial in T, but in general is exponential. The following results allow us to transform a given problem into an equivalent problem with a smaller value of L, which results in a reduction of the computation time. - 11

Theorem 7: Let Y be an optimal schedule. Then Yt > Min ( LDt J, Qt ~), V t. Proof: The proof is intuitive. Suppose Yt < LDt J < Qt0. Then It-1 > Dt - Yt > LDt I - Yt = E > 0. Thus, there is a feasible schedule in which an earlier shipment is reduced by E and Yt is increased by an equal quantity. The transportation cost is the same, and the inventory cost is is reduced by at least H~. Thus, Yt < LDt I < Qt~ cannot be optimal. Now suppose that Yt < Qt~ < LDt J. Then we can set E = Qt~ - Yt and the same argument above applies. Let P be a problem with demand D, and let (Qt~) be the set of FOC containers allowed. Let Yt = Min I LDt I, Qt~ ). Then the optimal solution to P can be obtained by solving a problem P', derived from P by: (i) reducing Dt to Dt= Dt - Yt, and (ii) reducing Qt~ to Qt~=Qt0 -Yt. Let Y' be the solution to problem P'. Then the solution to problem P is obtained by summing Y't and Yt in each period. Observe that in P', in each period, either the reduced demand is less than a container, or the reduced FOC volume is zero. This will considerably reduce the amount of computation. Note that if the demand is less than a container in each period, then the amount of computation is O(T4). Also, if the FOC volume is zero in each period, then the problem reduces to the basic single-item problem, SIVS, for which we have devised an O(T3) solution procedure. A heuristic solution to the multi-item problem can be developed on the basis of the singleitem analysis. The problem is decomposed into single-item problems which are solved sequentially. One of the most important factors in a procedure of this type is the sequencing rule. Two logical ways of ranking the items are by inventory cost (per unit of truck volume), or by container volume. The first measure is important in a lot-sizing context, and the second is critical in a bin-packing context. From preliminary experimental results, it is not clear which ranking rule is better. As we will see later, this myopic approach is outperformed by a heuristic that considers all items simultaneously. This multi-item heuristic is described in the next section. 5. A Multi-Item Heuristic Any optimal procedure to the multi-item problem must simultaneously consider lot-sizing and bin-packing decisions. We present a heuristic procedure, where we make initial lotsizing decisions, which are then adjusted, taking into account container sizes and truck capacity considerations. This heuristic will be referred to as the bin-packing/lot-sizing (BINLOT) heuristic. The heuristic features three main modules: - 12

1. Lot-sizing based on an approximation of the transporation costs and a relaxation of the container constraints. 2. Bin-packing. 3. Adjustment of the lot-sizes from those in the relaxed problem. We now discuss these modules, and the flow of information among them, in more detail. Lot-sizing: MIJR-VSC is a multi-item dynamic lot-sizing problem that is complicated by the structure of the ordering cost. In the MIJR literature, the ordering cost structure is usually assumed to be very simple. Most authors assume that the ordering cost, A, is equal to A=AO + A aj, where AO is a fixed cost associated with an order and aj is the cost associated with J ordering item j. Literature based on this cost assumption is surveyed by Aksoy and Erenguc (1988). In our problem, the joint-ordering cost, i.e., the volume-sensitive transportation cost, cannot be computed explicitly. Its value is obtained by solving a bin-packing subproblem in each period: given the decision to order Yjt containers of item j, l<j<N, in some period t, l<t<T, the transportation cost, TCt, is computed as: M N TCt=MinK 6[ X Xjtm] (18) m=l j=l subject to Vj Xjtm <1 m=,..,M (19) J=l M I Xjtm = Yjt j= 1,..N (20) m=l Xjtm integer j=1,..N; m=l,..,M (21) This is a one dimensional bin-packing problem, which is known to be NP-hard. Therefore, we need to approximate TCt. We disregard the integrality of the containers and implicitly assume that no space is wasted because of partially loaded containers. We express all the data and decision variables related to the items in terms of truckloads. Let Yjt' be the delivery quantity of item j, l<j<N, in period t, l<t<T. Then the number of trucks used in N period t, is given by IFYjt'l. The truck capacity constraint (19) and the truck index m can j=1 now be eliminated from the model. The relaxed problem, (MIJR-VS), is formulated as: - 13

T N T N Minimize E Hj'Ijt'+ Kr Yjt'1 (22) t=1 j=1 t=1 j=1 subject to Ijt' =Ij +Yjt' - Djt (23) IjT' = Ij' = 0 (24) Ijt, Yjt'> 0 (25) where Hj' = Hj / Vj is the inventory holding cost per truckload of item j, Djt'= DjtVj is the demand for item j in period t expressed in truckloads, Yjt' is the delivery quantity for item j in period t (in truckloads), and Ijt' is the inventory for item j held in period t (in truckloads). Note that MIJR-VS is not the linear programming relaxation of MIJR-VSC because the integrality of trucks is still maintained. It can be formulated as a mixed integer program by rewriting the transportation cost in terms of T integer variables representing the number of trucks used in each period. Ben-Kheder and Yano (BY) (1989a) characterize the optimal solution for this problem. They show, among other results, that at most one item has both a positive initial inventory and a positive delivery quantity in any given period. Furthermore, they show that if such an item exists then the total shipment size in that period is an integer number of full trucks. They develop a mixed branch and bound-dynamic programming procedure to solve t the problem optimally. As a substitute, they suggest an O(NT3) heuristic based on the restriction of holding less than a truckload of inventory in each period. Both the optimal algorithm and the heuristic are shown to be computationally reasonable for very large problems. Their computational results indicate that the heuristic performs very well. Our heuristic procedure consists of three main steps. In the first step, we use the BY algorithm (either optimal or heuristic) to find the solution to our relaxed problem, MIJR-VS. The delivery schedule, Y, is converted to container units by letting Yjt = Yjt/Vj, which in general is not integer. At this point, a feasible solution to the original problem could be obtained by rounding up to the next container. This, however, may result in substantial transportation cost penalties. Consequently, we defer the decision to round down or round up, as well as the decision of whether to ship full or partially loaded containers, to Step 3 of the heuristic. In Step 2, we consider the delivery of LYjt'/VjJ (= Yjt~) full containers which partially satisfies the demand, and assign these containers to trucks so as to minimize the number of trucks operated in each period. In Step 3, the remaining demands are considered, and the heuristic considers opportunities for container consolidation, as well as opportunities to fill the remaining capacity of partially loaded trucks at no additional transportation cost. - 14

Bin-packing The bin-packing problem is one of the most well-studied problems in the field of Operations Research. Extensive surveys of results for this problem appear in Garey and Johnson (1981) and in Coffman et al. (1984). Empirical studies (e.g., Hall et al. 1986) indicate that several heuristics routinely provide solutions which are very close to optimal for many instances of the problem. Worst case analysis of several heuristics has been conducted by Johnson et al. (1974), Coffman et al. (1978) and Yao (1980). The most popular heuristic, namely the first-fit decreasing heuristic (FFD), has been shown to use at most 22.2% more bins than required by the optimal solution. This bound is reduced to 15% in the case where the volume of each item does not exceed 1/4 of the bin volume. Empirical studies indicate that the error ratio for the heuristic is less than 2% on the average. In the FFD heuristic, the items are arranged in decreasing order of size. The algorithm sequentially assigns the items to the lowest-indexed bin into which the item fits, starting a new bin only when necessary. We suggest the following algorithm which is based on FFD. Let Yjt~ be the number of item j containers in period t, as determined by the lot-sizing step. Define Em as the unfilled portion of truck m, and Mas the total number of trucks used. Step 0. Rank the items in decreasing order of their unit container volumes. Assume the items are indexed in that order. t < — 1 Step 1. (la) j < — 1,M < — 1, EM < — 1. (lb) Y < — Yjt~ Load non-empty trucks: For m:=1 to M do Q:= LEm/Vj I (# of item j containers that will fit into truck m) q:=Min (Q,Y) (# of item j containers to be assigned to truck m) Y< —Y- q Em < — Em- q Vj Load empty trucks: While (Y > 0) do M < — M+1 Q:= L1/Vj J (maximum # of item j containers that fit into truck m) q:=Min (Q,Y) (# of item j containers to be assigned to truck m) Y< — Y- q EM < — 1 - q Vj -15

(lc) j< —j+l if j < N then go to Step lb else go to Step 2. Step 2. t< —t+l if t < T, go to step 1 else terminate. The most complex part of the algorithm is sorting the items which is O(NlogN). Adjustment of lot-sizes In step 1, the delivery quantities in the solution to the relaxed problem, MIJR-VS, were rounded down in order to obtain integer container units. Therefore, only a portion of the demand is satisfied by this solution. These quantities need to be properly adjusted to satisfy the total demand requirements. Let Ijt0 be the inventory, if any, resulting from the delivery of Yjt~ full containers in period t, i.e., Ijt~ = max (0, Ijt- +Yjt~ - Djt). Then the demand remaining to be satisfied in period t is given by djt = Max (0, Djt- (Ijt 1~+Yjto) ). (26) The multi-item problem with these reduced demands is then solved by a variation of the heuristic for the single-item problem presented in Sections 3 and 4, as described below. Since inventory costs are an important factor in this problem, it would be logical to try to ship the expensive items as they are needed. For this reason, we rank the items in decreasing order of their inventory holding costs per truckload (Hj/Vj), and henceforth assume that the items are indexed accordingly. The incremental delivery quantities, Yjt1, are determined by the following procedure: Step 0. j < — 1 Mt < — total # of trucks used for loading Ylt~,...,YNt~, <t<T. Emt < — capacity slack of truck m in period t Step 1. (la) Determine the number of free of charge containers and the remaining demand: Mt Qjt~:= LEmt/Vj J, 1<t<T. m=l djt defined by (26), 1<t<T. (lb) Solve the single-item problem SIVTS(j,djt,Qjt~). Let Yjtl,Fjtl be the solution obtained. -16

(Ic) Update Mt, 1t<T. Update Emt, 1<m<Mt, 1<t<T. Step 2. Update the delivery quantities: Yjt:=Yjt~+ Yjt1 (number of containers ), 1t<T. Fjt:=Fjt1 (fraction of item j container left empty), 1<t<T. j < —j+1 If j < N then go to Step 1 else terminate. We can easily show that the total reduced demand for a given item, djt, does not t=1 exceed T containers. Therefore the computational effort needed to solve each single item problem is O(T4), as discussed in section 4. The total effort needed for this procedure is O(NT4), plus O(NlogN) for ranking the items. The BINLOT heuristic Let us summarize the steps of the heuristic suggested in this section: Step 1. Lot-sizing (la) Express the data in truckloads and reformulate the problem as MIJR-VS. (lb) Solve the problem obtained by the BY algorithm (Ic) Let Yjt' be the solution to MIJR-VS, expressed in truckloads. A portion, Yjt~ (= LYjt'/VjJ), of the total delivery quantity is fixed at this step. Step2. Bin-packing (2a) Rank the items in decreasing order of their container volumes (2b) For each period t, use a FFD rule to load the Yjt~ containers in an attempt to minimize the number of trucks. (2c) Determine the capacity slack for each partially loaded truck. Step 3. Lot-size adjustment (3a) Rank the items in decreasing order of inventory cost per truckload. (3b) For each item, starting with the highest ranked item - Compute the remaining demand to be satisfied, djt. - Compute the number of FOC containers, Qjt~. - Solve the single-item problem optimally by the DP algorithm in section 4. Let Yjt1, Fjt1be the solution obtained. (3c) Update the delivery quantities: Yjt:= Yjtl+Yjt~ Fjt:=Fjtl. Terminate. -17

The solution procedure is composed of several heuristics, one for each subproblem. Each of these heuristics can be altered without affecting the others. For example, the FFD rule in step 2 can be replaced by another one- dimensional BP heuristic without modifying steps 1 or 3. Similarly, if the containers do not fit well together, or if both volume and weight are constraining, the FFD heuristic can be replaced by an n-dimensional BP heuristic. The ranking rules in steps 1 and 3 also can be modified. Several variants of the basic heuristic can be developed by modifying the solution procedure at one or more steps, while keeping the same decision framework: lot-sizing, bin-packing and adjustment of lot-sizes. We investigate a group of heuristics based on this decomposition concept. The heuristics differ one from one another in the importance of the relaxed problem solution (Step 1) in determining the final solution. The two extreme cases can be described as follows: 1. Round up the lot sizes obtained at Step 1 to the next container, but ship only the given lot sizes. The solution obtained is feasible to the original problem. Assign these containers to trucks as in Step 2. All the demand is satisfied, therefore there is no need to perform Step 3. This heuristic is referred to as BINLOT - oo. 2. Solve a sequence of single-item problems with modified transportation costs. The lotsizing and bin-packing decisions for the entire demand are made at step 3. Steps 1 and 2 are disregarded. We refer to this heuristic as BINLOT-O, or alternatively as SEQLOT. Several other variants of BINLOT lie between these two extreme cases. We let BINLOTk, 0 < k <1, denote the version of BINLOT with the following change: the delivery quantities decided at Step 1 correspond to a fraction k of the lot sizes obtained from the relaxed problem, that is, Yjt~= L kYjt'VjJ. Notice that for k= 1, we obtain the basic heuristic BINLOT, and for k=0, we obtain SEQLOT. Additionally, we consider two variants of SEQLOT: SEQLOT/VOL, where the item ranking is based on the container volumes, and SEQLOT/INV, where the ranking is based on the inventory cost per truck. In our computational experiments, these heuristics are compared to one another and to a lower bound. A lower bound is provided, with no additional effort, by the solution to the relaxed problem in Step 1. Another way to test the effectiveness of these heuristics is to compare them to simpler rule-of-thumb heuristics. We consider two simple rules: JIT delivery: No inventory is held. We ship exactly the quantity required in each period. This rule is just-in-time in its classical definition. - 18

Adjusted JIT (AJIT) delivery: In each period, we ship the demand for the period, minus the inventory remaining from deliveries in earlier periods (if any), all rounded up to the next container. The remaining empty space in the trucks is filled up with the least expensive items whose demand is not yet satisfied. The containers are full in all periods, except possibly in the last period of delivery. Clearly, the first rule will perform well when the inventory holding costs are very high and the transportation cost insignificant. On the other hand, the second heuristic emphasizes filling both the containers and the trucks, and therefore is expected to perform well when the transportation costs are high in comparison to the inventory costs. Next, we empirically investigate the effectiveness of the heuristics. First, we will show that, when the solution is not trivial, i.e., when there is a tradeoff between inventory costs and transportation costs, BINLOT outperforms the rule-of-thumb heuristics. In another test, we show that for many instances of the problem, BINLOT gives better solutions than its variants, BINLOT-k. We also comment on the deviation of BINLOT from optimality. 6. Computational Experience We perform a series of experiments to test the effectiveness of the different heuristics discussed in the previous section. CPU times are all given for a workstation with an 80386 processor running at 16 MHz, excluding the input and output operations. The computer codes are written in Turbo Pascal version 5.0. Experimental setting: We consider three control variables: the average number of trucks per period, TR, the maximum container volume, Vmax, and the transportation to inventory cost parameter, a, which is explained later. First, we generate the container volume (fraction of a truckload), Vj, from U[0.01,Vmax]. The demand matrix is then obtained by the following scheme: for item j, the average demand in truckloads in a given period is generated from the uniform distribution U[0,2TR/N], then divided by Vj to convert it to container units. Let |tj, be the average demand obtained. The demand in period t, Djt, is generated from U[1,2ptj]. The inventory holding cost of item j, Hj, is obtained from the inventory cost of item j+1, Hj+i, by the recurrence relation Hj = Hj+(l1+incr), where HN is set at an arbitrary value and incr - U[0,incrmax]. The value of incrmax is given by the equality (1+incrmax)N = P, which implies that the inventory cost of item 1 is at most P times the inventory cost of item - 19

N. The geometric progression of the inventory costs reflects the fact that in most situations, there are many nexpensive items and a relatively few expensive items. We set P = 10. Once the demands and the inventory costs are generated, the transportation cost per INV T truck, TC, is obtained from the following formula: TC = a NTR' where INV = j Hj Djh h=l j=l T N is the cost of holding the total demand in inventory for one period and NTR = r[ E Djh h=l j=l is a lower bound on the number of trucks shipped. Consequently a is a measure of the importance of the transportation cost relative to the inventory cost (at an aggregate level). It has a direct effect on the best number of regeneration points in the planning horizon, and is analogous to the time between orders (TBO) factor commonly used in computational experiments related to lot-sizing problems. Experiment 1. Comparison of BINLOT to Other Heuristics (la) BINLOT vs. Rule of Thumb Heuristics: We compare BINLOT to JIT and AJIT. We set the control variables as follows: N = 20, T= 12, Vmax = 5% of a truck, and TR=1 truck per period. For various values of a between 0.1 and 4, we randomly generate ten problems. Table 7.1 shows the average deviation of JIT and AJIT solutions from the solution obtained by BINLOT. Figure 7.1 indicates the number of times each heuristic is the best. a ratio JIT Heuristic AJIT Heuristic [0.1,0.5] 5.4 % 59.3 % [0.5,1] 19.5 % 32.3 % [1,1.5] 17.6 % 21.5 % [1.5,2] 25.9 % 16.1% [2,2.5] 23.3 % 10.3 % [2.5,3] 30.8 % 7.7 % [3,3.5] 28.5 % 2.8 % [3.5,4] 32.0 % 3.5 % Table 7.1: Average deviation of the cost of JIT and AJIT solutions from that of BINLOT -20

3.5 -4 3 - 3.5 0 2.5-3 ct 2 -2.5 9Q5 1.5-2 E- 1 - 1.5 0.5 - 1 0.1 - 0.5 H BINLOT B JIT g AJIT 0 2 4 6 8 10 Best Heuristic Figure 7.1: Best heuristic for different values of the Transportation to inventory cost ratio The results indicate that BINLOT outperforms these rule of thumb heuristics when there is a trade-off between inventory costs and transportation costs. However, in the extreme cases, the simpler heuristics sometimes prevail. Since JIT and AJIT require little computational effort, we can use them along with BINLOT to find a good solution to the problem for any value of a. We note that in most of the cases where BINLOT is not the best heuristic, a variant of BINLOT gives a solution close to the best solution obtained by the rule of thumb heuristics. For example, when the inventory costs are very high, BINLOT-oo gives the same solution as JIT. (Ib) BINLOT vs. BINLOT-k: We compare BINLOT to its variants, SEQLOT and BINLOT-k (O < k <1), both in terms of computation time and solution quality. We consider two versions of SEQLOT, one based on a ranking of the items according to the inventory holding costs, and a second one where the items are ranked by container volumes. We set the control variables as follows: N = 20, T = 12, Vmax - U[2,10], TR=1, and a -U[0.5,3], and randomly generate 50 test problems. Results are summarized in Table 7.2. The myopic SEQLOT heuristics are significantly outperformed by BINLOT, which considers the items simultaneously. BINLOT-oo is, on the average, about 30% worse than BINLOT. We note, however, that in some special settings where the inventory costs are very high, BINLOT-oo gives a better solution than BINLOT. In these cases the solutions were similar to the ones obtained by the JIT heuristic. A comparison of BINLOT with BINLOT-k (k=0.5, 0.25, 0) indicates that BINLOT provides the best solution in 78% of the cases. As k decreases, the chances of getting the best solution by BINLOT-k also decreases. In some -21

marginal cases, BINLOT-k is better than BINLOT, but even here, BINLOT is at most 6% worse than the best heuristic. % of time best Average Deviation Heuristic heuristic from BINLOT CPU times (secs.) Below Above Mean Std. Dev BINLOT 78 % - 12.7 2.10 BINLOT-oo __ - 27.7 % 1.1 0.05 BINLOT-0.50 18 % 3.3 % 9.5 % 23.2 8.90 BINLOT-0.25 4 % 5.0 % 10.7 % 25.3 11.40 SEQLOT -INV - 36.5 % 64.9 39.40 SEQLOT-VOL ___ 37.5 % 63.6 40.80 Table 7.2: Comparison of BINLOT to its variants Computation times also favor BINLOT. Except for BINLOT-oo, BINLOT is 2 to 5 times faster than its variants. Also, the computational times for BINLOT are more predictable. Step 3 consumes most of the computation time. The amount of computation required is O(NLT3), where L is an upper bound on the delivery quantities remaining to be scheduled in Step 3. Except for BINLOT, where L is known to be bounded by T, the computational effort needed for the variants of BINLOT depends on L, and is not polynomial. This explains the high variability of the CPU times. Experiment 2: Computation Times We report the computation time of the basic heuristic BINLOT, not including the input/output and ranking operations. As explained in section 5, the amount of computation needed by BINLOT is O(NT3) for step 1 (if a heuristic is used to solve the relaxed problem), O(NlogN) for step 2, and O(NT4) for step 3. Therefore the total computational effort is expected to grow linearly with the number of items and polynomially with the number of periods. The number of items is set to 5, 25 and 50 and the number of periods is set to 6, 9 and 12. The other control variables take the following values: Vmax = 5% of a truck, TR=1 truck per period, and a-U[0.5,4]. For each (T,N) combination we randomly generate ten problems. Summary statistics appear in Table 7.3. The heuristic remains computationally tractable for very large problems. The computation time for a problem with 50 items and 12 periods does not exceed 40 seconds. -22

Such a problem, if solved as a MIP, has more than 600 integer variables. In a few tests, we found that general IP software with bounds obtained from linear programming relaxations requires hours of computation time and generates thousands of nodes in a Branch-andBound tree to find a solution close to the heuristic solution. CPU times N T Mean I Std. Dev. 6 0.56 0.09 5 9 1.76 0.32 12 4.41 0.82 6 2.49 0.16 25 9 6.73 0.66 12 15.41 1.73 6 5.24 0.29 50 9 13.32 0.91 ___1__12 31.19 4.11 Table 7.3: Computation times as a function of N and T Experiment 3: Effect of Different Factors on the Lower Bound Gap A lower bound on the optimal solution is obtained in step 1 of the heuristic, where we relax the container constraints. We investigate the effect of both the container sizes and the demand level on the deviation of the cost of the solution from BINLOT from the lower bound solution. Effect of Vmax: We set Vmax to 2, 5 and 15 %. For each value of Vmax, we randomly generate 10 problems. The control variables are set as follows: N = 20, T = 12, xa=l, and TR= 3 trucks per period. Effect of the Demand Level: we set the average number of trucks, TR, to 1, 5 and 10 trucks per period. For each value of TR, we generate ten problems. The control variables are set as follows: N=20, T=12, a=1, and Vmax = 5% of a truck. Before discussing the computational results, let us first comment on the values of the control variables. We set the average (total) demand in experiments 1 and 2 to one truck per period. Note that any reasonable strategy is expected to have one or two trucks more than the minimum possible number. This might be insignificant for suppliers with large delivery quantities, say 3 or 4 trucks per period, but is certainly important for a supplier with smaller demands. The maximum size of a container rarely exceeds 10% of a truckload in practice. - 23

The number of periods and the number of items are set to 12 and 20, respectively. The heuristic can handle larger problems as well. Preliminary experiments showed that provided the problem is of a realistic size (more than 5 items and 6 periods), the quality of the heuristic solution is not influenced by the problem size. It is virtually impossible to solve problems of realistic size to optimality using a general IP code. A problem with N items, T periods and an upper bound on the number of trucks, M, has NHM integer variables, HM 0-1 variables, and more than (2N+M)H constraints. Therefore, we will compare the cost obtained by BINLOT, not to the optimal objective value, but to the lower bound obtained by relaxing the container constraints. Unfortunately, such a bound is not a good indication of how far BINLOT is from the optimal solution. It is similar to a bound obtained for a bin packing problem by solving its continuous version. This similarity is confirmed in the following experimental tests. Table 7.4 reports deviations from the lower bound, as a function of the container volume and the demand level. Deviation from Lower Bound Average Std. Dev. Average Number of Trucks per Period 1 22.87 % 5.65 % 5 6.00 % 1.40 % 10 3.02 % 0.83 % 15 2.65 % 0.69 % Maximum Container Volume (% of a truck) 2 3.93 % 2.26 % 5 9.30 % 2.65 % 15 22.14 % 2.04 % Table 7.4: Deviation of BINLOT from the lower bound The deviation drastically increases as the maximum container volume increases. A major part of the increase is the "integrality" gap between the integer solution and the "continuous" solution. The standard deviation, however, remains of the same magnitude, which suggests that the performance of the heuristic is consistent. Note that in realistic applications Vmax would not exceed 5 to 10%. The lower bound becomes tighter as the demand (in number of trucks) increases. In a BP problem, the number of bins in the continuous solution is usually one bin less than the optimal number of bins in the integer solution, especially if all the bins are full in the - 24

continuous solution. A similar phenomenon seems to hold in our context. The relaxed solution has full trucks in all the non-regeneration periods. Thus, wer might expect the gap to be approximately one truck per non-regeneration period. We observed that the difference in the number of trucks between the relaxed and heuristic solutions was 1 to 2 trucks for a 5 period problem and 3 to 4 trucks for a 12 period problem. Thus, the solutions from the heuristic are probably very close to the optimal solutions. It is difficult, unfortunately, to find good bounds for such problems. 8. Conclusions In this paper, we addressed a multi-item dynamic lot-sizing problem, in which some logistical aspects were considered. The transportation cost is assumed to be proportional to the number of trucks operated in each period. The items are packed into containers, which then are loaded onto the trucks. As a result, the lot-sizing problem is complicated by binpacking considerations. The problem is NP-hard and is difficult to solve optimally. We present a heuristic based on a solution to a relaxation in which the container constraints are ignored. Experimental results show that the solution to the "continuous" version of the problem results in a good solution to the original problem, if it is intelligently converted into container units. Among the decisions involved in the conversion scheme is when to ship partially loaded containers. These decisions are made sequentially, item by item, by solving a single-item version of the problem where only a portion of the demand is considered and where the transportation cost is appropriately modified to account for uncommitted space in the trucks. This modified single-item problem is analyzed and an optimal algorithm for it is presented. The computational results show that our heuristic performs well especially when there is an opportunity to trade off transportation and inventory costs. Our heuristic was compared to some of its variants, as well as rule of thumb heuristics. However, we have not been able to compare it to the optimal solution. A problem of realistic size would have hundreds of integer variables, and therefore cannot be solved in reasonable time by any existing general MIP software. Also the problem is highly integral, and therefore it is difficult to find any good lower bounds. Nevertheless, the results suggest that the heuristic is able to find very good solutions in a short period of time. ACKNOWLEDGEMENTS The authors are grateful for financial support for this work from a U.S. automobile manufacturer through a research contract to the University of Michigan. -25

REFERENCES Aksoy, Y. and Erenguk, S. (1988), "Multi-Item Inventory Models with Coordinated Replenishments: A Survey," Operations and Production Management 8, pp. 63-71. Ben-Kheder, N. and Yano, C.A. (1989a), "The Multi-Item Joint Replenishment Problem with Volume-Sensitive Transportation Costs," Technical Report 89-19, Department of Industrial & Operations Engineering, The University of Michigan, Ann Arbor, MI. Ben-Kheder, N. and Yano, C.A. (1989b), "The Multi-Item Joint Replenishment Problem with Volume-Sensitive Transportation Costs and Container Constraints," Technical Report 89-29, Department of Industrial & Operations Engineering, The University of Michigan, Ann Arbor, MI. Coffman, E.G., Jr., Leung, J.Y. and Ting, D.W. (1978), "Bin Packing: Maximizing the Number of Pieces Packed," Acta Informatica 9, pp. 263-271. ----------—, Garey, M.R. and Johnson, D.S. (1984), "Approximation Algorithms for Bin Packing - An Updated Survey," from Algorithm Design Computer System Design, editor Ausiello, G. et al., Springer, pp. 49-106. Garey, M.R. and Johnson, D.S. (1979), "Computers and Intractability: A Guide to the Theory of NP-Completeness," Freeman, W.H. and Co., San Fransisco. --------------------------------------- (1981), "Approximation Algorithms for Bin Packing: A Survey," from the Design and Analysis of Algorithms in Combinatorial Optimization, editor Ausiello, G. and Lucertini, M., Springer. Hall, N., Ghosh, S., Kankey, R.D., Narasimhan, S. and Rhee, W.T. (1986), "Bin Packing Problems in One Dimension: Heuristic Solutions and Confidence Intervals," Computers and Operations Research, to appear. Johnson, D.S., Demers, A., Ullman, J,D., Garey, M.R. and Graham, R.L. (1974), "Worst Case Performance Bounds for Simple One-Dimensional Bin Packing Algorithms," SIAM J. Comput. 3, pp. 299-325. Joneja, D. (1988), "The Joint Replenishment Problem: New Heuristics and Worst Case Performance Bound, "Technical Report 765, School of O.R and I,E, Cornell University, Ithaca, NY. Lippman, S.A. (1969), "Optimal Inventory Policy with Multiple Setup Costs," Management Science 16, pp. 118-138. Yao, A.C. (1980), "New Algorithms for Bin Packing," J. Assoc. Comput. Mach.27, pp. 207-227. -26

Appendix Theorems and proofs Theorem 1: Let Y be an optimal solution to SIVS. Then It-i Ft = 0, V t. Proof: Let Y be an optimal schedule to SIVS, and suppose there exists a period t for which we have FtItl- > 0. Let u be the most recent period before t with a positive delivery quantity. Let e = Min (It-i, Ft, 1-F ) (>0). We define the schedule Y' to be the same as schedule Y, except in periods u and t, where: Ft'= Ft-~,. fFu+e if Fu+ <1 u O otherwise; Yu if Fu+e <1 Yu = YU-1 otherwise. We can easily verify the feasibility of Y'. Next we show that schedule Y' has a lower cost than schedule Y. Let us first consider the transportation cost. The shipment sizes in Y and Y' are identical in all periods, except in period u where the shipment size in Y' may be decreased by one container. Therefore the transportation cost of schedule Y' is less than or equal to the transportation cost of Y. The inventory, however, is decreased by at least He (> 0). Thus, a solution with FtIt-1 > 0 cannot be optimal. Theorem 2: Let Y be an optimal schedule to SIVS. Then It < Q, V t. Proof: Let Y be an optimal schedule and suppose there exists a period t for which It > Q, i.e., more than a truckload of inventory is held. Let u be the most recent period before t +1 with a positive delivery quantity. Let m=Min (Yu, Q ) ( > 0 and integer). We define the schedule Y' to be the same as schedule Y, except in periods u and t+1, where Yu = Yu - m, and Yt+l=Yt+l+m. We can easily verify the feasibility of Y'. Next we show that schedule Y' has a lower cost than schedule Y. The inventory level decreases by m units in periods u,..,t, resulting in a positive decrease in inventory costs. The only changes in the delivery quantities occur in -27

period u and t+1. The transportation cost of schedule Y' is no greater than the transportation cost of schedule Y, since: (i) if m=Yu(<Q), then the total number of trucks shipped in period u and t is equal to F(Yu+Yt+i)/Ql, which is less than [Yt+i/Ql + 1, and therefore is less than rYt+i/Ql + FYu/Q], which is the total number of trucks shipped in period u and t+1 in schedule Y, and (ii) if m=Q, then the total number of trucks shipped in period t+1 increases by one, while the number of trucks shipped in period u decreases by one, which implies that the transportation cost is the same for both schedules. We therefore conclude that Y is better than Y, which contradicts the optimality of Y. Theorem 3: Let Y be an optimal schedule to SIVS. Then It-1 (Yt Mod Q) = 0, V t. Proof: Let Y be an optimal schedule and suppose that there exists a period u > 1, for which It-i > 0 and (k-l)Q < Yt < kQ for some integer k. Let u be that most recent period before t with a positive delivery quantity. Let e=Min ( 1-FU, It-i) (>0). We define the schedule Y to be that same as schedule Y, except in periods u and t, where: Yt=Yt+,F't = 1-e, Fu Fu+E if Fu+e <1 Fu= to otherwise,and fYu if Fu+ <1 Yu Yu-1 otherwise. In Y', the delivery of E units is delayed from period u to period t, since they are not needed before then. We can easily verify the feasibility of Y. Next we show that schedule Y' has a lower cost than schedule Y. The inventory cost is decreased by at least H E (> 0). The only changes in the transportation cost occur in periods u and t. In Y', the number of containers delivered in period u is less than or equal to the number of containers delivered in the same period in Y. The number of containers delivered in period t increases by one. However, since (k-l)Q < Yt < kQ, we have r(Yt+1)/Ql = FYt/Q1 = k, and therefore the number of trucks remains the same in both schedules. Hence, the total transportation cost resulting from Y is less than or equal to the transportation cost resulting from Y. We therefore conclude that Y is better than Y, which contradicts the optimality of Y. -28

Theorem 4: Let Y be an optimal solution to SIVTS. Then Yt > Qt~ ==> It < Q, V t. Proof: Let Y be an optimal schedule and suppose there exists a period t for which Yt > QtO and It > Q, i.e., more than a truckload of inventory is held. Let m=Min Yt-Qt, Q ) (> 0 and integer). We define the delivery schedule Y to be the same as schedule Y, except in periods u and t, where Yt = Yt-m and Yt+i=Yt+l+m. We can easily verify the feasibility of Y'. Next we show that schedule Y' has a lower cost than schedule Y. The inventory level decreases by m units in period t, resulting in a positive decrease in inventory costs. The only changes in the delivery quantities occur in period t and t+1. The transportation cost of schedule Y' is no greater than the transportation cost of schedule Y, since: (i) if m=Yt-Qt~, then Ct[Yt'] + Ct+l[Yt+i'] = Ct[Qt0] + Ct+l[Yt+l+m] < 0 + K + Ct+l[Yt+l] (since m< Q, and C[u+Q] < C[u]+K for u >0) = Ct[Yt] + Ct+l[Yt+l] (since Qt~ < Yt < Qt~+ Q ), or (ii) if m=Q, then Ct[Yt'] + Ct+l[Yt+l'] = Ct[Yt-Q] + Ct+l[Yt+l+Q] < CtYt] - K + Ct+l[Yt+l] + K ( since C[u-Q] = C[u] - K for u > Q t~) = Ct[Yt] + Ct+i[Yt+i]. We therefore conclude that Y is better than Y, which contradicts the optimality of Y. Theorem 5: Let Y be an optimal solution to SIVTS. Then It-1 [(Yt-Qt~ ) Mod Q] Yt = 0, Vt. Proof: Let Y be an optimal schedule, and suppose that there exists a period t for which It-1 > 0, and (k-1)Q < Yt-Qt~ < kQ for some integer k. Let u be the most recent period before t with a positive delivery quantity. Let E=Min (l1-FU,Iti) (>0). We define the schedule Y to be the same as schedule Y, except in periods u and t, where: Yt'= Yt+l, Ft'= 1-, -29

' Fu+E ifFu+ <1 and Fu= 10 otherwise; fYu if Fu+e <1'u =Yu- otherwise. In Y, the delivery of units is delayed from period u to period t, since they are not needed before then. We can easily verify the feasibility of Y. Next we show that schedule Y' has a lower cost than schedule Y. The inventory cost is decreased by at least H e (> 0). The only changes in the transportation cost occur in periods u and t. In Y', the number of containers delivered in period u is less than or equal to the number of containers delivered in the same period in Y. The number of containers delivered in period t increases by one. However, since (k-1)Q < Yt-Qt0 < kQ, we have R(Yt - Qt~ +1)/Ql = r(Yt-Qto)/Ql = k, and therefore the transportation cost is the same in both schedules. Hence, the total transportation cost for Y' is less than or equal to the transportation cost forY. We therefore conclude that Y is better than Y, which contradicts the optimality of Y. Corollary 5.1: Let (Yu+i,..,Yt-i) be a partial solution in the regeneration interval [u,v]. Then there exists at most one integer value kt, for which Yt = Qt~ + ktQ and (Yu+l,..,Yt-l,Yt) is a partial solution. Proof: Let u, v be two consecutive regeneration points. Let (Yu+i,..,Yt-l), u+2 < t < v, be a partial solution. Let Rt= Dh, be the total demand from period u+1 up to and including h=u+l period t, let St = Y Yh be the total number of containers delivered up to and including h=u+1 period t, and let f= 1 Dtl] - Dt be the total number of containers left empty during the t=u+l t=u+1 regeneration interval. Note that by Theorem 1, the containers are always full except in period u+1. By Theorem 5, for each period t, u+2 < t < v, the only possible delivery quantity is given by Yt = Qt~ + ktQ for some integer values kt. Suppose kt > 0. Then, by Theorem 4, the inventory in period t must be less than a truckload, i.e., It = St - f- Rt < Q. Since no backordering is allowed, the inventory must be non-negative, i.e., St - f- Rt > 0. Now, St=St1+Qt~+ktQ. Therefore, we have 0 < (St-i + Qt~ +ktQ) - f - Rt < Q, which implies that -30

[Rt + f- (St-i+Qt~)]/Q < kt < 1 + [Rt+f-(St-i+Qt~)]/Q. Since k is integer, the only possible value that can be assumed by kt within these bounds is F[Rt+f-(St-l+Qt~)]/Q, if this value is positive. If it is positive, this implies that (St-i+Qt~)-f-Rt, which is the amount of inventory that results from delivering QtO containers in period t, is negative, and therefore Yt = Qt~ is not feasible. We conclude that the only possible value of kt such that (Yu+,..,Yt) is a partial solution, and Yt=Q~t+ktQ, is Max (0, r[Rt+f-(St-l+Qot)]Ql 1. -31

UNIVERSITY OF MICHIGAN I 3 9015 04732 7377 3 9015 04732 7377