# Determining the Optimum Ordering Policy in Multi-Item Joint Replenishment Problem Using a Novel Method

Authors: Wen-Tsung Ho
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

This work investigates the joint replenishment problem (JRP) involving multiple items where economies exist for replenishing several items simultaneously. The demand rate for each item is known and constant. Shortages are not permitted and lead times are negligible. Many heuristic algorithms have been proposed to find quality solutions for the JRP. In this paper, cycle time division and recursive tightening methods are developed to calculate an efficient and optimal replenishment policy for JRP. Two theorems are demonstrated to guarantee that an optimal solution to the problem can be derived using cycle time division and recursive tightening methods. Restated, cycle time division and recursive tightening methods theoretically yield the optimal solution in 100% of instances. The complexity of cycle time division and recursive tightening methods is justO(NlogN), where N represents the number of items involved in the problem. Numerical examples are included to demonstrate the algorithmic procedures.


---

## Body

## 1. Introduction

The joint replenishment problem (JRP) is an inventory problem involving multiple items where economies exist for replenishing several items simultaneously. These cost savings can be achieved when the replenishment of several items is coordinated.The JRP has received considerable attention over recent decades. Detailed surveys of the JRP are available in [1–3]. Numerous heuristic algorithms have been developed for the JRP [4–8], but few optimal algorithms have been proposed. Balintfy [9] was among the first to consider the case in which joint ordering of several items may result in savings in set-up costs. A general formulation to the JRP and a graphical solution for the two-item case were provided in [10]. Furthermore, the author of [11] was the first to present an optimal algorithm for the inventory problem involving multiple items supplied by a single supplier with the assumption of purchase orders placed at equal time intervals. A branch and bound algorithm for devising an optimal policy was proposed in [12]. Furthermore, in [13], the authors demonstrated that the assumption of [11] of equally spaced manufacturing runs does not necessarily yield an optimal solution in situations involving more than two items. Additionally, a heuristic method was proposed for determining order quantities in joint replenishments with deterministic demand in [14]. Then, the algorithm of [14] was improved by [15, 16]. Moreover, an effective heuristic algorithm was presented in [17]. Finally, an optimal production-packaging policy for jointly replenished items was demonstrated in [18].Additionally, a simple heuristic procedure, called RAND, was proposed based on the comparison of several values of the cycle timeT [19]. Furthermore, the range of cycle time was divided into m equally spaced values of T. Subsequently, for each value of T, the improved Silver algorithm [15] was applied to calculate the total costs and select the lowest cost as the optimal solution. In [20], the authors modified the RAND using a better estimate of the minimal value of the cycle time T. Simulation experiments were performed to demonstrate the superiority of the modified RAND procedure. The author of [21] pointed out that the lower bound of the Goyal method [11] cannot guarantee to yield an optimal solution. He thus recommended the correct lower bound on T and demonstrated a heuristic algorithm for deriving the optimal among the various cyclic policies. In [22], a heuristic method based on relaxing the nonlinear mixed integer programming (NLP) formulation of JRP was proposed. Beginning with the ordering frequencies derived from the solution of NLP relaxation, the near-optimal replenishment policies were determined. Subsequently, the authors of [23] performed a simulation experiment to compare the efficient exhaustive search heuristic for JRP proposed by [20] with that proposed by [22]. The problem in discrete time was considered and the lower and upper bounds of the optimal cycle time were derived in [24]. Additionally, a heuristic algorithm was presented to reduce the computational effort by improving the bounds on the basic cycle time T in [25]. Furthermore, an alternative optimal approach based on global optimization theory was proposed in [26]. The problem can efficiently be solved via Lipschitz optimization. In [27], the authors proposed heuristic methods for optimizing the cyclic policy and the strict cyclic policy for the JRP. The method of [27] for determining the optimal strict cyclic policy that does not guarantee an optimal solution was demonstrated in [28]. A modified method was thus devised for obtaining the optimal strict cyclic policy. The author of [29] considered the deterministic multiproduct inventory model. The problem is to determine a production schedule to meet the demands and minimize the sum of production and holding costs. Also, some qualitative properties of the multi-item joint replenishment inventory problem are obtained. The JRP for M items under deterministic demand, with a minimum order, quantity constraint for each item in the replenishment order was studied in [30]. The bounds on the basic cycle time are derived and a global optimization procedure is proposed to solve the JRP with constraints. A heuristic method based on a spreadsheet technique for solving joint replenishment problems with strict cycle policies was proposed in [31]. Based on the test data, the modified RAND algorithm of [20] and Nilsson et al. algorithm of [31] achieve the optimal solutions in 81.7% and 92.9% of 48,000 instances, respectively. In [32], the author presented an analysis and solution method to solve the JRP with correction factor, which is a generalization of the method presented in [30]. Also, genetic algorithms (GAs) were developed for solving the JRP and we compared their performance to the RAND method in the literature [4, 33–35]. The algorithm first decides grouping, that is, which items are replenished together, and then assigns a fixed replenishment cycle for the items in the same group.This study proposes the cycle time division (CTD) and recursive tightening (RT) methods to calculate an efficient and optimal strict cyclic policy for JRP. Two theorems are demonstrated to guarantee that the problem can be solved optimally using the CTD and RT methods. Restated, CTD and RT methods theoretically yield the optimal solution in every instance. The complexity of the CTD and RT methods is justO(NlogN).The remainder of this paper is organized as follows. Section2 introduces a statement of the problem and the required notations. Sections 3 and 4 then describe the cycle time division and recursive tightening methods. Additionally, Section 4 demonstrates the validity of two theorems. Subsequently, Section 5 proposes an optimization algorithm. Section 6 then presents numerical examples. Finally, conclusions are drawn in Section 7.


## 2. Assumptions, Notations, and Problem Statement

In the formulation of the joint replenishment problem, the following assumptions are made:(1)
the demand rate for each item is known and constant;(2)
shortages are not allowed;(3)
the replenishment rate is infinite (zero lead time);(4)
there is an infinite horizon.Moreover, to discuss the joint replenishment problem, we introduce the following notation:N: number of items;A: major ordering cost associated with each replenishment ($/order);i: 1,2,…,N, an item index;di: annual demand for item i (units/year);ai: the minor ordering cost incurred if item i is ordered in a replenishment ($/order);hi: holding cost per unit per year of item i ($/unit/year);T: time between successive replenishments (years), ( basic cycle time, decision variable);Qi: order quantity of item i;Ti: time interval between successive replenishments of item i (years);mi: frequency of ordering item i (an integer multiple, decision variable).The JRP is an inventory problem concerning multiple items where economies exist for replenishing several items together. There are N items, and for each item i, demand occurs at a constant annual rate of di. Holding costs are incurred at the rate of hi per unit of item i held. A major ordering cost A is incurred for every replenishment (independent of the items that are replenished) and a minor ordering cost ai for each item i included in the replenishment. The cycle time for every item is an integer multiple mi of the replenishment basic cycle time T. Thus, the cycle time for item i is Ti=miT, and the order quantity for item i is Qi=Tidi=Tmidi. The objective of the JRP is to develop inventory policies so as to minimize the total annual costs. The problem involves determining the basic cycle time T and the integer multiples mi for each item i. Let M=(m1,m2,…,mN) be the replenishment frequency vector and let C(T,M) be the objective annual cost function, including the holding and ordering costs, which can be expressed as
(1)C(T,M)=1T(A+∑i=1Naimi)+∑i=1NmidihiT2.


## 3. Cycle Time Division Method

For any fixed vectorM,C(T,M) is convex in T, since
(2)∂2C(T,M)∂T2=2T3(A+∑i=1Naimi)>0.
Setting ∂C(T,M)/∂T to zero and solving it for T(M) with fixed vector M, it follows that
(3)T(M)=2(A+∑i=1Nai/mi)∑i=1Nmidihi.
Substituting back optimal T(M) into (1), the total cost function can be expressed as
(4)C(M)=2(A+∑i=1Naimi)(∑i=1Nmidihi).
For a given basic cycle time T, the associated ordering costs decrease with increasing the frequency of ordering items. However, the inventory level and holding cost inevitably increase accordingly. Therefore, a decision regarding the integer multiples involves a tradeoff between the holding and ordering costs. Consequently (for item j), for each pair of mj and mj+1, define T=Tj,mjs such that
(5)C(Tj,mjs,m1,m2,…,mj,…,mN)=C(Tj,mjs,m1,m2,…,mj+1,…,mN)
or
(6)ajTj,mjsmj+Tj,mjsmjdjhj2=ajTj,mjs(mj+1)+Tj,mjs(mj+1)djhj2
as a critical cycle time. A given item j may have multiple critical cycle times.Solve forTj,mjs then;
(7)Tj,mjs=2aj((1/mj)-(1/(mj+1)))hjdj.
Additionally, the difference in the objective cost function between mj and (mj+1) is
(8)C(T,m1,m2,…,mj,…,mN)-C(T,m1,m2,…,mj+1,…,mN)=ajT(1mj-1mj+1)-Tdjhj2.
Taking partial derivative of this difference with respect to T, then
(9)∂[C(T,m1,…,mj,…,mN)00-C(T,m1,…,mj+1,…,mN)]×(∂T)-1=-ajT2[1mj-1mj+1]-djhj2<0.
Since C(Tj,mjs,m1,…,mj,…,mN)=C(Tj,mjs,m1,…,mj+1,…,mN) and ∂[C(T,m1,…,mj,…,mN)-C(T,m1,…,mj+1,…,mN)]/∂T<0, it follows that(a)
C(T,m1,…,mj,…,mN)>C(T,m1,…,mj+1,…,mN) for T<Tj,mjs;(b)
C(T,m1,…,mj,…,mN)<C(T,m1,…,mj+1,…,mN) for T>Tj,mjs.Hence, the following lemma is obtained.Lemma 1.
For multiple items jointly replenished, if basic cycle timeT is greater than the critical cycle time Tj,mjs, then mj is chosen as the frequency of ordering item j; otherwise, (mj+1) is selected as the frequency of ordering item j.Applying results from the study of [13], the lower bound for cycle time is TL=min{ai/dihi,i=1,2,…,N}. Therefore, for j=1,2,…,N, use (7) to find all critical cycle is times Tj,mjs, namely, Tj,1s, Tj,2s, and so on, until the resulting critical cycle time less than TL for each item. Let Tj,mj(max)s be the smallest critical cycle time for item j then there are decreasing sequential critical cycle times Tj,1s, and Tj,2s,…, Tj,mj(max)-1s, Tj,mj(max)s, where Tj,mj(max)-1s≥TL and Tj,mj(max)s<TL for item j. Merge the critical cycle times for all items to establish an ordered critical cycle time vector S=(s1,s2,…,sNc) such that s1≥s2≥⋯≥sNc, where sNc=max{Tj,mj(max)s,j=1,2,…,N}. Let RG1=(r1,1) be the first cycle time range, where r1=s1. If the basic cycle time T falls in RG1, then T>Ti,1s, for i=1,2,3,…,N. Moreover, since r1 is the largest among the critical cycle time for all items, the local optimal integer multiples for every item is 1; that is, M1=(1,1,…,1) is the local optimal replenishment frequency vector for this case according to Lemma 1.Next, constructRG2=[r2,r1] where r2=s2. If r2 (or s2) and r1 are the respective critical cycle times for items j and k, define M'=(0,…,0,1,0,…,0), where the only non-zero element of M' occurs in the jth position. Suppose the basic cycle time T lies in RG2, then Tj,1s≥T and T≥Ti,1s, for i=1,2,…,N, and i≠j. In this case, the local optimal integer multiples for item j is increased to two, while the local optimal integer multiples for the other items remain at one; thus M2=M1+M', and the corresponding local optimal replenishment frequency vector is M2. This process is continued and the local optimal replenishment frequency vector Mi is obtained for the cycle time range RGi, for i=1,2,…,Nc, provided the critical order intervals differ for all items.Givensi+1=si and si+1>si+2,where si and si+1 are the critical cycle times for items e and f, respectively, the aforementioned procedure is modified slightly as follows. Let RGi+1=[ri+1,ri], M'=(0,…,0,1,0,…,0,1,0,…,0), and Mi+1=Mi+M', where ri+1=si+2, ri=si, and the two 1’s of M'occupy the eth and fth positions, respectively. Thus, the local optimal replenishment frequency vector is Mi+1 for the situation where the basic cycle time T falls within the range RGi+1. A similar modification is performed if more than two critical cycle times are equal.Upon the completion of the procedure, there existsU resulting cycle time ranges RG1,RG2,…,RGU  with respective associated replenishment frequency vectors M1,M2,…,MU, where U≤Nc.


## 4. Recursive Tightening Method

Clearly, at least one element inMi+1 is greater than that in Mi at the same position. An application of (3) yields T(Mi)>T(Mi+1). Consequently, the following lemma is obtained.Lemma 2.
For multiple items jointly replenished,T(Mi)>T(Mi+1).Next, two properties are established to identify the candidate replenishment frequency vectors for the problem being investigated.Theorem 3.
For multiple items jointly replenished, if the basic cycle timeT(Mi) obtained by (3) does not lie within its associated cycle time range RGi but rather lies in the range RGj=[rj,rj-1], where i<j, then C(T(Mi),Mi)>C(T(Mi),Mj). Consequently, none of the replenishment frequency vector Mi,Mi+1,…, or Mj-1 is the global optimal replenishment frequency vector, and none of T(Mi),T(Mi+1),…, or T(Mj-1) is the global optimal cycle time.Proof.
Let the corresponding replenishment frequency vector ofRGi be Mi=(m(i)1,m(i)2,…,m(i)N), and let that of RGj be Mj=(m(j)1,m(j)2,…,m(j)N), where i<j. From the construction of Mi and Mj, it is evident that m(i)1≤m(j)1,m(i)2≤m(j)2,…, and m(i)n≤m(j)N. Consider RGi=[ri,ri-1] and its adjacent cycle time range RGi+1=[ri+1,ri]. It is known that T(Mi) does not lie within RGi but rather lies in RGj, where i<j, so we have T(Mi)<ri. With very few distinctions (at least one), most of the elements of Mi and Mi+1 are the same. For the sake of simplicity, assume that there is only one element different from Mi and Mi+1, and let it be the kth element or m(i)k+1=m(i+1)k. Since T(Mi)<ri, according to Lemma 1, m(i+1)k is chosen as the integer multiples for item k; consequently, C(T(Mi),Mi)>C(T(Mi),Mi+1). Similarly, C(T(Mi),Mi+1)>C(T(Mi),Mi+2), and C(T(Mi),Mi+2)>C(T(Mi),Mi+3),…, C(T(Mi),Mj-1)>C(T(Mi),Mj). Hence, it follows that C(T(Mi),Mi)>C(T(Mi),Mj).
From Lemma2, it is known that T(Mi)>T(Mi+1)>⋯>T(Mj-1)>T(Mj), where i<j. Suppose that T(Mi+1),…,T(Mj-1), and T(Mj) lie in the cycle time ranges RGw=[rw,rw-1],…,RGy=[ry,ry-1], and RGz=[rz,rz-1], respectively, where i≤j-1<j≤w≤⋯≤y≤z. From Lemma 1, it has been shown that C(T(Mi),Mi)>C(T(Mi),Mj), C(T(Mi+1),Mi+1)>C(T(Mi+1),Mw),…, C(T(Mj-1),Mj-1)>C(T(Mj-1),My) and C(T(Mj),Mj)≥C(T(Mj),Mz). Hence, none of Mi,Mi+1,…,Mj-2, and Mj-1 is the global optimal replenishment frequency vector.
Again by Lemma2, we have (Mz)≤T(My)≤T(Mw)≤T(Mj)<T(Mj-1)<⋯<T(Mi+1)<T(Mi). Therefore, it follows that C(T(Mi),Mj)>C(T(Mj),Mj), C(T(Mi+1),Mw)>C(T(Mw),Mw),…, C(T(Mj-1),My)>C(T(My),My), and C(T(Mj),Mz)≥C(T(Mz),Mz). Hence, none of T(Mi),T(Mi+1),…,T(Mj-2) and T(Mj-1) is the global optimal cycle time.Theorem 4.
For multiple items jointly replenished, if the basic cycle timeT(Mi) calculated by (3) does not lie within its associated cycle time range RGi but rather lies in the range RGj=[rj,rj-1], where j<i, then C(T(Mi),Mi)>C(T(Mi),Mj). Consequently, none of the vectors Mj+1,Mj+2,…,Mi-1, or Mi is the global optimal replenishment frequency vector and none of T(Mj+1),T(Mj+2),…,T(Mi-1), or T(Mi) is the global optimal cycle time.Proof.
Similar to the proof of Theorem3.Next, we use Theorems3 and 4 to explain how to find the optimal T and Mi. Since the minimal integer multiples for each item are one, M1 is used in (3) to calculate the maximal cycle time as follows:
(10)Tmax(M1)=2(A+∑i=1Nai)∑i=1Ndihi.Suppose that the maximal cycle timeTmax(M1) falls in RGi=[ri,ri-1]. If i=1, then set Mmin=M1,Tmax=T(Mmin) and stop. Otherwise, consider the situation where i>1. From Theorem 3, none of the replenishment frequency vectors M1,M2,…, and Mi-1 provides a solution for the global optimal integer multiples, and none of T(M1),T(M2),…,T(Mi-2), and T(Mi-1) is the global optimal cycle time. The resulting minimal replenishment frequency vector Mi is designated as Mmin. Next, Mmin is used in (3) to calculate the cycle time T(Mmin), while RGj=[rj,rj-1] and Mj denote its associated cycle time range and replenishment frequency vector. If Mmin=Mj, then stop; otherwise, set Mmin equal to Mj and repeat the procedure until the aforementioned stopping criterion is reached. This process is termed the downward recursive tightening procedure while the resulting Mmin is an upper bound of the candidate vector set.The same approach can be applied in the opposite direction to determine the lower bound of the candidate vector set.MU is used in (3) to calculate the minimal cycle time Tmin(MU). Suppose the resulting Tmin(MU) falls in RGi=[ri,ri-1], where i<U. From Theorem 4, none of the replenishment frequency vectors MU,MU-1,…,Mi+2, and Mi+1 provides a solution for the global optimal integer multiples, and none of T(MU),T(MU-1),…,T(Mi+2) and T(Mi+1) is the global optimal cycle time. The associated replenishment frequency vector Mmax is set equal to Mi and Mmax is used in (3) to compute T(Mmax), while RGj=[rj,rj-1] and Mj denote the associated cycle time range and replenishment frequency vector. If Mmax=Mj, then stop; otherwise, set Mmax equal to Mj and repeat the procedure until the stopping criterion is satisfied and the resulting Mmax yielded is the lower bound of the candidate vector set. This approach is termed the upward recursive tightening procedure.Finally, the replenishment frequency vectors between the lower and the upper bounds of the candidate vector set are compared for optimality.


## 5. Optimization Algorithm

The following procedure integrates the cycle time division and the recursive tightening methods to obtain the optimal values ofT and M for the problem being studied.Step 1.
SetTL=min{ai/dihi,i=1,2,…,N}.Step 2.
Forj=1,2,…,N, do(a)
setmj=1.(b)
compute the critical cycle timeTj,mjsusing (7);(c)
ifTj,mjs≥TL, then setmj=mj+1; go to Step2(b); else setmj(max)=mj.Step 3.
Merge all the critical cycle times to establish a critical cycle time vectorS=(s1,s2,…,sNc) such that s1≥s2≥⋯≥sNc, where sNc=max{Tj,mj(max)s,j=1,2,…,N} and Nc≤∑j=1Nmj(max). Construct vector B=(bk) such that bk is the item number with which rk is associated for k = 1, 2, …, Nc.Step 4.
SetM1=(1,1,…,1), M'=0, k=1, r1=s1, and RG1=(r1,1).Step 5.
Forj=2,3,…,Nc, (a)
setM''=(0,…,0,1,0,…,0), where the only non-zero element of M'' is in the (bj-1)th position.(b)
ifsj-1>sj, then set rk+1=sj, RGk+1=[rk+1,rk], and Mk+1=Mk+M'+M'', k=k+1,M′=0;
else setM'=M'+M''.Step 6.
SetMU=Mk.Step 7.
UseM1 in (10) to calculate Tmax(M1) and obtain its associated replenishment frequency vector Mmin.Step 8.
IfMmin=M1, then set Tmax=Tmax(M1), e=1, and go to Step 11.Step 9.
UseMmin and (3) to calculate T(Mmin).Step 10.
IfM'=Mmin, then set Tmax=T(Mmin), e = the index of the cycle time range in which T(Mmin) falls, and go to Step 11;
else setMmin=M' and go to Step 9.Step 11.
UseMU in (3) to find Tmin(MU) and identify its associated replenishment frequency vector Mmax.Step 12.
IfMmax=MU, then set Tmin = Tmin(MU), f=U, and go to Step 15.Step 13.
UseMmax in (3) to calculate T(Mmax) and its associated replenishment frequency vector M'.Step 14.
IfM'=Mmax, then set Tmin=T(Mmax), f = the index of the cycle time range in which T(Mmax) falls, and go to Step 15;
else setMmax=M',and go to Step 13.Step 15.
FindC(T*,M*)=Min{C(Ti,Mi), i=e,e+1,…,f-1,f, where Mi is the candidate replenishment frequency vector}.Step 16.
T
* and M* are the optimal solutions with the optimal objective function of C(T*,M*).The complexity of the algorithm is analyzed as follows. SupposeN items in the jointly replenished system, where item j has mj critical cycle times, and m¯=(1/N)∑j=1Nmj. Thus the complexity involved in finding the critical cycle times for all items is O(Nm¯), or simply O(N). Forming the critical cycle time vector R requires O(NlogN) operations, and the complexity involved in generating the cycle time ranges is O(N). The recursive tightening procedure uses O(N) operations to identify the lower and upper bounds of the candidate vector set and O(N) operations to identify the optimum in the candidate vector set. Thus, the complexity of the overall solution procedure is O(NlogN).


## 6. Numerical Examples

Example 1.
Consider a multi-item inventory system with seven items involving the data summarized in Table1. The proposed algorithm is applied. In Step 1, TL=0.0516. The resulting critical cycle times of each item are listed in Table 2. Furthermore, Table 3 lists the cycle time ranges established by merging all the critical cycle times and the associated replenishment frequency vectors found.Table 1
Data of Example1 (the parameter’s values are adopted from [31]).
Items
A
=
30
d
j
a
j
h
j
Item 1
2500
20.0
3.0
Item 2
300
4.5
2.5
Item 3
700
15.0
2.0
Item 4
225
22.0
5.0
Item 5
650
15.0
1.0
Item 6
150
14.0
2.0
Item 7
100
9.5
1.5Table 2
The critical cycle times of Example1.
j
1
2
3
4
5
6
7
T
1
,
j
s
0.0516
0.0298
—
—
—
—
—
T
2
,
j
s
0.0775
0.0447
—
—
—
—
—
T
3
,
j
s
0.1035
0.0598
0.0423
—
—
—
—
T
4
,
j
s
0.1398
0.0807
0.0571
0.0442
—
—
—
T
5
,
j
s
0.1519
0.0877
0.0620
0.0480
—
—
—
T
6
,
j
s
0.2160
0.1247
0.0882
0.0683
0.0558
0.0471
—
T
7
,
j
s
0.2517
0.1453
0.1027
0.0796
0.0650
0.0549
0.0476Table 3
The cycle time ranges and associated replenishment frequency vectors for Example1.
i
r
i
M
i
i
r
i
M
i
1
0.2517
1, 1, 1, 1, 1, 1, 2
12
0.0796
1, 1, 2, 3, 3, 4, 5
2
0.2160
1, 1, 1, 1, 1, 2, 2
13
0.0775
1, 2, 2, 3, 3, 4, 5
3
0.1519
1, 1, 1, 1, 2, 2, 2
14
0.0683
1, 2, 2, 3, 3, 5, 5
4
0.1453
1, 1, 1, 1, 2, 2, 3
15
0.0650
1, 2, 2, 3, 3, 5, 6
5
0.1398
1, 1, 1, 2, 2, 2, 3
16
0.0620
1, 2, 2, 3, 4, 5, 6
6
0.1247
1, 1, 1, 2, 2, 3, 3
17
0.0598
1, 2, 3, 3, 4, 5, 6
7
0.1035
1, 1, 2, 2, 2, 3, 3
18
0.0571
1, 2, 3, 4, 4, 5, 6
8
0.1027
1, 1, 2, 2, 2, 3, 4
19
0.0558
1, 2, 3, 4, 4, 6, 6
9
0.0882
1, 1, 2, 2, 2, 4, 4
20
0.0549
1, 2, 3, 4, 4, 6, 7
10
0.0877
1, 1, 2, 2, 3, 4, 4
21
0.0516
2, 2, 3, 4, 4, 6, 7
11
0.0807
1, 1, 2, 3, 3, 4, 4
22
0.0480
2, 2, 3, 4, 5, 6, 7Starting withM1 = (1, 1, 1, 1, 1, 1, 1), the upper bound candidate replenishment frequency vector identified via the downward recursive tightening procedure is M7= (1, 1, 1, 2, 2, 3, 3) as illustrated in Table 4. Similarly, the lower bound candidate replenishment frequency vector identified via the upward recursive tightening procedure is also M7 = (1, 1, 1, 2, 2, 3, 3). This indicates that the optimal replenishment frequency vector M* is M7 = (1, 1, 1, 2, 2, 3, 3) with optimal basic cycle time of T*=0.1148 time units and the corresponding optimal objective function of C(T*,M*) = $1669.96/time unit. This solution is the best solution our procedure can find and also in this case the optimal solution of the problem (can be verified using for instance Goyal [18] and Nilsson et al. [31]).Table 4
The results of the recursive tightening procedures for Example1.
i
RG
i
M
i
T
(
M
i
)
C
(
T
(
M
i
)
,
M
i
)
1
0.2517
1
1, 1, 1, 1, 1, 1, 1
0.1480
1757.13
4
0.1453
0.1519
1, 1, 1, 1, 2, 2, 2
0.1307
1695.28
6
0.1247
0.1398
1, 1, 1, 2, 2, 2, 3
0.1174
1672.65
7
0.1035
0.1247
1, 1, 1, 2, 2, 3, 3LU*
0.1148
1669.96
9
0.0882
0.1027
1, 1, 2, 2, 2, 3, 4
0.1043
1678.94
16
0.0620
0.0650
1, 2, 2, 3, 3, 5, 6
0.0885
1728.01
22
0.0480
0.0516
2, 2, 3, 4, 4, 6, 7
0.0627
1920.85
LLower bound, *optimal solution, Uupper bound.Example 2.
Consider a multi-item inventory system with fourteen items involving the data listed in Table5. The proposed algorithm is performed. In Step 1, TL = 0.0516. The resulting critical cycle times of each item are listed in Table 6. The cycle time ranges formed by merging all the critical cycle times and the associated replenishment frequency vectors found are listed in Table 7.Table 5
The data of Example2.
Items
A
=
30
d
j
a
j
h
j
Item 1
2500
20.0
3.0
Item 2
300
4.5
2.5
Item 3
700
15.0
2.0
Item 4
225
22.0
5.0
Item 5
650
15.0
1.0
Item 6
150
14.0
2.0
Item 7
100
9.5
1.5
Item 8
250
10.0
3.0
Item 9
350
12.0
2.0
Item 10
520
18.0
3.0
Item 11
345
8.0
2.0
Item 12
700
11.0
3.5
Item 13
200
10.0
4.0
Item 14
110
7.0
2.5Table 6
The critical cycle times of Example2.
j
1
2
3
4
5
6
7
T
1
,
j
s
0.0516
0.0298
—
—
—
—
—
T
2
,
j
s
0.0775
0.0447
—
—
—
—
—
T
3
,
j
s
0.1035
0.0598
0.0423
—
—
—
—
T
4
,
j
s
0.1398
0.0807
0.0571
0.0442
—
—
—
T
5
,
j
s
0.1519
0.0877
0.0620
0.0480
—
—
—
T
6
,
j
s
0.2160
0.1247
0.0882
0.0683
0.0558
0.0471
—
T
7
,
j
s
0.2517
0.1453
0.1027
0.0796
0.0650
0.0549
0.0476
T
8
,
j
s
0.1155
0.0667
0.0471
—
—
—
—
T
9
,
j
s
0.1309
0.0756
0.0535
0.0414
—
—
—
T
10
,
j
s
0.1074
0.0620
0.0439
—
—
—
—
T
11
,
j
s
0.1077
0.0622
0.0440
—
—
—
—
T
12
,
j
s
0.0670
0.0387
—
—
—
—
—
T
13
,
j
s
0.1118
0.0645
0.0456
—
—
—
—
T
14
,
j
s
0.1595
0.0921
0.0651
0.0505
—
—
—Table 7
The cycle time ranges and associated replenishment frequency vectors for Example2.
i
r
i
M
i
1
0.2517
1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1
2
0.2160
1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1
3
0.1595
1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 2
4
0.1519
1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2
5
0.1453
1, 1, 1, 1, 2, 2, 3, 1, 1, 1, 1, 1, 1, 2
6
0.1398
1, 1, 1, 2, 2, 2, 3, 1, 1, 1, 1, 1, 1, 2
7
0.1309
1, 1, 1, 2, 2, 2, 3, 1, 2, 1, 1, 1, 1, 2
8
0.1247
1, 1, 1, 2, 2, 3, 3, 1, 2, 1, 1, 1, 1, 2
9
0.1155
1, 1, 1, 2, 2, 3, 3, 2, 2, 1, 1, 1, 1, 2
10
0.1118
1, 1, 1, 2, 2, 3, 3, 2, 2, 1, 1, 1, 2, 2
11
0.1077
1, 1, 1, 2, 2, 3, 3, 2, 2, 1, 2, 1, 2, 2
12
0.1074
1, 1, 1, 2, 2, 3, 3, 2, 2, 2, 2, 1, 2, 2
13
0.1035
1, 1, 2, 2, 2, 3, 3, 2, 2, 2, 2, 1, 2, 2
14
0.1027
1, 1, 2, 2, 2, 3, 4, 2, 2, 2, 2, 1, 2, 2
15
0.0921
1, 1, 2, 2, 2, 3, 4, 2, 2, 2, 2, 1, 2, 3
16
0.0882
1, 1, 2, 2, 2, 4, 4, 2, 2, 2, 2, 1, 2, 3
17
0.0877
1, 1, 2, 2, 3, 4, 4, 2, 2, 2, 2, 1, 2, 3
18
0.0807
1, 1, 2, 3, 3, 4, 4, 2, 2, 2, 2, 1, 2, 3
19
0.0796
1, 1, 2, 3, 3, 4, 5, 2, 2, 2, 2, 1, 2, 3
20
0.0775
1, 2, 2, 3, 3, 4, 5, 2, 2, 2, 2, 1, 2, 3
21
0.0756
1, 2, 2, 3, 3, 4, 5, 2, 3, 2, 2, 1, 2, 3
22
0.0683
1, 2, 2, 3, 3, 5, 5, 2, 3, 2, 2, 1, 2, 3
23
0.0670
1, 2, 2, 3, 3, 5, 5, 2, 3, 2, 2, 2, 2, 3
24
0.0667
1, 2, 2, 3, 3, 5, 5, 3, 3, 2, 2, 2, 2, 3
25
0.0651
1, 2, 2, 3, 3, 5, 5, 3, 3, 2, 2, 2, 2, 4
26
0.0650
1, 2, 2, 3, 3, 5, 6, 3, 3, 2, 2, 2, 2, 4
27
0.0645
1, 2, 2, 3, 3, 5, 6, 3, 3, 2, 2, 2, 3, 4
28
0.0622
1, 2, 2, 3, 3, 5, 6, 3, 3, 2, 3, 2, 3, 4
29
0.0620
1, 2, 2, 3, 4, 5, 6, 3, 3, 2, 3, 2, 3, 4
30
0.0620
1, 2, 2, 3, 4, 5, 6, 3, 3, 3, 3, 2, 3, 4
31
0.0598
1, 2, 3, 3, 4, 5, 6, 3, 3, 3, 3, 2, 3, 4
32
0.0571
1, 2, 3, 4, 4, 5, 6, 3, 3, 3, 3, 2, 3, 4
33
0.0558
1, 2, 3, 4, 4, 6, 6, 3, 3, 3, 3, 2, 3, 4
34
0.0549
1, 2, 3, 4, 4, 6, 7, 3, 3, 3, 3, 2, 3, 4
35
0.0535
1, 2, 3, 4, 4, 6, 7, 3, 4, 3, 3, 2, 3, 4
36
0.0516
2, 2, 3, 4, 4, 6, 7, 3, 4, 3, 3, 2, 3, 4
37
0.0505
2, 2, 3, 4, 4, 6, 7, 3, 4, 3, 3, 2, 3, 5Starting withM1 = (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1), the upper bound candidate replenishment frequency vector identified via the downward recursive tightening procedure is M9= (1, 1, 1, 2, 2, 3, 3, 1, 2, 1, 1, 1, 1, 2) as shown in Table 8. Similarly, the lower bound candidate replenishment frequency vector identified via upward the recursive tightening procedure is M15 = (1, 1, 2, 2, 2, 3, 4, 2, 2, 2, 2, 1, 2, 2). Between the lower and upper bounds, M10, M11, M12,M13, and M14 are not the candidate replenishment frequency vectors (it is becuase the corresponding cycle time is not falling in the range that determines Mi). Comparison of the objective function of the replenishment frequency vectors in the candidate vector set of {M9,M15} indicates that the optimal replenishment frequency vector M* is M15 = (1, 1, 2, 2, 2, 3, 4, 2, 2, 2, 2, 1, 2, 2) with optimal basic cycle time of T*=0.0966 time units, and the corresponding optimal objective function of C(T*,M*)= $2713.77/time unit.Table 8
The results of the recursive tightening procedures for Example2.
i
RG
i
M
i
T
(
M
i
)
C
(
T
(
M
i
)
,
M
i
)
1
0.2517
1
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
0.1469
2805.21
5
0.1453
0.1519
1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2
0.1338
2739.36
7
0.1309
0.1398
1, 1, 1, 2, 2, 2, 3, 1, 1, 1, 1, 1, 1, 2
0.1253
2724.70
8
0.1247
0.1309
1, 1, 1, 2, 2, 2, 3, 1, 2, 1, 1, 1, 1, 2
0.1211
2719.11
9
0.1155
0.1247
1, 1, 1, 2, 2, 3, 3, 1, 2, 1, 1, 1, 1, 2U
0.1195
2717.75
10
0.1118
0.1155
1, 1, 1, 2, 2, 3, 3, 2, 2, 1, 1, 1, 1, 2NC
0.1157
2719.31
11
0.1077
0.1118
1, 1, 1, 2, 2, 3, 3, 2, 2, 1, 1, 1, 2, 2NC
0.1120
2720.92
12
0.1074
0.1077
1, 1, 1, 2, 2, 3, 3, 2, 2, 1, 2, 1, 2, 2NC
0.1090
2722.81
13
0.1035
0.1074
1, 1, 1, 2, 2, 3, 3, 2, 2, 2, 2, 1, 2, 2NC
0.1024
2720.04
14
0.1027
0.1035
1, 1, 2, 2, 2, 3, 3, 2, 2, 2, 2, 1, 2, 2NC
0.0971
2714.68
15
0.0921
0.1027
1, 1, 2, 2, 2, 3, 4, 2, 2, 2, 2, 1, 2, 2L*
0.0966
2713.77
18
0.0807
0.0877
1, 1, 2, 2, 3, 4, 4, 2, 2, 2, 2, 1, 2, 3
0.0928
2720.68
22
0.0683
0.0756
1, 2, 2, 3, 3, 4, 5, 2, 3, 2, 2, 1, 2, 3
0.0857
2748.10
32
0.0571
0.0598
1, 2, 3, 3, 4, 5, 6, 3, 3, 3, 3, 2, 3, 4
0.0695
2856.13
37
0.0505
0.0516
2, 2, 3, 4, 4, 6, 7, 3, 4, 3, 3, 2, 3, 4
0.0581
2953.51
LLower bound, *optimal solution, Uupper bound, NCnoncandidate.Comparing Examples1 and 2 reveals that the number of critical cycle times increases with increasing number of items. Again, the results from Tables 3 and 7 indicate that the number of cycle time regions generated increases with increasing number of critical cycle times; however, the span of each cycle time region is inevitably reduced. A reduction in the span of a cycle time region may eventually lessen its probability of containing the T(M) computed via (3). As a result, the RT procedures generate 1 and 2 candidate replenishment frequency vectors in Examples 1 and 2, respectively. Restated, the larger the number of items involved in a distribution system, the better the efficiency of the proposed algorithm.


## 7. Concluding Remarks

This work studies the joint replenishment problem involving multiple items where economies can be achieved by replenishing several items simultaneously. To solve the problem being studied, this study devises a cycle time division method for establishing a set of ranges that contain the optimal cycle time and corresponding optimal replenishment frequency vector of the problem and subsequently develops a recursive tightening procedure to further reduce the set of replenishment frequency vectors to facilitate the search for the optimal cycle time and associated replenishment frequency for each item. The proposed solution procedure has a polynomial complexity ofO(NlogN), where N denotes the number of items involved in the problem. Two theorems are proven, thus guaranteeing that an optimal solution to the problem can be obtained using cycle time division and recursive tightening. Restated, CTD and RT methods theoretically can achieve the optimal solution in all cases. In addition, in comparison with the heuristic method proposed by Nilsson et al. [31], our new method performs uninterestingly and complexly. However, comparing with many newer heuristic methods, we argue that the optimal solution searching is guaranteed to this new method, and the larger the number of items the system involved, the better the efficiency this novel method had.



---

*Source: 469794-2013-11-26.xml*