# Two Parallel Machines Scheduling with Two-Vehicle Job Delivery to Minimize Makespan

Authors: Lisi Cao; Jianhong Hao; Dakui Jiang
Journal: Complexity
 (2020)

---

## Abstract

A problem of parallel machine scheduling with coordinated job deliveries is handled to minimize the makespan. Different jobs call for dissimilar sizes of storing space in the process of transportation. A range of jobs of one customer in the problem have priority to be processed on two identical parallel machines without preemption and then delivered to the customer by two vehicles in batches. For this NP-hard problem, we first prove that it is impossible to have a polynomial heuristic with a worst-case performance ratio bound less than 2 unless P = NP. Thereafter, we develop a polynomial heuristic for this problem, the worst-case ratio of which is bounded by 2.


---

## Body

## 1. Introduction

Production and distribution operations are two key operational functions in a supply chain; it is critical to integrate these two functions and schedule them jointly in a coordinated manner so as to achieve optimal operational performance [1]. However, in traditional scheduling problems, it is always assumed that there are enough vehicles for delivery of jobs that are finished with no time needed for transportation. Unlike conventional scheduling, a scheduling problem with two stages is investigated in the current research, with the first stage for processing jobs on two parallel machines while the second for delivering jobs that are finished using two vehicles.In integrated production and outbound distribution scheduling (IPODS) problems, it is required to coordinate scheduling, batching, and delivery decisions at all levels of the supply chain in order to minimize the overall scheduling and delivery cost [2]. In the last two decades, various IPODS models have been widely studied. Chen [1] conducted a comprehensive survey on these models. Based on the survey, the problem of interest is regarded as an IPODS model of jobs with general size and a finite quantity of vehicles. Therefore, in the following, we just review a few closely related research works. In recent years, some works on IPODS models with parallel machines and equal-size jobs were done, in which all the jobs have the same size. For example, Hall and Potts [3] studied several models having enough vehicles. In their models, all the finished products are delivered to one customer. The models with multiple customers were also investigated in [4, 5]. Wang and Cheng [6] ever studied a model with two identical parallel machines and a single vehicle to minimize the makespan. In this model, an unavailable interval existed on one of the machines due to preventive maintenance, and an unfinished job can resume processing after the machine becomes available again. They showed that the problem is NP-hard and proposed a heuristic with a worst-case ratio of 5/3. Recently, Pan and Su [7] developed an improved heuristic with a worst-case ratio of 3/2. Obviously, for the models where the jobs have generally different sizes, it will be considerably tougher to resolve compared with models involving jobs of equal size since the batching decision now involves bin packing, which alone is NP-hard in the strong sense [8] in the case that it does not allow split delivery. Chang and Lee [9] took the lead to research models involving jobs of general size. In accordance with their models, one can use only a vehicle for delivery of jobs during the second stage. They proposed two heuristics with worst-case ratio of 5/3 and 2, respectively, for the models with single machine configuration and two identical parallel machine configurations. After that, several improved heuristics were proposed. For the model with single machine configuration, He et al. [10] and Zhong et al. [11] put forward a modified heuristic and a most feasible heuristic with ratios in the worst case of 53/35 and 3/2+ϵ, where ϵ is positive and can be an arbitrary value approximating 0; for the model with two identical parallel machine configurations, Zhong et al. [11] provided a heuristic with a worst-case ratio of 5/3, and Su et al. [12] proposed a heuristic with a worst-case ratio of 63/40, except for two particular cases. For the model with more than one vehicle, Chen and Pundoor [13] carried out a research study on a model having enough vehicles and all jobs therein have their deadlines. For the purpose of minimizing total cost for transportation, they developed a heuristic for the model. Jiang and Tan [14] designed a polynomial-time heuristic with a worst-case ratio of 2 for the model with a single machine and two vehicles. However, to the best of our knowledge, little attention is paid on the models with identical parallel machines and a finite number of vehicles not less than two.The problem we study is an extension of the model studied by Jiang and Tan [14], in which the machine environment in the first stage is extended from one machine to two identical parallel machines. The problem in the research is summarized as follows: for a cluster of customer’s jobs with the number of n and independent from each other, N=J1,J2,…,Jn, each of which must be first nonpreemptively processed by one of the two identical parallel machines, M1 and M2, in a manufacturing system and then delivered to the customer. Job Jj, j=1,2,…,n, needs a processing time of pj in the manufacturing system and has a size sj which represents the physical space Jj as it is loaded in vehicles. There are two homogeneous vehicles (V1 and V2) that can be used for delivery of batched completed jobs originally in the manufacturing system. The capacity of each of the vehicles is z. It indicates that one can arrange completed jobs to match the physical space of vehicles provided the total size is smaller than z. One delivery batch refers to jobs that are delivered all at once by the same vehicle. One vehicle takes a time period of T, for transportation while delivering a batch of jobs, a duration from the beginning moment of the vehicle in delivery of the batch to that when it goes back to the machine after the delivery. As for the goal, it is to search for a schedule of handling jobs in manufacturing systems, followed by delivery of completed jobs to customers so as to minimize the time needed for all jobs in N waiting for processing and delivery to customers. For ease of analysis, makespan of a schedule is defined as Cmax. It is duration from one of the vehicles accomplishing delivery of the last batch to customers to the moment it goes back to the manufacturing system. Under the condition, what we need to solve is to search for a schedule that can minimize the makespan.Since so far as we know that we are the first to consider the model with two machines and two vehicles, this paper has two objectives. Our first objective is to analyze the computational complexity of our model and provide some optimality properties satisfied by the model. Also, the well-known algorithms for similar models could not solve our model. So, our second objective is to develop a fast heuristic targeting the problem. Organization of the rest of the research is shown as follows: Section2 introduces notations, along with several optimality properties of the problem of interest at first. Section 3 provides a heuristic for the problem of interest, followed by analysis of performance of the heuristic in the worst case. Section 4 draws on conclusions.


## 2. Notations and Preliminaries

The section introduces the following notations at first. These notations are used uniformly throughout the paper:P: total times for processing all jobs in a manufacturing system, i.e., P=∑j=1npj.As to a scheduleδ for the problem, it is defined thatbδ: total quantity of batches to be delivered in δ.For eachk=1,…,bδ, we define the following:Bkδ: kth batch delivered in δ.Pkδ=∑Jj∈Bkδpj: sum of processing times of all the jobs in batch Bkδ.σkδ: time for a vehicle to depart from the manufacturing system for delivering Bkδ.ρkδ: time for preparation of Bkδ, representing the latest time for completing processing of jobs allocated to Bkδ. It is worth noting that in any possible schedule, there is σkδ≥ρkδ.Unless it is ambiguous,Bkδ, Pkδ, σkδ, and ρkδ are simplified as Bk, Pk, σk, and ρk, separately.For the optimum schedule, it is defined thatCmax∗: optimum makespan.CmaxM∗: time moment at which machines complete processing of the last job.b∗: amount of batches delivered.Several optimality properties of the problem are given as follows. Because of straightforwardness of the conditions, the proofs are omitted.Lemma 1.
An optimal schedule exists for a problem meeting the following conditions:(i)
There is no idle time between the jobs processed on any machine(ii)
For each delivery batch, all the jobs in the batch that are processed on the same machine are processed consecutively on that machine(iii)
Jobs assigned to one batch and processed on the same machine can be processed on that machine in any order
Hence, only schedules that satisfy the above properties are considered further.Lemma 2.
C
max
∗
≥
max
C
max
M
∗
+
T
,
b
∗
/
2
T.
Clearly, our problem is NP-hard since a special case with transportation timeT=0 is equivalent to solving the classical two parallel machine makespan minimization problems, which are NP-hard.Lemma 3.
It is impossible to have a polynomial heuristic with a worst-case performance ratio bound less than 2 unless P = NP.Proof.
We prove this by a reduction from the following PARTITION problem, which is known to be NP-complete [8].
PARTITION: Givenn natural numbers a1,…,an, is there a subset S⊆1,…,n such that ∑i∈Sai=∑i∉Sai?
Given this instance of PARTITION, we consider an instance of our problem withn jobs, J1,…,Jn, where(1)pj=0,sj=2aj∑i=1naiz,forj=1,…,n.
As a subsetS∗⊆1,…,n satisfying ∑i∈S∗ai=∑i∉S∗ai can be attained. It is obvious that the above PARTITION instance has an affirmative answer when and only when there are two batches formed in the optimal schedule for the instance. As to the schedule, jobs in Jjj∈S∗ and Jjj∉S∗ are separately processed by machines M1 and M2 followed by assignment to two different batches, each of which is delivered by one vehicle, with the makespan of Cmax=T. In contrast, it needs three batches or more for the instance for any subset S⊆1,…,n satisfying ∑i∈Sai≠∑i∉Sai. One of the vehicles at least delivers two batches, so the makespan of relevant schedule is Cmax≥2T.
It is assumed that there exists a polynomial heuristic for our problem with worst-case ratio bound less than 2. For the formation of two batches under the optimal schedule of the instance, as has been noted, the optimal makespan isCmax∗=T. It is obvious that the presumptive algorithm is able to search the optimal schedule all the time, as the makespan Cmax=2T when 3 batches are under demand. This is supposed to be a polynomial-time algorithm for which the bound of a performance ratio in the worst case is 2. Therefore, through the reduction above, the algorithm is able to resolve the PARTITION instance just in the polynomial time, implying that P = NP, which contradicts our claim that P≠NP.
Therefore, for the problem, there is no possibility for obtaining a polynomial heuristic with a worst-case performance ratio bound less than 2 unless P = NP.


## 3. Heuristic

In this section, we first introduce the following algorithm FFD (First Fit Decreasing) [15], which is a classical algorithm for solving the bin-packing problem. It will be applied to constitute batches in the heuristic proposed. Note that vehicle capacity (z) and job sizes (sj) proposed in the research underlay the algorithm FFD.


### 3.1. Algorithm FFD

Step 1: sort the jobs in a nonincreasing order of size (sj)
Step 2: assign the job with the largest size toB1
Step 3: Forj = 2, …, n, if the jth largest job is considered, then assign it to the lowest indexed batch such that the total job size of the corresponding batch does not exceed zLemma 4 (see [16]).
For an instance I of binning, assuming thatFFDI and OPTI are separate numbers of bins used for the optimal solution and the solution obtained using the FFD algorithm, we have FFDI≤3/2OPTI.In the following, we will present a heuristic for the problem and analyze its worst-case performance. This heuristic is described as follows.


### 3.2. Heuristic HA

Step 1: FFD algorithm is used to assign jobs to batches. Supposing the amount of formed batches isbH.Step 2: As to jobs in batchBk, the total times for processing them are calculated and denoted as Pk, for k=1,2,…,bH. The batches are retrieved so that P1≤P2≤⋯≤PbH.Step 3: Batches are assigned one after another fromB1 to a machine having a lower load before assignment (allocating jobs in one batch to the same machine). Jobs in each batch are sorted according to a random order.Step 4: The first and second vehicles are supposed to deliver all batches allocated to machinesM1 and M2. Each vehicle needs to distribute each finished batch waiting for delivery whenever; in the case that there are more than one batch finished under conditions that a vehicle is available, the vehicle requires dispatching a batch having the lowest index.We first analyze the time complexity of heuristic HA. Since it is well known that the time complexity of the FFD algorithm isOn2, it will take time period On2 in Step 1; also, it will take On times to obtain all Pk for k=1,2,…,bH in Step 2; the job batch assignment will cost at most Onlogn in Step 3, and the batch delivery will take at most On in Step 4 depending on bH. So, we have that heuristic HA has a time complexity of On2. It is supposed that CmaxH represents the makespan from heuristic HA. Furthermore, in the solution of the heuristic, let Cmax1 and Cmax2 represent time moments for finishing jobs sorted in the last two machines M1 and M2. Then, CmaxM∗=maxCmax1∗,Cmax2∗. Also, define CmaxM=maxCmax1,Cmax2.Lemma 5 (see [9]).
C
max
M
≤
P
≤
2
C
max
M
∗.
Based on heuristic HA, batches are indexed in a nondecreasing order of their processing times and are assigned one by one to the machine that has a smaller load before the batch is assigned. It can be shown easily that each batch with an odd index is assigned to machineM1 and delivered by vehicle V1; for batches having even indexes, they are allocated to M2, followed by delivery using vehicle V2. Furthermore, the delivery of a batch with a smaller index happens earlier compared with that having a larger index. Suppose that x and y are separate total times for dealing with jobs allocated to the first and second batches in a solution attained using heuristic HA, that is, x=P1 and y=P2.Corollary 1.
x
≤
2
C
max
M
∗
/
b
H; y≤2CmaxM∗/bH−1 if bH≥2.Proof.
BecauseP1≤Pk, for k=1,…,n, according to Step 2, we have bHP1≤P and P1+bH−1P2≤P if bH≥2, which mean that x=P1≤P/bH≤2CmaxM∗/bH and y=P2≤P/bH−1≤2CmaxM∗/bH−1 if bH≥2.Lemma 6.
b
H
≤
3
/
2
b
∗.Proof.
It is assumed thatbL∗ represents the amount of batches when an optimal method is used to allocate jobs to batches, instead by algorithm FDD in Step 1. Obviously, there is bL∗≤b∗. Meanwhile, bH≤3/2bL∗ based on Lemma 4, which suggests bH≤3/2b∗.Lemma 7.
The schedule attained using heuristic HA is considered.(i)
On conditions that a batchBk exists for machine M1 so that σk=ρk and k≥3, there is σk+2i=ρk+2i, for i=0,1,2,…(ii)
In the case that machineM2 is assigned with a batch Bq so that σq=ρq and q≥4, there is σq+2i=ρq+2i, for i=0,1,2,…Proof.
(i)
Recall that batches are indexed and delivered in a nondecreasing order ofPj, ∀j. Note that ρk=ρk−2+Pk and σk=maxδk−2+T,ρk. Since δk=ρk, σk−2+T≤ρk=ρk−2+Pk by Lemma 1(i). Since σk−2≥ρk−2, there is Pk≥T. Thus, Pk+l≥T for l=0,1,…,b−k. It follows that σk+2=maxσk+T,ρk+2=maxσk+T,ρk+Pk+2=ρk+Pk+2=ρk+2. Applying the same argument repetitively, there is σk+2i=ρk+2i, for i=0,1,2,…(ii)
Similar to (i).Corollary 2.
Consider the schedule obtained by heuristic HA. IfCmaxH>CmaxM+T, then CmaxH=maxx+bH+1/2T,y+bH−1/2T if bH is odd and CmaxH=y+bH/2T if bH is even.Lemma 8.
IfCmaxH=CmaxM+T, then CmaxH≤2Cmax∗.Proof.
(2)
C
max
H
C
max
∗
≤
C
max
M
+
T
C
max
M
∗
+
T
≤
2
C
max
M
∗
+
T
C
max
M
∗
+
T
≤
2.Corollary 3.
IfbH=1 or bH=2, then CmaxH≤2Cmax∗.Lemma 9.
IfbH is odd and bH≥3, then CmaxH≤2Cmax∗.Proof.
IfCmaxH=CmaxM+T, then CmaxH≤2Cmax∗ according to Lemma 8. Now, suppose that CmaxH>CM+T. By Corollary 2, CmaxH=maxx+bH+1/2T,y+bH−1/2T if bH is odd.Case 1.
C
max
H
=
x
+
b
H
+
1
/
2
T.(3)CmaxHCmax∗=x+bH+1/2TCmax∗≤2CmaxM∗/bH+bH+1/2TCmax∗=2bH⋅CmaxM∗+bH+1bH/4TCmax∗≤2bH⋅CmaxM∗+TCmaxM∗+T+2bH⋅bH+1bH/4T−Tb∗/2T=2bH+bH+1bH−4bHb∗≤2bH+bH+1bH−42/3bH2=32+7bH−122bH2≤2.Case 2.
C
max
H
=
y
+
b
H
−
1
/
2
T.(4)CmaxHCmax∗=y+bH−1/2TCmax∗≤2CmaxM∗/bH−1+bH−1/2TCmax∗=2bH−1⋅CmaxM∗+bH−1/22TCmax∗≤2bH−1⋅CmaxM∗+TCmaxM∗+T+2bH−1⋅bH−1/22T−Tb∗/2T=2bH−1+bH−12−4bH−1b∗≤2bH−1+bH−12−42/3bH−1bH<2bH−1+32.
Clearly,CmaxH/Cmax∗<2 if bH≥5. Because bH is odd and bH≥3, we only need to consider the case with bH=3. If bH=3, then(5)CmaxHCmax∗≤2bH−1+bH−12−4bH−1b∗=1.
Therefore, we haveCmaxH≤2Cmax∗ if bH is odd and bH≥3.Lemma 10.
IfbH is even and bH≥4, then CmaxH≤2Cmax∗.Proof.
IfCmaxH=CmaxM+T, then CmaxH≤2Cmax∗ according to Lemma 8. Now, suppose that CmaxH>CmaxM+T. By Corollary 2, CmaxH=y+bH/2T if bH is even. Hence,(6)CmaxHCmax∗=y+bH/2TCmax∗≤2CmaxM∗/bH−1+bH/2TCmax∗=2bH−1⋅CmaxM∗+bH−1bH/4TCmax∗≤2bH−1⋅CmaxM∗+TCmaxM∗+T+2bH−1⋅bH−1bH/4T−Tb∗/2T=2bH−1+bH−1bH−4bH−1b∗≤2bH−1+bH−1bH−42/3bH−1bH<2bH−1+32.
Obviously,CmaxH/Cmax∗<2 if bH≥5. Because bH is even and bH≥4, we only need to consider the case with bH=4. If bH=4, by Lemma 6, we have b∗=3 or b∗=4.
IfbH=4 and b∗=3, then(7)CmaxHCmax∗≤2bH−1+bH−1bH−4bH−1b∗=23+89<2.
IfbH=b∗=4, then(8)CmaxHCmax∗≤2bH−1+bH−1bH−4bH−1b∗=23+812<2.
Therefore, we haveCmaxH≤2Cmax∗ if bH is even and bH≥4.
From Corollary3, Lemma 9, and Lemma 10, we haveTheorem 1.
C
max
H
/
C
max
∗
≤
2.
According to Lemma3 and Theorem 1, we can conclude that our heuristic is a best possible polynomial heuristic for the problem.


## 3.1. Algorithm FFD

Step 1: sort the jobs in a nonincreasing order of size (sj)
Step 2: assign the job with the largest size toB1
Step 3: Forj = 2, …, n, if the jth largest job is considered, then assign it to the lowest indexed batch such that the total job size of the corresponding batch does not exceed zLemma 4 (see [16]).
For an instance I of binning, assuming thatFFDI and OPTI are separate numbers of bins used for the optimal solution and the solution obtained using the FFD algorithm, we have FFDI≤3/2OPTI.In the following, we will present a heuristic for the problem and analyze its worst-case performance. This heuristic is described as follows.


## 3.2. Heuristic HA

Step 1: FFD algorithm is used to assign jobs to batches. Supposing the amount of formed batches isbH.Step 2: As to jobs in batchBk, the total times for processing them are calculated and denoted as Pk, for k=1,2,…,bH. The batches are retrieved so that P1≤P2≤⋯≤PbH.Step 3: Batches are assigned one after another fromB1 to a machine having a lower load before assignment (allocating jobs in one batch to the same machine). Jobs in each batch are sorted according to a random order.Step 4: The first and second vehicles are supposed to deliver all batches allocated to machinesM1 and M2. Each vehicle needs to distribute each finished batch waiting for delivery whenever; in the case that there are more than one batch finished under conditions that a vehicle is available, the vehicle requires dispatching a batch having the lowest index.We first analyze the time complexity of heuristic HA. Since it is well known that the time complexity of the FFD algorithm isOn2, it will take time period On2 in Step 1; also, it will take On times to obtain all Pk for k=1,2,…,bH in Step 2; the job batch assignment will cost at most Onlogn in Step 3, and the batch delivery will take at most On in Step 4 depending on bH. So, we have that heuristic HA has a time complexity of On2. It is supposed that CmaxH represents the makespan from heuristic HA. Furthermore, in the solution of the heuristic, let Cmax1 and Cmax2 represent time moments for finishing jobs sorted in the last two machines M1 and M2. Then, CmaxM∗=maxCmax1∗,Cmax2∗. Also, define CmaxM=maxCmax1,Cmax2.Lemma 5 (see [9]).
C
max
M
≤
P
≤
2
C
max
M
∗.
Based on heuristic HA, batches are indexed in a nondecreasing order of their processing times and are assigned one by one to the machine that has a smaller load before the batch is assigned. It can be shown easily that each batch with an odd index is assigned to machineM1 and delivered by vehicle V1; for batches having even indexes, they are allocated to M2, followed by delivery using vehicle V2. Furthermore, the delivery of a batch with a smaller index happens earlier compared with that having a larger index. Suppose that x and y are separate total times for dealing with jobs allocated to the first and second batches in a solution attained using heuristic HA, that is, x=P1 and y=P2.Corollary 1.
x
≤
2
C
max
M
∗
/
b
H; y≤2CmaxM∗/bH−1 if bH≥2.Proof.
BecauseP1≤Pk, for k=1,…,n, according to Step 2, we have bHP1≤P and P1+bH−1P2≤P if bH≥2, which mean that x=P1≤P/bH≤2CmaxM∗/bH and y=P2≤P/bH−1≤2CmaxM∗/bH−1 if bH≥2.Lemma 6.
b
H
≤
3
/
2
b
∗.Proof.
It is assumed thatbL∗ represents the amount of batches when an optimal method is used to allocate jobs to batches, instead by algorithm FDD in Step 1. Obviously, there is bL∗≤b∗. Meanwhile, bH≤3/2bL∗ based on Lemma 4, which suggests bH≤3/2b∗.Lemma 7.
The schedule attained using heuristic HA is considered.(i)
On conditions that a batchBk exists for machine M1 so that σk=ρk and k≥3, there is σk+2i=ρk+2i, for i=0,1,2,…(ii)
In the case that machineM2 is assigned with a batch Bq so that σq=ρq and q≥4, there is σq+2i=ρq+2i, for i=0,1,2,…Proof.
(i)
Recall that batches are indexed and delivered in a nondecreasing order ofPj, ∀j. Note that ρk=ρk−2+Pk and σk=maxδk−2+T,ρk. Since δk=ρk, σk−2+T≤ρk=ρk−2+Pk by Lemma 1(i). Since σk−2≥ρk−2, there is Pk≥T. Thus, Pk+l≥T for l=0,1,…,b−k. It follows that σk+2=maxσk+T,ρk+2=maxσk+T,ρk+Pk+2=ρk+Pk+2=ρk+2. Applying the same argument repetitively, there is σk+2i=ρk+2i, for i=0,1,2,…(ii)
Similar to (i).Corollary 2.
Consider the schedule obtained by heuristic HA. IfCmaxH>CmaxM+T, then CmaxH=maxx+bH+1/2T,y+bH−1/2T if bH is odd and CmaxH=y+bH/2T if bH is even.Lemma 8.
IfCmaxH=CmaxM+T, then CmaxH≤2Cmax∗.Proof.
(2)
C
max
H
C
max
∗
≤
C
max
M
+
T
C
max
M
∗
+
T
≤
2
C
max
M
∗
+
T
C
max
M
∗
+
T
≤
2.Corollary 3.
IfbH=1 or bH=2, then CmaxH≤2Cmax∗.Lemma 9.
IfbH is odd and bH≥3, then CmaxH≤2Cmax∗.Proof.
IfCmaxH=CmaxM+T, then CmaxH≤2Cmax∗ according to Lemma 8. Now, suppose that CmaxH>CM+T. By Corollary 2, CmaxH=maxx+bH+1/2T,y+bH−1/2T if bH is odd.Case 1.
C
max
H
=
x
+
b
H
+
1
/
2
T.(3)CmaxHCmax∗=x+bH+1/2TCmax∗≤2CmaxM∗/bH+bH+1/2TCmax∗=2bH⋅CmaxM∗+bH+1bH/4TCmax∗≤2bH⋅CmaxM∗+TCmaxM∗+T+2bH⋅bH+1bH/4T−Tb∗/2T=2bH+bH+1bH−4bHb∗≤2bH+bH+1bH−42/3bH2=32+7bH−122bH2≤2.Case 2.
C
max
H
=
y
+
b
H
−
1
/
2
T.(4)CmaxHCmax∗=y+bH−1/2TCmax∗≤2CmaxM∗/bH−1+bH−1/2TCmax∗=2bH−1⋅CmaxM∗+bH−1/22TCmax∗≤2bH−1⋅CmaxM∗+TCmaxM∗+T+2bH−1⋅bH−1/22T−Tb∗/2T=2bH−1+bH−12−4bH−1b∗≤2bH−1+bH−12−42/3bH−1bH<2bH−1+32.
Clearly,CmaxH/Cmax∗<2 if bH≥5. Because bH is odd and bH≥3, we only need to consider the case with bH=3. If bH=3, then(5)CmaxHCmax∗≤2bH−1+bH−12−4bH−1b∗=1.
Therefore, we haveCmaxH≤2Cmax∗ if bH is odd and bH≥3.Lemma 10.
IfbH is even and bH≥4, then CmaxH≤2Cmax∗.Proof.
IfCmaxH=CmaxM+T, then CmaxH≤2Cmax∗ according to Lemma 8. Now, suppose that CmaxH>CmaxM+T. By Corollary 2, CmaxH=y+bH/2T if bH is even. Hence,(6)CmaxHCmax∗=y+bH/2TCmax∗≤2CmaxM∗/bH−1+bH/2TCmax∗=2bH−1⋅CmaxM∗+bH−1bH/4TCmax∗≤2bH−1⋅CmaxM∗+TCmaxM∗+T+2bH−1⋅bH−1bH/4T−Tb∗/2T=2bH−1+bH−1bH−4bH−1b∗≤2bH−1+bH−1bH−42/3bH−1bH<2bH−1+32.
Obviously,CmaxH/Cmax∗<2 if bH≥5. Because bH is even and bH≥4, we only need to consider the case with bH=4. If bH=4, by Lemma 6, we have b∗=3 or b∗=4.
IfbH=4 and b∗=3, then(7)CmaxHCmax∗≤2bH−1+bH−1bH−4bH−1b∗=23+89<2.
IfbH=b∗=4, then(8)CmaxHCmax∗≤2bH−1+bH−1bH−4bH−1b∗=23+812<2.
Therefore, we haveCmaxH≤2Cmax∗ if bH is even and bH≥4.
From Corollary3, Lemma 9, and Lemma 10, we haveTheorem 1.
C
max
H
/
C
max
∗
≤
2.
According to Lemma3 and Theorem 1, we can conclude that our heuristic is a best possible polynomial heuristic for the problem.


## 4. Conclusion

The study investigated the scheduling problem involving two identical parallel machines with coordinated delivery of jobs to minimize the makespan, which can be viewed as an IPODS model involving two parallel machines that are completely the same, as well as general-size jobs. We first showed that the problem is NP-hard and then provided a polynomial heuristic for the problem. We also proved that it is impossible to have a polynomial heuristic for this problem with a worst-case performance ratio bound less than 2 unless P = NP; besides, the performance ratio of our heuristic in the worst case has a bound of 2, which means that our heuristic is the best possible one. Models involving more than two vehicles or machines are expected to be studied in future research.



---

*Source: 1647401-2020-01-31.xml*