# Integrated Scheduling of Production and Distribution with Release Dates and Capacitated Deliveries

Authors: Xueling Zhong; Dakui Jiang
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

This paper investigates an integrated scheduling of production and distribution model in a supply chain consisting of a single machine, a customer, and a sufficient number of homogeneous capacitated vehicles. In this model, the customer places a set of orders, each of which has a given release date. All orders are first processed nonpreemptively on the machine and then batch delivered to the customer. Two variations of the model with different objective functions are studied: one is to minimize the arrival time of the last order plus total distribution cost and the other is to minimize total arrival time of the orders plus total distribution cost. For the former one, we provide a polynomial-time exact algorithm. For the latter one, due to its NP-hard property, we provide a heuristic with a worst-case ratio bound of 2.


---

## Body

## 1. Introduction

Integrated scheduling of production and distribution problem coordinates the scheduling, batching, and delivery decisions at the detailed scheduling level of the supply chain so as to achieve optimal operational performance in a supply chain. The problem has been attracting considerable attention from scheduling researchers as well as operation managers in the past few decades. In this paper, we study a static offline model on scheduling a set ofn orders, N={1,2,…,n}, on a single machine and batch delivering them to the customer. In the production stage, each order j∈N, associated with a release date rj and a processing time pj, needs to be processed once without interruption. Order j∈N cannot be processed before rj and is required to process pj time units on the machine. In the distribution stage, completed orders are delivered to the customer in batches by a sufficient number of homogeneous vehicles so that each vehicle will be used at most once and each delivery shipment will be transported by a dedicated vehicle. Without loss of generality, we assume that n vehicles (B1,B2,…,Bn) are available at time 0. Each order is packaged into a standard-size pallet for delivery convenience regardless of its size, and each vehicle can deliver at most b orders. The delivery cost incurred by each shipment is f. Since all orders are delivered to the same customer and the delivery time of any vehicle is the same, we assume without loss of generality that the delivery time is 0. For a given solution, we use Cj, Dj, and T to denote the processing completion time of order j∈N, the arrival time of order j∈N, and total distribution cost, respectively. Additionally, define Dmax=max⁡{Dj∣j∈N} and Dtotal=∑j∈NDj. The problem is to find a feasible solution such that one of the following two objective functions is minimized: (1) the arrival time of the last order plus total distribution cost, that is, Dmax+T; (2) the total arrival time of orders plus total distribution cost, that is, Dtotal+T. In the following, let P1 and P2 represent the two variations of model to minimize (1) and (2), respectively.The researches on integrated scheduling of production and distribution models have been studied extensively in recent years, and the majority of them assume that all orders are available at time 0 (e.g., Hall and Potts [1]; Hall and Potts [2]; Chen and Vairaktarakis [3]; Chen and Pundoor [4]; Ji et al. [5]; Li and Ou [6]; Wang and Cheng [7]; Armstrong et al. [8]; Jiang and Li [9]; Jiang et al. [10]; Li et al. [11]; and Viergutz and Knust [12]). However, in some applications orders have arbitrary release dates. Hence, some related models involving release dates were also studied. Potts [13] was the first to study the model with single machine in which each order is delivered individually and immediately upon its completion. A heuristic with a worst-case ratio bound of 3/2 was proposed to minimize the arrival time of the last order. After that, Hall and Shmoys [14] proposed a better heuristic for the model with a worst-case ratio bound of 4/3. Zdrzałka [15] provided a heuristic with a worst-case ratio bound of 3/2 for a similar model with constraints that preemption is permitted and a sequence-independent setup time is incurred before processing a job. Gharbi and Haouari [16] studied a model with identical-parallel-machine configuration and proposed an exact branch-and-bound algorithm to solve the model. In addition, a polynomial-time approximation scheme was presented for this model by Mastrolilli [17]. Moreover, the single machine online model was also studied by Seiden [18], Hoogeveen and Vestjens [19], and van den Akker et al. [20], respectively. In recent years, batch delivery and delivery cost are involved in the models. Averbakh and Xue [21] and Averbakh [22] assumed that the orders are released online and batch delivered to the customer. To minimize the sum of the total flow time and total delivery cost, they proposed online algorithms for the single machine model with uncapacitated and capacitated deliveries, respectively. Fan [23] presented an approximation algorithm for the offline version of the model with uncapacitated deliveries proposed by Averbakh and Xue [21]. Lu et al. [24] studied an offline single machine model with capacitated deliveries that assumed that only one vehicle is available to deliver orders. They showed that the problem of minimizing the arrival time of the last order is strongly NP-hard and provided a 5/3-approximation algorithm. Liu and Lu [25] proposed an improved approximation algorithm for the model, which improved the performance ratio from 5/3 to 3/2. However, to the best of our knowledge, little attention is paid on the offline model with release dates in which the delivery batches are capacitated and delivery cost is considered in the objective functions. For more information, we refer the reader to Chen [26] for a comprehensive review on integrated production-distribution scheduling models.The model we study in this paper can be viewed as an extension of production scheduling model with release dates. In production scheduling models, the following two functions are analogous to two widely used functions for measuring customer service: total completion timeCtotal=∑j∈NCj and maximum completion time Cmax=maxj∈NCj. In the following, we review some articles on single machine scheduling models with release dates. For ease of presentation, we adopt the well-known three-field notation α|β|γ introduced by Graham et al. [27], where α describes the machine configuration, β specifies restrictions and constraints associated with the jobs, and γ describes the objective function. Baker [28] showed that the preemptive model 1|rj,pmtn|Ctotal is polynomially solvable, whereas Lenstra et al. [29] showed that the nonpreemptive model 1|rj|Ctotal is NP-hard in the strong sense. In addition, the model 1|rj,pmtn|Cmax is polynomially solvable. Lawler [30] pointed out that the nonpreemptive model 1|rj|Cmax is also polynomially solvable. Since both production scheduling with release dates and batch delivery scheduling are considered, our model will be more complex. This leads us to be interested in the computational complexity of P1 and P2.In this paper, we analyze the computational complexity of the problems and provide efficient algorithms for the problems, respectively. The paper is organized as follows. In Sections2 and 3, we study the problems with different objective functions, respectively. In Section 4, we conclude the paper.


## 2.P1: MinimizingDmax +T

In this section, we first introduce some optimality properties satisfied for problemP1. Then, we provide a polynomial-time exact algorithm for it. We now present some preliminary results about the structure of an optimal solution of P1 as follows.Lemma 1.
There exists an optimal solution for problemP1 in which all of the following hold:(1)
The orders are delivered in the increasing sequence of their processing completion time.(2)
The orders are delivered inz=n/b shipments, where n/b is the smallest integer no less than n/b. The first shipment contains n-(z-1)b orders and each of the remaining z-1 shipments contains b orders.(3)
The departure time of each shipment is the time when all the orders in it complete processing.The above optimality properties are straightforward; we omit the proofs.Further, we define anEarliest Release Date first (ERD) rule. That is, a set of customer orders is in ERD order if the customer orders are sequenced in a nondecreasing order of their release dates, and the customer orders with equal release dates are sequenced in the arbitrary order.Lemma 2.
There exists an optimal solution for problemP1 in which the customer orders are scheduled in ERD order.Proof.
By Lemma1, the orders are delivered by z=n/b vehicles in an optimal solution of problem P1, which is independent of how the orders are scheduled on the machine. Hence, problem P1 is reduced to minimizing Dmax. Because the delivery time of each shipment is assumed to be 0, we have Dmax=Cmax for a given solution, in which Cmax is the maximum processing completion time of orders. As a result, the optimal solution of single machine makespan scheduling problem with release dates 1|rj|Cmax is an optimal order processing schedule of problem P1. Note that ERD rule provides an optimal solution for problem 1|rj|Cmax [30]. Hence, ERD rule provides an optimal order processing schedule for problem P1.Based on the results stated in Lemmas1 and 2, an exact algorithm for problem P1 is given as follows.Algorithm EAStep 1.
Place all orders in a list in ERD order. Reindex the orders by their position in the list. Set current instantt=r1.Step 2.
Choose the first unscheduled orderj of the list. Schedule it to process at instant t′=max⁡{t,rj}. Set t=t′+pj. Repeat Step 2 until all orders are scheduled.Step 3.
Deliver the orders such that they satisfy Lemma1.In algorithm EA, the majority of computation time is used for sorting orders in Step 1, which takesO(nlog⁡n) time. Hence, we have the following.Theorem 3.
Algorithm EA finds an optimal solution of problemP1 in O(nlog⁡n) time.


## 3.P2: MinimizingDtotal +T

When delivery cost of each shipment is ignored, that is,f=0, problem P2 is reduced to problem 1|rj|Ctotal, which is known to be NP-hard in the strong sense [29]. Thus, problem P2 is also NP-hard in the strong sense. To solve problem P2, we first study an auxiliary problem Paux. Everything else in problem Paux is the same as in problem P2 except that preemption is allowed; that is, order processing can be preempted and resumed later. We first introduce an optimality property of Paux related to theShortest Remaining Processing Time first (SRPT) rule, which prescribes to process at each instant t the job with the smallest remaining processing time among all already released unfinished jobs, with some unambiguous rule for breaking ties. For example, the jobs can be indexed, and in case of a conflict between jobs with equal remaining processing times, the job with the smallest index would be given priority; such rule is called lexicographic [22]. According to this definition, there is exactly one SRPT order for a given set of jobs. Moreover, for two classical preemptive problems 1|rj,pmtn|Ctotal and 1|rj,pmtn|Cmax, the SRPT rule provides an optimal solution [28]. Pruhs et al. [31] also presented the following result.Lemma 4.
In the SRPT job schedule, at any instant the number of processed jobs is not smaller than in any other job schedule.According to Lemma4, we obtain the following result satisfied for problem Paux.Lemma 5.
There exists an optimal solution for problemPaux in which the orders are processed in the sequence ordered by SRPT rule on the machine.Proof.
Suppose that there exists an optimal solution in which the order processing schedule does not follow the SRPT rule. Denote the number of vehicles used in this solution byk∗. Let τk be the arrival time of vehicle k and nk the number of the finished orders in time τk in this solution, k=1,…,k∗. Clearly, nk∗=n. Then, the total arrival time of orders in this solution is equal to(1)n1τ1+∑k=1k∗-1nk+1-nkτk+1=∑k=1k∗-1nkτk-τk+1+nτk∗.
By Lemma4, at any instant k the number of processed orders nk in the SRPT order processing schedule is the biggest one in all order processing schedules. In addition, τk-τk+1<0, for k=1,…,k∗-1. Hence, we can rearrange the jobs in the SRPT order without increasing ∑k=1k∗-1nk(τk-τk+1). Also, because the SRPT rule provides an optimal solution for 1|rj,pmtn|Cmax, the SRPT order processing schedule is the one in which τk∗ is minimized. Therefore, we can rearrange the customer orders in the SRPT order without increasing the objective value.Without loss of generality, we assume that the customer orders are indexed in SRPT order so thatC1≤⋯≤Cn. The following dynamic programming algorithm finds an optimal solution for Paux.Algorithm DP. Define value function V(j) = minimum total cost contribution of a solution for the first j orders {1,…,j}.Initial condition:V(0)=0.Recursive relation: forj=1,…,n,(2)Vj=min⁡Vj-h+h·Cj+f∣h=1,…,min⁡b,j.Optimal solution value: it isV(n).Theorem 6.
Algorithm DP finds an optimal solution of problemPaux in O(nlog⁡n+nb) time.Proof.
By Lemma5, in a solution for the first j order {1,…,j}, where the production schedule follows SRPT rule, the departure time of the last vehicle is always Cj. This implies that the delivery time of all the orders in the last vehicle is Cj. In the recursive relation, the value function is computed by trying every possible size of the last vehicle. Given that the size of the last vehicle is h, the total cost contributed by the last vehicle is h·Cj+f, where h·Cj is the contribution to the total delivery time and f is the distribution cost. This proves the correctness of the recursive relation and hence the optimality of the algorithm. There are n states in this DP, and it takes no more than O(b) time to calculate the value for each state. Sorting the orders by SRPT rule takes O(nlog⁡n) time. Therefore, the overall time complexity of DP is bounded by O(nlog⁡n+nb).Corollary 7.
The valueV(n) generated by algorithm DP is a lower bound of the optimal objective value of P2.Proof.
Because the optimal solution ofP2 is a feasible solution of Paux, the optimal objective value of Paux is no larger than that of P2. By Theorem 6, the solution obtained by algorithm DP is an optimal one for problem Paux. Hence, the value V(n) generated by algorithm DP is a lower bound of the optimal objective value of P2.In the remainder of this section, we present a polynomial-time heuristic for problemP2 and analyze its worst-case performance.Heuristic HAStep 1.
Run algorithm DP to obtain a basic solutionSaux∗. Denote the number of vehicles used in this solution by k∗. Let Caux(j) be denoted as the processing completion time of order j, for j∈N. Place all orders in a list sorted by an increasing order of their processing completion times Caux(j) in this basic solution. Reindex the orders by their position in the list. Set current instant t=r1.Step 2.
Choose the first unscheduled orderj of the list. Schedule it to process at instant t′=max⁡{t,rj}. Set t=t′+pj. Repeat Step 2 until all orders are scheduled.Step 3.
Usek∗ vehicles to deliver orders. Each vehicle delivers the same orders as in Saux∗. The departure time of each vehicle is the time when all the orders in it complete processing. Denote the resulting solution by S∗.Clearly, the time complexity of heuristic HA isO(nlog⁡n+nb) because the majority of its computation time is to run algorithm DP. Next, we analyze its worst-case performance. Denote the optimal objective value of problems P2 and Paux by FP2∗ and Faux∗, respectively. Let FP2(S∗) be denoted as the contribution of solution S∗ to the objective value of problem P2.Theorem 8.
F
P
2
(
S
∗
)
≤
2
F
P
2
∗; that is, the worst-case ratio of heuristic HA is bounded by 2.Proof.
InS∗, let k¯ be the order in vehicle Bk with largest processing completion time Cj, k=1,…,k∗. Clearly, Ck¯=DBk. Because there is no idle time between instant maxj∈Bkrj and Ck¯, we have(3)Ck¯=DBk≤maxj∈Bk⁡rj+∑h=1k∑j∈Bhpj.
Denote the arrival time of orderj in Saux∗ by Daux(j), for j∈N. Let Daux(Bk) be denoted as the arrival time of vehicle Bk in Saux∗, k=1,…,k∗. For each order j in vehicle Bk, we have rj≤Caux(j)≤Caux(k¯). This implies that maxj∈Bkrj≤Caux(k¯). In addition, ∑h=1k∑j∈Bhpj≤Caux(k¯). Hence, we have Ck¯≤2Caux(k¯). Consequently, BkDBk≤2BkDaux(Bk). Then,(4)∑j∈NDj=∑k=1k∗BkDBk≤2∑k=1k∗BkDauxBk.
Since the numbers of vehicles used inSaux∗ and S∗ are equal, the distribution cost of these solutions is also identical. Hence, FP2(S∗)≤2Faux∗. By Corollary 7, we have Faux∗≤FP2∗. Hence, FP2(S∗)≤2FP2∗.


## 4. Conclusions

In this paper, we have studied two variations of the integrated scheduling of production and distribution model with release dates and capacitated deliveries, each of which has a different objective function. The first variation is to minimize the arrival time of the last order plus total distribution cost; we first presented some optimality properties satisfied for the variation. Adopting these optimality properties, we proposed a polynomial-time exact algorithm which implies that this problem is easy. The second variation is to minimize total arrival time of the orders plus total distribution cost; due to its NP-hard property, we developed a heuristic for it. In this heuristic, we first construct an auxiliary problem which is the problem with preemptions and develop a dynamic programming algorithm for the auxiliary problem. Then we propose the heuristic based on the solution obtained by the dynamic programming algorithm. Finally, we analyze its worse-case performance and show that its worst-case ratio is bounded by 2.For future research, it will be worth extending the existing model to parallel machines and developing effective and efficient algorithms.



---

*Source: 9315197-2016-03-28.xml*