# Supply Chain Batching Problem with Identical Orders and Lifespan

Authors: Shanlin Li; Maoqin Li; Hong Yan
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

In the real world, there are a large number of supply chains that involve the short lifespan products. In this paper, we consider an integrated production and distribution batch scheduling problem on a single machine for the orders with a short lifespan, because it may be cheaper or faster to process and distribute orders in a batch than to process and distribute them individually. Assume that the orders have the identical processing time and come from the same location, and the batch setup time is a constant. The problem is to choose the number of batches and batch sizes to minimize the total delivery time without violating the order lifespan. We first give a backward dynamic programming algorithm, but it is not an actually polynomial-time algorithm. Then we propose a constant time partial dynamic programming algorithm by doing further research into the recursion formula in the algorithm. Further, using the difference characteristics of the optimal value function, a specific calculating formula to solve the problem with the setup time being integer times of the processing time is obtained.


---

## Body

## 1. Introduction

In the past two decades, research in the area of supply chain management (SCM) has increased significantly. An important aspect of SCM concerns integrated planning of production and distribution processes since the increasing globalization and strong competition force companies not only to compete with others with regard to prices or quality, but with regard to reliability and timeliness of the deliveries as well. Thus, a coordinated planning of production and transportation is vital for the success of a business; especially if products with short lifespans are involved, the coordination of related operations becomes a challenging issue, such as food (Tarantilis and Kiranoudis [1]; Arbib et al. [2]; Chen et al. [3]; Farahani et al. [4]; Méndez et al. [5]; Amorim et al. [6]; Bilgen and Günther [7]; Kaplan and Rabadi [8]; Shirvani et al. [9]), yoghurt products (Kopanos et al. [10]; Bilgen and Çelebi [11]), industrial chemicals (Geismar et al. [12]; Armstrong et al. [13]; Viergutz and Knust [14]), ready-mix concrete (García et al. [15]; Garcia and Lozano [16, 17]), medical specimens (Zangeneh-Khamooshi et al. [18]), or also daily newspapers (van Buer et al. [19]). The integrated production and distribution scheduling problems can be classified into two types based on whether there is a lifespan as the specific parameter of the problem. Since the focus of this paper is on problems with lifespan constraints, we do not review papers that study problems without lifespan constraints, which can be found in Chen [20].Chen et al. [3] consider production scheduling and vehicle routing with time windows for perishable food products to maximize the expected total profit of the supplier. The demands at retailers are assumed stochastic and perishable goods will deteriorate once they were produced. They propose a nonlinear mathematical model, which is NP-hard, and give a solution algorithm composed of the constrained Nelder-Mead method and a heuristic for the vehicle routing with time windows to solve the complex problem. Farahani et al. [4] study a similar problem but with multiple production lines and sequence dependent setup times and costs. The production scheduling problem is solved through an mixed-integer linear programming modeling approach which is based on a block planning formulation.Méndez et al. [5] and Amorim et al. [6] study the integrated batch scheduling and vehicle routing problem and the integrated lot sizing and scheduling and vehicle routing problem for perishable goods respectively. They propose mixed-integer programming models and analyse computational results of the models, respectively.Bilgen and Günther [7] present an integrated production scheduling and truck routing model for a fruit juice supply chain. They considered different transportation modes and described the production system based on the block planning approach which establishes cyclical production patterns with regard to the definition of setup families.Kaplan and Rabadi [8] focus on the scheduling of perishable products on parallel machines. Each job has a due date, which is the preferred delivery date of the retailers and might be violated subject to a penalization as lateness penalty, and there is a strict deadline imposed by the retailer that should not be exceeded. The objective is to minimize the total penalty cost. They propose a mixed-integer programming model and analyse computational results of the model. Shirvani et al. [9] study a similar problem but with job dependent holding cost. They propose also a mixed integer programming model and a heuristic solution beside an iterated greedy algorithm is developed to generate good and feasible solutions for the problem.Kopanos et al. [10] consider production scheduling and distribution planning in the yoghurt processing industry with the limited shelf life of intermediate mixes in the aging stage. The model proposed by them decides the assignment of transportation trucks to processing sites-distribution center in every period as well as transportation load for every truck. They impose material balance and logistics operations constraints. Three different transportation modes and min/max truck capacity are taken into consideration. Bilgen and Çelebi [11] study a similar problem but with maximizing the benefit by considering the shelf life dependent pricing component and costs such as processing, setup, storage, overtime, backlogging, and transportation costs. A mixed-integer linear programming model is developed for the considered problem. The efficiency and applicability of the proposed model and approach are demonstrated in a case study for a dairy manufacturing company in Turkey.Motivated by applications of certain time-sensitive chemical compounds, Geismar et al. [12], Armstrong et al. [13], and Viergutz and Knust [14] consider problems where orders expire within a certain time frame once they are produced and hence must be delivered before they expire. In Geismar et al.’s problem, orders to be delivered in the same batch are produced as a lot together and once a lot is completed the shipment must depart immediately and deliver the orders to their destinations within a given time frame. They propose a metaheuristic for this strongly NP-hard problem and evaluate the performance of the heuristic computationally. In the Armstrong et al.’s problem, all the orders are processed and delivered in a single shipment in a prespecified sequence. In addition to a common expiration time frame, each order has an individual time window within which the order must be delivered. The objective is to choose a subset of the orders to be delivered such that the total demand of the chosen orders is maximized. The authors show that their problem is at least ordinarily NP-hard and give a branch-and-bound exact algorithm and a heuristic for the problem. Viergutz and Knust’s problem is similar to Armstrong et al.’s. They refine the Armstrong et al.’s algorithm and extend the model for handling delays of the production start as well as for variable production and distribution sequences and give heuristic and evaluate their performance computationally.Garcia and Lozano [16] consider a ready-mix concrete production and vehicle scheduling problem with identical parallel machines and multiple customers. They give a new approach for constructing the min-cost network flow problem. They also consider a dual problem with the objective of minimizing the number of vehicles used subject to the constraint that a given number of orders are covered. They give an exponential-time exact solution approach and a partial branch and bound heuristic. More specifically, Garcia and Lozano [17] study a similar problem but with an ideal due date for each order. The revenue of a delivered order decreases with the deviation from the ideal due date. This problem is strongly NP-hard. They give a tabu search based heuristic.Zangeneh-Khamooshi et al. [18] consider a medical specimens collection problem with a central depot and multiple customers which is modeled as a multishift vehicle routing problem with windows and cycle times, which is a strongly NP-hard problem. They give an new version of the vehicle routing problem with time windows that minimizes the total cycle time of the orders. When the courier’s schedule is allowed to vary, they propose an algorithm to determine feasible routes and schedules of the available couriers and evaluate their performance computationally.van Buer et al. [19] consider a newspaper printing and delivery problem with a single machine and multiple customers. There are sequence-dependent setup times between orders in the production part and each order has a delivery deadline that must be met. There is a fixed cost for using a vehicle and a vehicle if used can be used to cover multiple trips. The objective is to minimize the total fixed and variable transportation cost. The authors give several heuristics and evaluate their performance computationally.In this paper, we study a supply chain involving the product with a short lifespan which consists of a plant and a set of customer groups, where the production facility of the plant consists of a single machine and the set of customer groups comes from the same location (e.g., a distribution hub). At the single machine a single product with a limited lifespan is produced. The product lifespan specifies that the product expires after the end of its production. The orders of the product from all of customers are identical. Our problem is to schedule and deliver these identical orders in batches, since it may be cheaper or faster to process and deliver orders in a batch than to process and deliver them individually. A setup time is required at the start of the schedule and on each occasion when the machine switches from processing orders in one batch to orders in another batch (e.g., the time of changing a tool or to clean the machine). The delivery time of an order coincides with the delivery time of the last scheduled orders in its batch and all orders in this batch have the same delivery time. For a given number of orders, we want to choose batch sizes so as to minimize the sum of the delivery times of the orders without violating the order lifespan.Formally, there is a set ofn orders from the same location with identical processing time p and a limited lifespan L, J={j1,…,jn}={1,…,n}, to be processed on a single machine. In a given schedule, for each job j∈J, we denote Cj to be its completion time and Dj=Cj+T delivery time of order j, where T is the transportation time from the plant to order j’s destination. The problem is, given a setup time S, to find the number of batches k and batch sizes bi satisfying ∑i=1kbi=n, so as to minimize ∑j=1nDj=∑j=1n(Cj+T)=∑i=1kbi∑j=1i(S+bjp)+nT without violating the order lifespan, where all of p, L, T, and S are positive integers.In a given batch schedule, to respect the lifespan constraint of the order, it is necessary that(bi-1)p+T≤L for each batch sizes bi, where (bi-1)p+T is the time from the completion time point of the first scheduled order in ith batch to its delivery time point. Let B denote the maximal integer less than or equal to rational number (L-T)/p+1. Since nT in the objective function ∑j=1nDj=∑j=1nCj+nT is a constant, our problem can be translated to the problem: find the number of batches k and batch sizes bi satisfying ∑i=1kbi=n and bi≤B for i=1,…,k, so as to minimize ∑j=1nCj=∑i=1kbi∑j=1i(S+bjp). The problem is referred to as 1pj=p;B;S-batch∑Cj.This paper is organized as follows. In Section2, we give a backward dynamic programming algorithm to solve problem 1pj=p;B;S-batch∑Cj, which is not an actually polynomial-time algorithm. In Section 3, we first show the relation between optimal solution and the first order difference of the optimal objective function of the number of orders and investigate the properties of the first order difference. Then a partial dynamic programming algorithm to solve the problem in constant time is given. A specific calculating formula to solve the problem in case S=vp is shown in Section 4. In Section 5, we present some numerical examples to show the effectiveness of our proposed algorithms. Section 6 contains a conclusion and a discussion of some possible extensions.


## 2. Dynamic Programming Algorithm

For ease of presentation, we sequence the orders according to nonincreasing indices. Any solution of problem1pj=p;B;S-batch∑Cj is of the form(1)BS:Snk⋯nk-1+1Snk-1⋯nk-2+1⋯Sn1⋯1,where k is the number of batches, 1≤n1<n2<⋯<nk=n, and batch sizes b1=nk-nk-1,…,bk-1=n2-n1, bk=n1 satisfied with bi≤B for i=1,…,k. Every solution BS corresponds to a objective function value(2)FBS=∑j=1nCj=∑i=1kbi∑j=1iS+bjp=∑i=1kniS+ni-ni-1p,where n0=0.In order to solve the batch sizing problem, we obviously have to find a constantk and a sequence of indices 1≤n1<n2<⋯<nk=n such that the above objective function value is minimized. Clearly, problem 1pj=p;B;S-batch∑Cj is a trivial matter when S≤p or B<2. We have the result as follows.Theorem 1.
IfS≤p or B<2, then for problem 1pj=p;B;S-batch∑Cj there exists an optimal solution in which k=n and ni=i for i=1,…,n; that is, b1=⋯=bk=1.By Theorem1, we assume that S>p and B≥2 hereafter. Below we give a backward dynamic programming algorithm to solve the problem 1pj=p;B;S-batch∑Cj.Algorithm 2 (dynamic programming algorithm).
LetF(j) denote the minimum the sum of the completion times for j-orders batching problem containing orders 1,…,j. The initialization is(3)F0=0and the recursion for j=1,…,n is(4)Fj=min⁡⁡jS+j-ip+Fi∣max⁡⁡0,j-B≤i≤j-1.The minimization selects a batch{j,…,i+1} which dose not violate the product lifespan to insert at the start of the previous schedule containing orders i,…,1. Batch {j,…,i+1} completes at time S+(j-i)p, and the processing of the batches containing jobs i,…,1 is delayed by time S+(j-i)p as a result of the insertion. The optimal solution value is then equal to F(n). Under the most natural implementation, the algorithm requires O(nB) time.However, it is not an actually polynomial-time algorithm, since the usual definition of the input size is the sum of the logarithms of the input parametersn, S, p, and B. In the following sections, we will do further research into the recursion formula: F(j)=min⁡⁡{j[S+(j-i)p]+F(i)∣max⁡⁡{0,j-B}≤i≤j-1}=j[S+(j-t)p]+F(t), so as to determine completely the optimal successor t for every j in an polynomial-time of the input size.


## 3. Partial Dynamic Programming Algorithm

In this section, we first show the relation between optimal solution and the first order difference of the optimal objective function in terms of the number of orders and investigate the properties of the first order difference. Then we give a partial dynamic programming algorithm to solve the problem in constant time. For each orderj, if order t with max⁡⁡{0,j-B}≤t≤j-1 such that(5)Fj=jS+j-tp+Ftholds, we call order t the optimal successor of order j and denote the optimal successor t of j by SUCC(j). For 0≤i≤j-1, set(6)Fj,i=jS+j-ip+Fi.Thus, we have(7)Fj=min⁡i=max⁡⁡0,j-Bj-1⁡Fj,i.Note that the fact thati+1 is better (worse) than i as a successor of j, that is, F(j,i+1)-F(j,i)=j[S+(j-i-1)p]+F(i+1)-j[S+(j-i)p]+F(i)=F(i+1)-F(i)-jp<(>)0, is equivalent to F(i+1)-F(i)<(>)jp, which indicates that the optimal successor of j is related to the first order difference sequence of the optimal objective function of the number of orders. We denote the first order difference sequence of the optimal objective function of the number of orders by Δ(i)=F(i+1)-F(i) for i=0,1,…,+∞. We define that Δ(-1)=0. Then, i+1 is better (worse) than i as a successor of j if and only if Δ(i)<(>)jp. To break ties when choosing the successor, we assume that if Δ(i)=jp, that is, F(j,i+1)=F(j,i), then i+1 is better than i as a successor of j. The following lemma shows an important characteristic of the first order difference sequence.Lemma 3.
IfS>p, then all of the following hold: (i)
p≤Δ(j)-Δ(j-1)≤2pforj=1,2,…;(ii)
ifSUCC(j+1)=sj+1andSUCC(j)=sj, then(j+1)-sj+1≥j-sj.Proof.
We prove this lemma by induction. Simple calculations yield the following:SUCC(1)=0 and Δ(0)=F(1)-F(0)=S+p,F2=min⁡⁡F2,1,F2,0=min⁡⁡{2(S+p)+S+p,2(S+2p)}=2(S+2p), and SUCC(2)=0,Δ1=F2-F1=S+3p>Δ0=S+p and Δ(1)-Δ(0)=2p and 2-0>1-0.Thus, (i) and (ii) hold for j=1. Now suppose that they hold when j≤h for some positive integer h, that is, p≤Δ(t)-Δ(t-1)≤2p and (t+1)-st+1≥t-st for t=1,2,…,h. We need to show that they hold when j=h+1. Assume that SUCC(h+1)=t(0≤t≤h). By Δ(1)-Δ(0)=2p and p≤Δ(j)-Δ1(j-1) for j=2,…,h, we have that (h+1)p≤Δ(h). Equation (h+1)p=Δ(h) does not hold. Otherwise, inequalities Δ(0)<⋯<Δ(h-1)<(h+1)p imply that 1 is better than 0, 2 better than 1,…,h better than h-1 in order as a successor of h+1. The result is that SUCC(h+1)=h; that is, F(h+1)=(h+1)(S+p)+F(h). Then (h+1)p=Δ(h)=F(h+1)-F(h)=(h+1)(S+p)+F(h)-F(h)=(h+1)(S+p). This is a contradiction. Thus, we have that (h+1)p<Δ(h). Noting the fact that {Δ(j)}j=-1h is a strictly monotone increasing sequence, there is 0≤t0≤h such that Δ(t0-1)≤(h+1)p<Δ(t0). There are two cases to consider: (a) h+1-t<B; (b) h+1-t=B.
Case (a) (
h
+
1
-
t
<
B
). Since the inequalities Δ(-1)<Δ(0)<⋯<Δ(t0-1)≤(h+1)p imply that t0 is better than t0-1, t0-1 better than t0-2,…,1 better than 0 in order and the inequalities (h+1)p<Δ(t0)<⋯<Δ(h) imply that t0 is better than t0+1, t0+1 better than t0+2,…,h-1 better than h in order as a successor of (h+1), along with h+1-t<B, we have that t=t0=SUCC(h+1). This implies that SUCC(h+1)=t and h+1-t<B if and only if Δ(t-1)≤(h+1)p<Δ(t).
Ift0=0, then SUCC(h)=0. If t0=1, either SUCC(h)=0 or SUCC(h)=1 follows from the fact that hp<(h+1)p<Δ(t0)<⋯<Δ(h). If t0>1, due to p≤Δ(t0-1)-Δ(t0-2), either SUCC(h)=t0 or SUCC(h)=t0-1 follows from the fact that Δ(t0-2)≤hp<(h+1)p<Δ(t0). In sum, if SUCC(h+1)=t, then either SUCC(h)=t or SUCC(h)=t-1. Similarly, we have that if SUCC(h+1)=t, then either SUCC(h+2)=t or SUCC(h)=t+1. This implies that (ii) holds. To end the proof of (i), there are four cases to consider: (a1) SUCC(h)=SUCC(h+1)=SUCC(h+2)=t, (a2) SUCC(h)=t-1, SUCC(h+1)=SUCC(h+2)=t, (a3) SUCC(h)=SUCC(h+1)=t, SUCC(h+2)=t+1, and (a4) SUCC(h)=t-1, SUCC(h+1)=t, SUCC(h+2)=t+1.
Case (a1) (
S
U
C
C
(
h
)
=
S
U
C
C
(
h
+
1
)
=
S
U
C
C
(
h
+
2
)
=
t
). In this case,(8)Fh=hS+h-tp+Ft,Fh+1=h+1S+h+1-tp+Ft,Fh+2=h+2S+h+2-tp+Ft.Thus, we have that Δ(h)=F(h+1)-F(h)=S+(2h+1-t)p, Δ(h+1)=F(h+2)-F(h+1)=S+(2h+3-t)p, and(9)Δh+1-Δh=2p.
Case (a2) (
S
U
C
C
(
h
)
=
t
-
1
,
S
U
C
C
(
h
+
1
)
=
S
U
C
C
(
h
+
2
)
=
t
). In this case,(10)Fh=hS+h-t+1p+Ft-1,Fh+1=h+1S+h+1-tp+Ft,Fh+2=h+2S+h+2-tp+Ft.Thus, we have that Δ(h)=F(h+1)-F(h)=S+(h+1-t)p+F(t)-F(t-1)=S+(h+1-t)p+Δ(t-1),  Δ(h+1)=F(h+2)-F(h+1)=S+(2h+3-t)p, and(11)Δh+1-Δh=h+2p-Δt-1.Since SUCC(h+1)=SUCC(h+2)=t, the inequalities Δ(t)>(h+2)p>(h+1)p≥Δ(t-1) hold. This implies Δ(h+1)-Δ(h)=(h+2)p-Δ(t-1)≥p. By t-1≥0, 1≤t≤h hold. Due to the induction assumption, along with Δ(t)>(h+2)p, we have that Δ(h+1)-Δ(h)=(h+2)p-Δ(t-1)≤Δ(t)-Δ(t-1)≤2p.
Case (a3) (
S
U
C
C
(
h
)
=
S
U
C
C
(
h
+
1
)
=
t
,
S
U
C
C
(
h
+
2
)
=
t
+
1
). In this case,(12)Fh=hS+h-tp+Ft,Fh+1=h+1S+h+1-tp+Ft,Fh+2=h+2S+h+2-t-1p+Ft+1.Thus, we have that Δ(h)=F(h+1)-F(h)=S+(2h+1-t)p, Δ(h+1)=F(h+2)-F(h+1)=S+(h+1-t)p+F(t+1)-F(t)=S+(h+1-t)p+Δ(t), and(13)Δh+1-Δh=Δt-hp.Since SUCC(h)=SUCC(h+1)=t, the inequalities Δ(t)>(h+1)p>hp hold. This implies Δ(h+1)-Δ(h)=Δ(t)-hp≥p. Also, we have that Δ(h+1)-Δ(h)=Δ(t)-hp≤2p. Otherwise, Δ(t)-hp>2p implies Δ(t)>(h+2)p. This contradicts with the fact that Δ(t)≤(h+2)p<Δ(t+1).
Case (a4) (
S
U
C
C
(
h
)
=
t
-
1
,
S
U
C
C
(
h
+
1
)
=
t
,
S
U
C
C
(
h
+
2
)
=
t
+
1
). In this case,(14)Fh=hS+h+1-tp+Ft-1,Fh+1=h+1S+h+1-tp+Ft,Fh+2=h+2S+h+1-tp+Ft+1.Thus, we have that(15)Δh+1-Δh=Δt-Δt-1.Since 1≤t≤h, along with the induction assumption, the inequalities p≤Δ(h+1)-Δ(h)≤2p hold. This ends the proof for Case (a).
Case (b) (
h
+
1
-
t
=
B
). The inequalities Δ(t0-1)≤(h+1)p<Δ(t0) still hold, where 0≤t0≤h. Clearly, t≥t0. Otherwise, t<t0. Since h+1-t0<B which means that the product lifespan is not violated and Δ(t0-1)≤(h+1)p<Δ(t0), SUCC(h+1)=t0. This contradicts with SUCC(h+1)=t. Assume that SUCC(h)=t′. There are two cases to consider: (b1) h-t′=B and (b2) h-t′<B.
Case (b1) (
h
-
t
′
=
B
). By Δ(t′+1)-Δ(t′)≥p and hp<Δ(t′), we have that (h+1)p<Δ(t′+1). This, along with ((h+1)-t′)>B, implies that SUCC(h+1)=t′+1; that is t′=t-1. similarly, SUCC(h+2)=t+1. Similar to the proof of Case (a4), (i) and (ii) hold for the case.
Case (b2) (
h
-
t
′
<
B
). Clearly, t′≤t0. By (h+1)-t0≤(h+1)-t′≤B, along with Δ(t0-1)≤(h+1)p<Δ(t0), we have that t=t0. Meanwhile we claim t′=t0. Otherwise t′<t0. Then (h+1)-t=(h+1)-t0≤h-t′<B. This contradicts with h+1-t=B. Similarly, by h+1-t=B, SUCC(h+2)=t+1=t0+1. Similar to the proof of Case (a3), (i) and (ii) hold for the case. This ends the proof of the lemma.The lemma, as well as four formulas yielded in the proof of the lemma, is very important for our batch sizing problem.Δ(0)=S+p implies that 0 is the optimal successor of 1,2,…,(S+p)/p, where (S+p)/p denotes the maximal integer less than rational number (S+p)/p and (S+p)/p≤B. p≤Δ(j)-Δ(j-1)≤2p implies that each positive integer must be the optimal successor of one or two positive integers. If SUCC(h)=t and h-t=B, then SUCC(j)=j-B for j=h+1,h+2,…. By (ii) in Lemma 3, we may assume that h∗ is the minimal integer such that SUCC(h∗)=t∗ and h∗-t∗=B. Then j<h∗ and SUCC(j)=t imply that j-t<B and then that j<h∗ and SUCC(j)=t hold if and only if Δ(t-1)≤hp<Δ(t). By (ii) in Lemma 3, if h∗ may be found by recursion (4) in a constant time, then the our problem is solvable in a constant time, since SUCC(j)=j-B for j>h∗.Now we define thatNk={j∣the optimal number of batches of j-orders batching problem is equal to k} for k=1,2,…, called k-batches case set of orders and sequence integers in Nk in increasing natural order. Then (N1,…,Nk,…) is a partition of the set of position integers. Let C1,i=i for i=1,…,N1. Then N1=(C1,1,…,C1,N1). We define that Ck,i={j∣SUCC(j)∈Ck-1,i} for k=2,3,… and i=1,…,N1, called the ith periodic set of Nk, and sequence integers in Ck,i in increasing natural order. Then Nk=(Ck,1,…,Ck,N1) and (C1,1,…,C1,N1,…,Ck,1,…,Ck,N1,…) is a partition of the set of position integers. If we can find a upper bound of Ck,i, the upper bound of j-t will be estimated, where j∈Ck,i, t∈Ck-1,i and SUCC(j)=t. The following lemma shows how to do this.Lemma 4.
LetS=vp+r and qk-1=∑t=1k-1Nt, where q0=0, 0≤r<p, and v are integers. Then for all of k satisfying with j-t<B where j∈Nk and SUCC(j)=t, all of the following hold: (i)
|Cki|=k for i=1,…,v,(ii)
Δ(qk-1+(i-1)k+k)-Δ(qk-1+(i-1)k)=(k+1)p for i=1,…,v.Proof.
ByS=vp+r and Δ(0)=S+p=(v+1)p+r, N1={1,…,v} if r=0; N1={1,…,v+1} if r>0. Let C1,v+1=∅ if r=0 and C1,v+1=v+1 if r>0. We prove this lemma by induction. Clearly, C1i=i for i=1,…,v. If C1,v+1=v+1, Δ(i)-Δ(i-1)=2p for i=1,…,v follows from (9), since SUCC(0)=SUCC(1)=⋯=SUCC(v+1). If C1,v+1=∅, Δ(i)-Δ(i-1)=2p for i=1,…,v-1 follows from (9), since SUCC(0)=SUCC(1)=⋯=SUCC(v). By SUCC(v-1)=SUCC(v)=0, SUCC(v+1)=1, and (13), Δ(v)-Δ(v-1)=Δ(0)+(v-1)p=2p. Thus (i) and (ii) hold when k=1. Now suppose that they hold when k=h for some positive integer h. We need to show that they hold when k=h+1. For any i∈{1,…,v}, by result (ii) with k=h: Δ(qh-1+(i-1)h+h)-Δ(qh-1+(i-1)h)=(h+1)p and j∈C(h+1)i if and only if Δ(qh-1+(i-1)h)≤jp<Δ(qh-1+(i-1)h+h), we have that Ch+1i=h+1. Thus the result (i) holds when k=h+1.
Now we rewriteCh+1,i as (b+1,…,b+(h+1)), where b=qh+(i-1)(h+1). By |Ch,i|=h and |Ch+1,i|=h+1, every integer in Ch,i must be the optimal successor of some integer in Ch+1,i and there is a integer, say a+t0 where a=qh-1+(i-1)h, in Ch,i such that it is the optimal successor of two integers in Ch+1,i. So, we have that(16)SUCCb+t=a+tfort=1,…,t0-1,SUCCb+t0=SUCCb+t0+1=a+t0,SUCCb+t=a+t-1fort=t0+2,…,h+1.By (15),(17)Δb+t-Δb+t-1=Δa+t-Δa+t-1,fort=1,…,t0-1.By (11),(18)Δb+t0-Δb+t0-1=b+t0+1p-Δa+t0-1.By (13),(19)Δb+t0+1-Δb+t0=Δa+t0-b+t0p.By (15),(20)Δb+t-Δb+t-1=Δa+t-1-Δa+t-2,fort=t0+2,…,h+1.Equations (17), (18), (19), and (20), along with the induction assumption, imply Δ(b+h+1)-Δ(b)=Δ(a+h)-Δ(a)+p=(h+2)p; that is, the result (ii) holds when k=h+1. This ends the proof of the lemma.In the following we give a partial dynamic programming algorithm to solve the problem1pj=p;B;S-batch∑Cj.Algorithm 5 (partial dynamic programming algorithm).
LetF(j) denote the minimum the sum of the completion times for j-orders batching problem containing orders 1,…,j. The initialization is(21)F0=0,and for j=1,…,h∗ the recursion is(22)Fj=min⁡⁡jS+j-ip+Fi∣0≤i≤j-1;for j>h∗ the recursion is(23)Fj=jS+Bp+Fj-B,where h∗ is the minimal integer such that SUCC(h∗)=t∗ and h∗-t∗=B.Theorem 6.
Algorithm5 finds an optimal solution of problem 1|pj=p;B;S-batch|∑‍Cj in constant time.Proof.
By (ii) in Lemma3, j-sj is monotonic increasing, where SUCC(j)=sj. By (i) in Lemma 4, Cki=k for k≥1 and i=1,…,v, where S=vp+r. Noting the fact that SUCC(jk+1,v)=jk,v, where jk+1,v and jk,v are the last orders in Ck+1,v and Cki, respectively, we have that (jk+2,v-jk+1,v)-(jk+1,v-jkv)≥v for k≥1. This, along with v≥1, implies that the recursion: Fj=min⁡⁡jS+j-ip+Fi∣0≤i≤j-1 for j=1,…,h∗ finishes in O(B) time. Thus, Algorithm 5 finds an optimal solution of the problem in constant time.In the following section, we will show a specific calculating formula for the solution of the problem withS=vp.


## 4. Specific Calculating Formula in CaseS=vp

AssumeS=vp. By (i) in Lemma 4, we may obtain a partition of the set of j-orders with j≤h∗ as follows: N1={1,…,v}, N2={v+1,…,3v},…,  and Nk={∑t=1k-1tv+1,…,∑t=1ktv},…. For example, if v=3, C11={1}, C12={2}, C13={3}, and N1={1,2,3}, C21={4,5}, C22={6,7}, C33={8,9}, and N2={4,…,9};….For ease of presentation, we denote by(k,i,w) the wth order in the ith periodic set Cki of the kth batch case set Nk, where all k, i, and w with k≥1, 1≤i≤v, and 1≤w≤k are integers; that is,(24)k,i,w=∑t=1k-1tv+i-1k+w=k-1k2v+i-1k+w,where ∑t=10tv=0. Equation (24) establishes a one-to-one correspondence between {(k,i,w)∣k≥1,1≤i≤v,1≤w≤k} and the set of positive integers. For example, if v=3, (4,3,2)=∑t=14-1tv+(3-1)4+2=28 and 101=33v+2=((7×8)/2)v+(3-1)8+1=(8,3,1). We define (0,0,0)=0;  (k,i,w)=(k,i-1,k) if w=0 and i>1; (k,i,w)=(k-1,v,k-1) if w=0 and i=1. The following lemma describes the special properties of first order difference in case S=vp.Lemma 7.
AssumeS=vp. Then all of the following hold.(i)
For each order(k,i,w) with (k,i,w)≤h∗, Δ(k,i,w)-Δ(k,i,w-1)=p if w<k and Δ(k,i,w)-Δ(k,i,w-1)=2p if w=k, where k≥1, 1≤i≤v, and 1≤w≤k.(ii)
LetB=mv+r, where m and 0≤r<v are nonnegative integers. Then h∗=(m+1,r,m+1).Proof.
We prove result (i) by induction. BySUCC(i)=0 for i=0,1,…,v, along with (9), we have that Δ(1,i,1)-Δ(1,i,0)=Δ(i)-Δ(i-1)=2p for i=1,…,v-1. By SUCC(v-1)=SUCC(v)=0 and SUCC(v+1)=1, along with (13), we have Δ(1,v,1)-Δ(1,v,0)=Δ(v)-Δ(v-1)=Δ(0)-(v-1)p=(v+1)p-(v-1)p=2p. Thus, result (i) holds for k=1. Now suppose that it holds when k≤h; that is, Δ(h,i,w)-Δ(h,i,w-1)=p if w<h and Δ(h,i,w)-Δ(h,i,w-1)=2p if w=h for i=1,…,v. We need to show it for k=h+1.
For eachi with 1≤i≤v, by the induction assumption, SUCC(h+1,i,w)=(h,i,w) for w=1,…,h and SUCC(h+1,i,h+1)=(h,i,h) for w=h+1 follow from the fact that Δ(h,i,w)-Δ(h,i,w-1)=p if w<h and Δ(h,i,w)-Δ(h,i,w-1)=2p if w=h for i=1,…,v. Since (h+1,i,0)=(h+1,i-1,h+1) if i>1 and (h+1,i,0)=(h,v,h), along with the induction assumption, we have that SUCC(h+1,i,0)=(h,i-1,h) if i>1 and SUCC(h+1,i,0)=(h-1,v,h-1). This implies that SUCC(h+1,i,w), SUCC(h+1,i,w+1), and SUCC(h+1,i,w+2) are different from each other for 0≤w≤h-2. By (15) and the induction assumption, we have that Δ(h+1,i,w)-Δ(h+1,i,w-1)=Δ(h,i,w)-Δ(h,i,w-1)=p for w=1,…,h-1. Since SUCC(h+1,i,h-1)=(h,i,h-1) and SUCC(h+1,i,h)=SUCC(h+1,i,h+1)=(h,i,h), Δ(h+1,i,h)-Δ(h+1,i,h-1)=(h+1,i,h+1)p-Δ(h,i,h-1)=[∑t=1htv+(i-1)(h+1)+(h+1)]p  −  Δ(h,i,h-1) follows from (11). By Δ(0,0,0)=(v+1)p, (ii) in Lemma 4 and the induction assumption, we have that Δh,i,h-1=v+1p+v2p+v3p+⋯+vhp+i-1h+1p+h-1p  =  ∑t=1htvp+[(i-1)(h+1)]p+hp. This implies that Δ(h+1,i,h)-Δ(h+1,i,h-1)=p. Note the fact that (h+1,i,h+1)+1=(h+1,i+1,1) if i<v and (h+1,i,h+1)+1=(h+2,1,1) if i=v. We have that SUCC(h+1,i,h)=SUCC(h+1,i,h+1)=(h,i,h) and SUCC[(h+1,i,h+1)+1]=(h,i,h)+1. By (19), Δ(h+1,i,h+1)-Δ(h+1,i,h)=Δ(h,i,h)-(h+1,i,h)p=Δ(h,i,h)-[∑t=1htv+(i-1)(h+1)+h]p. By Δ(0,0,0)=(v+1)p, (ii) in Lemma 4 and the induction assumption, we have that Δ(h,i,h)=[(v+1)p]+[v(2p)+v(3p)+⋯+v(hp)]+[i(h+1)p]=[∑t=1htv]p+[(i-1)(h+1)]p+(h+2)p. This implies that Δ(h+1,i,h+1)-Δ(h+1,i,h)=2p. This ends the proof of result (i).
By (ii) in Lemma3 and result (i), order h∗ satisfying with SUCC(h∗)=t∗ and h∗-t∗=B must be one of the set of {(k,i,k)∣k≥1,1≤i≤v}. Since SUCC(m+1,r,m+1)=(m,r,m) and (m+1,r,m+1)-(m,r,m)=∑t=1mtv+(r-1)(m+1)+(m+1)-∑t=1m-1tv+(r-1)m+m=mv+r=B, h∗=(m+1,r,m+1) holds. This ends the proof of the lemma.In the following we give a specific solution formula to solve the problem1pj=p;B;S-batch∑Cj.Algorithm 8 (specific solution formula).
LetB=mv+r. Then for n-orders batch sizing problem,(1)
h∗=(m+1,r,m+1)=∑t=1m‍tv+r(m+1) and n=(n-h∗)/BB+(d,i,w)=aB+(d,i,w),(2)
the number of batchesk=a+d,(3)
batch sizes(25)bt=B,fort=1,…,a;d-t+av+i-1,fort=a+1,…,a+d-w;d-t+av+i,fort=a+d-w+1,…,a+d,wherex denotes the minimal nonnegative integer greater than or equal to rational number x.Theorem 9.
Algorithm8 give a specific calculating formula to solve problem 1pj=p;B;S-batch∑Cj with S=vp.Proof.
By (ii) in Lemma4 and SUCC(j)=j-B if j≥h∗, along with (n-h∗)/B≤(n-h∗)/B<(n-h∗)/B+1, we have that n-((n-h∗)/B-1)B>n-((n-h∗)/B+1-1)B=h∗. This implies that bt=B for t={1,…,(n-h∗)/B}={1,…,a} and SUCC(n-((n-h∗)/B-1)B)=n-((n-h∗)/B-1)B-B=n-((n-h∗)/B)B=(d,i,w). By n-((n-h∗)/B)B≤n-((n-h∗)/B)=h∗ and (i) in Lemma 7, we have that SUCC(d,i,w)=(d-1,i,w),…,  SUCC(w+1,i,w)=(w,i,w), and SUCC(w,i,w)=(w-1,i,w-1),…,  SUCC(1,i,1)=0. Thus, for s=0,…,d-w-1, (d-s,i,w)-(d-s-1,i,w)=(d-s-1)v+(i-1); that is, for t=a+1,…,a+d-w, bt=(d-t+a)v+(i-1) and for s=d-w,…,d-1, (d-s,i,w)-(d-s-1,i,w-1)=(d-s-1)v+i; that is, for t=a+d-w+1,…,a+d,  bt=(d-t+a)v+i. This ends the proof of the theorem.


## 5. Results and Discussion

In this section, we will present three numerical examples to show the effectiveness of our proposed algorithms.Example 1.
Solve by Algorithm2 the following instance of the 1pj=p;B;S-batch∑Cj problem: (26)n≔9,p≔2,S≔5,B≔5.Solution. Let F(j,i)=j[S+(j-i)p]+F(i). We have F(j)=min⁡i=max⁡{0,j-B}j-1F(j,i). Set F(0)=0.ByF(1,0)=1[5+(1-0)2]+F(0)=7, we have that F(1)=7. Thus SUCC(1)=0.ByF(2,0)=2[5+(2-0)2]+F(0)=18 and F(2,1)=2[5+(2-1)2]+F(1)=21, we have that F(2)=18. Thus SUCC(2)=0.ByF(3,0)=33, F(3,1)=34, and F(3,2)=39, we have that F(3)=33. Thus SUCC(3)=0.ByF(4,0)=52, F(4,1)=51, F(4,2)=54, and F(4,3)=61, we have that F(4)=51. Thus SUCC(4)=1.ByF(5,0)=75, F(5,1)=72, F(5,2)=73, F(5,3)=78, and F(5,4)=86, we have that F(5)=72. Thus SUCC(5)=1.ByF(6,1)=97, F(6,2)=96, F(6,3)=99, F(6,4)=105, and F(6,5)=114, we have that F(6)=96. Thus SUCC(6)=2.ByF(7,2)=123, F(7,3)=124, F(7,4)=128, F(7,5)=135, and F(7,6)=145, we have that F(7)=123. Thus SUCC(7)=2.ByF(8,3)=153, F(8,4)=155, F(8,5)=160, F(8,6)=168, and F(8,7)=179, we have that F(8)=153. Thus SUCC(8)=3.ByF(9,4)=186, F(9,5)=189, F(9,6)=195, F(9,7)=204, and F(9,8)=216, we have that F(9)=186. Thus SUCC(9)=4.We obtain the optimal solution of the problem instance: the number of batchesk=3; batch sizes b1=5, b2=3, and b3=1.Example 2.
Solve by Algorithm5 the following instance of the 1|pj=p;B;S-batch|∑‍Cj problem: (27)n≔81,p≔2,S≔5,B≔5.Solution. By doing same calculations in Example 1, we have that SUCC(1)=0, SUCC(2)=0, SUCC(3)=0, SUCC(4)=1, SUCC(5)=1, SUCC(6)=2, and SUCC(7)=2. Noting the fact that h∗=7 is the minimal integer such that SUCC(h∗)=t∗ and h∗-t∗=B, along with Algorithm 5, we obtain the optimal solution of the problem instance: the number of batches k=17; batch sizes bt=5 for t=1,…,15, b16=4, and b17=2.Example 3.
Solve by Algorithm8 the following instance of the 1pj=p;B;S-batch∑Cj problem: (28)n≔2000,p≔7,S≔28=4×p,B≔111.Solution. Since B=27×4+3, we have that h∗=(28,3,28)=∑t=1274t+3×28=1596. 2000 can be written as 2000=(2000-1596)/111111+(d,i,w)=4×111+1556=4×111+(27,6,17). By Algorithm 8, we obtain the optimal solution of the problem instance: the number of batches k=31; batch sizes bt=111 for t=1,2,3,4, bt=4(27-t+4)+5=129-4t for t=5,…,14, and bt=4(27-t+4)+6=130-4t for t=15,…,31.


## 6. Conclusions

In this paper, we study the supply chain problem of batching identical orders with lifespan constraints and from the same location on a single machine. The problem is to choose the number of batches and batch sizes to minimize the total delivery time without violating the order lifespan. We first give a backward dynamic programming algorithm, but it is not an actually polynomial-time algorithm. Then, we do further research into the recursion formula in the dynamic programming algorithm and prove thatj-SUCC(j)=B when j is a sufficiently large integer. Following from the property, a constant time partial dynamic programming algorithm is given. Further, using the difference characteristics of the optimal value function, a specific calculating formula to solve the problem in case S=vp is obtained. An interesting open question is whether there is a specific calculating formula to solve the problem 1pj=p;B;S-batch∑Cj in a general case of S. The difference analysis technique should be able to be used to study some other supply chain scheduling problem with lifespan constraints.



---

*Source: 716248-2015-05-05.xml*