# Integrated Scheduling Problem on a Single Bounded Batch Machine with an Unavailability Constraint

Authors: Jing Fan
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

We consider a scheduling problem where a set of jobs are first processed on a machine with an unavailability interval and, then, delivered to the customer directly. We focus on an integrated schedule of production and distribution such that the sum of the maximum delivery time and total delivery cost is optimized. We study two classes of processing machines in the production part. In the first class, the serial-batch machine, the processing time of a batch is the sum of the processing times of its jobs. In the second class, the parallel-batch machine, the processing time of a batch is the maximum processing time of the jobs contained in the batch. The machine has a fixed capacity, and the jobs are processed in batches under the condition that the total size of the jobs in a batch cannot exceed the machine capacity. Two patterns of job’s processing, i.e., resumable and non-resumable, are considered if it is interrupted by the unavailability interval on the machine. In the distribution part, there are sufficient vehicles with a fixed capacity to deliver the completed jobs. The total size of the completed jobs in one delivery cannot exceed the vehicle capacity. We show that these four problems are NP-hard in the strong sense in which the jobs have the same processing times and arbitrary sizes, and we propose an approximation algorithm for solving these four problems. Moreover, we show that the performance ratio of the algorithm is 2 for the serial-batch machine setting, and the error bound is 71/99 for the parallel-batch machine setting. We also evaluate the performance of the approximation algorithm by the computational results.


---

## Body

## 1. Introduction

Joint consideration of production and distribution is so beneficial in making higher level decisions for the manufacturers in the realistic supply chain environment that many researchers kept on studying on various models of such integrated scheduling problems. Potts [1] was probably the first researcher who considered scheduling with job delivery. Hall and Potts [2] studied integrated scheduling that involves a supplier, a manufacturer, and a customer. Up to now, there are an increasing number of literature and a variety of new models on scheduling problems with job delivery. For one machine, Chen and Vairaktarakis [3] studied the problem to minimize the weighted sum of maximum delivery time and total transportation cost with a relative preference, in which sufficient vehicles without capacity limit were used to deliver completed jobs to customers. They proposed two optimal algorithms for one customer and multiple customers. Chen [4] and Wang et al. [5] have surveyed the integrated scheduling problems of production and distribution operation.In most models of scheduling with delivery, one machine processes one job at a time. However, a new kind of integrated scheduling problems concerned with batch processing has already been investigated by many researchers. Batch scheduling is motivated by many industrial manufacturing processes. For example, in the burn-in stage of semiconductor manufacturing, burn-in ovens can handle up to multiple jobs simultaneously. Generally, batch-processing machine has two versions: serial-batch and parallel-batch, according to [6]. When processed on the serial-batch machine, jobs may be batched and one job in a batch is processed at a time so that the processing time of a batch is the sum of the processing times of its jobs. Learning effect of jobs is always accompanied with the serial-batching scheduling problems. Lee et al. [7] and Pei et al. [8–10] investigated the serial-batching scheduling problems with deteriorating jobs or learning effects to minimize the makespan. There is no setup time in [7], but there are independent setup times in [8–10]. Pei et al. [11] considered the coordinated scheduling problem of production and transportation with deteriorating jobs. The batches including completed jobs would be delivered to a customer by a single vehicle with only one batch in one delivery. They analysed some useful properties and presented a heuristic for the general case and two optimal algorithms for two special cases. Lu et al. [12] studied the integrated production and delivery scheduling on a serial-batch machine to minimize the makespan and considered four different problems from the situations whether split is allowed in the production or delivery of the jobs.When processed on the parallel-batch machine, several jobs can be processed as a batch simultaneously on a machine at one time such that the processing time of a batch is the maximum processing time of the jobs contained in the batch. The bounded parallel-batch-processing machine setting is introduced by Lee et al. [13], which is always encountered in burn-in operations in the semiconductor industry and heat treatment operations in the metalworking industries. Uzsoy [14] showed the problem is NP-hard to minimize makespan on a single bounded parallel-batch machine and provided some approximation algorithms. And Brucker et al. [15] discussed two variants: the unbounded model and the bounded model. Lee and Lee [16] developed a heuristic by iterative decomposition of a mixed integer programming model. Li et al. [17], Gong et al. [18], Lu and Yuan [19], and Cheng et al. [20] considered some integrated scheduling of production and distribution on parallel-batch-processing machines. In [20], the authors focused on finding a schedule of the jobs and a delivery plan so that the maximum delivery time of jobs is minimized. They showed that the problem can be solved optimally in O (nlogn) time if the jobs have identical sizes and proposed two approximation algorithms with an asymptotical performance ratio of 11/9 if the jobs have identical processing times and 2 if the jobs have arbitrary processing times and arbitrary sizes.Up to now, most works have studied the machine setting which is always available. But, the machines can become unavailable during the production stage due to the occurrence of breakdowns or the necessity for maintenance and repair, which is called as the scheduling under the constraint of machine unavailability. When job processing is interrupted by machine unavailability, the interrupted job may be resumable or nonresumable once the machine is available again. In the resumable case, the interrupted job can be processed continuously, but in the nonresumable case, the interrupted job needs to be processed anew. For the integrated scheduling problem with a capacitated vehicle to minimize the maximum delivery time, Wang and Cheng [21] showed that it is NP-hard and proposed a 3/2-approximation algorithm and provided the instance with the worst-case ratio 3/2. More details on this research stream can be found in the work of Wang et al. [5] and Ma et al. [22]. There are a few literatures concerned with the integrated scheduling problem on the batch-processing machine with the unavailable constraints. Pei et al. [23] considered a single-machine serial-batching scheduling problem with a machine availability constraint, position-dependent processing time, and time-dependent setup time. Fan et al. [24] studied the integrated scheduling problem to minimize the maximum delivery time to the customer on a single bounded parallel-batch machine with an unavailability interval. For the nonresumable jobs, two approximation algorithms with the worst-case ratios 3/2 and 5/3 are explored in two cases where the jobs have the same size and arbitrary processing times, and the jobs have the same processing time and arbitrary sizes, respectively.In this paper, we consider an integrated scheduling problem for a customer on a bounded batch machine with a machine unavailability period, where the jobs have identical processing times and sufficient capacitated vehicles are used to deliver the completed jobs to the customer. The objective is to minimize the sum of the delivery time when the last completed job is delivered to the customer and the total delivery cost. There are four classes of problems corresponding to different conditions during the processing of the interrupted job after the unavailability period and the type of machine, i.e., serial-batching and parallel-batching. In the practical aluminum-making process, serial-batching is common. Cylindrical aluminum ingots are processed one after another in the same batch on an extrusion machine, which has a schedule to be checked. Also, in the burn-in stage of semiconductor manufacturing, the burn-in oven can handle up to multiple jobs simultaneously, which is the form of parallel-batching. The oven must be stopped to accept inspection as a plan. All completed jobs have to be transported to the customer as soon as possible. Therefore, how to schedule the production and the delivery effectively is worth to study in such complicated settings.


## 2. Problem Formulation

A set ofn jobs J1,J2,…,Jn is given, where job Jj has the processing time pj and size sj. Each job has an arbitrary size but an identical processing time pj=p for j=1,2,…,n. In the production part, the machine has a capacity U, i.e., it can simultaneously process several jobs as a batch if their total size does not exceed the machine capacity. We discuss two types of batches, that is, serial-batching and parallel-batching. For the serial-batching, the processing time of a batch is the sum of the processing times of its jobs. For the parallel-batching, the processing time of a batch is the maximum processing time of the jobs contained in the batch. Meanwhile, the machine has an unavailability period η1,η2 because of maintenance and breakdown. Let η be the length of the unavailability period, i.e., η=η2−η1. If there is, at least, one job in a batch that is interrupted by the unavailable period η1,η2, the interrupted job may be processed continuously just after η2, in which case we call it resumable and denoted by r − a, or needs to be processed anew after η2, defined as nonresumable and denoted by nr − a. In the latter case, the processing time of the batch containing this job is not affected for the parallel-batching mao the sum of η and the total processing time of the jobs and the idle time of the machine for the serial-batching machine. In the delivery part, there are sufficient vehicles to deliver the completed jobs to the customer and each of them has the same capacity V. Similar to [20], we assume that V=xU, where x ≥ 2 and x is a positive integer. The transport price of one trip between the machine and the customer is denoted by c and the total delivery cost is denoted by TC. Let Dj be the delivery time of job Jj, i.e., the arrival time of the batch containing job Jj to the customer. Let Dmax be the maximum delivery time of all the jobs. Our goal is to minimize the sum of maximum delivery time and total delivery cost. Using the five-field notation proposed by Chen [4] to denote an integrated scheduling problem, we denote the four classes of the problem in this paper as follows:P1:1,h1r−a,s−batch,sj,pj=pV∞,c,direct1Dmax+TCP2:1,h1nr−a,s−batch,sj,pj=pV∞,c,direct1Dmax+TCP3:1,h1r−a,p−batch,sj,pj=pV∞,c,direct1Dmax+TCP4:1,h1nr−a,p−batch,sj,pj=pV∞,c,direct1Dmax+TCHere,h1 denotes one unavailability interval and V (∞, c) presents the situation of the vehicle. Also, because there is one customer, the vehicle should transport jobs directly from the manufacturer to the customer. In the problems P1 and P2, s-batch means serial-batching. On the contrary, in the problems P3 and P4, p-batch means parallel-batching.We organize the rest of the paper as follows. In Section3, we show that all problems are NP-hard in the strong sense and propose some elementary properties. In Section 4, we present an approximation algorithm for these four problems and prove the different error bounds for these four problems. In the last section, we conclude our results and discuss the direction of the future research.


## 3. Properties of Four Problems

In this section, we analyse the computational complexity of the problemsP1–P4.Theorem 1.
ProblemsP1–P4 are all strongly NP-hard.Proof.
Consider the special caseP′ of problems P1 and P2, in which p=0, η1=η2, and c = 0, i.e., the processing time of each job is zero, and there is no unavailability interval on the machine and no delivery in problem P′. Hence, the problem P′ is equivalent to minimize the number of batches, i.e., the bin-packing problem, which is a well-known strongly NP-hard problem. Therefore, problems P1 and P2 are strongly NP-hard.
Similarly, we construct the special caseP″ of problems P3 and P4, in which η1=η2 and c = 0. Since each job has a processing time of p, every batch has a processing time of p. Hence, the problem P″ is also equivalent to the bin-packing problem. Therefore, problems P3 and P4 are both strongly NP-hard.
Associating with the bin-packing problem, we study some properties of the optimal solutions for these four problems.Lemma 1.
There exists an optimal scheduleγi∗ of the problem Pi for i=1,2,3,4, satisfying the following properties:(1)
LetX∗ to be the number of batches in the optimal schedule γi∗; then, X∗=n/U(2)
The batches are processed consecutively before and after the unavailability period(3)
The batch that becomes available earlier is delivered earlier(4)
The first delivery includesβ∗ batches, and each of the last α∗ deliveries x batches, where α∗ and β∗ are two positive integers satisfying X∗=α∗x+β∗ and 0<β∗≤x
This lemma can be proved similar with the proof in [21].


## 4. Algorithm and Analyses

To minimize the objective function value, we must assign many enough jobs in every batch to reduce the number of batches and deliveries. Therefore, associating with the algorithm of the bin-packing problem, we present the following algorithm to solve four scheduling problems.


### 4.1. Algorithm H

Step 1: reindex all jobs asJ1,J2,…,Jn so that s1≥s2≥…≥sn.Step 2: use the First Fit Decreasing (FFD) rule to assign the jobs into batches, in which jobs are to be processed together on the machine. Build the first empty batchB1 and put the job into it one by one in the sequence in Step 1 if the current total sizes of the batch B1 are no more than U. When all the jobs have been checked and there are still jobs need to be assigned, build the second batch B2 and assign the remaining jobs as the sequence in Step 1. Repeat the assignment until there is no job left. Let X be the number of batches produced in Step 2.Step 3: assign the batches in a nondecreasing order of their processing times to process continuously from time 0 except the unavailability interval.Step 4: Let.X=αx+β and 0<β≤x deliver the first completed β batches in D1. Also, deliver x batches immediately in the following every delivery. When the last x batches are delivered to the customer, the algorithm finishes.Recalling the FFD rule for the bin-packing problem, we can easily obtain Lemma2.Lemma 2.
(see [25]). X≤11/9X∗+6/9.
Based on Lemma2, we can explore the corresponding values of X and X∗ if X∗≤9 (see Table 1).
In order to list the corresponding relationship of values betweenX and X∗ if X∗≥10, we use two positive integers a≥1 and 1≤b≤9 such that X∗=9a+b similar to that in [26]. Hence, we can obtain Table 2.
Furthermore, we analyse the relationship of the objective function values produced by algorithm H and the optimal schedule in the problemsP1–P4, respectively. For convenience, we use γi to denote the schedule obtained by algorithm H for the problem Pi.Table 1
The corresponding values ofX and X∗ if X∗≤9.
VariablesValuesX∗123456789X12, 33, 44, 55, 66, 7, 87, 8, 98, 9, 109, 10, 11Table 2
The maximal values ofX and the upper bound of X/X∗ if X∗≥10.
VariablesValuesX∗9a+ 19a+ 29a+ 39a+ 49a+ 5The maximal value ofX11a+ 111a+ 311a+ 411a+ 511a+ 6Upper bound ofX/X∗11/914/115/416/1311/9X∗9a+69a+79a+89a+9The maximal value ofX11a+811a+911a+1011a+11Upper bound ofX/X∗19/155/421/1711/9Lemma 3.
(1)
dP2−d∗P2≤np, where dP2andd∗P2 are the idle times on the machine before the unavailability interval in schedules γ2, γ2∗ for the problem P2, respectively(2)
dP4≤d∗P4, where dP4andd∗P4 are the idle times on the machine before the unavailability interval in schedules γ4, γ4∗ for the problem P4, respectivelyProof.
(1)
According to Step 3 of Algorithm H, the batches are processed in a nondecreasing order of their processing times. Letnb, nb∗ be the number of jobs completed before the beginning time of η1,η2in schedules γ2, γ2∗, respectively. Because the length of the available time before η1 on the machine is the fixed, we have nbp+dP2=nb∗p+d∗P2. Hence, dP2−d∗P2≤nb∗−nbp≤nb∗p≤np.(2)
Because the processing time of each batch is equal top no matter how many jobs are in it and the starting time of processing is zero by the algorithm H, it is obvious that the idle time in γ4 must be no more than that in γ4∗, i.e., dP4≤d∗P4.
For the problemPi, we use DmaxPi, D∗maxPi,TCPi, and TC∗Pi to denote the maximum delivery time, the total delivery cost in γi, and γi∗ (i=1,2,3,4), respectively. We can easily conclude every value of DmaxPi, Dmax∗Pi, TCPi, and TC∗Pi for i=1,2,3,4.Lemma 4.
(1)
In the problemP1, DmaxP1=η+np,TCP1=α+1c and D∗maxP1=η+np,TC∗P1=α∗+1c(2)
In the problemP2, DmaxP2=η+np+dP2,TCP2=α+1c and D∗maxP2=η+np+d∗P2,TC∗P2=α∗+1c(3)
In the problemP3, DmaxP3=η+Xp,TCP3=α+1c and Dmax∗P3=η+X∗p, TC∗P3=α∗+1c(4)
In the problemP4, DmaxP4=η+Xp+dP4,TCP4=α+1c and D∗maxP4=η+X∗p+d∗P4,TC∗P4=α∗+1cProof.
Because the processes of batches are resumable in the problemP1, the difference between the result of the algorithm H and the optimal solution is only the number of deliveries. In the problem P2, the idle time of the machine is also different between the result of the algorithm H and the optimal solution. Moreover, in the problem P3, the total processing time Xp is needed in the solution of the algorithm H, but Xp∗ is needed in the optimal solution. Also, the difference of the idle time of the machine is obvious in the objective function value of the algorithm H and the optimal schedule in the problem P4.
It is notable that the completion time of the last batch is larger than the ending time of the unavailability interval in the optimal scheduleγi∗ (i=1,2,3,4). Otherwise, the performance ratio will approach infinity.
From the objectives of every problem, we find that the relationship betweenα and α∗ is critical. Hence, we explore the following lemma.Lemma 5.
(See [24]). α∗≤α<11/9α∗+14/9.Proof.
α∗≤α is obvious. Due to x ≥ 2, Lemma 2, and the explanation of X∗=α∗x+β∗, X=αx+β, we can deduce(1)α≤Xx≤1x119X∗+69=1x119α∗x+β∗+69≤119α∗+149.
Moreover, ifα=11/9α∗+14/9, we have(2)119X∗+69=119α∗x+β∗+69≤119α∗x+119x+69≤119α∗x+149x=αx<X,which contradicts Lemma 2.
Consequently, we can easily obtain the corresponding values ofα and α∗ if α∗≤4 (see Table 3).
To simplify the expression the objective function value of each problem, we useZPi and Z∗Pi to denote the objective function values obtained by algorithm H and the optimal schedule, respectively.Table 3
The corresponding values ofα and α∗ if α∗≤4.
VariablesValuesα∗1234α1, 22, 33, 4, 54, 5, 6Theorem 2.
Algorithm H is a 2-approximation algorithm for solving the problem (P1) and the problem (P2), and the worst-case ratio is tight.Proof.
According to Lemma4, it is obvious that(3)ZP1−Z∗P1Z∗P1=α−α∗cη+np+α∗+1c≤α−α∗cη+np+α∗c≤α−α∗α∗.
From Table3, we have that the algorithm reaches the worst-case ratio when α=2 and α∗=1.
For the problem (P2), because of (1) in Lemma 3, we have(4)ZP2−Z∗P2Z∗P2=α−α∗c+dP2−d∗P2η+np+d∗P2+α∗+1c≤α−α∗c+npnp+α∗c≤1.
Similarly, whenα=2 and α∗=1, the algorithm reaches the worst-case ratio.
Consider the following instance:n = 6, p = 2, U = 7, x = 2, η1,η2=2,2+ε, and s1=s2=3, s3=s4=s5=s6=2. The schedule produced by algorithm H is as follows: the first delivery including job J6 as the first batch is delivered at time 2; the second delivery including two batches, which consist of jobs J1 and J2 and jobs J3, J4, and J5 respectively, is delivered at time 12+ε. Hence, ZP1=ZP2=12+ε+2c. However, in the optimal schedule, there is only one delivery, including two batches which consist of jobs J1, J3, and J4 and jobs J2, J5, and J6 respectively. This delivery occurs at time 12+ε, and the optimal objective value is Z∗P1=Z∗P2=12+ε+c. If c is sufficiently large, we have ZP1/Z∗P1=ZP2/Z∗P2⟶2.
For the problem (P3) and the problem (P4), we obtain the error bound of algorithm H in the following theorem.Theorem 3.
Algorithm H has an error bound 71/99 when solving the problem (P3) and the problem (P4).Proof.
Because of (2) of Lemma 3, we have(5)ZP3−Z∗P3Z∗P3=X−X∗p+α−α∗cη+X∗p+α∗+1c≤X−X∗p+α−α∗cX∗p+α∗+1c,ZP4−Z∗P4Z∗P4=X−X∗p+dP4−d∗P4+α−α∗cη+X∗p+α∗+1c≤X−X∗p+α−α∗cX∗p+α∗+1c, We only need analyse the upper bound of X−X∗p+α−α∗c/X∗p+α∗+1c. Moreover, we prove the result in two cases according to α∗≤4 and α∗≥5, respectively.Case 1:α∗≤4. We discuss this case in two subcases.Subcase 1.1: when we consider the situation thatβ∗≤β, we can obtain the following inequality for α=α∗+k (k=0,1,2) according to Table 3:(6)α∗+kx+β∗≤α∗+kx+β=αx+β=X≤119X∗+69=119α∗x+β∗+69.(7)k−29α∗−29x≤69.(8)X−X∗p+α−α∗cX∗p+α∗+1c=α−α∗xp+β−β∗p+α−α∗cα∗x+β∗p+α∗+1c≤α−α∗xp+xp+α−α∗cα∗xp+α∗+1c.Fork=0, X−X∗p+α−α∗c/X∗p+α∗+1c≤X−X∗/X∗≤3/11<71/99 according to Tables 1 and 2.Fork=1, α∗=4, we have X−X∗p+α−α∗c/X∗p+α∗+1c≤xp+xp+c/α∗xp+α∗+1c≤2xp+c/4xp+5c<1/2<71/99.Subcase 1.2: when we consider the situation thatβ∗>β, we have the following inequality from Table 3 except for α∗=1andα=2:(9)X−X∗p+α−α∗cX∗p+α∗+1c=α−α∗xp+β−β∗p+α−α∗cα∗x+β∗p+α∗+1c≤α−α∗xp+α−α∗cα∗xp+α∗+1c≤α−α∗α∗≤23<7199.(10)X−X∗p+α−α∗cX∗p+α∗+1c≤X−X∗X∗+α−α∗α∗+1.Moreover, associating withβ∗≤x, we haveWhen k=0, k=1 withα∗ = 4, it is easy to deduce that inequality (7) holds when, k=1withα∗=4.Forα∗=1andα=2, X−X∗p+α−α∗c/X∗p+α∗+1c=X−X∗p+c/X∗p+2c. Moreover, we have X/X∗≤3/2 according to Tables 1 and 2. Hence, X−X∗p+α−α∗c/X∗p+α∗+1c≤1/2<71/99.Case 2:α∗≥5. We can easily obtain the inequality (10).
BecauseX/X∗≤14/11 according to Table 2 and α−α∗/α∗+1<2/9α∗+14/9/α∗+1=2/9+4/3⋅1/α∗+1≤2/9+4/3⋅1/6=4/9 according to Lemma 5, we obtain(11)X−X∗p+α−α∗cX∗p+α∗+1c≤311+49=7199,
andZP3−Z∗P3/Z∗P3≤71/99 and ZP4−Z∗P4/Z∗P4≤71/99.


## 4.1. Algorithm H

Step 1: reindex all jobs asJ1,J2,…,Jn so that s1≥s2≥…≥sn.Step 2: use the First Fit Decreasing (FFD) rule to assign the jobs into batches, in which jobs are to be processed together on the machine. Build the first empty batchB1 and put the job into it one by one in the sequence in Step 1 if the current total sizes of the batch B1 are no more than U. When all the jobs have been checked and there are still jobs need to be assigned, build the second batch B2 and assign the remaining jobs as the sequence in Step 1. Repeat the assignment until there is no job left. Let X be the number of batches produced in Step 2.Step 3: assign the batches in a nondecreasing order of their processing times to process continuously from time 0 except the unavailability interval.Step 4: Let.X=αx+β and 0<β≤x deliver the first completed β batches in D1. Also, deliver x batches immediately in the following every delivery. When the last x batches are delivered to the customer, the algorithm finishes.Recalling the FFD rule for the bin-packing problem, we can easily obtain Lemma2.Lemma 2.
(see [25]). X≤11/9X∗+6/9.
Based on Lemma2, we can explore the corresponding values of X and X∗ if X∗≤9 (see Table 1).
In order to list the corresponding relationship of values betweenX and X∗ if X∗≥10, we use two positive integers a≥1 and 1≤b≤9 such that X∗=9a+b similar to that in [26]. Hence, we can obtain Table 2.
Furthermore, we analyse the relationship of the objective function values produced by algorithm H and the optimal schedule in the problemsP1–P4, respectively. For convenience, we use γi to denote the schedule obtained by algorithm H for the problem Pi.Table 1
The corresponding values ofX and X∗ if X∗≤9.
VariablesValuesX∗123456789X12, 33, 44, 55, 66, 7, 87, 8, 98, 9, 109, 10, 11Table 2
The maximal values ofX and the upper bound of X/X∗ if X∗≥10.
VariablesValuesX∗9a+ 19a+ 29a+ 39a+ 49a+ 5The maximal value ofX11a+ 111a+ 311a+ 411a+ 511a+ 6Upper bound ofX/X∗11/914/115/416/1311/9X∗9a+69a+79a+89a+9The maximal value ofX11a+811a+911a+1011a+11Upper bound ofX/X∗19/155/421/1711/9Lemma 3.
(1)
dP2−d∗P2≤np, where dP2andd∗P2 are the idle times on the machine before the unavailability interval in schedules γ2, γ2∗ for the problem P2, respectively(2)
dP4≤d∗P4, where dP4andd∗P4 are the idle times on the machine before the unavailability interval in schedules γ4, γ4∗ for the problem P4, respectivelyProof.
(1)
According to Step 3 of Algorithm H, the batches are processed in a nondecreasing order of their processing times. Letnb, nb∗ be the number of jobs completed before the beginning time of η1,η2in schedules γ2, γ2∗, respectively. Because the length of the available time before η1 on the machine is the fixed, we have nbp+dP2=nb∗p+d∗P2. Hence, dP2−d∗P2≤nb∗−nbp≤nb∗p≤np.(2)
Because the processing time of each batch is equal top no matter how many jobs are in it and the starting time of processing is zero by the algorithm H, it is obvious that the idle time in γ4 must be no more than that in γ4∗, i.e., dP4≤d∗P4.
For the problemPi, we use DmaxPi, D∗maxPi,TCPi, and TC∗Pi to denote the maximum delivery time, the total delivery cost in γi, and γi∗ (i=1,2,3,4), respectively. We can easily conclude every value of DmaxPi, Dmax∗Pi, TCPi, and TC∗Pi for i=1,2,3,4.Lemma 4.
(1)
In the problemP1, DmaxP1=η+np,TCP1=α+1c and D∗maxP1=η+np,TC∗P1=α∗+1c(2)
In the problemP2, DmaxP2=η+np+dP2,TCP2=α+1c and D∗maxP2=η+np+d∗P2,TC∗P2=α∗+1c(3)
In the problemP3, DmaxP3=η+Xp,TCP3=α+1c and Dmax∗P3=η+X∗p, TC∗P3=α∗+1c(4)
In the problemP4, DmaxP4=η+Xp+dP4,TCP4=α+1c and D∗maxP4=η+X∗p+d∗P4,TC∗P4=α∗+1cProof.
Because the processes of batches are resumable in the problemP1, the difference between the result of the algorithm H and the optimal solution is only the number of deliveries. In the problem P2, the idle time of the machine is also different between the result of the algorithm H and the optimal solution. Moreover, in the problem P3, the total processing time Xp is needed in the solution of the algorithm H, but Xp∗ is needed in the optimal solution. Also, the difference of the idle time of the machine is obvious in the objective function value of the algorithm H and the optimal schedule in the problem P4.
It is notable that the completion time of the last batch is larger than the ending time of the unavailability interval in the optimal scheduleγi∗ (i=1,2,3,4). Otherwise, the performance ratio will approach infinity.
From the objectives of every problem, we find that the relationship betweenα and α∗ is critical. Hence, we explore the following lemma.Lemma 5.
(See [24]). α∗≤α<11/9α∗+14/9.Proof.
α∗≤α is obvious. Due to x ≥ 2, Lemma 2, and the explanation of X∗=α∗x+β∗, X=αx+β, we can deduce(1)α≤Xx≤1x119X∗+69=1x119α∗x+β∗+69≤119α∗+149.
Moreover, ifα=11/9α∗+14/9, we have(2)119X∗+69=119α∗x+β∗+69≤119α∗x+119x+69≤119α∗x+149x=αx<X,which contradicts Lemma 2.
Consequently, we can easily obtain the corresponding values ofα and α∗ if α∗≤4 (see Table 3).
To simplify the expression the objective function value of each problem, we useZPi and Z∗Pi to denote the objective function values obtained by algorithm H and the optimal schedule, respectively.Table 3
The corresponding values ofα and α∗ if α∗≤4.
VariablesValuesα∗1234α1, 22, 33, 4, 54, 5, 6Theorem 2.
Algorithm H is a 2-approximation algorithm for solving the problem (P1) and the problem (P2), and the worst-case ratio is tight.Proof.
According to Lemma4, it is obvious that(3)ZP1−Z∗P1Z∗P1=α−α∗cη+np+α∗+1c≤α−α∗cη+np+α∗c≤α−α∗α∗.
From Table3, we have that the algorithm reaches the worst-case ratio when α=2 and α∗=1.
For the problem (P2), because of (1) in Lemma 3, we have(4)ZP2−Z∗P2Z∗P2=α−α∗c+dP2−d∗P2η+np+d∗P2+α∗+1c≤α−α∗c+npnp+α∗c≤1.
Similarly, whenα=2 and α∗=1, the algorithm reaches the worst-case ratio.
Consider the following instance:n = 6, p = 2, U = 7, x = 2, η1,η2=2,2+ε, and s1=s2=3, s3=s4=s5=s6=2. The schedule produced by algorithm H is as follows: the first delivery including job J6 as the first batch is delivered at time 2; the second delivery including two batches, which consist of jobs J1 and J2 and jobs J3, J4, and J5 respectively, is delivered at time 12+ε. Hence, ZP1=ZP2=12+ε+2c. However, in the optimal schedule, there is only one delivery, including two batches which consist of jobs J1, J3, and J4 and jobs J2, J5, and J6 respectively. This delivery occurs at time 12+ε, and the optimal objective value is Z∗P1=Z∗P2=12+ε+c. If c is sufficiently large, we have ZP1/Z∗P1=ZP2/Z∗P2⟶2.
For the problem (P3) and the problem (P4), we obtain the error bound of algorithm H in the following theorem.Theorem 3.
Algorithm H has an error bound 71/99 when solving the problem (P3) and the problem (P4).Proof.
Because of (2) of Lemma 3, we have(5)ZP3−Z∗P3Z∗P3=X−X∗p+α−α∗cη+X∗p+α∗+1c≤X−X∗p+α−α∗cX∗p+α∗+1c,ZP4−Z∗P4Z∗P4=X−X∗p+dP4−d∗P4+α−α∗cη+X∗p+α∗+1c≤X−X∗p+α−α∗cX∗p+α∗+1c, We only need analyse the upper bound of X−X∗p+α−α∗c/X∗p+α∗+1c. Moreover, we prove the result in two cases according to α∗≤4 and α∗≥5, respectively.Case 1:α∗≤4. We discuss this case in two subcases.Subcase 1.1: when we consider the situation thatβ∗≤β, we can obtain the following inequality for α=α∗+k (k=0,1,2) according to Table 3:(6)α∗+kx+β∗≤α∗+kx+β=αx+β=X≤119X∗+69=119α∗x+β∗+69.(7)k−29α∗−29x≤69.(8)X−X∗p+α−α∗cX∗p+α∗+1c=α−α∗xp+β−β∗p+α−α∗cα∗x+β∗p+α∗+1c≤α−α∗xp+xp+α−α∗cα∗xp+α∗+1c.Fork=0, X−X∗p+α−α∗c/X∗p+α∗+1c≤X−X∗/X∗≤3/11<71/99 according to Tables 1 and 2.Fork=1, α∗=4, we have X−X∗p+α−α∗c/X∗p+α∗+1c≤xp+xp+c/α∗xp+α∗+1c≤2xp+c/4xp+5c<1/2<71/99.Subcase 1.2: when we consider the situation thatβ∗>β, we have the following inequality from Table 3 except for α∗=1andα=2:(9)X−X∗p+α−α∗cX∗p+α∗+1c=α−α∗xp+β−β∗p+α−α∗cα∗x+β∗p+α∗+1c≤α−α∗xp+α−α∗cα∗xp+α∗+1c≤α−α∗α∗≤23<7199.(10)X−X∗p+α−α∗cX∗p+α∗+1c≤X−X∗X∗+α−α∗α∗+1.Moreover, associating withβ∗≤x, we haveWhen k=0, k=1 withα∗ = 4, it is easy to deduce that inequality (7) holds when, k=1withα∗=4.Forα∗=1andα=2, X−X∗p+α−α∗c/X∗p+α∗+1c=X−X∗p+c/X∗p+2c. Moreover, we have X/X∗≤3/2 according to Tables 1 and 2. Hence, X−X∗p+α−α∗c/X∗p+α∗+1c≤1/2<71/99.Case 2:α∗≥5. We can easily obtain the inequality (10).
BecauseX/X∗≤14/11 according to Table 2 and α−α∗/α∗+1<2/9α∗+14/9/α∗+1=2/9+4/3⋅1/α∗+1≤2/9+4/3⋅1/6=4/9 according to Lemma 5, we obtain(11)X−X∗p+α−α∗cX∗p+α∗+1c≤311+49=7199,
andZP3−Z∗P3/Z∗P3≤71/99 and ZP4−Z∗P4/Z∗P4≤71/99.


## 5. Computational Results

Since the four problems are all strongly NP-hard and the bin-packing problem is contained in these problems, solving them will be costly and time consuming. But, in order to evaluate the effectiveness of the algorithm H, we consider four numerical simulations for the small size problems. The optimal schedule is obtained by processing the batches according to the branch-and-bound algorithm for the bin-packing problem in [27] and delivering as (4) in Lemma 1.The approximation algorithm and the branch-and-bound algorithm are coded in VC++, and the computational experiments are run on a personal computer. We utilize three different job numbers,n = 30 and 50. Let the processing time of each job be 1, and the sizes of all jobs are generated randomly from a discrete uniform distribution [1, 10]. Let the capacity of the machine U = 3, 7 and the capacity of the vehicle V = xU = 2U, 10U. We set two levels of the length of the unavailability period η=0.2,1.2 and two levels of the beginning time of the unavailability interval η1=3,10 in the experiments. The cost of each delivery batch is set as c=0.5,2. For each combination of n, η, η1, and c, 20 random instances are used, and the computational results are summarized in from Tables 4 to 7, which reports the average number of seconds of CPU time of the optimal solutions and the solutions of algorithm H for each combination of parameters. The percentage error of the solution produced by the algorithm H is calculated as ρ=ZPi−Z∗Pi/Z∗Pi.Table 4
The results of the algorithm H and branch-and-bound (B&B) algorithm for (P1).
nUxηη1cAverage CPU times of the algorithm HAverage CPU times of B&B algorithmAverage value ofρ50320.230.50.060315.03461.01220.061515.01911.0130.2100.50.061815.02331.01120.061215.02121.0111.230.50.060915.03051.01320.062015.01451.0121.2100.50.060515.02211.01220.061815.03141.013507100.230.50.060715.03241.01120.060815.02191.0120.2100.50.062115.03091.01220.062415.02421.0131.230.50.061915.02871.01120.061815.02371.0121.2100.50.062015.02281.01020.062115.01581.011Table 5
The results of the algorithm H and branch-and-bound (B&B) algorithm for (P2).
nUxηη1cAverage CPU times of the algorithm HAverage CPU times of B&B algorithmAverage value ofρ30320.230.50.05123.53461.13020.05263.61211.1260.2100.50.05183.51931.21320.05723.40231.2041.230.50.05013.50121.12720.05133.39861.1231.2100.50.05423.45911.11320.05373.50291.138307100.230.50.05273.30921.21420.05283.42901.2090.2100.50.05183.42321.12020.05193.50141.1181.230.50.05293.48791.10420.06083.38711.1061.2100.50.05383.43811.16920.05213.30801.184Table 6
The results of the algorithm H and branch-and-bound (B&B) algorithm for (P3).
nUxηη1cAverage CPU times of the algorithm HAverage CPU times of B&B algorithmAverage value ofρ503100.230.50.060115.04121.10320.061215.03811.1040.2100.50.062315.03151.11320.062515.04061.1181.230.50.061415.03371.21720.062315.03411.2121.2100.50.062515.05021.20420.063115.05131.21050720.230.50.060515.03721.13220.061115.03811.1790.2100.50.060815.04011.12420.062115.04271.1191.230.50.062015.03811.22120.061915.03481.2201.2100.50.061815.03291.21720.062315.04141.215Table 7
The results of the algorithm H and branch-and-bound (B&B) algorithm for (P4).
nUxηη1cAverage CPU times of the algorithm HAverage CPU times of B&B algorithmAverage value ofρ303100.230.50.05253.52811.21920.05273.53561.1930.2100.50.05413.50271.20120.05473.53011.2081.230.50.05353.55311.12020.05393.58901.1191.2100.50.05413.62111.30120.05453.62361.27130730.230.50.05293.72101.27120.05323.81041.2290.2100.50.05373.71471.20120.05393.78181.2031.230.50.05313.82011.30820.06103.90321.3201.2100.50.05493.71381.30120.05563.91021.284It is observed from Tables4–7 that the average CPU times increase in polynomial times for the algorithm H when the number of jobs increase and increase in exponential times for the branch-and-bound algorithm. It is found that the average worst-case error bounds of the optimal solution of (P2) and (P4) are generally more than (P1) and (P3) because of the nonresumable conditions. Finally, the most important thing is that these four tables show that the approximation algorithm performs efficiently and the actual error bounds of four problems are lower than the theoretical error bounds.


## 6. Conclusions

We consider four integrated scheduling problems to minimize the sum of the maximum delivery time and the total delivery cost, in which a set of jobs are first processed on a single batch machine with an unavailability interval and, then, delivered to the customer directly, and the jobs have the same processing time and arbitrary sizes. We show that these four problems are all strongly NP-hard and propose an approximation algorithm for them. Moreover, we obtain that the worst-case error bound of the algorithm for the serial-batch machine setting and the parallel-batch machine setting, respectively. We also provide computational results to evaluate the performance of the heuristics.The direction of future research may focus on other settings of jobs and vehicles, such as jobs with arbitrary processing times and arbitrary sizes or one vehicle with limited capacity.



---

*Source: 8625849-2020-12-01.xml*