# Online Scheduling with Delivery Time on a Bounded Parallel Batch Machine with Limited Restart

Authors: Hailing Liu; Long Wan; Zhigang Yan; Jinjiang Yuan
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

We consider the online (over time) scheduling of equal length jobs on a bounded parallel batch machine with batch capacityb to minimize the time by which all jobs have been delivered with limited restart. Here, “restart” means that a running batch may be interrupted, losing all the work done on it, and jobs in the interrupted batch are then released and become independently unscheduled jobs, called restarted jobs. “Limited restart” means that a running batch which contains some restarted jobs cannot be restarted again. When b=2, we propose a best possible online algorithm H(b=2) with a competitive ratio of 1+α, where α is the positive solution of 2α(1+α)=1. When b≥3, we present a best possible online algorithm H(b≥3) with a competitive ratio of 1+β, where β is the positive solution of β(1+β)2=1.


---

## Body

## 1. Introduction

In this paper, we consider the online scheduling of equal length jobs on a bounded parallel batch machine with batch capacityb to minimize the time by which all jobs have been delivered with limited restart. Here, a bounded parallel batch machine is a machine which can process up to b jobs simultaneously as a batch, where b is the batch capacity. The processing time of a batch is the longest processing time of jobs in the batch. Jobs in a batch have the same starting time and the same completion time. According to the characteristic of batch capacity b, there are the bounded model and the unbounded model. The bounded model means that b is finite; that is, b<∞. The unbounded model means that b can be as large as possible; that is, b=∞. In this paper, we study the bounded model, that is, bounded parallel batch machine.In this paper, online means that each job becomes available at its arrival time which is unknown beforehand and the characteristics of the job are unknown until it arrives. Each jobJj has an arrival time rj, a processing time pj, and a delivery time qj. In our research, we assume that all jobs have equal processing times. By scaling, we may assume that each job has a processing time 1. Each job needs to be processed on the bounded parallel batch machine and then delivered to the destination by a delivery vehicle. Here we assume that there are sufficiently many delivery vehicles, which means that a job can be transported as soon as it is completed on the bounded parallel batch machine. Let Cj be the completion time of Jj on the bounded parallel batch machine and let Lj be the time by which Jj has been delivered. Then Lj=Cj+qj. Let Lmax⁡=max⁡j⁡{Lj:Lj=Cj+qj}. Our objective is to minimize Lmax⁡, that is, the time by which all jobs have been delivered.The quality of an online algorithm is measured by the competitive ratio. An online algorithm is calledρ-competitive if, for any input instance, it produces a schedule with an objective value not worse than ρ times the value of an optimal offline schedule.Restart (see Hoogeveen et al. [1]) means that a running task may be interrupted, losing all the work done on it. The jobs in the interrupted task, which are called restarted jobs, are then released and become independently unscheduled jobs which can be scheduled anew later. Using restarts means that we have a chance to change our original mind to get a better schedule according to the newly arrived jobs and so can efficiently improve the quality of some online algorithms. For example, for the problem of minimizing the time by which all jobs have been delivered on a single machine without restarts, the best possible online algorithm has a competitive ratio of (5+1)/2. While using restarts, a best possible online algorithm with a competitive ratio of 3/2 was given in Akker et al. [2]. Other researches with restarts can see Epstein and Stee [3], Stee and Poutré [4], and Yuan et al. [5].Limited restart is first introduced by Fu et al. [6]. Limited restart means that once a batch contains some restarted jobs, we cannot restart the batch again. Limited restart implies that a job can be restarted at most once. Limited restart is of practical value. In fact, too many restarts of a job may cause the waste of cost and improve the possibility of a spoiled product.Parallel batching scheduling is motivated by burn in operations in semiconductor manufacture (see [7, 8]). For online scheduling on a single unbounded parallel batch machine to minimize makespan, that is, the time by which all jobs are completed on the parallel batch machine, Deng et al. [9] and Zhang et al. [10] independently gave the same online algorithm with the competitive ratio of (5+1)/2 and proved it is best possible. For online scheduling on a single bounded parallel batch machine to minimize makespan, Poon and Yu [11] proved that any FBLPT-based algorithm is 2-competitive. Particularly for batch capacity b=2, they presented an online algorithm with the competitive ratio of 7/4. For online scheduling on m unbounded parallel batch machines to minimize makespan, Liu et al. [12] and Tian et al. [13] independently presented two different but best possible online algorithms with a competitive ratio of 1+αm, where αm is the positive solution of the equation am2+mαm-1=0. For online scheduling on a single parallel batch machine to minimize Lmax⁡, that is, the time by which all jobs have been delivered, Tian et al. [14] gave a 2-competitive online algorithm for the unbounded model and a 3-competitive online algorithm for the bounded model. Moreover, when each job has the same processing time, they provided two (5+1)/2-competitive optimal online algorithms for the two models, respectively. Yuan et al. [15] gave a best possible online algorithm with a competitive ratio of (5+1)/2 for the two models of qj≤pj and [pi>pj implying qi≥qj]. Fang et al. [16] studied the restricted model that all jobs have their processing times in [p,((1+5)/2)p] and provided a class of optimal online algorithms with a competitive ratio of (1+5)/2. Tian et al. [17] presented a (22-1)-competitive online algorithm for the unbounded model. Liu and Lu [18] studied online scheduling on m unbounded parallel batch machines to minimize Lmax⁡. For the restricted model of [pi>pj implying qi≥qj], they gave a best possible online algorithm with competitive ratio of 1+αm, where αm is the positive solution of αm2+mαm=1. For the general case, they gave an online algorithm with competitive ratio of 1+2/m.For the problem of minimizing makespan on an unbounded parallel batch machine with restarts, Fu et al. [19] showed that any online algorithm cannot have a competitive ratio of less than (5-5)/2 and Yuan et al. [5] gave a best possible online algorithm matching the lower bound. For the corresponding problem using limited restart, Fu et al. [6] gave an online algorithm with a competitive ratio of 3/2 and proved that it is best possible. For the problem of minimizing makespan on two unbounded parallel batch machines with limited restart, Fu et al. [20] provided a best possible online algorithm which is (3+1)/2-competitive under the second-restart assumption. Recently, Liu and Yuan [21] presented best possible online algorithms for minimizing makespan of equal length jobs on a bounded parallel batch machine with limited restart or restart.LetJ be a job set. Then J is used to denote the number of jobs in J. Let q(J) denote the largest delivery time of jobs in J and let r(J) denote the latest arrival time of jobs whose delivery times are q(J) in J. For a batch B in some schedule, S(B) is starting time of B on the parallel batch machine. Batch B is calledfull if |B|=b andnonfull if |B|<b. In an online algorithm H which generates a schedule consisting of n processing batches, let Bi denote the ith processing batch such that S(B1)<S(B2)<⋯<S(Bn). For simplicity, we write S(Bi) as Si. Let U(t) be the set of the available unscheduled jobs at time t in H.If, in an online algorithmH, Bk is being processed at the current time t, then the following subprocedure which is called Restart (k,t) may be used.Restart
k
,
t. At time t, interrupt Bk and select min⁡{b,|Bk∪U(t)|} jobs in Bk∪U(t) such that each job selected has a delivery time not less than the largest delivery time of jobs not selected in Bk∪U(t) as the batch Bk+1 starting at time t. Then reset k to be k+1.This paper studies the online scheduling of equal length jobs on a bounded parallel batch machine with batch capacityb to minimize Lmax⁡ with limited restart. Here Lmax⁡ means the time by which all jobs have been delivered. This problem can be denoted by 1∣online,rj,pj=1,P-batch,b<∞,L-restart∣Lmax⁡. For simplicity, when b=2, the problem is shortly written as P-batch (b=2). When b≥3, the problem is shortly written as P-batch (b≥3).Letα be the positive solution of 2α(1+α)=1 and let β be the positive solution of β(1+β)2=1.This paper is organized as follows. In Section2, we give a best possible online algorithm with a competitive ratio of 1+α for problem P-batch (b=2). In Section 3, we give a best possible online algorithm with a competitive ratio of 1+β for problem P-batch (b≥3).


## 2. Problem P-Batch(b=2)

For a job instanceI, let Lon⁡=Lon⁡(I) and Lopt=Lopt(I) denote, respectively, the values of Lmax⁡ given by an online algorithm and an offline optimal algorithm.Theorem 1.
Any online algorithm for problem P-batch(b=2) cannot have a competitive ratio of less than 1+α.Proof.
Letϵ be a sufficiently small positive number. For any online algorithm H, we consider the following instance. At time 0, the first job J1 with q1=0 arrives and no jobs arrive before the starting time of J1.
IfS1≥α, no jobs arrive later. We have Lon⁡=S1+1 and Lopt=1. Hence, Lon⁡/Lopt=(S1+1)/1≥1+α.
IfS1<α, then, at time S1+α, the second job J2 with q2=0 arrives and no jobs arrive before the starting time of J2. We distinguish the following two cases.
Case 1 (S2≥S1+1). Then no jobs arrive later. Then Lon⁡≥S1+2 and Lopt=S1+α+1. Thus Lon⁡/Lopt≥(S1+2)/(S1+α+1)≥(α+2)/(2α+1)=1+α.
Case 2 (S2<S1+1). Then B2 interrupts B1.
IfB2 is a batch containing only one job J2, no jobs arrive later. We have Lon⁡≥S2+2≥S1+α+2 and Lopt=S1+α+1. Hence, Lon⁡/Lopt≥(S1+α+2)/(S1+α+1)≥1+1/(2α+1)>1+α.
IfB2 is a batch consisting of {J1,J2} and S2≤2α, then job J3 with q3=1 arrives at time S2+ϵ and no jobs arrive later. As B2 cannot be restarted, we have Lon⁡≥S2+2+q3=S2+2+1. In the offline setting, we can schedule J3 starting at time S2+ϵ and {J1,J2} as a single batch starting at time S2+1+ϵ. So Lopt≤S2+2+ϵ. Then when ϵ→0, we have Lon⁡/Lopt≥(S2+3)/(S2+2+ϵ)→(S2+3)/(S2+2)≥1+1/(2α+2)=1+α.
IfB2 is a batch consisting of {J1,J2} and S2>2α, then job J3 with q3=0 arrives at time S2+ϵ and no jobs arrive later. As B2 cannot be restarted, we have Lon⁡≥S2+2. In the offline setting, we can schedule J1 starting at time 0 and {J2,J3} as a single batch starting at time max⁡{1,S2+ϵ}. So Lopt≤max⁡{2,S2+1+ϵ}. Then when ϵ→0, we have Lon⁡/Lopt≥(S2+2)/max⁡{2,S2+1+ϵ}→(S2+2)/max⁡{2,S2+1}=min⁡{(S2+2)/2,1+1/(S2+1)} ≥ min⁡{1+α,1+1/(α+2)}=1+α.
The theorem follows.Algorithm
H
(
b
=
2
). Initially set k=0. At the current time instant t, do the following.S
(
1
): if k=0, U(t)≠∅, and t≥α, then select min⁡2,Ut jobs in U(t) such that each job selected has a delivery time not less than the largest delivery time of jobs not selected in U(t) as the batch Bk+1 starting at time t. Then reset k to be k+1.S
(
2
): if k≥1, the machine is idle, and U(t)≠∅, then select min⁡{2,|U(t)|} jobs in U(t) such that each job selected has a delivery time not less than the largest delivery time of jobs not selected in U(t) as the batch Bk+1 starting at time t. Then reset k to be k+1.S
(
3
): if the machine is occupied by Bk, k∈{1,2}, U(t)≠∅, and each batch starting earlier than Sk is not interrupted, do the following.S
(
3.1
): if Bk is nonfull and t=Sk+α, then do Restart (k,t).S
(
3.2
): if k=1, Bk is full, t=Sk+α, and some job in U(t) has a delivery time larger than the delivery time of some job in Bk, then do Restart (k,t).S
(
4
): otherwise, do nothing but wait.From algorithmH(b=2), we have the following observation.Observation 1.
(1) For each batchBi in algorithm H(b=2), we have Si≥α.
(2) All jobs arrive at or afterS1-α. And if S1>α, then all jobs arrive at or after S1.
(3) IfBj interrupts Bj-1, then Sj=Sj-1+α.
(4) Ifk≥3, then Sk≥2α+1.Theorem 2.
For problem P-batch(b=2), H(b=2) is a best possible online algorithm with a competitive ratio of 1+α.Proof.
Suppose to the contrary thatI is an instance so that Lon⁡/Lopt>1+α. Let σ be the schedule generated by running algorithm H(b=2), for instance, I. For simplicity, in the following we always write q(Bi) as qi and write r(Bi) as ri without causing confusion. By the definitions of q(Bi) and r(Bi), we know that qi is the largest delivery time of jobs in Bi and ri is the latest arrival time of jobs whose delivery times are qi in Bi. Let Bn be the earliest starting batch in σ which assumes Lon⁡ and is not interrupted. Then Lon⁡=Sn+1+qn. Let π be an offline optimal schedule, for instance, I. As S1≤max⁡{r1,α}, then the assumption that Lon⁡/Lopt>1+α implies n≥2.
LetCon⁡=Sn+1; that is, Con⁡ is the completion time of Bn on the parallel batch machine. Let t be the minimum time instant such that, in σ, there are no idle times between t and Con⁡ and each batch processed in the time interval [t,Con⁡] is not interrupted. Suppose that there are h batches Bn-h+1,…,Bn processed in the time interval [t,Con⁡] in σ. Then Con⁡=t+h. Set n′=n-h+1. So Sn′=t.
Claim 1 (Bn does not interrupt Bn-1 and h≥2). Otherwise, Bn interrupts Bn-1. Then Lon⁡=Sn+1+qn=Sn-1+α+1+qn. By algorithm H(b=2), we have n=2,3. Let J′ be the job with the largest delivery time among jobs arriving in the interval (Sn-1,Sn], let q′ be the delivery time of J′, and let r′ be the arrival time of J′. Then qn=max⁡{qn-1,q′}. If q′≥qn-1, then qn=q′, Lopt≥r′+1+q′>Sn-1+1+q′, Lon⁡=Sn-1+α+1+q′, and, accordingly, Lon⁡/Lopt<1+α, a contradiction. If there exists only one batch in the offline optimal schedule π, then Lopt≥r′+1+qn>Sn-1+1+qn, and accordingly, Lon⁡/Lopt≤(Sn-1+α+1+qn)/(Sn-1+1+qn)<1+α, a contradiction. So in the following we assume that q′<qn-1, that is, qn=qn-1, and assume that there exist at least two batches in the offline optimal schedule π. Then Lon⁡=Sn-1+α+1+qn-1 and Lopt≥2.
Ifn=2, then Lon⁡=S1+α+1+q1. By Observation 1, we have Lopt≥S1-α+1+q1. Noticing that Lopt≥2, we have Lon⁡/Lopt≤1+α, a contradiction.
Ifn=3, then Lon⁡=S2+α+1+q2. By algorithm H(b=2), we know that B2 does not interrupt B1; that is, S2≥S1+1. If S2>S1+1, then all jobs in B2 arrive at or after S2, and so Lopt≥S2+1+q2. Thus, Lon⁡/Lopt<1+α, a contradiction. If S2=S1+1, then Lon⁡=S1+α+2+q2. If, in the offline optimal schedule π, J2 is scheduled after the first starting batch, then Lopt≥S1-α+2+q2. Thus, Lon⁡/Lopt≤(S1+α+2+q2)/(S1-α+2+q2)≤1+α, a contradiction. If, in the offline optimal schedule π, J2 is scheduled in the first starting batch and r2≥S1+α, considering there exist at least two batches in the offline optimal schedule π, then Lopt≥max⁡{S1+α+1+q2,S1+α+2}. Thus, Lon⁡/Lopt≤(S1+α+2+q2)/max⁡{S1+α+1+q2,S1+α+2}≤1+1/(2α+2)=1+α, a contradiction. If, in the offline optimal schedule π, J2 is scheduled in the first starting batch and r2<S1+α, then B1 is full and the smallest delivery time of jobs in B1 is not less than q2. Thus Lopt≥S1-α+2+q2, and so Lon⁡/Lopt≤(S1+α+2+q2)/(S1-α+2+q2)≤1+α, a contradiction.
The above analysis means thatBn does not interrupt Bn-1. Note that n≥2. If h=1, then Sn>Sn-1+1. From S(2) in algorithm H(b=2), we know that Sn=rn. Thus Lon⁡=Sn+1+qn=rn+1+qn≤Lopt, a contradiction. Thus, h≥2. Claim 1 follows.
Claim 2 (some batch in the h-1 batches Bn′,Bn′+1,…,Bn-1 is nonfull). Otherwise, all of the h-1 batches Bn′,Bn′+1,…,Bn-1 are full.
If the delivery time of some job inBn′,Bn′+1,…,Bn-1 is less than qn, let Bk be the latest starting batch in Bn′,Bn′+1,…,Bn-1 such that some job in Bk has a delivery time less than qn. Then each job in batches starting in the time interval (Sk,Sn) and Jn have delivery times not less than qn and then arrive after Sk. Then Lopt≥Sk+n-k+qn, Lon⁡=Sk+n-k+1+qn, and Lon⁡-Lopt≤1.
Ifk≥3 or [k=2 and n≥4], then Sk+n-k≥2+2α, and so (Lon⁡-Lopt)/Lopt≤1/(2α+2)=α, a contradiction.
Ifk=2 and n=3, then we have r3>S2 and Lopt≥r3+1+q3>S2+1+q3. As B2 is full, there exist at least two batches in the offline optimal schedule π. Suppose that B2 interrupts B1, which means that S2=S1+α and Lon⁡=S1+α+2+q3. If J3 is scheduled in the first starting batch in the offline optimal schedule π, then Lopt≥r3+2≥S1+α+2≥2+2α. Thus, (Lon⁡-Lopt)/Lopt≤1/(2α+2)=α, a contradiction. If J3 is scheduled after the first starting batch in the offline optimal schedule π, then Lopt≥S1-α+2+q3. Thus, Lon⁡/Lopt≤(S1+α+2+q3)/(S1-α+2+q3)≤1+α, a contradiction. So we suppose that B2 does not interrupt B1; that is, S2≥S1+1. Note that now Lon⁡=S2+2+q3. If S2>S1+1, then each job in {B2,B3} arrives at or later than S2. Considering that B2 is full, then Lopt≥S2+2≥3+α. Thus, (Lon⁡-Lopt)/Lopt≤1/(α+3)<α, a contradiction. If S2=S1+1, then Lon⁡=S2+2+q3=S1+3+q3. If B1 is full, then Lopt≥3. Thus, (Lon⁡-Lopt)/Lopt≤1/3<α, a contradiction. If B1 is nonfull, considering that B2 does not interrupt B1, then each job in {B2,B3} arrives later than S1+α which means that Lopt≥S1+α+2≥2α+2. So (Lon⁡-Lopt)/Lopt≤1/(2α+2)=α, a contradiction.
Ifk=1, noticing that now B1 is full and B2 does not interrupt B1, then each job in batches starting in the time interval (S1,Sn) and Jn have delivery times not less than qn and arrive after S1+α by S(3) in algorithm H(b=2). So Lopt≥S1+α+n-1+qn and Lon⁡=S1+n+qn. Thus, Lon⁡/Lopt≤(S1+n+qn)/(S1+α+n-1+qn)≤(2+α)/(2α+1)=1+α, a contradiction.
So in the following we assume the delivery time of each job in{Bn′,Bn′+1,…,Bn-1} is not less than qn. Then Lopt≥S1-α+h+qn.
IfBn′ interrupts Bn′-1, then n′=2,3. If n′=2, then Lon⁡=S2+h+qn=S1+α+h+qn. Considering h≥2 and S1≥α, we have Lon⁡/Lopt≤(S1+α+h+qn)/(S1-α+h+qn)≤1+α, a contradiction. If n′=3, then B2 is nonfull, S2≥S1+1, and Lon⁡=S3+h+qn=S2+α+h+qn. Note that now there is only one job in B2. If q2<qn, considering jobs in the set of {Bn′,Bn′+1,…,Bn-1,Jn} all have delivery times not less than qn, then these jobs arrive after S2, and, accordingly, Lopt≥S2+h+qn. So Lon⁡/Lopt≤(S2+α+h+qn)/(S2+h+qn)<1+α, a contradiction. If q2≥qn and r2<S1+α, then S2=S1+1, Lon⁡=S1+α+h+1+qn, B1 is full, and the delivery time of any job in B1 is not less than qn. And so Lopt≥S1-α+h+1+qn. So Lon⁡/Lopt≤(S1+α+h+1+qn)/(S1-α+h+1+qn)<1+α, a contradiction. If q2≥qn and S1+α≤r2≤S1+1, considering that there is only one job in B2, then S2=S1+1 and Lon⁡=S1+α+h+1+qn, and each job in {Bn′,Bn′+1,…,Bn} arrives at or after S1+α. So Lopt≥S1+α+h+qn. Thus Lon⁡/Lopt≤(S1+α+h+1+qn)/(S1+α+h+qn)≤1+1/(2+2α)=1+α, a contradiction. If q2≥qn and r2>S1+1, then S2>S1+1 and each job in {Bn′,Bn′+1,…,Bn} arrives at or after S2, and so Lopt≥S2+h+qn. Thus, Lon⁡/Lopt≤(S2+α+h+qn)/(S2+h+qn)≤1+α, a contradiction.
Ifn′=1 or [n′≥2 and Bn′ does not interrupt Bn′-1], then there exists some time instant t′ such that t′<Sn′ and the time interval [t′,Sn′) is an idle time in σ. Then by S(1), S(2) in algorithm H(b=2), the arrival time of any job in {Bn′,Bn′+1,…,Bn} is not less than Sn′-α. Thus Lopt≥Sn′-α+h+qn, and so Lon⁡/Lopt≤(Sn′+h+qn)/(Sn′-α+h+qn)<1+α, a contradiction. Claim 2 follows.
Lete≤n-1 be maximum so that Be is a nonfull batch. From Claim 2, we have e≥n′.
Claim 3 (e≤n-2). Otherwise, suppose that e=n-1. Since Bn-1 is nonfull, we have rn>Sn-1, Lon⁡=Se+2+qn, and Lopt≥rn+1+qn>Se+1+qn. If some batch starting before Se is interrupted, noticing that Be is a nonfull batch, then the interrupted batch must start before Se-1, and then Se≥S3≥2α+1. Hence, Lon⁡/Lopt≤(Se+2+qn)/(Se+1+qn)≤1+1/(2α+2)=1+α, a contradiction. So in the following we assume that each batch starting before Se is not interrupted. If n≤3, then e≤2. As Be is a nonfull batch and not interrupted, by S(3.1) in algorithm H(b=2), all jobs in Bn arrive after Se+α, which means that Lopt≥Se+α+1+qn. Hence, Lon⁡/Lopt≤(Se+2+qn)/(Se+α+1+qn)≤(2+α)/(2α+1)=1+α, a contradiction. If n≥4, then Se≥S3≥1+2α, and accordingly, Lon⁡/Lopt≤(Se+2+qn)/(Se+1+qn)≤1+1/(2α+2)=1+α, a contradiction. Claim 3 follows.
By the definition ofBe and Claim 3, n-e≥2, Be+1,…,Bn-1 are all full and each job in batches starting after Se arrives after Se. And Lon⁡=Se+n-e+1+qn.
If each job inBe+1,…,Bn-1 has a delivery time not less than qn, then Lopt≥Se+n-e+qn. If e≥2, then Se≥2α. Then Lon⁡/Lopt≤(Se+n-e+1+qn)/(Se+n-e+qn)≤1+1/(2α+2)=1+α, a contradiction. If e=1, considering Be is nonfull and not interrupted, then, by S(3.1) in algorithm H(b=2), each job in batches starting after S1 arrives after S1+α. Thus Lopt≥S1+α+n-1+qn. Hence, Lon⁡/Lopt≤(S1+n+qn)/(S1+α+n-1+qn)≤(3+α)/(2α+2)<1+α, a contradiction.
So in the following we assume that some job inBe+1,…,Bn-1 has a delivery time less than qn. Let e+1≤k′≤n-1 be maximum so that some job in Bk′ has a delivery time less than qn. Then k′≥2 and batches starting in the time interval (Sk′,Sn) are all full. Also each job in batches starting in the time interval (Sk′,Sn) and Jn have delivery times not less than qn and arrive after Sk′. Thus Lopt≥Sk′+n-k′+qn. Noting that Lon⁡=Sk′+n-k′+1+qn, we have Lon⁡-Lopt≤1. If k′≥3, then Sk′≥1+2α. Hence, Lon⁡/Lopt≤(Sk′+n-k′+1+qn)/(Sk′+n-k′+qn)≤1+1/(2α+2)=1+α, a contradiction. If k′=2, then e=1, n≥3, and Sk′≥2α. As now B1 is nonfull and not interrupted, then by S(3.1) in algorithm H(b=2), each job in batches starting after S1 arrives after S1+α. Thus Lopt≥S1+α+2≥2α+2. So (Lon⁡-Lopt)/Lopt≤1/(2α+2)=α, a contradiction.
From the above discussion we conclude that algorithmH(b=2) has a competitive ratio of at most 1+α. By Theorem 1, we know that algorithm H(b=2) is an optimal online algorithm with a competitive ratio of 1+α. This completes the proof.


## 3. Problem P-Batch(b≥3)

Note thatβ is the positive solution of β(1+β)2=1.Theorem 3.
For problem P-batch(b≥3), there exists no online algorithm with a competitive ratio of less than 1+β.Proof.
Theorem 2.4 in Liu and Yuan [21] shows that, for problem 1∣online,rj,pj=1,P-batch,b<∞,L-restart∣Cmax⁡ with b≥3, no online algorithm has a competitive ratio of less than 1+β. Here Cmax⁡ is makespan, namely, the maximum completion time of all jobs on the parallel batch machine. Problem 1∣online,rj,pj=1,P-batch,b<∞,L-restart∣Cmax⁡ is the special case of 1∣online,rj,pj=1,P-batch,b<∞,L-restart∣Lmax⁡. So for problem P-batch (b≥3), no online algorithm has a competitive ratio of less than 1+β. The theorem follows.Algorithm
H
(
b
≥
3
). Initially set k=0. At the current time instant t, do the following.S
(
1
): if k=0, U(t)≠∅, and t≥β, then select min⁡b,Ut jobs in U(t) such that each job selected has a delivery time not less than the largest delivery time of jobs not selected in U(t) as the batch Bk+1 starting at time t. Then reset k to be k+1.S
(
2
): if k≥1, the machine is idle, and U(t)≠∅, select min⁡b,Ut jobs in U(t) such that each job selected has a delivery time not less than the largest delivery time of jobs not selected in U(t) as the batch Bk+1 starting at time t. Then reset k to be k+1.S
(
3
): if S1<1/β-1, U(t)≠∅, the machine is occupied by Bk, k∈{1,2}, and each batch starting earlier than Sk is not interrupted, do the following.S
(
3.1
): if k=1, Bk is nonfull, t=(1+β)Sk+β, and |Bk|+|U(t)|≤b, then let q′ be the largest delivery time of jobs in U(t). If q′≥q1, or q′≥β, or [q′<β, and q1<1-β], then do Restart (k,t).S
(
3.2
): if k=1, Bk is full, t=Sk+β, the largest delivery time of jobs in U(t) is not less than β2+β, and the delivery time of some job in B1 is less than the delivery time of some job in U(t), then do Restart (k,t).S
(
3.3
): if k=2, Bk is nonfull, t=Sk+β, |Bk|+|U(t)|≤b, and {either B1 is full or [B1 is nonfull and the number of jobs arriving in the time interval [0,(1+β)S1+β] is not more than b]}, then do Restart (k,t).S
(
4
): otherwise, do nothing but wait.From algorithmH(b≥3) we have the following observation.Observation 2.
(1) The earliest arrival time of all jobs is not less thanS1-β. If S1>β, then all jobs arrive at or after S1.
(2) IfS1≥1/β-1 or {S1<1/β-1, B1 is nonfull, and the number of jobs arriving in the time interval [0,(1+β)S1+β] is more than b}, then there exists no batch which is interrupted.
(3) Ifk≥3, then Sk≥2β+1.
(4) IfS1<1/β-1, then (1+β)S1+β<S1+1.Theorem 4.
For problem P-batch(b≥3), H(b≥3) is a best possible online algorithm with a competitive ratio of 1+β.Proof.
Suppose to the contrary thatI is an instance so that Lon⁡/Lopt>1+β. Let σ be the schedule generated by running algorithm H(b≥3) for the instance I and let π be an offline optimal schedule for the instance I. As the proof in Theorem 2, qi is used to denote the largest delivery time of jobs in Bi and ri is the latest arrival time of jobs whose delivery times are qi in Bi. Let Bn be the earliest starting batch in σ which is not interrupted and assumes Lon⁡. Then Lon⁡=Sn+1+qn. As S1≤max⁡{r1,β}, then the assumption that Lon⁡/Lopt>1+β implies n≥2.
LetCon⁡=Sn+1; that is, Con⁡ is the completion time of Bn on the parallel batch machine. Let t be the minimum time instant such that, in σ, there are no idle times between t and Con⁡ and each batch processed in the time interval [t,Con⁡] is not interrupted. Suppose that there are h batches Bn-h+1,…,Bn processed in the time interval [t,Con⁡] in σ. Then Con⁡=t+h. Set n′=n-h+1. So Sn′=t.
Claim 1 (Bn does not interrupt Bn-1 and h≥2). Otherwise, Bn is a restricted batch. By algorithm H(b≥3), we have n=2,3 and S1<1/β-1; that is, (1+β)S1+β<S1+1. Let q′′ be the largest delivery time of jobs arriving in the interval (Sn-1,Sn], let J′′ be the job with delivery time q′′, and let r′′ be the arrival time of J′′. Then qn=max⁡⁡{qn-1,q′′}. If q′′≥qn-1, then qn=q′′, Lopt≥Sn-1+1+q′′, Lon⁡=Sn+1+q′′≤(1+β)Sn-1+β+1+q′′, and, accordingly, Lon⁡/Lopt≤1+β, a contradiction. So in the following we assume that q′′<qn-1; that is, qn=qn-1. Then Lon⁡=Sn+1+qn-1. If, in the offline optimal schedule π, there exists only one batch, or Jn-1 and J′′ are scheduled in one batch, or the batch containing Jn-1 starts later than the batch containing J′′, then Lopt≥Sn-1+1+qn-1. Considering Lon⁡=Sn+1+qn-1≤(1+β)Sn-1+β+1+qn-1, then Lon⁡/Lopt≤1+β, a contradiction. So in the following we assume that, in the offline optimal schedule π, there exist at least 2 batches, Jn-1 and J′′ are scheduled in two different batches, and the batch containing Jn-1 starts earlier than the batch containing J′′. Then we easily get Lopt≥max⁡{rn-1+1+qn-1,rn-1+2+q′′}≥S1-β+2+q′′.
Ifn=2 and B1 is full, then q′′<q1, S2=S1+β, and Lon⁡=S1+β+1+q1. By Observation 2, we have Lopt≥S1-β+1+q1. Considering Lopt≥2, then (Lon⁡-Lopt)/Lopt≤(2β)/2=β, a contradiction.
Ifn=2 and B1 is nonfull, then Lon⁡=(1+β)S1+β+1+q1. If q1<1-β, then Lon⁡<(1+β)S1+2. Noticing that Lopt≥S1-β+2, then Lon⁡/Lopt≤((1+β)S1+2)/(S1-β+2)<1+β, a contradiction. Hence we have q1≥1-β. As B2 interrupts B1, considering q′′<q1 and q1≥1-β, then, by S(3.1) in algorithm H(b≥3), the only possibility is that q′′≥β. Then Lopt≥S1-β+2+q′′≥S1+2. Thus, Lon⁡/Lopt≤((1+β)S1+β+1+q1)/max⁡{S1-β+1+q1,S1+2}≤1+(β(S1+2))/(S1+2)=1+β, a contradiction.
Ifn=3, then S3=S2+β and Lon⁡=S2+β+1+q2. Also noticing that now B2 does not interrupt B1, we have S2≥S1+1. Note that q′′<qn-1 and in the offline optimal schedule π, the batch containing Jn-1=J2 starts earlier than the batch containing J′′. If r2≤S1, then S2=S1+1, Lon⁡=S1+β+2+q2, B1 is full and each job in B1 has a delivery time not less that q2, and, accordingly, Lopt≥S1-β+2+q2. Thus, Lon⁡/Lopt≤(S1+β+2+q2)/(S1-β+2+q2)≤1+β, a contradiction. If r2≥S2, then Lopt≥S2+1+q2. Thus Lon⁡/Lopt≤(S2+β+1+q2)/(S2+1+q2)<1+β, a contradiction. If (1+β)S1+β≤r2<S2, then S2=S1+1, Lon⁡=S1+β+2+q2, and Lopt≥(1+β)S1+β+1+q2. Thus Lon⁡/Lopt<(S1+β+2+q2)/((1+β)S1+β+1+q2)≤(2β+2+q2)/((1+β)β+β+1+q2)<1+β, a contradiction. So in the following we assume that S1<r2<(1+β)S1+β. Then S2=S1+1, Lon⁡=S1+β+2+q2, and Lopt≥r2+2>S1+2. If q2≤β+β2, then Lon⁡/Lopt<(S1+β+2+β+β2)/(S1+2)≤1+β, a contradiction. If q2>β+β2, noticing that B2 does not interrupt B1 and B3 interrupts B2, by S(3) in algorithm H(b≥3), then B1 is full. If each job in the full batch B1 has a delivery time not less than q2, then Lopt≥S1-β+2+q2, and then Lon⁡/Lopt≤(S1+β+2+q2)/(S1-β+2+q2)≤1+β, a contradiction. So some job in the full batch B1 has a delivery time less than q2. As B1 is full, q2>β+β2, some job in B1 has a delivery time less than q2, and B2 does not interrupt B1, then r2>S1+β, and so Lopt≥max⁡{S1+β+1+q2,S1+β+2}. Thus, Lon⁡/Lopt<(S1+β+2+q2)/max⁡{S1+β+1+q2,S1+β+2}≤1+1/(2β+2)<1+β, a contradiction.
The above analysis means thatBn does not interrupt Bn-1. Note that n≥2. If h=1, then Sn>Sn-1+1. From S(2) in algorithm H(b≥3), we know that Sn=rn. Thus Lon⁡=Sn+1+qn=rn+1+qn≤Lopt, a contradiction. Hence, h≥2. Claim 1 follows.
Claim 2 (some batch in the h-1 batches Bn′,Bn′+1,…,Bn-1 is nonfull). Otherwise, all of the h-1 batches Bn′,Bn′+1,…,Bn-1 are full.
If the smallest delivery time of jobs inBn′,Bn′+1,…,Bn-1 is not less than qn and Bn′ interrupts Bn′-1, then n′=2,3. If n′=2 and B1 is full, then Lon⁡=Sn′+h+qn=S1+β+h+qn and Lopt≥S1-β+h+qn. Thus, considering h≥2 and S1≥β, we have Lon⁡/Lopt≤(S1+β+h+qn)/(S1-β+h+qn)≤1+β, a contradiction. If [n′=2 and B1 is nonfull] or n′=3, then Bn′-1 is nonfull and each job in batches starting after Sn′ arrives after Sn′. Then Lopt≥Sn′+h-1+qn and Sn′≥min⁡{(1+β)S1+β,S1+1+β}≥min⁡{(1+β)2-1,1+2β}≥(1+β)2-1. Thus Lon⁡/Lopt≤(Sn′+h+qn)/(Sn′+h-1+qn)≤1+1/(1+β)2=1+β, a contradiction.
If the smallest delivery time of jobs inBn′,Bn′+1,…,Bn-1 is not less than qn and {n′=1 or [n′≥2 and Bn′ does not interrupt Bn′-1]}, then the arrival time of any job in Bn′,Bn′+1,…,Bn is not less than Sn′-β. Thus Lopt≥Sn′-β+h+qn, and so Lon⁡/Lopt≤(Sn′+h+qn)/(Sn′-β+h+qn)<1+β, a contradiction.
So in the following we suppose that the delivery time of some job inBn′,Bn′+1,…,Bn-1 is less than qn. Let Bk be the latest starting batch in Bn′,Bn′+1,…,Bn-1 such that some job in Bk has a delivery time less than qn. Then each job in batches starting in the time interval (Sk,Sn) and Jn have delivery times not less than qn and, accordingly, arrive after Sk. Then Lopt≥Sk+n-k+qn, Lon⁡=Sk+n-k+1+qn, and Lon⁡-Lopt≤1.
Ifk≥3 or [k=2 and n≥4], then Lopt≥Sk+n-k≥2+2β, and, accordingly, (Lon⁡-Lopt)/Lopt≤1/(2+2β)<β, a contradiction.
Ifk=2, n=3, and {B1 is nonfull or [B1 is full and B2 does not interrupt B1]}, then S2≥min⁡{(1+β)S1+β,S1+1}≥(1+β)2-1. Thus, (Lon⁡-Lopt)/Lopt≤1/(1+β)2=β, a contradiction. If k=2, n=3, B1 is full, and B2 interrupts B1, then some job with a delivery time not less than β2+β arrives after S1 and Lopt≥S1+1+β2+β≥(1+β)2. Thus, (Lon⁡-Lopt)/Lopt≤1/(1+β)2=β, a contradiction.
Ifk=1 and n≥3, then Lopt≥Sk+n-k≥2+β, and, accordingly, (Lon⁡-Lopt)/Lopt≤1/(β+2)<β, a contradiction. If k=1 and n=2, then there are at least two batches in the offline optimal schedule π. Note that now r2>S1. If Jn=J2 is scheduled in the first batch in the offline optimal schedule π, then Lopt≥max⁡{S1+1+q2,S1+2}≥2+β. Thus, (Lon⁡-Lopt)/Lopt≤1/(β+2)<β, a contradiction. If Jn=J2 is scheduled in the batch starting after the first batch in the offline optimal schedule π, then Lopt≥S1-β+2+q2. Thus, Lon⁡/Lopt≤(S1+2+q2)/(S1-β+2+q2)≤1+β, a contradiction. Claim 2 follows.
Lete≤n-1 be maximum so that Be is a nonfull batch. From Claim 2, we have k≥n′.
Claim 3 (e≤n-2). Otherwise, suppose that e=n-1. As Be is a nonfull batch, then rn>Se, Lon⁡=Se+2+qn, and Lopt≥rn+1+qn>Se+1+qn.
Ife≥2, noticing that Be is a nonfull batch, then Se≥min⁡{(1+β)S1+β,S1+1}≥(1+β)2-1. Then Lon⁡/Lopt≤(Se+2+qn)/(Se+1+qn)≤1+1/(1+β)2=1+β, a contradiction.
Ife=1, then n=2, r2>S1, Lon⁡=S1+2+q2, and Lopt>S1+1+q2. If S1≥1/β-1, then Lon⁡/Lopt≤(S1+2+q2)/(S1+1+q2)≤1+1/(1/β)=1+β, a contradiction. So we suppose that S1<1/β-1. If r2≥(1+β)S1+β, then Lopt≥r2+1+q2≥(1+β)2. Thus Lon⁡/Lopt≤1+1/(1+β)2=1+β, a contradiction. So in the following we assume that r2<(1+β)S1+β. If there is only one batch in the offline optimal schedule π, then |B1|+|B2|≤b and Lopt≥S1+1+q1. Also considering that B2 does not interrupt B1, we have that q1≥1-β and q2<β. Then Lopt≥S1+1+q1≥S1+2-β. And Lon⁡/Lopt≤(S1+2+q2)/(S1+1+q1)≤(S1+2+β)/(S1+2-β)≤1+β, a contradiction. So in the following we assume that there are at least two batches in the offline optimal schedule π. If Jn=J2 is scheduled in the first starting batch in the offline optimal schedule π, then Lopt≥max⁡{S1+1+q2,S1+2}≥2+β. Thus, Lon⁡/Lopt≤1+1/(β+2)<1+β. If Jn=J2 is scheduled in the batch starting after the first starting batch in the offline optimal schedule π, then Lopt≥S1-β+2+q2. Thus, Lon⁡/Lopt≤(S1+2+q2)/(S1-β+2+q2)≤1+β, a contradiction. Claim 3 follows.
By the definition ofBe and Claim 3, n-e≥2, Be+1,…,Bn-1 are all full and each job in batches starting after Se arrives after Se. And Lon⁡=Se+n-e+1+qn.
If each job inBe+1,…,Bn-1 has a delivery time not less than qn, then Lopt≥Se+n-e+qn≥2+β. Then Lon⁡/Lopt≤(Se+n-e+1+qn)/(Se+n-e+qn)≤1+1/(β+2)<1+β, a contradiction. So in the following we assume that some job in Be+1,…,Bn-1 has a delivery time less than qn. Let e+1≤k′≤n-1 be maximum so that some job in Bk′ has a delivery time less than qn. Then k′≥2 and batches starting in the time interval (Sk′,Sn) are all full. And each job in batches starting in the time interval (Sk′,Sn) and Jn have delivery times not less than qn and then arrive after Sk′. Thus Lopt≥Sk′+n-k′+qn. Note that Lon⁡=Sk′+n-k′+1+qn. Considering k′≥2, then Sk′≥Se+1≥1+β. Hence, Lon⁡/Lopt≤(Sk′+n-k′+1+qn)/(Sk′+n-k′+qn)≤1+1/(β+2)<1+β, a contradiction.
From the above discussion we conclude that algorithmH(b≥3) has a competitive ratio of at most 1+β. By Theorem 3 we know that algorithm H(b≥3) is an optimal online algorithm with a competitive ratio of 1+β. This completes the proof.



---

*Source: 628254-2015-07-28.xml*