# Scheduling and Common Due Date Assignment on a Single Parallel-Batching Machine with Batch Delivery

Authors: Hua Gong; Biao Zhang; Wuliang Peng
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

We consider a single parallel-batching machine scheduling problem with delivery involving both batching scheduling and common due date assignment. The orders are first processed on the single parallel-batching machine and then delivered in batches to the customers. The batching machine can process several orders at the same time. The processing time of a production batch on the machine is equal to the longest processing time of the orders assigned into this batch. A common due date for all the orders in the same delivery batch and a delivery date for each order need to be determined in order to minimize total weighted flow time. We first prove that this problem is NP hard in the strong sense. Two optimal algorithms by using dynamic programming are derived for the two special cases with a given sequence of orders on the machine and a given batching in the production part, respectively.


---

## Body

## 1. Introduction

A wide variety of practical problems are closely related to the batching production and delivery in batches considered in this paper. In a supply chain of many industries, production operation and delivery operation are two key operational functions. Many industries first produce products and transport their finished products to the customers directly without holding intermediate inventories. For example, there exist the operations with production of steel ingots and delivery of the finished ingots in the iron and steel industry. The steel ingots need to heat to a high temperature in a soaking pit in order to keep the steady performance of the steel ingots. The soaking pit heats several ingots simultaneously where the soaking pit can be viewed as a parallel-batching machine. Then the steady ingots finished in the soaking pit are directly transported to the corresponding customers in batches. This is the motivation for the considered problem. All ingots in the same shipment for delivery to the customer have a common due date. The common due date is a decision variable. Production operation and delivery operation are linked together without any intermediate step since no inventory is involved. The customer does not want to accept his order earlier than the due date. Thus, the orders are finished before the due date, and they have to be storage in inventory for the industries. It is important to coordinate these two operations and schedule them jointly in order to achieve optimal inventory level in the iron and steel industry. Hence, the coordination between production and delivery has become more practical and become one of the most important topics. In such supply chain application, it is well understood that coordinated production and delivery scheduling can significantly reduce the inventory level and the customer service level for the decision maker.Motivated by the above-described applications in the supply chain, we address a coordinated scheduling problem of production on a single batching machine and delivery operation in batches. The orders are first processed on the single batching machine and then delivered to the customers directly without intermediate. In the production part, the production schedule specifies the processing sequencing and batching of the orders on the machine. Completed orders are delivered in batches to the customers by homogeneous vehicles. We assume that each delivery shipment can only carry up to a number of orders. The delivery schedule specifies how many batches to use, how to batch, and the delivery date of each batch from the machine. The production batches may be partitioned into delivery batches to determine the delivery date. A common due date for the same delivery batch has to be determined. A delivery batch has the same delivery date and the same due date. The problem is to find a coordinated schedule of production batching and delivery batching such that an objective function that takes into account the inventory level is optimized. The inventory level is measured by a function of the times when the finished orders are delivered to the customers. A common due date for the orders in the same delivery batch is the flow time of each order in this batch. Therefore, the objective is to minimize total weighted flow time of orders.The described problem in this paper falls into two categories: batch delivery and batching scheduling. Many researchers have made contributions in the coordinated scheduling area with production and delivery. We briefly discuss some work related to the problems where the objective is to minimize the sum of the total flow time and delivery cost. Cheng and Kahlbacher [1] and Cheng et al. [2] study a single machine scheduling problem with batch delivery cost, respectively. Wang and Cheng [3] consider a scheduling problem on the parallel machines with batch deliveries where the batch delivery date is equal to the completion time of the last job in a batch. Hall and Potts [4, 5] consider the single machine and identical-parallel machine scheduling problems with batch deliveries in batches involving the due dates, but without a transporter availability constraint. Yin et al. [6] consider a batch delivery scheduling problem with unrelated or uniform parallel machines. Wan and Zhang [7] consider a coordinated scheduling on parallel identical machines with batch delivery with objective of minimizing the sum of job arrival times. Yin et al. [8] address a single machine scheduling with batch delivery in which jobs have an assignable common due window. Chen [9] gives a detail survey for the production-delivery coordination. Ji et al. [10] study a single machine scheduling problem with release times and job delivery to minimize total weighted completion time of jobs. For the objective with minimizing the flow time and delivery cost, Mazdeh et al. [11] consider a single machine scheduling problem with batch deliveries and job release times. Mazdeh et al. [12] and Selvarajah et al. [13] study the single machine scheduling problem with delivery in batches, respectively. Chen and Vairaktarakis [14] consider single machine and parallel machine scheduling problems with delivery routing for the completed jobs to the customers. Yin et al. [15] consider a scheduling problem of nonresumable and simultaneously available jobs on a single machine and delivery in batches where the machine has a fixed unavailability interval.Batching is an important feature of many practical industries in the supply chain. The parallel-batching scheduling problems considered in this paper are motivated by burn-in operations in the very large-scale integrated circuit manufacturing. The detail surveys for the batching scheduling problems can be seen in [16–18]. For the coordinated scheduling problem with the parallel-batching machine and transportation, Tang and Liu [19] study a flow shop scheduling problem with a parallel-batching machine where the intermediate transportation is considered between two machines. Tang and Gong [20] consider a coordinated scheduling problem with transportation before and after production scheduling on a single parallel-batching machine. In [19, 20], they assume that the processing time of a batch on the batching machine is a constant.The problem formulated above combines three types of decisions: scheduling, batching, and due date assignment. The independent and simultaneously available orders have to be scheduled and partitioned into batches during processing and delivery. After the orders in a batch finished processing on the parallel-batching machine, they must be delivered to the customers in batches within limited delivery capacity. In a real supply chain, the managers may not stipulate the delivery for each specific order. In such a coordinated system, the linkage between order production scheduling and delivery dispatching of finished orders is extremely important in order to determine the common due date for each delivery batch. Our work differs from the above where we study not only the batching and sequencing schedule of orders on the parallel-batching machine, but also the batching for the finished orders in the delivery part where the delivery date and the common due date for each delivery batch need to be determined.The rest of this paper is organized as follows. In Section2, we describe the problem and introduce the notation to be used. In Section 3, we give a strongly NP-hardness proof by a polynomial-time reduction. In Section 4, we develop the efficient algorithms for two special cases. Finally, our conclusion is presented in the last section.


## 2. Model and Preliminary Results

In this paper, a coordinated scheduling problem on a single parallel-batching machine with batch delivery is addressed in order to determine the common due date for each delivery. The problem can be described as follows.(1)
All the ordersN={J1,J2,…,Jn} have the same production-delivery routing: they are first processed on a single parallel-batching machine in the production part, and then they are transported to the customers in batches in the delivery part.(2)
In the production part, all orders and the machine are available at time 0. The parallel-batching machine has a capacity limitB and can process several orders simultaneously. A production batch is defined as a set of orders processed on the parallel-batching machine at the same time. The processing time of a production batch on the machine is equal to the longest processing time of the orders assigned into this batch.(3)
In the delivery part, each delivery shipment will transported by a dedicated vehicle. Due to limited vehicle capacityC, each delivery shipment can carry up to a number of orders. A delivery batch is defined as a set of orders transported together in the same shipment.(4)
The vehicle is stationed at the processing facility at time 0 and must go back to the facility once it finishes a delivery batch. A delivery vehicle can depart from the processing facility only when all the orders to be delivered have finished processing.(5)
All orders are not interruption. When the processing of a batch is executed, it cannot be interrupted, and other orders cannot be introduced into the batch. Orders processed in a batch have the same starting time and completion time on the machine.(6)
The production batches may be partitioned into delivery batches to determine their delivery dates. A common due date for the same delivery batch has to be determined. A delivery batch has the same delivery date and the same due date.Next, we present the notation that will be used throughout the paper:pi: the processing time of order Ji on the parallel-batching machine, i=1,2,…,n;t1: the delivery time of the vehicle from the machine to the customer;t2: the return time of the vehicle from the customer back to the machine;wi: the weight of order Ji, i=1,2,…,n.Decision variables are as follows:Bk: the production batch k;Ci: the completion time of order Ji on the machine, i=1,2,…,n;Dl: the delivery batch l;dl: the common due date of delivery batch Dl;Fi: the flow time of order Ji which is defined as the time when it arrives at the customer, i=1,2,…,n, Fi=dl, if Ji∈Dl;∑wiFi: total weighted flow time.Here, the flow times of the orders assigned into the same delivery batch are equal to the common due date of the delivery batch. For convenience, we denote our problem by (P). Next, we present three general properties that will be useful throughout our study.Lemma 1.
There exists an optimal schedule that production batches of the orders are processed continuously from time 0 without idle time on the single parallel-batching machine.Proof.
If there is any idle time between two continuous batches in the production part, the latter batch can be moved earlier to be processed on the machine. The objective value is not increased.Lemma 2.
There exists an optimal schedule where the delivery date of a delivery batch is either the completion time of the last order on the machine which is included in the delivery batch or the available time of the vehicle immediately.Proof.
Assume that there exists a delivery batch such that its delivery date does not fit any above condition. That is neither at the completion time of the last order on the machine which is included in the delivery batch nor the available time of the vehicle immediately. Then we can move the delivery batch such that this delivery date can fit either of those conditions. It is easy to see that this delivery batch can be transported at that earlier time to the customer without increasing the total weighted flow time.Lemma 3.
The delivery batch must contain all orders which are processed on the machine but not delivered within the scope of the delivery capacity to allow.Proof.
The finished orders on the parallel-batching machine should be delivered to the customer as early as possible. The delivery batch should contain orders as many as possible which are processed on the machine but not delivered.


## 3. Strongly NP Hardness

In this section, we show that problem (P) is strongly NP hard by a reduction from 3-partition problem, which is known to be NP hard in the strong sense (see Garey and Johnson [21]).The following theorem shows the computational complexity of problem (P).Theorem 4.
Problem (P) is strongly NP hard.Proof.
We next perform a polynomial time reduction from 3-partition problem.
3-Partition Problem (3-PP). Given 3h+1 positive integers {a1,a2,…,a3h} and a satisfying a/4<ai<a/2 for i=1,2,…,3h and ∑i=13hai=ha, can {1,2,…,3h} be partitioned into h sets S1,S2,…,Sh such that ∑i∈Slai=b for 1≤l≤h? Without loss of generality, if there exists a solution to 3-partition problem, then the elements can be numbered such that a3j-2+a3j-1+a3j=a, for j=1,2,…,h.
Given a 3-PP instance, we construct an instance for (P) as follows.
There are6h+6 orders with machine capacity of 2 and delivery capacity of 6.
Assume thatt1=t2=a/2.
Processing times and weights of orders as follows:
p
i
=
p
i
+
3
h
=
w
i
=
w
i
+
3
h
=
a
i, i=1,2,…,3h;
p
i
=
0, wi=a, i=6h+1,…,6h+6;
threshold:y=a2(h2+2h+3).
We prove there exists a schedule for this instance with total weighted flow time less than or equal toy if and only if there exists a feasible solution to 3-partition problem. Note that the processing times of orders J6h+1,…,J6h+6 are equal to 0. We first prove the following two properties: in a solution to this instance of (P) with total weighted flow time less than or equal to y, (1) orders J6h+1,…,J6h+6 form the first delivery batch to the customer; (2) there is no idle time once the vehicle starts to deliver from time point 0 in the delivery part. Then the related total weighted flow time of these orders in the first delivery batch is 3a2.
If Part. Consider that the sets Hl, l=1,2,…,h, form a solution to 3-partition. The batching for the production and delivery is shown as follows. In the production part, the orders J1,…,J6 are partitioned into 3h production batches on the machine where B1={J1,J3h+1}, B2={J2,J3h+2},…, B3h={J3h,J6h}. In the delivery part, all the orders are partitioned into h+1 delivery batches where each delivery batch contains 6 orders; that is, D1={J6h+1,…,J6h+6}, D2={J1,J2,J3,J3h+1J3h+2,J3h+3},…,Dh+1={J3h-1,J3h-2,J3h,J6h-2,J6h-1,J6h}. The delivery date and the common due date of Dl are (l-1)a and (l-1/2)a, respectively, for l=1,2,…,h+1. It is easy to see that total weighted flow time of orders in the above schedule is y.
Only If Part. Suppose that there exists a schedule for the instance of (P) with total weighted flow time less than or equal to y. Since the machine capacity is 2, we can see that each production batch on the machine contains exactly two orders with identical processing times: B1={J1,J3h+1}, B2={J2,J3h+2},…,B3h={J3h,J6h}. Due to the delivery capacity of 6, the delivery batches of the orders are at least h+1 in the delivery part. Assume that total weighted flow time to minimize a solution with k(k≥h) delivery batches for these 6h orders except the first delivery batch. From property (1), we can derive total weighted flow time of this problem as follows:(1)Minimizehh2x1x1+a2+x2x1+x2+a2hhhhhhhhhhhhh+⋯+xkx1+⋯+xk+a2+3a2Subjecttox1+⋯+xk=ha,where xj is total processing time of orders assigned into the same batch Dj, for j=1,…,k. The total weighted flow time can be formulated as (2)∑j=1kxj2+∑j=1kxj2+(h+3)a2=∑j=1kxj2+(h2+h+3)a2.
Note that the second term is minimized by settingx1=⋯=xk=ha/k. We obtain that total weighted flow time for the k delivery batches is greater than or equal to ∑j=1k(ha/k)2+(h2+h+3)a2. Then this expression means a minimum objective value with respect to k at k=h, and this minimum total weighted flow time is y. From (1), it means that these 6h orders are partitioned into h delivery batches. Furthermore, the minimum total weighted flow time is contributed by h+1 delivery batches. Each delivery batch contains exactly 6 orders which are assigned into three production batches, that is, D1={J6h+1,…,J6h+6}, D2={J1,J2,J3,J3h+1J3h+2,J3h+3},…,Dh+1={J3h-1,J3h-2,J3h,J6h-2,J6h-1,J6h}. According to (2), the delivery date of the delivery batch Dj is (j-1)a, for j=1,2,…,h+1. The common due date of Dj is (j-1/2)a, for j=1,2,…,h+1. From the above discussion, we see that a3j-2+a3j-1+a3j=a, for j=1,2,…,h. This means that the 3-Partition problem has a solution. Combining the “if” part and “only if” part, we have proved the theorem.


## 4. Solving Two Special Cases

In this section, we consider two special cases of problem (P): (1) the problem where the order sequence on the machine in the production part is predetermined and (2) the problem where the batching on the machine in the production part is predetermined. Case (1) occurs when direct sequence is the production strategy used for the customer, while case (2) occurs when direct batching is the production strategy used for the producer. In practice, a direct sequence strategy will be used when the customer’s demands are relatively high, while it is more likely that a direct batching will be used when the production cost is relatively high.


### 4.1. The Predetermined Sequence of Orders

In this case of the problem, the sequence of orders on the batching machine is predeterminedJ1≺J2≺⋯≺Jn. If Ji≺Jj, then order Ji is in preference to order Jj or they are assigned into the same production batch to be processed on the machine. Then the case of (P) can be expressed as (P-case1). In this case, we need to make decisions on the production batching on the machine and delivery batching in the delivery part according to the predetermined sequence of orders. The following dynamic programming algorithm solves the case of the problem.Algorithm DP1. (a) Number the orders in the predetermined sequence and (b) function values.Letg(l,k) be the minimum completion time of order Jk on the parallel-batching machine if orders J1,…,Jk have been scheduled such that the current production batch contains orders Jl+1,…,Jk and 0<k-l≤B.Letf(i,j) be the minimum common due date of the current batch containing Ji+1,…,Jj when they are delivered to the customer and 0<j-i≤C.Definez(j) as the minimum total weighted flow time for the first scheduled orders J1,…,Jj.(c)
Dynamic programming is as follows.Initial conditions are as follows:(3)f0,j=min⁡0<j-k≤Bg(k,j)+t1,j=1,…,C,where g(k,j)=min⁡0<k-h≤Bg(h,k)+max⁡{pk+1,…,pj}, and g(0,0)=0, z(0)=0.Recurrence relations are as follows:(4)zj=min⁡0<j-i≤Czi+∑s=i+1jwsfi,j,where f(i,j)=min⁡0<i-l≤Cmax⁡0<j-k≤Bf(l,i)+t2,g(k,j)+t1 and g(k,j)=min⁡h≤l{g(h,k) + max⁡{pk+1,…,pj}∣i≤k < min⁡{l+B+1,j},0<k-h≤B}.Optimal solution value isz(n).Theorem 5.
Algorithm DP1 solves problem (P-case 1) inO(n4) time.Proof.
Due to the predetermined order sequence, the batching on the machine, the batching, and the delivery date of orders for the delivery need to be decided. From Lemma2, the delivery date of a new delivery batch has two possibilities: the vehicle transports a current delivery batch immediately or the vehicle waits the last order of the current delivery batch that finished processing on the machine. Therefore, the delivery date of the current delivery batch can be derived as max⁡0<j-k≤Bf(l,i)+t2,g(k,j). Hence, we can determine the common due date of the new delivery batch according to its delivery date. Since the delivery capacity and the production capacity are limited, the relations satisfy that 0<j-k≤B and 0<i-l≤C. The increase of the total weighted flow time for the current delivery batch is computed by its common due date f(i,j). Then the total weighted flow time of orders J1,…,Jj is z(j)=min⁡0<j-i≤Cz(i)+∑s=i+1jwsf(i,j). This proves the correctness of the recursive relations and the optimality of the algorithm.
The time complexity of Algorithm DP1 can be established as follows. Due tok,l,i,j≤n, we can obtain that the overall time complexity of Algorithm DP1 is bounded by O(n4).


### 4.2. The Given Batching of Orders in the Production Part

In this case of the problem, the production batching of orders on the machine is predeterminedB1,B2,…,Bk. Then the case can be expressed as (P-case 2). In this case, we need to make decisions on the sequence of the given production batches on the machine and the delivery batching in the delivery part. Let P(Bi) and W(Bi) be the processing time of production batch Bi and the total weight of production batch Bi, respectively.Lemma 6.
For problem (P-case 2), there exists an optimal schedule in which the production batches are processed in the nondecreasingP(Bi)/W(Bi) rule on the machine.Proof (by contradiction).
Consider an optimal scheduleπ∗ formed from a sequence that is not processed in the nondecreasing P(Bi)/W(Bi) rule. In this schedule, there must be at least two adjacent batches, say Bi followed by Bj, such that (5)PBiWBi>PBjWBj.
Now consider the scheduleπ′ formed by interchanging the positions of these two batches. Clearly, the flow times of all the batches preceding the pair under consideration will remain unaffected and so will the flow times of all the succeeding batches. Let z(π∗) and z(π′) denote the total weighted flow time of π∗and π′, respectively. Now if the completion time of the last batch preceding the pair Bi and Bj is s, then the flow times of two batches in π∗ are F(Bi)=s+P(Bi)+t1 and F(Bj)=s+P(Bi)+P(Bj)+t1. We can obtain the flow times of two batches in π′ are F′(Bj)=s+P(Bj)+t1 and F′(Bi)=s+P(Bi)+P(Bj)+t1=F(Bi). Then (6)z(π′)-z(π∗)=WBiF′(Bi)+WBjF′(Bj)-W(Bi)F(Bi)-W(Bj)F(Bj)=W(Bi)F(Bj)-WBjFBi<0.
Comparing terms, it is clear that total weighted flow time ofπ′ is smaller than that of π∗. Thus interchanging the positions of these two batches Bi and Bj can decrease overall weighted flow time. A finite number of repetitions of this argument establish that there exists an optimal schedule where the production batches are processed in the nondecreasing P(Bi)/W(Bi) rule on the machine.Based on Lemma6, the orders processed in the same production batch have the same starting time and completion time on the machine. Hence, the processing on the machine is not influenced by the sequence of orders in a batch. If the orders of the same production batch can be transported to the customer in the same delivery batch, the sequence of order in one batch is irrelevant to the delivery. Otherwise, the sequence of orders in the same production batch affects the batching decision in the delivery part. We have the following lemma to partition the orders into the delivery batches.Lemma 7.
For problem (P-case 2), there exists an optimal schedule in which the orders in the same production batch are sequenced in the longest weight rule of orders in the delivery part.Proof.
Assume that there exists an optimal scheduleπ∗. If π∗ contains orders that are not delivered in the longest weight rule of orders of the same production batch for two adjacent orders Ji and Jj in the same production batch, we assume that Ji is the last order to be delivered in some batch Dl and Jj is the first order to be processed in the next batch Dl+1 such that wi<wj in π∗. Let π′ be a schedule obtained by swapping Ji and Jj. After swapping orders Ji and Jj, π′ contains two new delivery bathes which contain jobs Dl∪{Jj}∖{Ji} and Dl+1∪{Ji}∖{Jj}. All other orders remain the same schedule in π′ as in π∗. Then the flow times of orders Ji and Jj are Fi′=Fj and Fj′=Fi. We have(7)zπ′-zπ∗=wjFi+wiFj-wjFj-wiFi=wi-wjFj-Fi<0.
Therefore, regardless of whetherJi and Jj are transported in the same delivery batch or not, the total weighted flow time associated with π′ is less than that associated with π∗. We can establish the property using a finite number of repetitions of this argument such that there exists an optimal schedule where the orders in the same production batch are sequenced in the longest weight rule of orders in the delivery part.The following dynamic solves the case of (P-case 2).Algorithm DP2. (a) Sequence the given production batches B1,B2,…,Bk in the nondecreasing P(Bi)/W(Bi) rule on the machine. (b) Calculate the completion time of order Ji on the parallel-batching machine Ci, i=1,2,…,n. (c) Number the orders in the shortest weight rule in each production batch. (d) Function values are as follows.Letf(i,j) be the minimum common due date of the current batch containing orders Ji+1,…,Jj when they are delivered to the customer, 0<j-i≤C and l≤j≤n.Letz(j) be the minimum total weighted flow time for the first scheduled orders J1,…,Jj.(e)
Dynamic programming is as follows.Initial conditions are as follows:(8)f0,j,1=Cj+t1,j=1,…,C.Recurrence relations are as follows:(9)zj=min⁡z(i)+∑s=i+1jwsf(i,j,l)∣0<j-i≤C,hhhhhhhh∑s=i+1jwsfi,j,ljC≤l≤j,where f(i,j,l)=min⁡0<s-i≤Ci/C≤l-1≤imax⁡0<s-i≤Cf(s,i,l-1)+t2,Cj+t1.Optimal solution value isz(n).Theorem 8.
Algorithm DP2 can solve problem (P-case 2) inO(n3) time.Proof.
By Lemmas6 and 7, in the schedule for the given production batches B1,B2,…,Bk, where the production schedule follows the nondecreasing P(Bi)/W(Bi) rule on the parallel-batching machine, the delivery schedule follows the longest weight rule for the orders in the same batch. In the recursive relations, the function value is computed by trying every possible size {i+1,…,j} of the last delivery batch and the delivery date of this batch. The common due date contributed by the last batch is max⁡0<s-i≤Cf(s,i,l-1)+t2,Gj. This proves the correctness of the recursive relations and the optimality of the algorithm.
The time complexity of Algorithm DP2 can be established as follows. Sorting the production batches in the nondecreasingP(Bi)/W(Bi) rule requires O(nlog⁡n) time. Sequencing the orders of the same batch in the longest weight rule takes O(nlog⁡n) time. In addition, by definition, we have l,i,j≤n. Therefore, the overall time complexity of Algorithm DP 2 is bounded by O(n3).


## 4.1. The Predetermined Sequence of Orders

In this case of the problem, the sequence of orders on the batching machine is predeterminedJ1≺J2≺⋯≺Jn. If Ji≺Jj, then order Ji is in preference to order Jj or they are assigned into the same production batch to be processed on the machine. Then the case of (P) can be expressed as (P-case1). In this case, we need to make decisions on the production batching on the machine and delivery batching in the delivery part according to the predetermined sequence of orders. The following dynamic programming algorithm solves the case of the problem.Algorithm DP1. (a) Number the orders in the predetermined sequence and (b) function values.Letg(l,k) be the minimum completion time of order Jk on the parallel-batching machine if orders J1,…,Jk have been scheduled such that the current production batch contains orders Jl+1,…,Jk and 0<k-l≤B.Letf(i,j) be the minimum common due date of the current batch containing Ji+1,…,Jj when they are delivered to the customer and 0<j-i≤C.Definez(j) as the minimum total weighted flow time for the first scheduled orders J1,…,Jj.(c)
Dynamic programming is as follows.Initial conditions are as follows:(3)f0,j=min⁡0<j-k≤Bg(k,j)+t1,j=1,…,C,where g(k,j)=min⁡0<k-h≤Bg(h,k)+max⁡{pk+1,…,pj}, and g(0,0)=0, z(0)=0.Recurrence relations are as follows:(4)zj=min⁡0<j-i≤Czi+∑s=i+1jwsfi,j,where f(i,j)=min⁡0<i-l≤Cmax⁡0<j-k≤Bf(l,i)+t2,g(k,j)+t1 and g(k,j)=min⁡h≤l{g(h,k) + max⁡{pk+1,…,pj}∣i≤k < min⁡{l+B+1,j},0<k-h≤B}.Optimal solution value isz(n).Theorem 5.
Algorithm DP1 solves problem (P-case 1) inO(n4) time.Proof.
Due to the predetermined order sequence, the batching on the machine, the batching, and the delivery date of orders for the delivery need to be decided. From Lemma2, the delivery date of a new delivery batch has two possibilities: the vehicle transports a current delivery batch immediately or the vehicle waits the last order of the current delivery batch that finished processing on the machine. Therefore, the delivery date of the current delivery batch can be derived as max⁡0<j-k≤Bf(l,i)+t2,g(k,j). Hence, we can determine the common due date of the new delivery batch according to its delivery date. Since the delivery capacity and the production capacity are limited, the relations satisfy that 0<j-k≤B and 0<i-l≤C. The increase of the total weighted flow time for the current delivery batch is computed by its common due date f(i,j). Then the total weighted flow time of orders J1,…,Jj is z(j)=min⁡0<j-i≤Cz(i)+∑s=i+1jwsf(i,j). This proves the correctness of the recursive relations and the optimality of the algorithm.
The time complexity of Algorithm DP1 can be established as follows. Due tok,l,i,j≤n, we can obtain that the overall time complexity of Algorithm DP1 is bounded by O(n4).


## 4.2. The Given Batching of Orders in the Production Part

In this case of the problem, the production batching of orders on the machine is predeterminedB1,B2,…,Bk. Then the case can be expressed as (P-case 2). In this case, we need to make decisions on the sequence of the given production batches on the machine and the delivery batching in the delivery part. Let P(Bi) and W(Bi) be the processing time of production batch Bi and the total weight of production batch Bi, respectively.Lemma 6.
For problem (P-case 2), there exists an optimal schedule in which the production batches are processed in the nondecreasingP(Bi)/W(Bi) rule on the machine.Proof (by contradiction).
Consider an optimal scheduleπ∗ formed from a sequence that is not processed in the nondecreasing P(Bi)/W(Bi) rule. In this schedule, there must be at least two adjacent batches, say Bi followed by Bj, such that (5)PBiWBi>PBjWBj.
Now consider the scheduleπ′ formed by interchanging the positions of these two batches. Clearly, the flow times of all the batches preceding the pair under consideration will remain unaffected and so will the flow times of all the succeeding batches. Let z(π∗) and z(π′) denote the total weighted flow time of π∗and π′, respectively. Now if the completion time of the last batch preceding the pair Bi and Bj is s, then the flow times of two batches in π∗ are F(Bi)=s+P(Bi)+t1 and F(Bj)=s+P(Bi)+P(Bj)+t1. We can obtain the flow times of two batches in π′ are F′(Bj)=s+P(Bj)+t1 and F′(Bi)=s+P(Bi)+P(Bj)+t1=F(Bi). Then (6)z(π′)-z(π∗)=WBiF′(Bi)+WBjF′(Bj)-W(Bi)F(Bi)-W(Bj)F(Bj)=W(Bi)F(Bj)-WBjFBi<0.
Comparing terms, it is clear that total weighted flow time ofπ′ is smaller than that of π∗. Thus interchanging the positions of these two batches Bi and Bj can decrease overall weighted flow time. A finite number of repetitions of this argument establish that there exists an optimal schedule where the production batches are processed in the nondecreasing P(Bi)/W(Bi) rule on the machine.Based on Lemma6, the orders processed in the same production batch have the same starting time and completion time on the machine. Hence, the processing on the machine is not influenced by the sequence of orders in a batch. If the orders of the same production batch can be transported to the customer in the same delivery batch, the sequence of order in one batch is irrelevant to the delivery. Otherwise, the sequence of orders in the same production batch affects the batching decision in the delivery part. We have the following lemma to partition the orders into the delivery batches.Lemma 7.
For problem (P-case 2), there exists an optimal schedule in which the orders in the same production batch are sequenced in the longest weight rule of orders in the delivery part.Proof.
Assume that there exists an optimal scheduleπ∗. If π∗ contains orders that are not delivered in the longest weight rule of orders of the same production batch for two adjacent orders Ji and Jj in the same production batch, we assume that Ji is the last order to be delivered in some batch Dl and Jj is the first order to be processed in the next batch Dl+1 such that wi<wj in π∗. Let π′ be a schedule obtained by swapping Ji and Jj. After swapping orders Ji and Jj, π′ contains two new delivery bathes which contain jobs Dl∪{Jj}∖{Ji} and Dl+1∪{Ji}∖{Jj}. All other orders remain the same schedule in π′ as in π∗. Then the flow times of orders Ji and Jj are Fi′=Fj and Fj′=Fi. We have(7)zπ′-zπ∗=wjFi+wiFj-wjFj-wiFi=wi-wjFj-Fi<0.
Therefore, regardless of whetherJi and Jj are transported in the same delivery batch or not, the total weighted flow time associated with π′ is less than that associated with π∗. We can establish the property using a finite number of repetitions of this argument such that there exists an optimal schedule where the orders in the same production batch are sequenced in the longest weight rule of orders in the delivery part.The following dynamic solves the case of (P-case 2).Algorithm DP2. (a) Sequence the given production batches B1,B2,…,Bk in the nondecreasing P(Bi)/W(Bi) rule on the machine. (b) Calculate the completion time of order Ji on the parallel-batching machine Ci, i=1,2,…,n. (c) Number the orders in the shortest weight rule in each production batch. (d) Function values are as follows.Letf(i,j) be the minimum common due date of the current batch containing orders Ji+1,…,Jj when they are delivered to the customer, 0<j-i≤C and l≤j≤n.Letz(j) be the minimum total weighted flow time for the first scheduled orders J1,…,Jj.(e)
Dynamic programming is as follows.Initial conditions are as follows:(8)f0,j,1=Cj+t1,j=1,…,C.Recurrence relations are as follows:(9)zj=min⁡z(i)+∑s=i+1jwsf(i,j,l)∣0<j-i≤C,hhhhhhhh∑s=i+1jwsfi,j,ljC≤l≤j,where f(i,j,l)=min⁡0<s-i≤Ci/C≤l-1≤imax⁡0<s-i≤Cf(s,i,l-1)+t2,Cj+t1.Optimal solution value isz(n).Theorem 8.
Algorithm DP2 can solve problem (P-case 2) inO(n3) time.Proof.
By Lemmas6 and 7, in the schedule for the given production batches B1,B2,…,Bk, where the production schedule follows the nondecreasing P(Bi)/W(Bi) rule on the parallel-batching machine, the delivery schedule follows the longest weight rule for the orders in the same batch. In the recursive relations, the function value is computed by trying every possible size {i+1,…,j} of the last delivery batch and the delivery date of this batch. The common due date contributed by the last batch is max⁡0<s-i≤Cf(s,i,l-1)+t2,Gj. This proves the correctness of the recursive relations and the optimality of the algorithm.
The time complexity of Algorithm DP2 can be established as follows. Sorting the production batches in the nondecreasingP(Bi)/W(Bi) rule requires O(nlog⁡n) time. Sequencing the orders of the same batch in the longest weight rule takes O(nlog⁡n) time. In addition, by definition, we have l,i,j≤n. Therefore, the overall time complexity of Algorithm DP 2 is bounded by O(n3).


## 5. Conclusions

In this paper, we propose a coordinated scheduling problem with production operation and delivery operation in the supply chain with batching scheduling and common due date assignment. The orders are processed on a single parallel-batching machine and then the finished orders are transported in batches to the customer. The parallel-batching machine has a limited capacity and the number of orders in each delivery batch cannot exceed the delivery capacity. All orders in the same delivery batch to the customer have a common due date. The common due date of each delivery batch needs to be determined. Inventory level in the supply chain is measured by a function of the common due date for each delivery batch when the completed orders are delivered to the customers. The objective is to minimize total weighted flow time. We first prove that this problem is NP hard in the strong sense. For the two special cases with a given sequence of orders on the machine and a given batching in the production part, we derive two optimal algorithms based on the dynamic programming, respectively. A natural extension of this work would consider approximation algorithms for the problem with the objective of the total weighted flow time. Another extension of this work would consider other objective functions.



---

*Source: 464390-2015-04-12.xml*