THE MULTI-ITEM JOINT REPLENISHMENT PROBLEM WITH TRANSPORTATION AND CONTAINER EFFECTS Nejib Bdh-Kheder American Airlines Decision Technologies P.O. Box 619616 Dallas-Fort Worth Airport, TX 75261-9616 Candace Arai Yano Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109 Technical Report 89-29 (revised) August 1990 Revised December 1991 Revised September 1992

The Multi-Item Joint Replenishment Problem with Transportation and Container Effects 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 (due to the presence of containers and finite-capacity trucks) and a multi-item joint replenishment problem. We present a heuristic solution procedure which starts with the optimal solution of the problem in which the integrality of the containers is relaxed. (A solution procedure for this relaxed problem appears in Ben-Kheder and Yano 1989a). We develop a method to modify this solution to account for the integrality of containers. This modification scheme involves sequentially considering each item and optimally scheduling the fractional containers in the relaxed solution. To solve this single-item problem, we devise a procedure that accounts for the availability of "free" remaining capacity of trucks that have been partially filled with other items. In a computational study, our heuristic is compared with a lower bound, with variations of our heuristic, and with simple rule-of-thumb policies. The results suggest that our heuristic performs very well, especially in problems where considering tradeoffs between inventory and transportation costs is important. Keywords: Inventory —Multi-Item Transportation

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 units 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, with each delivering a range of items. This is especially evident in the U.S. automobile industry, which motivated our study. JIT also has resulted in a change in the structure of ordering costs (sum of order processing and transportation costs). Order processing costs have been reduced through the use of long-term supply contracts and electronic ordering. Consequently, the transportation cost has become the main reason for ordering in batches. Because of these transportation 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 collectively 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 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. 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 a schedule is constructed that can be repeated indefinitely. 3. The demands for each item are deterministic but may vary over time. Near-term demands generally exhibit this property in actual applications. 4. No backordering is allowed. 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. We assume, without loss of generality, that there is no initial inventory. If there is initial inventory, it is optimal to apply it to the demands in periods 1, 2,..., until it is depleted. We also assume that there is no inventory at the end of the final period. In a finite horizon problem, it is easy to show that there is an optimal schedule with this property. The optimal repeating schedule may not have the property that at least one period in the cycle has zero inventory. However, schedules without this zero-inventory property are very difficult to identify. By assuming that there is zero ending inventory, we can repeat the schedule indefinitely. Such repeating schedules facilitate implementation, especially when the -2

number of periods in the cycle is chosen to be a convenient number, such as the number of working days in a week. By applying our procedure to consider each period as the last period in the cycle, we can determine the best period (or periods) in which to have zero inventory. If a repeating schedule is not desired, our procedure can be appplied to any finite horizon problem. 7. Each demand and delivery quantity is expressed as an integer number of containers, but the containers may be partially filled. 8. All trucks have the same capacity. In section 8, we explain how our model might be generalized to consider trucks with different capacities. 9. The containers fit into a truck if 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 truck, this assumption is realistic. Even if the containers are not standardized, it is usually possible to estimate the effective capacity of a truck. We also assume that the effective capacity of a truck 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 filled containers are charged pro rata. b. Transportation cost: There is a fixed charge K for each truck shipped regardless of the volume in the truck. (Such a cost function has a staircase form and is a special case of a piecewise concave cost function. For a discussion of piecewise concave functions, see Zangwill 1967.) Thus, there are economies of scale associated with filling up each of the trucks. However, there are no additional economies of scale from shipping more than one truck from any supplier on any given day. (Any discounts arising because of the contract are subsumed in the contracted price, K). 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 -3

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, thereby possibly reducing transportation costs. A mathematical formulation The multi-item joint replenishment (MIJR) problem with a "staircase" (S) transportation cost and container (C) restrictions, MIJR-SC, can be formulated as: (MIJR-SC) T N T M N Min Z= I HI- jt + 1 1 K 8[ Xjtm (1) tl j=1 t=lm=1 j=1 subject to ljt = Yjt- Fjt + Ijt-l - Djt, N XVj Xtm < 1, j=l M Xjtm = Yjt, m=l Fjt Min 1, Yjt }, IjT = Ijo =0, Yjt, jt, Fjt o, Xjtm integer, t=1,..,T; j=l,..N; t=l,..,T; m=l,..,M; t=l,..,T;j=l,..N; t=1,..,T; j=1,..N; j=l,..,N; t=l,..,T; j=1,..N; t=1,..,T; j=,..N; m=l,..,M; (2) (3) (4) (5) (6) (7) (8) where 8[u] = if u>0 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, -4

regardless of whether these containers are full. Constraints (3) are the truck capacity constraints. Constraints (4) give the total number of containers delivered of each item in each period. Constraints (5) ensure that the empty portion of the container is less than 1, and is zero when no delivery occurs. 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-SC 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 develop good solution procedures that take advantage of the special structure of the problem. The complexity of MIJR-SC 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 transportation cost is itself an optimization problem, where we fit containers into trucks in order to minimize the number of trucks used. Both subproblems are known to be difficult to solve optimally. Joneja (1987) reports that the MIJR problem, with a fixed-charge for placing an order and with an individual ordering cost associated with each item is NP-complete. 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 SN, 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 NPhard (Garey and Johnson 1979). Thus, it is unlikely that an optimal, polynomial-time algorithm can be developed for our problem. Our approach to MIJR-SC is a combination of two heuristic procedures, both of which explicitly consider the structure of the transportation cost. We briefly describe the two approaches, and then explain how we combine them. One approach is to approximate the transportation cost by ignoring the origintegrality of the containers. The resulting problem can be viewed as a "continuous" relaxation of the original problem where the delivery quantities are continuous but the transportation cost retains the staircase structure. Ben-Kheder and Yano (1989a) characterize the solution to this relaxed problem and develop both an optimal algorithm and a simple heuristic to solve it. Once the -5

solution to this problem has been obtained, the container decisions can be 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 is not yet full. 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 delivery quantities. We use this approximation to determine the lot sizes (in truckloads), which may represent non-integer container quantities. A solution procedure for this relaxation of the problem can be found in Ben-Kheder and Yano (1989a). A portion of the delivery quantity is fixed by rounding the non-integral values down to the nearest integer. The remaining requirements are 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 remaining (fractional container) requirements. We consider the inventory cost and a modified transportation cost that takes into account the "free" truck capacity. Our contributions in this paper are as follows. First, we develop an optimal O(T3) algorithm for the single-item problem with a staircase transportation cost structure and container constraints, and an optimal pseudopolynomial time algorithm for a variation of this problem with time-varying transportation costs. These are described in the next two sections. To our knowledge, these are the first optimal procedures for problems of this type with container considerations. These procedures form the foundation for our scheme to a al with fractional containers arising from the multi-item problem in which container integrality constraints are relaxed. Second, we devise a heuristic that allows us to integrate the full-container portion of the solution with the fractional container portion to construct a logical delivery schedule. To our knowledge, this is the first time that inventory, truck capacities and related transportation costs, and discrete container effects have been considered simultaneously in a multi-item procurement problem. We conclude with results of a series of computational experiments that demonstrate the efficiency and robustness of our heuristic and its ability to handle large problems on a routine basis. -6

The Single-Item Problem The single-item (SI) dynamic lot-sizing problem with piecewise concave (PC) ordering cost (SIPC), 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 [0,+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 such that: 1. an integer number of full trucks is delivered in periods with positive initial inventory, and 2. the inventory remaining at the end of each period is less than a truckload. For a cost structure in which there is a fixed cost per truck plus a variable cost per unit volume (which is the same as our problem when the variable cost is zero), he exploits these results to develop an O(T3) algorithm. The procedure involves computing the optimal cost for each possible regeneration interval, where a regeneration interval is a set of consecutive time periods starting and ending with zero inventory, but with no intermediate periods with zero inventory. Under the two properties stated above, it is straightforward to compute the optimal lot sizes, and for each potential regeneration interval, this can be done in linear time. Finding the optimal solution requires solving a shortest path problem for the induced network, which has complexity O(T2). The primary difference between Lippman's model and ours is that we must account for the space required for partially filled containers whereas Lippman's does not. Due to properties of the optimal solution that we describe below, the computation of the optimal cost for each regeneration cycle can still be done in linear time, and we can solve the resulting shortest path problem in the usual way. In the remainder of this section, we first show that the solution to the bin-packing (BP) component of the problem is trivial in the single-item case, yielding a simpler formulation. We then extend Lippman's result to consider container constraints and present an O(T3) solution procedure. For simplicity, we suppress the item subscript in this section. 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 (YJ 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. -7

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, M M TCt = K 8(Xtm) = Kr F Xtm /Q1 = KFYt/Ql. m=l m=l The truck index m can be omitted and consequently also constraints (4), as well as the truck capacity constraints (3). The single-item problem with a staircase transportation cost, SI-S, can be formulated as: (SI-S) T T Min H It + K rYQ1 (9) t=1 t=1 subject to Yt-Ft + It- It = Dt, t=l,..,T; (10) Ft< Min ( 1, Yt, t=1,..,T; (11) IT = 10 = 0; (12) It, Ft 0, t=1,..,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. Hence, the optimal solution is not sensitive to a change in the value of V within the interval (1/(Q+1),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, l<t<T, either the containers are full, or the initial inventory is zero. This result is quite intuitive. If the containers are partially filled then the shipment in period t can be increased with no additional ordering charge and a shipment 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. -8

Theorem 2 states that less than a truckload of inventory is held at the end of any 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 dynamic programming (DP) procedure for SI-S that is similar to Lippman's procedure. We solve a shortest path problem with T nodes and T2 arcs. An arc (u,v) links two consecutive regeneration points (periods with zero ending inventory) u and v (for u<v). The computation of the arc cost, Cuv, is achieved by a backward inductive scheme based on properties of the optimal solution. Theorems 1 and 3 collectively imply that for any regeneration interval (which must have positive initial inventory in all but the first period in the interval), only the first period in the interval may have a partial-truckload shipment. Theorem 2 implies that in the second through the last period in the interval, the number of full truckloads shipped is just enough to ensure that demand is satisfied. With these rules, it is a straightforward matter to compute the optimal shipment quantities, and amount of work required to compute Cuv is O(T), so the procedure for the single-item problem is O(T3). See Ben-Kheder and Yano (1989a) for further details. Next, we explain how the results for the single-item problem can be used in solving the multi-item problem. The interaction among items is reflected principally in the staircase 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 bin-packing rule. For a given period, t, there is a positive volume slack, Smt, for each partially filled truck, m. Let j be the item to be M scheduled next. Let Vj be the volume of an item j container. Also let Qjt~ = XL Smt NjJ, m=1 which represents the number of item j containers that can be delivered in period t with no additional transportation charge. We adjust the transportation cost accordingly, i.e., the cost of transporting Yjt containers of item j is set equal to K-max ( 0, r(Yjt - Qjt~ )/Qjl I where Qj = LlNj 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 -9

case, so the algorithm described above needs to be modified to handle time-varying costs. We investigate this extension in the next section. The Single-Item Problem with Time Varying Transportation Cost The single-item problem with time-varying transportation costs that we address in this section is a variant of SI-S, where the transportation cost, Ct, has the staircase form and is time-varying. We denote by Qt~ the number of containers free-of-charge (FOC) in period t. The single-item problem with a time-varying staircase (SI-TVS) transportation cost can be stated mathematically as: (SI-TVS) T T Min HIt + E Ct[Yt] (15) t=1 t=1 subject to (10) through (14) where Ct[Yt]= K-max { 0, F(Yt - Qt~)/ Q 1 is the staircase cost shown in Figure 1. Insert Figure I near here We extend the results for SI-S to SI-TVS. Theorem 1 still holds for the same intuitive reasons. Theorem 2 must be altered because it might be more economical to ship items 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, 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 It1 [(Yt-Qt 0) Mod Q] Yt = 0, V t Proof: See Appendix. 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 -10

number of full trucks. In the following corollary, the number of trucks in j period t, kt, is shown to be restricted for any regeneration interval. Corollary 5.1: Let (Yu+l,..,Yt-i) be a partial solution in the regeneration interval [u+l,v]. Then there exists at most one positive integer value kt, for which Yt = Qt~+ ktQ > 0 and (Yu+i,..,Yt-l,Yt) is a partial solution. 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=O for all except the first period in the regeneration interval and FU+1 = f v v = Fr Dt 1 - D Dt, which is the number of container units shipped in excess of that t=u+l t=u+1 required during the time interval [u+l,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 St-i is known. Then by Corollary 5.1, if Yt > 0, there is a unique integer kt such that Yt = Qt~+ ktQ, i.e., kt = max { 0, r(Rt - St.l - Qto)/Q1 }, 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 C 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 Rt, u+1 < t < v, and fare 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+l+Qt+l~+ kt+lQ)+ kt+l K) for Ste At (16) and g(Sv) = 0 for Sve Av - 11

where At, u+1 5t v, is the set of admissible states in period t. There are at most two admissible ways to reach a node St from stage t+1. Either no delivery occurs in period t+1, which is feasible only if St - f > Rt+l, or we deliver Qt+10 containers plus kt+l full trucks, where kt+i = max ( 0, r(Rt+ - (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 FRv 1. Observe that Av=(Quv), and that I Atl Quv, for u <tsv. In the first period of the regeneration interval, a tighter upper bound on Su+l can be obtained from Theorem 4. If Su+l > Qu+1~ then Iu+1 = Su+l - f - Du+j < Q (by Theorem 4), which implies that Su+1 s max (Qu+l~, rQ+(f+DU+1)1}. Once g(Su+ ) is computed for Su+1 in Au+1, CUV is obtained from: Cuv = Min (g(Su+l ) + K k(Su+l ), Su+l Au+l) (17) where k(SU+i) is the number of trucks needed to deliver the Su+1 containers in excess of the Qu+1~ FOC containers, i.e., k(Su+l) = max (0, F(Su+l -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 known not to grow faster than 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. Theorem 6: Let Y be an optimal schedule. Then Yt > Min (LDt J, Qt 0~, V t. Proof: The proof is intuitive. Suppose Yt < LDt J < Qt0. Then It.- 2 Dt - Yt 2 LDt J - Yt = > 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 reduced by at least He. Thus, Yt < LDt J < Qt0 cannot be optimal. Now suppose that Yt < Qt~ < LDt J. Then we can set e = Qt~ - Yt and the same argument above applies. - 12

Let P be a problem with demand D, and let (Qt0~ be the set of FOC containers allowed. Let Yt = Min LDt J, Qt~ }. Then the optimal solution to P can be obtained by solving a problem P', derived from P by: - reducing Dt to Dt' = Dt - Yt, and - reducing Qt~ to Qt'~=Qt~ -Yt. We refer to Dt as the reduced demand. The quantity Yt is the reduction, and it represents the minimum quantity that will be shipped in period t. Note that this quantity will be shipped free-of-charge. The problem that remains is to schedule the reduced demand, D', taking into consideration the free-of-charge containers reflected in Qt'~. We refer to this problem as P'. Let Y be the solution to problem P'. Then the solution to problem P is obtained by summing Yt 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 L < T, and the computational complexity is O(T4) since the procedure is O(LT3), as mentioned earlier. Also, if the FOC volume is zero in each period, then the problem reduces to the basic single-item problem, SI-S, for which we have devised an O(T3) solution procedure. We now have the basis for a sequential heuristic for the multi-item problem. The optimal procedure described above can be applied to each item in turn, with updating of the remaining truck capacity after each item has been scheduled. 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. Preliminary experiments indicated that this sequential heuristic does not perform well in general on the original problem because it is too myopic. On the other hand, it performed well for small demand quantities. Consequently, we decided to use such a sequential heuristic to make "rounding" adjustments after obtaining the optimal solution from a relaxation of our problem in which the integrality constraints on containers are relaxed. In the next section, we describe our proposed heuristic, including a sketch of the solution procedure for the problem with container integrality constraints relaxed, and methods for making adjustments to consider the container constraints. -13

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 related truck capacity considerations. This heuristic will be referred to as the bin-packing/lot-sizing (BINLOT) heuristic. The heuristic features three main modules: 1. Lot-sizing based on an approximation of the costs and a relaxation of the container constraints. 2. Bin-packing (assigning containers to trucks). 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-sizin MIJR-SC 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 ordering item j. Literature based on this cost assumption can be found in a recent survey by Aksoy and Erenguc (1988). In our problem, the transportation cost cannot be expressed in closed form. Its value is obtained by solving a bin-packing subproblem in each period: given the decision to deliver Yjt containers of item j, l~jSN, in some period t, l~tST, the transportation cost, TCt, is computed as: M N (TC) MinK 56[V Xjtm (18) m=l j=l subject to N VjXjtm < 1 m=1,..,M (19) j=1 M Xjtm j tj j=I,..N (20) m=l Xjtm integer j= 1,..N; m=l,..,M (21) - 14

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 there is no space 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, 1<<N, in period t, l<t<T. Then the number of trucks used in N period t is given by IjYjt'l. The truck capacity constraint (19) and the truck index m can j=l now be eliminated from the model. The relaxed problem, (MIJR-S), is formulated as: (MIJR-S) T N T N Minimize ~ zHj'Ijt'+ K YKrYjt' (22) t=l j=1 tl 1 j=1 subject to jt' = Ijt-l' + Yjt - Djt' (23) IjT' = Ijo'= 0 (24) Itjt', Yjt'0 (25) where Hj' = Hj / Vj is the inventory holding cost per truckload of item j per period, 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-S is not the linear programming relaxation of MIR-SC 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 (1989a) characterize the optimal solution for this problem. They show, among other results, that at most one item has both 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 the problem optimally. We refer to this algorithm as the BY algorithm. As a substitute, they suggest an O(NT3) heuristic based on a 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. At this point, we have a solution that may contain fractional containers. 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 to the next container, as well as the decision of - 15

whether to ship fully or partially loaded containers, to Step 3 of the heuristic. In Step 2, we consider the delivery of the LYjt/VjJ (= Yjt~) full containers, and assign these containers to trucks so as to minimize the number of trucks operated in each period. In Step 3, the remaining fractional containers are considered, and the heuristic considers opportunities for container consolidation, as well as opportunities to fill the remaining capacity of partially filled trucks at no additional transportation cost. We now discuss each of these steps in turn. Bin-packing: Assigning the Full Containers to Trucks 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 can be found in Garey and Johnson (1981) and in Coffman et al. (1984). Empirical studies (Hall et al. 1988, for example) indicate that several heuristics routinely provide solutions that are very close to optimal for many instances of the bin-packing 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 non-increasing order of size. The algorithm sequentially assigns the items to the bin with the lowest index in which the item fits (starting a new bin if the item will not fit into any non-empty bin). 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 unr ed portion of truck m, and M as the total number of trucks used. We assume that the items are indexed in non-increasing order of their unit container volumes. -16

For t: = 1 to T do begin M: = EM:= 1 Forj:= 1 to N do Y: = Yjt Load non-empty trucks: For m:= 1 to M do Q:= LEm/Vj J (# 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-qVj next m Load empty trucks: While (Y > 0) do M:=M+1 Q: = Ll/Nj 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-qVj next j next t The most complex part of the algorithm is the a priori sorting of the items which has complexity O(NlogN), but only needs to be performed once. Adustment of lot-sizes In step 1, the delivery quantities in the solution to the relaxed problem, MIJR-S, were rounded down in order to obtain integer numbers of containers. Therefore, only a portion of the demand is satisfied by this solution. These quantities need to be adjusted to satisfy the total demand requirements. Let Ijt~ be the inventory, if any, resulting from the delivery of Yjt~ full containers in period t, i.e., Ijt~ = max (0, Ijt-l+Yjt0 - Djt). Then the demand remaining to be satisfied in period t is given by djt = max (0, Djt- (Ijt-lO+YjtO) }. (26) -17

The multi-item problem with these reduced demands is then solved by a variation of the heuristic for the single-item problem (presented earlier) 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 nonincreasing order of their inventory holding costs per truckload (Hj/Vj), and henceforth assume that the items are indexed accordingly. The additional delivery quantities, YjI1, are determined by the following procedure, which considers each of the items in turn and applies the optimal procedure for SI-S (as described in the previous section) to each. Fort: = 1 to T Mt: = total # of trucks used for loading Ylt~,...,YNt0 Emt: = capacity slack of truck m in period t next t Forj:=1 toN Determine the number of free-of-charge containers and remaining demand: For t: = 1 to T Mt Qjt~:= LEmt/VjJ m=l djt: = max (0, Djt - (Ijt-1o+YjtO)) next t Solve the single-item problem SI-TVS(j,djt,Qjt~) and let Yjtl,Fjt1 be the solution obtained. For t: = 1 to T Yjt:=Yjto+ Yjt1 (number of containers) Fjt:=Fjtl (fraction of item j container left empty) Mt: = total # of trucks used for loading Yit,...,YNt For m: = 1 to Mt Update Emt next m next t nextj T The total reduced demand for a given item, [ djt, does not exceed T containers, since t=l djt < 1 for all j and t. Therefore the computational complexity of each single item problem is - 18

O(T4), as mentioned in the previous section. The computational complexity of the entire procedure is 0(NT4). 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-S. (lb) Solve the resultant problem using the BY algorithm (lc) Let Yjt' be the solution to MIJR-S, 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 non-increasing order of their container volumes (2b) For each period t, use the FFD rule to load the Yjt~ containers in an attempt to minimize the number of trucks. (2c) Determine the capacity slack for each partially filled truck. Step 3. Lot-size adjustment (3a) Rank the items in non-increasing 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 for SI-TVS. Let Yjt1, Fjtlbe the solution obtained. (3c) Update the delivery quantities: Yjt:= Yjtl+Yjt Fjt:=Fjtl. Terminate. The solution procedure is composed of several heuristics, one for each subproblem. Each of these procedures 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 - 19

same decision framework: lot-sizing, bin-packing and adjustment of lot-sizes. Such modifications are potential areas for future research. In the next section, we empirically investigate the effectiveness of the BINLOT heuristic, some variations of it, and simple rule-of-thumb policies. Computational Experience In our experimental study, we investigate several heuristics that retain the basic structure of the BINLOT heuristic, but differ from one another principally 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 number of containers obtained at Step 1 to the next integer, but ship only the given lot sizes. This solution 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-0, 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. We let Yjto= L kYjt'/VJ. Notice that for k=1, we obtain the basic heuristic BINLOT, and for k=0, we obtain SEQLOT. Additionally, we consider two different policies for ranking the items: SEQLOTNOL, where the ranking in Step 3 is based on the container volumes, and SEQLOT/INV, where the ranking in Step 3 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: -20

No inventory is held. We ship exactly the quantity required in each period. This rule is just-in-time in its classical definition. 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 (per unit volume) 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. We perform a series of experiments to test the effectiveness of the different heuristics discussed above. 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 ratio, a, which is explained later. First, we generate the container volume (fraction of a truckload), Vj, from U[O.O1,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 number of containers. Let gj be the average demand obtained. The demand in period t, Djt, is generated from U[1,2jl]. The inventory holding cost of item j, Hj, is obtained from the inventory cost of item j+1, Hj+1, 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 (l+incrmax)N = A, which implies that the inventory cost of item 1 is at most p times the inventory cost of item N. The geometric progression of the inventory costs reflects the fact that in most situations, there are many inexpensive items and few expensive items. We set P = 10. - 21 -

Once the demands and the inventory costs are generated, the transportation cost per INV T N truck, TC, is obtained from the following formula: TC = OCT R, where INV =, Hj Djt t.l j=l T N is the cost of holding the total demand in inventory for one period and NTR = r[. D-jt t=l j=1 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 number of regeneration points in the planning horizon that achieves the best trade-off between the transportation and inventory costs, 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 1 shows the average deviation of JIT and AJIT solutions from the solution obtained by BINLOT. Figure 2 indicates the number of times each heuristic is the best. Insert Table 1 and Figure I near here 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 aL 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-o gives the same solution as JIT. (Ib) BINLOT vs. BINLOT-k: we compare BINLOT to its variants, SEQLOT and BINLOT-k (0 < 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 cost per truck, and a second one where the items are ranked by container volume. We set the control variables as follows: N = 20, T = 12, Vmax - U[2,10], TR=1, and a -U[0.5,31, and randomly generate 50 test problems. Results are summarized in Table 2. The SEQLOT heuristics are myopic and are significantly outperformed by BINLOT, which considers the items simultaneously. BINLOT-ao is, on the average, about 28% worse than -22

BINLOT. We note however that in some special situations (detailed results not reported here) where the inventory costs are very high, BINLOT-eo gives a better solution than BINLOT. In these cases the solutions are 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 chance of getting the best solution by BINLOT-k also decreases. In the 22% of the cases where BINLOT-k outperformed BINLOT (details not reported here), the differences are less than 6%. Insert Table 2 near here 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 computational complexity 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 earlier, the computational complexity of 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: Vax =5% of a truck, TR=1 truck per period, and a-U[0.5,4]. For each (T,N) combination we generate ten problems, varying the demand data. Summary statistics appear in Table 3. The heuristic remains computationally tractable for very large problems. The computation times reported for a problem with 50 items and 12 periods do not exceed 40 seconds. Such a problem, if formulated 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-and-bound tree to find a solution close to the heuristic solution. Insert Table 3 near here - 23

Experiment 3: Effect of Different Factors on the Lower Bound Ga: 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 BINLOT solution from the lower bound. 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, a=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=l, 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 use 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 suppliers with smaller demands. The maximum size of a container rarely exceeds 10% of a truckload in practice. 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. Table 4 reports deviations from the lower bound, as a function of the demand level and the maximum container volume. Unfortunately, because of the bin-packing aspects of the problem, the bound from relaxing the container constraints is probably not a good indicator of how far the BINLOT solution is from the optimal solution. As mentioned earlier, the first-fit-decreasing algorithm for bin packing is guaranteed to produce a solution with the number of bins no greater than 119 times the optimal number of bins, plus 4, or roughly 22% greater than optimal as the number of bins grows large. Moreover, the worst case error bound decreases to 15% when the maximum container size is 25% of the bin (truck) capacity. Yet extensive empirical evidence (Hall et al., 1988) suggests that actual errors are less than 2% on average. -24

Since the comparisons of our heuristic solution to the lower bound include inventory holding costs as well as transportation costs, and only the latter is proportional to the number of trucks (bins), we cannot make an exact analogy. Nevertheless, the differences between the cost of the heuristic solution and the lower bound are of a similar order of magnitude to those in bin-packing. Thus, if transportation costs are dominant, it is likely that a significant portion of the deviation from the lower bound is due to the fact that our lower bound does not consider the bin-packing aspect of the problem. Insert Table 4 near here The deviation drastically increases as the maximum container volume increases, just as the results from the bin-packing literature would suggest. The standard deviation, however, remains of the same magnitude, which is further evidence the good performance of the heuristic. 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 continuous solution. A similar phenomenon seems to hold in our context. The relaxed solution has full-truckload shipments following all non-regeneration periods (periods with positive ending inventory). Thus, we might expect the gap to be approximately one truck per non-regeneration period. We observed that 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 horizon problem. Thus, the solutions from the heuristic are probably very close to the optimal solutions. It is difficult, unfortunately, to find good bounds for this problem. Conclusion In this paper, we addressed the problem of scheduling the delivery of multiple components (items) from a single supplier, over a finite horizon, to meet the requirements for multiple components at an assembly facility. 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 trucks. As a result, the determination of shipment quantities is complicated by bin-packing considerations that arise due to the integrality of the trucks. The problem is NP-hard and is therefore difficult to solve optimally. We present a heuristic based on a relaxation of the problem where the container constraints are ignored. Experimental results show that the solution to this "continuous" version of the problem results in a good solution to the original problem, if it is intelligently -25

adjusted to account for the integrality of containers. Among the decisions involved in the adjustment 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 fractional containers are 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 and to rule-of-thumb heuristics. In our computational study, our heuristic produced solutions within 16% of a (loose) lower bound on the average. More detailed analysis of the results suggest that the deviations from the lower bound may be attributable to the bin-packing aspect of the problem, for which it is difficult to obtain tight bounds on performance. Thus, the solutions appear to be quite good. They also were substantially better than simpler rule-of-thumb procedures, except in extreme cost conditions. Unfortunately, we have not been able to compare the solutions from our heuristic to optimal solutions. 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, most of the decision variables in the problem are integral, and therefore it is difficult to find good lower bounds. Nevertheless, the results suggest that the heuristic is able to find very good solutions in a short period of time. Further research is needed to devise an efficient procedure to handle trucks with different capacities. The multi-item problem with a staircase transportation structure (without container constraints) can be generalized to accommodate trucks of different zi2es. This is possible because, for any volume of freight to be delivered, it is possible to find the least expensive combination of trucks and their total cost. The resulting relationship between the total volume and the best transportation cost still forms a staircase function. However, because the staircase is not as simple as in the case of one truck type, some of the properties of the optimal solution for the case of one truck type will not hold. Consequently fewer alternatives can be eliminated from consideration and greater computational effort will be required to solve the problem. The problem of loading the full containers into trucks when there are multiple types of trucks with different costs can be formulated as a minimum cost set covering problem. (The problem can be formulated in several other ways, also.) In this formulation, we must first generate all feasible combinations of containers that can be loaded onto a single truck and identify the least expensive truck type that will hold these containers. (The trucks may not - 26

be full.) For each of these feasible combinations, a zero-one decision variable is created (or more than one zero-one decision variable if the combination can be profitably used more than once), and the cost associated with choosing that variable is the cost for the appropriate type of truck. We must decide which of these combinations to choose. If the number of trucks of each type is limited (such as in a private fleet), we would need to consider the possibility of shipping each feasible combination of containers in larger-than-needed trucks, and to impose constraints to ensure that the number of combinations using any particular type of truck is appropriately limited. In practice, this would be a difficult problem to solve because of the number of possible combinations. However, it should be possible to construct good heuristics. On the other hand, our sequential procedure for dealing with fractional containers can be applied, with relatively minor modifications, to handle multiple truck types. As with a single truck type, we would try to use any "free" space on the trucks already assigned. Costs for any additional trucks would be captured by the modified staircase function described above. Once the total shipment quantities have been determined (both full and fractional containers), it would be desirable to reconsider the mix of trucks in order to further reduce the total transportation cost. Heuristics for the minimum cost covering approach could be used for this purpose also. 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. -27

REFERENCES Y. Aksoy and S. Erenguc, "Multi-Item Inventory Models with Coordinated Replenishments: A Survey," Operations and Production Management 8, 63-71 (1988). N. Ben-Kheder and C.A. Yano, "The Multi-Item Joint Replenishment Problem with VolumeSensitive Transportation Costs," Technical Report 89-19, Department of Industrial & Operations Engineering, The University of Michigan, Ann Arbor, MI (1989a),. N. Ben-Kheder and C.A. Yano, C.A., "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 (1989b). E.G. Coffman, Jr., J.Y. Leung, and D.W. Ting, "Bin Packing: Maximizing the Number of Pieces Packed," Acta Informatica 9, 263-271 (1978). ---------------—, M.R. Garey, and D.S. Johnson, "Approximation Algorithms for Bin Packing - An Updated Survey," in Algorithm Design Computer System Design, editor Ausiello, G. et al. (eds.), Springer, 49-106 (1984). M.R. Garey and D.S. Johnson,, Computers and Intractability:A Guide to the Theory ofNPCompleteness, Freeman, W.H. and Co., San Fransisco (1979). —. —.. —---------------------- -, "Approximation Algorithms for Bin Packing: A Survey," in Design and Analysis of Algorithms in Combinatorial Optimization, Ausiello, G. and Lucertini, M. (eds.), Springer-Verlag (1981). N. Hall, S. Ghosh, R.D. Kankey, S. Narasimhan, and W.T. Rhee,, "Bin Packing Problems in One Dimension: Heuristic Solutions and Confidence Intervals," Computers and Operations Research 15, 171-177 (1988) D.S. Johnson, A. Demers, J.D. Ullman, M.R. Garey, and R.L. Graham, "Worst Case Performance Bounds for Simple One-Dimensional Bin Packing Algorithms," SIAM J. Comput. 3, 299-325 (1974),. D. Joneja, "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 (1988). S.A. Lippman, "Optimal Inventory Policy with Multiple Setup Costs," Management Science 16, 118-138 (1969). AC. Yao, "New Algorithms for Bin Packing," J. Assoc. Comput. Mach.2, 207-227 (1980). W. I. Zangwill, "'The Piecewise Concave Function," Management Science 13, 900-912 (1967). - 28

Appendix Theorems and Droofs Theorem 1: Let Y be an optimal solution to SI-S. Then It-1 Ft = 0, V t. Proof: Let Y be an optimal schedule to SI-S, and suppose there exists a period t for which we have FtIt-1 > 0. Let u be the most recent period before t with a positive delivery quantity. Let E = Min (It-1, 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-e, F {' F if FU+s <1 and 0 otherwise; Y J Yu if Fu+e <1 Yu lYu-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. Moreover, the inventory cost is decreased by at least H e ( > 0). Thus, a solution with FtIt-l > 0 cannot be optimal. Theorem 2: Let Y be an optimal solution to SI-S. 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 I 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 - 29

periods 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)/Q1, which is less than rYt+/Q1 + 1, and therefore is less than rYt+i/Q1 + FYu/Q1, which is the total number of trucks shipped in periods 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 solution to SI-S. Then Itl- (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 the most recent period before t with a positive delivery quantity. Let E=Min I 1-FU, It-l} (>0). We define the schedule Y to be that same as schedule Y, except in periods u and t, where: Yt =Yt+l, Ft = 1-, F u Fu+e ifFu+<l and 10 otherwise, and | Yu if Fu+e <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 ~ (> 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+l)/Ql = rYt/Qi = 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. Theorem 4: Let Y be an optimal solution to SI-TVS. Then Yt > Qt~ ==> It < Q, t -30

Proof: Let Y be an optimal schedule and suppose there exists a period t for which Yt > Qt0 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+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 period t, resulting in a positive decrease in inventory costs. The only changes in the delivery quantities occur in periods 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+l'] = Ct[Qt~] + 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+i'] = Ct[Yt-Q] + Ct+i[Yt+i+Q] < Ct[Yt] - K + Ct+l[Yt+l] + K ( since C[u-Q] = C[u] - K for u > Q t~) = Ct[Yt] + Ct+i[Yt+l]. We therefore conclude that Y is better than Y, which contradicts the optimality of Y. Theorem 5: Let Y be an optimal solution to SI-TVS. Then Itl. [(Yt-Qt~ ) Mod Q] Yt = 0, Vt. Proof: Let Y be an optimal schedule, and suppose there exists a period t for which It-l > 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 (l-Fu,It-) (>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-e, -31

Fu Fu+e if Fu+<l and Fu = o otherwise; Y=I Yu if Fu+e <1 Yu Yu-1 otherwise. In Y, the delivery of e item units is delayed from period u to period t, since it is 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. The number of containers delivered in period u, in Y, 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-Qt~ < kQ, we have (Yt - Qt~ +1)/Q1 = r(Yt-QtO)/Q1 = k, and therefore the transportation cost is 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. Corollary 5.1: Let (Yu+i,..,Yt-l) 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+1,..,Yt-l,Yt) is a partial solution. Proof: Let u, v be two consecutive regeneration points. Let (Yu+i,..,Ytli), u+2 < t < v, be a t partial solution. Let Rt= X Dh, be the total demand from period u+1 up to and including h=u+l t period t, let St =, Yh be the total number of containers delivered up to and including h=u+l v v period t, and let f 4 Y Dtl - ~ Dt be the total number of containers left empty during the t=u+l t=u+l 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 vales 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 20. By definition, St=St-l+Qt~+ktQ. Therefore, we have 0 < (St-1 + Qt~ +ktQ) - f - Rt < Q, which implies that - 32

[Rt + f - (Stl.+Qt~)l/Q < kt < 1 + [Rt+f-(St-l+Qt~)YQ. Since kt is an integer, the only possible value that can be assumed by kt within these bounds is r[Rt+f-(St-l+Qt)YQ1 Ql, if this value is positive. If it is positive, this implies that (Stl.+Qt0)-f-Rt, which is the amount of inventory that results from delivering Qt~ 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+i,..,Yt) is a partial solution, and Yt=Q~t+ktQ, is max (0, r[Rt+f-(St-l+Qot)]/Ql I. - 33

Transportation cost 4 3K 2K K shipment volume (in containers) 2Q+Qt 3Q+Q t t Figure 1: Modified transportation cost in period t -34

3.5 - 4 3 - 3.5.0 2.6 - 3 S. 2 - 2.5 1.6 - 2 1 - 1.5 0.6- 1 0.1 - 0.6 BINLOT JIT H AJIT Best Heurstic Best Heuristic 8 10 Figure 2: Best heuristic for different values of the transportation to inventory cost ratio - 35 -

Table 1: Average deviation of the cost of JIT and AJIT solutions from that of BINLOT a ratio [0.1,0.5] [0.5,1] [1,1.5] [1.5,2] [2,2.5] [2.5,3] [3,3.5] [3.5.4] JIT Heuristic 5.4% 19.5 % 17.6 % 25.9 % 23.3 % 30.8 % 28.5 % 32.0 % AJIT Heuristic 59.3 % 32.3 % 21.5 % 16.1% 10.3% 7.7% 2.8% 3.5% - 36

Table 2: Comparison of BINLOT to its variants Heuristic % of Time Best Average Cost CPU times (secs.) Heuristic Penalty vs. BINLOT Mean Std.Dev. BINLOT 78 % -- 12.7 2.10 BINLOT- o 27.7 % 1.1 0.05 BINLOT-0.50 18 % 7.2 % 23.2 8.90 BINLOT-0.25 4 % 10.1 % 25.3 11.40 SEQLOT-INV 36.5 % 64.9 39.40 SEQLOT-VOL _37.5 % 63.6 40.80 -37

Table 3: Computation times as a function of N and T CPU times N T MeanStd. 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 ____ 12 31.19 4.11 - 38 -

Table 4: Deviation of BINLOT from the lower bound Deviation from Lower Bound Average Std. Dev. I ____________________________________________ Average Number of Truck: 1 5 10 15 Maximum Container Volu 2 5 15 3 per Period 22.87 % 6.00 % 3.02 % 2.65 % me (% of a truck 3.93 % 9.30% 22.14 % 5.65 % 1.40 % 0.83 % 0.69 % 2.26 % 2.65 % 2.04% JL - -39

UNIVERSITY OF MICHIGAN 3 9015 04732 7351 Figure 1: Modified transportation cost in period t Figure 2: Best heuristic for different values of the transportation to inventory cost ratio Table 1: Average deviation of the cost of JIT and AJIT solutions from that of BINLOT Table 2: Comparison of BINLOT to its variants Table 3: Computation times as a function of N and T Table 4: Deviation of BINLOT from the lower bound -40