# Parallel Machine Scheduling with Batch Delivery to Two Customers

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

---

## Abstract

In some make-to-order supply chains, the manufacturer needs to process and deliver products for customers at different locations. To coordinate production and distribution operations at the detailed scheduling level, we study a parallel machine scheduling model with batch delivery to two customers by vehicle routing method. In this model, the supply chain consists of a processing facility withm parallel machines and two customers. A set of jobs containing n1 jobs from customer 1 and n2 jobs from customer 2 are first processed in the processing facility and then delivered to the customers directly without intermediate inventory. The problem is to find a joint schedule of production and distribution such that the tradeoff between maximum arrival time of the jobs and total distribution cost is minimized. The distribution cost of a delivery shipment consists of a fixed charge and a variable cost proportional to the total distance of the route taken by the shipment. We provide polynomial time heuristics with worst-case performance analysis for the problem. If m=2 and (n1-b)(n2-b)<0, we propose a heuristic with worst-case ratio bound of 3/2, where b is the capacity of the delivery shipment. Otherwise, the worst-case ratio bound of the heuristic we propose is 2-2/(m+1).


---

## Body

## 1. Introduction

To meet the soaring demands of electronic devices in recent years, manufacturers in China start building new factories to increase production capacities. Two different strategies are mainly adopted by these manufacturers, one is to build a new factory at the undeveloped land near current factory and the other is to place the new factory to a different region with lower labor cost. Take Foxconn Technology Group, the world’s largest electronics contractor manufacturer, for example, it not only built a new factory at Guanlan Technology Park after running one at Yousong Industrial District in Shenzhen city of China but also has been building many other factories at different regions of China. Clearly, it can share resources easily by adopting the former strategy and reduces production cost by adopting the latter one. Meanwhile, as a nonstandard parts supplier of a manufacturer adopting the former strategy, it should not only offer parts to the current factory but also provide parts to the new-built factory. In such applications, very little inventory of finished parts exists at any point of time since nonstandard parts are custom made and the supplier will not start production early before it receives orders from the manufacturer. Hence, the production and distribution operations of the supplier are linked immediately, and the close linkage between production and distribution necessitates coordinating production and distribution operations at the level of detailed scheduling.In this paper, we consider a parallel machine scheduling problem with batch delivery to two customers faced by the nonstandard part supplier in the above-described supply chain, which can be described as follows. There is a manufacturer, who has a set ofm>2 identical parallel machines facility, M={1,2,…,m}. At time zero, the manufacturer receives a set of n jobs, N={1,2,…,n}, from two customers 1 or 2, which are located at different locations in an underlying transportation network. Among jobs in N, jobs in the subset Nk⊆N are ordered by customer k, k=1,2. Let nk=|Nk| denote the number of jobs in Nk. It is easy to see that N=N1∪N2 and n=n1+n2. Each job in N should be processed onto one of the m machines in manufacturer and then delivered to its customer in batch without intermediate inventory. Associated with each job j∈N has a processing time of pj units. Job preemption is not allowed; that is, processing a job on a machine cannot be interrupted until it is finished. All jobs and machines are available at time 0. All the finished jobs ordered by customer k need to be delivered in batch to customer k by the vehicle, k=1,2. Suppose that there are enough homogeneous vehicles available so that each vehicle will be used once and each delivery shipment will be transported by a dedicated vehicle. All the vehicles are stationed at the processing facility at time 0 and must go back to the facility once they complete a shipment. Each vehicle can carry up to at most b jobs in one shipment. The transportation cost incurred by each batch consists of a fixed charge f and a variable cost dependent on the particular route taken by the vehicle. We use c0i, cij, and ci0, respectively, to denote the variable cost for traveling from the processing facility to customer i∈{1,2}, from customer i∈{1,2} to customer j∈{1,2}, and from customer i∈{1,2} to the processing facility. The corresponding delivery times are denoted as t0i, tij, and ti0, respectively. We assume that tii=cii=0, tij=tji, cij=cji, t0i+tij≥tj0, and c0i+cij≥cj0, i,j=0,1,2. A delivery vehicle can depart from the processing facility only when all the jobs to be delivered have completed processing. We use Dj to denote the time when job j∈N arrives to its customer. Define Dmax=max{Dj∣j∈N} as the maximum arrival time to the two customers of jobs in N. The problem is to find a joint production and distribution schedule such that the tradeoff between maximum delivery time of the jobs and total distribution cost, that is, αDmax+(1-α)T, is minimized, where T denotes the total distribution cost, Dmax measures customer service level, and 0≤α≤1 is a given constant and represents the decision maker’s relative preference on customer service level and total distribution cost. Such an objective function is also adopted by Chen and Vairaktarakis [1].This problem is a variation of the integrated production-distribution scheduling models with batch delivery to multiple customers by vehicle routing method, which is always encountered in make-to-order or time-sensitive product supply chains. In these supply chains, finished jobs are often delivered to customers immediately or shortly after the production which lead to production and distribution operations that are intimately linked with no intermediate inventory. Even though the research on integrated production-distribution scheduling models is fairly recent, much excellent work have been done in the last decade. Vehicle routing method is an efficient way to serve multiple customers by a shipment. However, only few literature studied the models with vehicle routing method (e.g., [1–4], among others). Chen and Vairaktarakis [1] studied a more general case, in which there are k≥2 customers in the supply chain. They proposed a heuristic with worst case ratio bound of 2-1/m, the time complexity of which is O(bkn2kkk-1). Clearly, when k=2 the heuristic also needs to take O(b2n4) time. However, if jobs are delivered to the customers individually and immediately, Woeginger [5] provided a heuristic with worst case ratio bound of 2-2/(m+1), the time complexity of which is merely O(nlog⁡n). Hence, there may exist a heuristic that could outperform the heuristic proposed by Chen and Vairaktarakis [1]. According to this observation, we are interested in designing a more effective and efficient algorithm by adopting the approach proposed by Woeginger [5].The rest of the paper is organized as follows. In Section2, we give some optimality properties of the problem and introduce some notations. Then, we study the problem with α=1 or α=0 in Section 3 and with 0<α<1 in Section 4. Finally, in Section 5, we conclude the paper.


## 2. Notations and Preliminary Results

In this section, we first summarize the notations we used in our model and introduce some new notations in the following list:M: a set of m identical parallel machines in manufacturer.N: a set of n jobs ordered by two customers.Nk: a subset of jobs ordered by customer k, k=1,2.nk: the number of jobs in Nk, k=1,2.pj: the processing time of job j, j∈N.f: the fixed cost of using a vehicle.c0i: the variable cost of traveling processing facility to customer j, j∈N.cij: the variable cost of traveling from customer i to customer j, i=1,2 and j=1,2.t0i: the time of traveling processing facility to customer i, i=1,2.tij: the time of traveling from customer i to customer j, i=1,2 and j=1,2.Dj: the arrival time of job j to its customer, j∈N.Dmax(π): the maximum arrival time of the jobs in solution π.T(π): the total distribution cost in solution π.α: the preference on customer service level and total distribution cost, 0≤α≤1.F(π): the objective value of solution π, F(π)=αDmax(π)+(1-α)T(π).Dmax∗: the optimal objective value of the problem with α=1.T∗: the optimal objective value of the problem with α=0.S∗: the optimal solution of our problem.We then present some straightforward optimality properties for the problem. Proofs are omitted.Lemma 1.
There exists an optimal solution for the problem in which(1)
there is no idle time between the jobs processed on each machine in the processing facility,(2)
the departure time of each shipment is the completion time of the last job included in the shipment,(3)
jobs that are processed on the same machine and delivered in the same shipment are processed consecutively on that machine.Lemma 2.
D
m
a
x
∗
≤
D
m
a
x
(
S
∗
) and T∗≤T(S∗).


## 3. The Problem withα=1 or α=0

In this section, we study two special cases of the problem withα=1 or α=0.In the problem withα=1, because no cost is considered, each job is delivered in a separate vehicle immediately after it completes processing. Then, the problem is reduced to minimize Dmax. If t01=t02=t12=0, this case is equivalent to the classical parallel machine maximum completion time scheduling problem Pm ∥ Cmax, which is known to be NP-hard [6]. Hence, this case is also NP-hard. Woeginger [5] studied a model as the same as ours except that each job j∈N is associated with an individual delivery time and develop a heuristic with worst-case ratio bound of 2-2/(m+1). Denote such a heuristic as MLS in [5]. The running complexity time of heuristic MLS is O(nlog⁡n). By the major idea of heuristic MLS, we propose a heuristic with worst-case ratio bound of 2-2/(m+1) for the problem with α=1 or α=0. Denote this heuristic as MMLS (Modified MLS). The running time complexity of heuristic MMLS is O(nlog⁡n). Similar to heuristic MLS, in heuristic MMLS, let Wm(j)=(m-1)pj+mt0j denote a weight of job j depending on its processing time and delivery time, j∈N. The value of Wm(j) can be computed in advance for each j∈N. Also, we let Li represent the total processing time of jobs assigned to machine i so far during the algorithm execution, i∈M. Heuristic MMLS can be described in detail as follows.Heuristic MMLSStep
1. Place all jobs in a list sorted by nonincreasing weight Wm(j). Set Li=0, for i∈M.Step
2. Select a machine i for which Li is as small as possible (select i arbitrarily if there is a tie). Choose the first unscheduled job j of the list and assign it to machine i. Set Li=Li+pj. Repeat Step 2 until all jobs are scheduled.Step
3. For all i∈M, resort the jobs assigned to machine i in Step 2 by nonincreasing delivery time. Denote this solution by Sα=1.Clearly, our problem withα=1 is a special case of the problem studied by Woeginger [5] and can also be solved by heuristic MMLS. Then, we have the following.Theorem 3.
F
(
S
α
=
1
)
≤
(
2
-
2
/
(
m
+
1
)
)
D
m
a
x
∗.The problem withα=0 is to minimize the total distribution cost. Because Dmax is not considered, each vehicle should deliver as many jobs as possible to minimize the total distribution cost. Thus, the following results hold for the problem with α=0. Before showing these results, we especially point out that job j directly delivered by a vehicle indicates that job j is delivered to its corresponding customer directly, and the vehicle loading job j does not pass by the other customer. We let yk=nk-b(⌈nk/b⌉-1), k=1,2. The useful properties are presented as follows.Lemma 4.
There exists an optimal solution for the problem withα=0 in which b(⌈nk/b⌉-1) jobs in Nk are directly delivered by ⌈nk/b⌉-1 vehicles, each of which contains b jobs, k=1,2.Corollary 5.
Ifc12≥f+c01+c02, ⌈nk/b⌉ vehicles are used in the optimal distribution schedule of the problem with α=0 to direct deliver all jobs in Nk, each of which contains b jobs, k=1,2.Corollary 6.
Ify1y2=0, ⌈nk/b⌉ vehicles are used in the optimal distribution schedule of the problem with α=0 to direct deliver all jobs in Nk, each of which contains b jobs, k=1,2.Corollary 7.
Ify1+y2>b, ⌈nk/b⌉ vehicles are used in the optimal distribution schedule of the problem with α=0 to direct deliver all jobs in Nk, each of which contains b jobs, k=1,2.Corollary 8.
Ifc12<f+c01+c02 and y1y2≠0 and y1+y2≤b, in the optimal distribution schedule of the problem with α=0, ⌈nk/b⌉-1 vehicles are used to direct deliver b(⌈nk/b⌉-1) jobs in Nk, each of which contains b jobs, k=1,2, one vehicle is used to deliver the remaining y1+y2 jobs, which goes to customer 2 via customer 1 and then directly returns to the processing facility.Since the above results are straightforward, we omit the proofs. Obviously, it is easy to construct the following polynomial-time exact algorithm for the problem withα=0 by adopting these results.Algorithm EAStep
1. Assign all jobs in N to the m machines in arbitrary sequence.Step
2. If c12≥f+c01+c02, schedule the job delivery such that it satisfies Corollary 5. Otherwise, if y1y2=0, schedule the job delivery such that it satisfies Corollary 6; if y1+y2>b, schedule the job delivery such that it satisfies Corollary 7; if y1y2≠0 and y1+y2≤b, schedule the job delivery such that it satisfies Corollary 8.


## 4. The Problem with0<α<1

When0<α<1, the problem is NP-hard. This is because the following case of the problem f=c0i=t0i=cij=tij=0, for i=1,2 and j=1,2, is equivalent to the classical NP-Hard problem Pm ∥ Cmax. Associated with n1 and n2 we study a case with nk<b for k=1,2 and the other cases. We will develop a heuristic for the case with nk<b for k=1,2 in Section 4.1 and develop another heuristic for the other cases in Section 4.2, respectively. Particularly notice that the other cases include two types: the case with nk≥b for k=1,2 and the case with (n1-b)(n2-b)≤0.


### 4.1. The Case withnk<b for k=1,2

We first introduce some straightforward optimality properties for this case, which will be used in the sequel. Proofs are easy, and we leave them to the reader.Lemma 9.
There exists an optimal solution for the casenk<b, k=1,2, and either c12>f+c01+c02, or n1+n2>b, in which all the jobs for customer k are delivered by a single vehicle, k=1,2.In the following, we present a polynomial-time heuristic, denoted as H1, for the case and analyze its worst-case performance. In heuristic H1, similar to heuristic MMLS, we also letWm(j)=(m-1)pj+mt0j denote a weight of job j depending on its processing time and delivery time, j∈N, and let Li represent the total processing time of jobs assigned to machine i so far during the algorithm execution, i∈M. The value of Wm(j) can be computed in advance for each j∈N. Note also that we provide a Largest Processing Time first (LPT) rule for sorting the jobs. Heuristic H1 can be described in detail as follows.Heuristic H1Step
1. If n1+n2≤b and c12<f+c01+c02, go to Step 2; otherwise, go to Step 5.Step
2. Place all jobs in a list in LPT order. Set Li=0, for i∈M.Step
3. Select a machine i for which Li is as small as possible (select i arbitrarily if there is a tie). Choose the first unscheduled job j of the list and assign it to machine i. Set Li=Li+pj. Repeat Step 3 until all jobs are scheduled.Step
4. Deliver all jobs in N by a single vehicle. In order to complete the travel, two routes can be opted for the vehicle. The first one is that the vehicle goes to customer 1 via customer 2 and then direct returns to the processing facility and the second one is that the vehicle goes to customer 2 via customer 1 and then directly returns to the processing facility. Denote the resulting solution adopting the first route and the second route by S22 and S23, respectively.Step
5. Place all jobs in a list sorted by nonincreasing weight Wm(j). Set Li=0, for i∈M.Step
6. Select a machine i for which Li is as small as possible (select i arbitrarily if there is a tie). Choose the first unscheduled job j of the list and assign it to machine i. Set Li=Li+pj. Set Li=Li+pj. Repeat Step 6 until all jobs are scheduled.Step
7. For all i∈M, resort the jobs assigned to machine i in Step 6 by nonincreasing delivery time.Step
8. For k=1,2, deliver all jobs in Nk by a single vehicle. Denote the resulting solution by S23.Step
9. Denote the final solution by S2. If n1+n2≤b and c12<f+c01+c02, select one from the three solutions S21, S22, and S23 with the lowest objective value as the final solution. Otherwise, set S23 as the final solution.In heuristic H1, most of the computing time is used for sorting jobs. Hence, the time complexity of the heuristic isO(nlog⁡n). Next, we analyze its worst-case performance.Theorem 10.
F
(
S
2
)
≤
(
2
-
2
/
(
m
+
1
)
)
F
(
S
∗
).Proof.
There are three cases associated withn1 and n2.
Case
(i). If n1+n2>b, then by Lemma 9, the distribution schedule of S23 is an optimal one. Meanwhile, Dmax(S23)≤(2-2/(m+1))Dmax(S∗). Therefore, we have F(S23)≤(2-2/(m+1))F(S∗).
Case
(ii). If n1+n2≤b and c12>f+c01+c02, then by Lemma 9, the distribution schedule of S23 is an optimal one. Due to Dmax(S23)≤(2-2/(m+1))Dmax(S∗), we thus have F(S23)≤(2-2/(m+1))F(S∗).
Case
(iii). If n1+n2≤b and c12≤f+c01+c02, there are two subcases associated with the distribution schedule of S∗.
Subcase
(i). If two vehicles are used to deliver jobs, one vehicle delivers all jobs in N1 and the other one delivers all jobs in N2; then F(S23)≤(2-2/(m+1))F(S∗).
Subcase
(ii). If only one vehicle is used to deliver all jobs in N, then T(S∗)=f+c01+c12+c02 and the optimal route of the vehicle is one of the routes adopted by S21 or S22. Therefore, the problem is reduced to the classical scheduling problem Pm ∥ Cmax. It is well known that the worst-case performance bound of the heuristic for this problem by applying LPT rule is 4/3-1/3m [7]. Thus, in this subcase, min{F(S21),F(S22)}≤(4/3-1/3m)F(S∗).
In Step 9 of the heuristic, we select the best of the three solutions; henceF(S2)≤(2-2/(m+1))F(S∗).


### 4.2.  The Other Cases

As mentioned before, except the case withnk<b for k=1,2 the other cases include the case with nk≥b for k=1,2 and the case with (n1-b)(n2-b)≤0. We have discussed the case with nk<b for k=1,2 in Section 4.1. In this subsection, we develop below a heuristic, denoted as H2, for the case with nk≥b for k=1,2 and the case with (n1-b)(n2-b)≤0. Similar to heuristic MMLS, we also let Wm(j)=(m-1)pj+mt0j denote a weight of job j depending on its processing time and delivery time, j∈N, and let Li represent the total processing time of jobs assigned to machine i so far during the algorithm execution, i∈M. The value of Wm(j) can be computed in advance for each j∈N. Heuristic H2 can be described in detail as follows.Heuristic H2Step
1. Place all jobs in a list sorted by nonincreasing weight Wm(j). Set Li=0, for i∈M.Step
2. Select a machine i for which Li is as small as possible (select i arbitrarily if there is a tie). Choose the first unscheduled job j of the list and assign it to machine i. Set Li=Li+pj. Repeat Step 2 until all jobs are scheduled.Step
3. For all i∈M, resort the jobs assigned to machine i in Step 2 by nonincreasing delivery time.Step
4. For k=1,2, use ⌈nk/b⌉ vehicles to deliver jobs in Nk, where the first vehicle delivers ni-(⌈nk/b⌉-1)b jobs and the remaining (⌈nk/b⌉-1) vehicles deliver b jobs. Denote the resulting solution by S11.Step
5. For k=1,2, use ⌈nk/b⌉-1 vehicles to deliver the last nk-yk jobs in Nk with largest processing completion time, each of which contains b jobs, where yk=nk-b(⌈nk/b⌉-1). Use one vehicle to deliver the remaining y1+y2 jobs. Two routes are available for the vehicle: the former one is that the vehicle goes to customer 1 via customer 2 and then directly returns to the processing facility and the latter one is that the vehicle goes to customer 2 via customer 1 and then directly returns to the processing facility. Denote the resulting solution adopting the former route and the latter route by S12 and S13, respectively.Step
6. Denote the final solution by S1. Select one from the three solutions S11, S12, and S13 with the smallest objective value as the final solution.In heuristic H2, most of the computing time is used for sorting jobs in Step 1. Hence, the time complexity of the heuristic isO(nlog⁡n). Next, we analyze its worst case performance.Theorem 11.
D
m
a
x
(
S
11
)
≤
(
2
-
2
/
(
m
+
1
)
)
D
m
a
x
(
S
∗
).Proof.
It is clear thatDmax(S11)=Dmax(Sα=1) since they adopt the same production schedule and the maximum arrival time of the jobs is independent of how the delivery shipments are formed when each job is direct delivered to its customer with no vehicle routing. In S11, let Pk be the maximum processing completion time of jobs in Nk, for k=1,2. Hence, Dmax(S11)=Dmax(Sα=1)=max{Pk+t0k∣k=1,2}. By Theorem 3, Dmax(S11)≤(2-2/(m+1))Dmax∗. Moreover, by Lemma 2, Dmax(S∗)≥Dmax∗. Thus we have Dmax(S11)≤(2-2/(m+1))Dmax(S∗).For the case withnk≥b for k=1,2 and the case with (n1-b)(n2-b)≤0, we have the following result.Theorem 12.
Ifnk≥b for k=1,2, T(S11)≤4/3T(S∗); if (n1-b)(n2-b)<0, T(S11)≤3/2T(S∗).Proof.
InS11, T(S11)=∑k∈K‍⌈nk/b⌉(f+2c0k). There are three cases associated with y1 and y2.
Case
(i). If y1y2=0, then, by Corollary 6, T∗=∑k=12‍⌈nk/b⌉(f+2c0k). Hence, T(S11)=T∗.
Case
(ii). If y1+y2>b, then, by Corollary 7, T∗=∑k=12‍⌈nk/b⌉(f+2c0k). Hence, T(S11)=T∗.
Case
(iii). If y1y2>0 and y1+y2≤b, then, by Corollary 8, we have(1)T∗=∑k=12nkb-1f+2c0k+min⁡f+c01+c12+c02,2f+2c01+2c02.
There are two subcases associated withT(S11) and T∗.
Subcase
(i). If f+c01+c12+c02≥2f+2c01+2c02, we have T(S11)=T∗.
Subcase
(ii). If f+c01+c12+c02<2f+2c01+2c02, we have T∗=∑k=12‍(⌈nk/b⌉-1)(f+2c0k)+f+c01+c12+c02. Now consider T(S11): (2)TS11=∑k=12nkb-1f+2c0k+2f+2c01+2c02=∑k=12nkb-2f+2c0k+433f+3c01+3c02.
Whennk≥b and y1y2>0, we have ⌈nk/b⌉>nk/b>1, for k=1,2. This implies that ⌈nk/b⌉≥2, k=1,2. Thus,(3)TS11≤43∑k=12nkb-2f+2c0k+433f+3c01+c12+3c02=43T∗.
When(n1-b)(n2-b)<0 and y1y2>0, there exists a k¯∈{1,2} that satisfies ⌈nk¯/b⌉≥1 and ⌈n3-k¯/b⌉≥2. Thus, (4)TS11≤32∑k=12nkb-1f+2c0k+2f+2c01+2c02-12f+2c0k¯=32∑k=12nkb-1f+2c0k+32f+c0k¯+2c03-k¯=32T∗-123c12-c03-k¯+c0k¯≤32T∗.
Therefore, in both cases, we can conclude thatT(S11)≤4/3T∗ if nk≥b for k=1,2 and T(S1)≤3/2T∗ if (n1-b)(n2-b)<0. By Lemma 2, T∗≤T(S∗). Therefore, T=(S11)≤4/3T(S∗) if n1≥b and n2≥b and T(S11)≤3/2T∗ if (n1-b)(n2-b)<0.Corollary 13.
Ifm=2 and (n1-b)(n2-b)<0, F(S1)≤3/2F(S∗); otherwise, F(S1)≤(2-2/(m+1))F(S∗).Proof.
By Theorem11, Dmax(S11)≤(2-2/m+1)Dmax(S∗). If n1≥b and n2≥b, by Theorem 12, T(S11)≤4/3T(S∗). Due to 4/3≤2-2/m+1 when m≥2, we have F(S11)≤(2-2/m+1)F(S∗). Otherwise, if (n1-b)(n2-b)<0, by Theorem 12, T(S11)≤3/2T(S∗). Due to 2-2/m+1≥3/2 when m>2, we have F(S11)≤(2-2/m+1)F(S∗). However, if m=2, then 2-2/m+1=4/3<3/2; if m>2, then 2-2/m+1≥3/2. Hence, if m=2 and (n1-b)(n2-b)<0, F(S11)≤3/2F(S∗); if m>2 and (n1-b)(n2-b)<0, F(S11)≤(2-2/m+1)F(S∗). Because S1 is one of the solutions S11, S12, and S13 with the smallest objective value, F(S1)≤F(S11). This implies that F(S1)≤3/2F(S∗) if m=2 and (n1-b)(n2-b)<0, and F(S1)≤(2-2/(m+1))F(S∗) otherwise.


## 4.1. The Case withnk<b for k=1,2

We first introduce some straightforward optimality properties for this case, which will be used in the sequel. Proofs are easy, and we leave them to the reader.Lemma 9.
There exists an optimal solution for the casenk<b, k=1,2, and either c12>f+c01+c02, or n1+n2>b, in which all the jobs for customer k are delivered by a single vehicle, k=1,2.In the following, we present a polynomial-time heuristic, denoted as H1, for the case and analyze its worst-case performance. In heuristic H1, similar to heuristic MMLS, we also letWm(j)=(m-1)pj+mt0j denote a weight of job j depending on its processing time and delivery time, j∈N, and let Li represent the total processing time of jobs assigned to machine i so far during the algorithm execution, i∈M. The value of Wm(j) can be computed in advance for each j∈N. Note also that we provide a Largest Processing Time first (LPT) rule for sorting the jobs. Heuristic H1 can be described in detail as follows.Heuristic H1Step
1. If n1+n2≤b and c12<f+c01+c02, go to Step 2; otherwise, go to Step 5.Step
2. Place all jobs in a list in LPT order. Set Li=0, for i∈M.Step
3. Select a machine i for which Li is as small as possible (select i arbitrarily if there is a tie). Choose the first unscheduled job j of the list and assign it to machine i. Set Li=Li+pj. Repeat Step 3 until all jobs are scheduled.Step
4. Deliver all jobs in N by a single vehicle. In order to complete the travel, two routes can be opted for the vehicle. The first one is that the vehicle goes to customer 1 via customer 2 and then direct returns to the processing facility and the second one is that the vehicle goes to customer 2 via customer 1 and then directly returns to the processing facility. Denote the resulting solution adopting the first route and the second route by S22 and S23, respectively.Step
5. Place all jobs in a list sorted by nonincreasing weight Wm(j). Set Li=0, for i∈M.Step
6. Select a machine i for which Li is as small as possible (select i arbitrarily if there is a tie). Choose the first unscheduled job j of the list and assign it to machine i. Set Li=Li+pj. Set Li=Li+pj. Repeat Step 6 until all jobs are scheduled.Step
7. For all i∈M, resort the jobs assigned to machine i in Step 6 by nonincreasing delivery time.Step
8. For k=1,2, deliver all jobs in Nk by a single vehicle. Denote the resulting solution by S23.Step
9. Denote the final solution by S2. If n1+n2≤b and c12<f+c01+c02, select one from the three solutions S21, S22, and S23 with the lowest objective value as the final solution. Otherwise, set S23 as the final solution.In heuristic H1, most of the computing time is used for sorting jobs. Hence, the time complexity of the heuristic isO(nlog⁡n). Next, we analyze its worst-case performance.Theorem 10.
F
(
S
2
)
≤
(
2
-
2
/
(
m
+
1
)
)
F
(
S
∗
).Proof.
There are three cases associated withn1 and n2.
Case
(i). If n1+n2>b, then by Lemma 9, the distribution schedule of S23 is an optimal one. Meanwhile, Dmax(S23)≤(2-2/(m+1))Dmax(S∗). Therefore, we have F(S23)≤(2-2/(m+1))F(S∗).
Case
(ii). If n1+n2≤b and c12>f+c01+c02, then by Lemma 9, the distribution schedule of S23 is an optimal one. Due to Dmax(S23)≤(2-2/(m+1))Dmax(S∗), we thus have F(S23)≤(2-2/(m+1))F(S∗).
Case
(iii). If n1+n2≤b and c12≤f+c01+c02, there are two subcases associated with the distribution schedule of S∗.
Subcase
(i). If two vehicles are used to deliver jobs, one vehicle delivers all jobs in N1 and the other one delivers all jobs in N2; then F(S23)≤(2-2/(m+1))F(S∗).
Subcase
(ii). If only one vehicle is used to deliver all jobs in N, then T(S∗)=f+c01+c12+c02 and the optimal route of the vehicle is one of the routes adopted by S21 or S22. Therefore, the problem is reduced to the classical scheduling problem Pm ∥ Cmax. It is well known that the worst-case performance bound of the heuristic for this problem by applying LPT rule is 4/3-1/3m [7]. Thus, in this subcase, min{F(S21),F(S22)}≤(4/3-1/3m)F(S∗).
In Step 9 of the heuristic, we select the best of the three solutions; henceF(S2)≤(2-2/(m+1))F(S∗).


## 4.2.  The Other Cases

As mentioned before, except the case withnk<b for k=1,2 the other cases include the case with nk≥b for k=1,2 and the case with (n1-b)(n2-b)≤0. We have discussed the case with nk<b for k=1,2 in Section 4.1. In this subsection, we develop below a heuristic, denoted as H2, for the case with nk≥b for k=1,2 and the case with (n1-b)(n2-b)≤0. Similar to heuristic MMLS, we also let Wm(j)=(m-1)pj+mt0j denote a weight of job j depending on its processing time and delivery time, j∈N, and let Li represent the total processing time of jobs assigned to machine i so far during the algorithm execution, i∈M. The value of Wm(j) can be computed in advance for each j∈N. Heuristic H2 can be described in detail as follows.Heuristic H2Step
1. Place all jobs in a list sorted by nonincreasing weight Wm(j). Set Li=0, for i∈M.Step
2. Select a machine i for which Li is as small as possible (select i arbitrarily if there is a tie). Choose the first unscheduled job j of the list and assign it to machine i. Set Li=Li+pj. Repeat Step 2 until all jobs are scheduled.Step
3. For all i∈M, resort the jobs assigned to machine i in Step 2 by nonincreasing delivery time.Step
4. For k=1,2, use ⌈nk/b⌉ vehicles to deliver jobs in Nk, where the first vehicle delivers ni-(⌈nk/b⌉-1)b jobs and the remaining (⌈nk/b⌉-1) vehicles deliver b jobs. Denote the resulting solution by S11.Step
5. For k=1,2, use ⌈nk/b⌉-1 vehicles to deliver the last nk-yk jobs in Nk with largest processing completion time, each of which contains b jobs, where yk=nk-b(⌈nk/b⌉-1). Use one vehicle to deliver the remaining y1+y2 jobs. Two routes are available for the vehicle: the former one is that the vehicle goes to customer 1 via customer 2 and then directly returns to the processing facility and the latter one is that the vehicle goes to customer 2 via customer 1 and then directly returns to the processing facility. Denote the resulting solution adopting the former route and the latter route by S12 and S13, respectively.Step
6. Denote the final solution by S1. Select one from the three solutions S11, S12, and S13 with the smallest objective value as the final solution.In heuristic H2, most of the computing time is used for sorting jobs in Step 1. Hence, the time complexity of the heuristic isO(nlog⁡n). Next, we analyze its worst case performance.Theorem 11.
D
m
a
x
(
S
11
)
≤
(
2
-
2
/
(
m
+
1
)
)
D
m
a
x
(
S
∗
).Proof.
It is clear thatDmax(S11)=Dmax(Sα=1) since they adopt the same production schedule and the maximum arrival time of the jobs is independent of how the delivery shipments are formed when each job is direct delivered to its customer with no vehicle routing. In S11, let Pk be the maximum processing completion time of jobs in Nk, for k=1,2. Hence, Dmax(S11)=Dmax(Sα=1)=max{Pk+t0k∣k=1,2}. By Theorem 3, Dmax(S11)≤(2-2/(m+1))Dmax∗. Moreover, by Lemma 2, Dmax(S∗)≥Dmax∗. Thus we have Dmax(S11)≤(2-2/(m+1))Dmax(S∗).For the case withnk≥b for k=1,2 and the case with (n1-b)(n2-b)≤0, we have the following result.Theorem 12.
Ifnk≥b for k=1,2, T(S11)≤4/3T(S∗); if (n1-b)(n2-b)<0, T(S11)≤3/2T(S∗).Proof.
InS11, T(S11)=∑k∈K‍⌈nk/b⌉(f+2c0k). There are three cases associated with y1 and y2.
Case
(i). If y1y2=0, then, by Corollary 6, T∗=∑k=12‍⌈nk/b⌉(f+2c0k). Hence, T(S11)=T∗.
Case
(ii). If y1+y2>b, then, by Corollary 7, T∗=∑k=12‍⌈nk/b⌉(f+2c0k). Hence, T(S11)=T∗.
Case
(iii). If y1y2>0 and y1+y2≤b, then, by Corollary 8, we have(1)T∗=∑k=12nkb-1f+2c0k+min⁡f+c01+c12+c02,2f+2c01+2c02.
There are two subcases associated withT(S11) and T∗.
Subcase
(i). If f+c01+c12+c02≥2f+2c01+2c02, we have T(S11)=T∗.
Subcase
(ii). If f+c01+c12+c02<2f+2c01+2c02, we have T∗=∑k=12‍(⌈nk/b⌉-1)(f+2c0k)+f+c01+c12+c02. Now consider T(S11): (2)TS11=∑k=12nkb-1f+2c0k+2f+2c01+2c02=∑k=12nkb-2f+2c0k+433f+3c01+3c02.
Whennk≥b and y1y2>0, we have ⌈nk/b⌉>nk/b>1, for k=1,2. This implies that ⌈nk/b⌉≥2, k=1,2. Thus,(3)TS11≤43∑k=12nkb-2f+2c0k+433f+3c01+c12+3c02=43T∗.
When(n1-b)(n2-b)<0 and y1y2>0, there exists a k¯∈{1,2} that satisfies ⌈nk¯/b⌉≥1 and ⌈n3-k¯/b⌉≥2. Thus, (4)TS11≤32∑k=12nkb-1f+2c0k+2f+2c01+2c02-12f+2c0k¯=32∑k=12nkb-1f+2c0k+32f+c0k¯+2c03-k¯=32T∗-123c12-c03-k¯+c0k¯≤32T∗.
Therefore, in both cases, we can conclude thatT(S11)≤4/3T∗ if nk≥b for k=1,2 and T(S1)≤3/2T∗ if (n1-b)(n2-b)<0. By Lemma 2, T∗≤T(S∗). Therefore, T=(S11)≤4/3T(S∗) if n1≥b and n2≥b and T(S11)≤3/2T∗ if (n1-b)(n2-b)<0.Corollary 13.
Ifm=2 and (n1-b)(n2-b)<0, F(S1)≤3/2F(S∗); otherwise, F(S1)≤(2-2/(m+1))F(S∗).Proof.
By Theorem11, Dmax(S11)≤(2-2/m+1)Dmax(S∗). If n1≥b and n2≥b, by Theorem 12, T(S11)≤4/3T(S∗). Due to 4/3≤2-2/m+1 when m≥2, we have F(S11)≤(2-2/m+1)F(S∗). Otherwise, if (n1-b)(n2-b)<0, by Theorem 12, T(S11)≤3/2T(S∗). Due to 2-2/m+1≥3/2 when m>2, we have F(S11)≤(2-2/m+1)F(S∗). However, if m=2, then 2-2/m+1=4/3<3/2; if m>2, then 2-2/m+1≥3/2. Hence, if m=2 and (n1-b)(n2-b)<0, F(S11)≤3/2F(S∗); if m>2 and (n1-b)(n2-b)<0, F(S11)≤(2-2/m+1)F(S∗). Because S1 is one of the solutions S11, S12, and S13 with the smallest objective value, F(S1)≤F(S11). This implies that F(S1)≤3/2F(S∗) if m=2 and (n1-b)(n2-b)<0, and F(S1)≤(2-2/(m+1))F(S∗) otherwise.


## 5. Conclusion

In this paper, we have studied a parallel machine scheduling model with batch delivery to two customers. The objective is to minimize the tradeoff between the maximum arrival time of the jobs and total distribution cost. Computational complexity of various cases of the problem has been clarified, and algorithms for these cases are provided. More specifically, we first provided a polynomial time heuristic with worst-case ratio bound of2-2/(m+1) and a polynomial time exact algorithm for the problem with α=1 and α=0, respectively; then we developed heuristics for the problem with 0<α<1. When the number of machines m is equal to 2 and the number of customer 1’s orders n1 and the number of customer 2’s orders n2 meet (n1-b)(n2-b)<0, the worst-case ratio bound of our heuristic is 3/2. Otherwise, the worst-case ratio of our developed heuristic is bounded by 2-2/(m+1). The heuristic we proposed has the advantages over the existing heuristic proposed by Chen and Vairaktarakis [1] that it possesses tighter worst-case ratio bound and lower time complexity. However, in this paper we just consider the case with two customers in the supply chain; for future research it will be worth designing heuristics with tighter bound for multiple customers.



---

*Source: 247356-2015-09-07.xml*