# Semi-Online Scheduling on Two Machines withGoS Levels and Partial Information of Processing Time

Authors: Taibo Luo; Yinfeng Xu
Journal: The Scientific World Journal
 (2014)

---

## Abstract

This paper investigates semi-online scheduling problems on two parallel machines under a grade of service (GoS) provision subject to minimize the makespan. We consider three different semi-online versions with knowing the total processing time of the jobs with higher GoS level, knowing the total processing time of the jobs with lower GoS level, or knowing both in advance. Respectively, for the three semi-online versions, we develop algorithms with competitive ratios of 3/2, 20/13, and 4/3 which are shown to be optimal.


---

## Body

## 1. Introduction

Scheduling problem under a grade of service provision was first proposed by Hwang et al. [1]. The jobs should be assigned irrevocably to machines as soon as they arrive. Each job and machine are labeled with the GoS levels. A job can be processed by a particular machine if and only if the GoS level of the job is not less than that of the machine. In practice, the scheduling with GoS eligibility constraints is widely used. For more details, please refer to [1–3].For the offline scheduling onm machines under a grade of service provision, Hwang et al. [1] presented an lg-lpt algorithm which has a tight bound of 5/4 for two machines and 2-1/(m-1) for m (m≥3) machines. Ji and Cheng [4] gave an fptas for this problem. However, Woeginger [5] gave two simpler fptass for the same problem. For the online version, Jiang [6] proved a lower bound of 2 for the case with two levels of GoS and presented an online algorithm with a competitive ratio of 2.52. Zhang et al. [7] improved the result and showed an algorithm with a competitive ratio of 1+(m2-m)/(m2-sm+s2)≤7/3.Form=2, Park et al. [8] presented an optimal algorithm with a competitive ratio of 5/3. However, there are many papers focusing on the semi-online scheduling on two machines under GoS [8–13]. As the total processing time of all jobs is known, Park et al. [8] gave an optimal algorithm with a competitive ratio of 3/2. When the largest processing time of all jobs is known, Wu et al. [12] presented an optimal algorithm with a competitive ratio of (5+1)/2. In the same paper, Wu et al. [12] gave an optimal algorithm with a competitive ratio of 3/2 when the optimal value of the instance is known. For the processing times bounded in an interval, Liu et al. [9] gave a competitive algorithm under some conditions and Zhang et al. [13] improved the result and gave an optimal algorithm for different intervals. In this paper, we focus on the semi-online scheduling problem where only partial information of the total processing time is known. The semi-online versions concerned in our paper are listed as follows.sum · higher: the total processing time of all jobs with higher GoS level is known in advance.sum · lower: the total processing time of all jobs with lower GoS level is known in advance.We useP2·GoS∣s∣Cmax⁡ to denote the semi-online problem with information s, where s∈{sum·higher,sum·lower}. Moreover, we use P2·GoS∣s1&s2∣Cmax⁡ to denote the semi-online problem where both information s1 and information s2 are available in advance.Our results indicate that competitive ratios of three algorithms are better than5/3 of the online version [8]. When knowing sum · higher in advance, the competitive ratio is the same as the optimal algorithm [8] presented for the semi-online problem where the total processing time of all jobs is known. For designing algorithm, the results indicate that knowing sum · higher&sum · lower is more useful than sum · higher or sum · lower. Moreover, knowing sum · higher is more useful than sum · lower. However, knowing sum · lower is better than knowing the largest processing time of all jobs [12].The rest of this paper is organized as follows: in Section2, we give some basic definitions. In Sections 3–5, we prove lower bounds and present algorithms for the three semi-online problems, respectively.


## 2. Basic Definitions

We are given two machines and a series of jobs arriving online which are to be scheduled irrevocably at the time of their arrivals. The arrival of a new job occurs only after the current job is scheduled. We denote by the setJ=1,…,n the set of all job indices arranged in the order of arrival. The jth arriving job is referred to as job Jj. We denote each job by Jj=(pj,gj). The GoS assigned to job Jj is denoted by gj, which is 1 if the job must be processed only by the first machine and 2 if it may be processed by either of the two; pj is the processing time of job Jj; pj and gj are not known until the arrival of job Jj. Let T1=∑gj=1‍pj and T2=∑gj=2‍pj.The scheduled can be seen as the partition ofJ into two subsets, denoted by (S1,S2), where S1 and S2 contain job indices assigned to the first and second machine, respectively. Let t(S)=ΣJj∈Spj for an arbitrary subset S of J. Then the maximum of t(S1) and t(S2), denoted by max⁡{t(S1),t(S2)}, is the makespan of the scheduled (S1,S2). The problem is to minimize max⁡{t(S1),t(S2)}.The minimum makespan obtained by an optimal offline algorithm is denoted byCopt. The makespan generated by algorithm A is denoted by CA. The competitive ratio of A is defined to be the maximum CA/Copt.


## 3. Optimal Algorithm forP2·GoS∣sum·higher∣Cmax⁡

In this section, we prove a lower bound of competitive ratio and present an optimal algorithm for the semi-online version asT1 is known in advance.


### 3.1. Lower Bound of Competitive Ratio

Theorem 1.
Any semi-online algorithm forP2·GoS∣sum·higher∣Cmax⁡ has a competitive ratio of at least 3/2.Proof.
The theorem will be proved by adversary method. LetT1=1 be known in advance. The first job is J1=(1,1). J1 must be scheduled on the first machine. Then, we generate job J2=(1,2). If job J2=(1,2) is scheduled on the first machine, and there is no job arriving after, we have CA/Copt=2>3/2. Otherwise, job J2 is scheduled on the second machine, and we generate job J3=(2,2). No matter which machine that job J3 is scheduled on, we have CA=3. Since the optimal algorithm will scheduled job J1 and job J2 on the first machine and scheduled job J3 on the second machine. Hence, CA/Copt=3/2. The proof is completed.


### 3.2.  Optimal Semi-Online AlgorithmGoS-TH

Since we knowT1 in advance and all the jobs with gj=1 must be scheduled on the first machine, we can regard them as one job; that is, J0=(T1,1). We scheduled job J0 on the first machine at first and do not need to care about the job with gj=1 later.At the arrival of each job,H is updated to become a half of the total processing time of the jobs which include the jobs with GoS=2 and job J0;  P is updated to become the maximum processing time. We define Pj, S1j, S2j, and Hj to be P, S1, S2, and H after we scheduled job Jj. Then, clearly the optimum makespan Copt≥L=max⁡(T,P). Combined with the online algorithm presented by Park et al. [8], we propose Algorithm GoS-TH.Algorithm  GoS-TH
(1)
ScheduledJ0 to the first machine and t(S10)=T1.
(2)
Letpj=0 for all the jobs with gj=1.
(3)
Suppose that the incoming job isJj and gj=1; assign job Jj to the first machine.
(4)
Suppose the incoming job isJj and gj=2. Hj=Hj-1+pj/2, Pj=max⁡(Pj-1,pj), and Lj=max⁡(Tj,Pj).
(4.1)
Ift(S2j)+pj≤(3/2)Lj, scheduled it to the second machine.
(4.2)
Ift(S2j)+pj>(3/2)Lj, scheduled it to the first machine.Theorem 2.
The competitive ratio of AlgorithmGoS-TH is 3/2 for P2·GoS∣sum·higher∣Cmax⁡.Proof.
Suppose that Theorem2 is false. There must exist an instance with the least number of jobs to make CGoS-TH>(3/2)Copt. The makespan is not determined until the arrival of job Jn. Therefore,(1)CGoS-TH=max⁡{t(S1n),t(S2n)}>32Copt,max⁡{t(S1n-1),t(S2n-1)}≤32Copt.
Ifgn=1, based on Algorithm GoS-TH, we have t(S1n)=t(S1n-1) and t(S2n)=t(S2n-1). Due to the fact that max⁡{t(S1n-1),t(S2n-1)}≤(3/2)Copt, we just need to prove Theorem 2 is true when gn=2.
Ifgn=2, when it is scheduled on the second machine, we have CGoS-TH=t(S2n)=t(S2n-1)+pn≤(3/2)Copt. This is contradicting with inequality (1). Otherwise, job Jn is scheduled on the first machine, which leads to t(S2n-1)+pn>(3/2)Ln≥(3/2)Hn; combined with (t(S2n-1)+pn+t(S1n-1))/2=Hn, we get that t(S1n-1)<(1/2)Ln≤(1/2)Copt. Since pn≤Copt, we have t(S1n-1)+pn<(3/2)Copt, which also contradicted with inequality (1). The proof is completed.


## 3.1. Lower Bound of Competitive Ratio

Theorem 1.
Any semi-online algorithm forP2·GoS∣sum·higher∣Cmax⁡ has a competitive ratio of at least 3/2.Proof.
The theorem will be proved by adversary method. LetT1=1 be known in advance. The first job is J1=(1,1). J1 must be scheduled on the first machine. Then, we generate job J2=(1,2). If job J2=(1,2) is scheduled on the first machine, and there is no job arriving after, we have CA/Copt=2>3/2. Otherwise, job J2 is scheduled on the second machine, and we generate job J3=(2,2). No matter which machine that job J3 is scheduled on, we have CA=3. Since the optimal algorithm will scheduled job J1 and job J2 on the first machine and scheduled job J3 on the second machine. Hence, CA/Copt=3/2. The proof is completed.


## 3.2.  Optimal Semi-Online AlgorithmGoS-TH

Since we knowT1 in advance and all the jobs with gj=1 must be scheduled on the first machine, we can regard them as one job; that is, J0=(T1,1). We scheduled job J0 on the first machine at first and do not need to care about the job with gj=1 later.At the arrival of each job,H is updated to become a half of the total processing time of the jobs which include the jobs with GoS=2 and job J0;  P is updated to become the maximum processing time. We define Pj, S1j, S2j, and Hj to be P, S1, S2, and H after we scheduled job Jj. Then, clearly the optimum makespan Copt≥L=max⁡(T,P). Combined with the online algorithm presented by Park et al. [8], we propose Algorithm GoS-TH.Algorithm  GoS-TH
(1)
ScheduledJ0 to the first machine and t(S10)=T1.
(2)
Letpj=0 for all the jobs with gj=1.
(3)
Suppose that the incoming job isJj and gj=1; assign job Jj to the first machine.
(4)
Suppose the incoming job isJj and gj=2. Hj=Hj-1+pj/2, Pj=max⁡(Pj-1,pj), and Lj=max⁡(Tj,Pj).
(4.1)
Ift(S2j)+pj≤(3/2)Lj, scheduled it to the second machine.
(4.2)
Ift(S2j)+pj>(3/2)Lj, scheduled it to the first machine.Theorem 2.
The competitive ratio of AlgorithmGoS-TH is 3/2 for P2·GoS∣sum·higher∣Cmax⁡.Proof.
Suppose that Theorem2 is false. There must exist an instance with the least number of jobs to make CGoS-TH>(3/2)Copt. The makespan is not determined until the arrival of job Jn. Therefore,(1)CGoS-TH=max⁡{t(S1n),t(S2n)}>32Copt,max⁡{t(S1n-1),t(S2n-1)}≤32Copt.
Ifgn=1, based on Algorithm GoS-TH, we have t(S1n)=t(S1n-1) and t(S2n)=t(S2n-1). Due to the fact that max⁡{t(S1n-1),t(S2n-1)}≤(3/2)Copt, we just need to prove Theorem 2 is true when gn=2.
Ifgn=2, when it is scheduled on the second machine, we have CGoS-TH=t(S2n)=t(S2n-1)+pn≤(3/2)Copt. This is contradicting with inequality (1). Otherwise, job Jn is scheduled on the first machine, which leads to t(S2n-1)+pn>(3/2)Ln≥(3/2)Hn; combined with (t(S2n-1)+pn+t(S1n-1))/2=Hn, we get that t(S1n-1)<(1/2)Ln≤(1/2)Copt. Since pn≤Copt, we have t(S1n-1)+pn<(3/2)Copt, which also contradicted with inequality (1). The proof is completed.


## 4. Optimal Algorithm forP2·GoS∣sum·lower∣Cmax⁡

In this section, we prove a lower bound of competitive ratio and present an optimal algorithm for the semi-online version asT2 is known in advance.


### 4.1. Lower Bound of Competitive Ratio

Theorem 3.
Any semi-online algorithm forP2·GoS∣sum·lower∣Cmax⁡ has a competitive ratio of at least 20/13.Proof.
We will construct a job sequence withT2=26 to make an arbitrary algorithm A behave poorly. We begin with jobs J1=(1,2) and J2=(1,2). We discuss the following three cases.
Case  1 (J1 and J2 are scheduled on the first machine). We continue to generate jobs J3=(12,2) and J4=(12,2). If job J3 and job J4 are scheduled on the second machine, we have t(S2)=24; thus, CA/Copt=24/14>20/13. Otherwise, if job J3 or job J4 is scheduled on the first machine or both of them are scheduled on the first machine, we further generate job J5=(26,1). We will have t(S1)≥40. Since optimal algorithm will scheduled jobs J1, J2, J3, and J4 on the second machine and scheduled job J5 on the first machine, we have CA/Copt≥20/13.
Case
2 (J1 or J2 is scheduled on the first machine). We continue to generate job J3=(2,2). Then we discuss the following two subcases.
Subcase  2.1 (job J3 is scheduled on the first machine). We continue to generate jobs J4=(11,2) and J5=(11,2). If job J4 and job J5 are scheduled on the second machine, we have t(S2)=23 and t(S1)=2, which lead to CA/Copt=23/13>20/13. Otherwise, if job J4 or job J5 is scheduled on the first machine or both of them are scheduled on the first machine, we further generate job J6=(26,1) which leads to CA/Copt≥20/13.
Subcase  2.2 (J3 is scheduled on the second machine). We generate job J4=(5,2). If job J4 is scheduled on the second machine, we generate job J5=(13,2). If job J5 is scheduled on the second machine, we have t(S2)=21. Since the optimal algorithm will scheduled jobs J1, J2, J3, and J4 on the first machine and scheduled job J5 on the second machine, we have CA/Copt=21/13>20/13. If job J5 is scheduled on the first machine, we generate job J6=(26,1) which leads to CA/Copt≥20/13.
Otherwise, if jobJ4 is scheduled on the first machine, we generate job J5=(8,2). If job J5 is scheduled on the first machine, we generate job J6=(26,1) which leads to CA/Copt≥20/13. If job J5 is scheduled on the second machine, we generate job J6=(9,2). If job J6 is scheduled on the second machine, we have t(S2)=20 and Copt=13; thus, CA/Copt=20/13. If J6 is scheduled on the first machine, we generate job J7=(26,1) and have t(S1)=40 and Copt=26, which also lead to CA/Copt=20/13.
Case  3 (J1 and J2 are scheduled on the second machine). We continue to generate job J3=(2,2). Then we discuss the following two subcases.
Subcase  3.1 (job J3 is scheduled on the second machine). We generate jobs J4=(3,2) and J5=(3,2). If job J4 or job J5 is scheduled on the second machine or both of them are scheduled on the second machine, we further generate job J6=(1,2). If job J6 is scheduled on the second machine, we generate job J7=(14,2). If job J7 is scheduled on the second machine, we have t(S2)=22. Since the optimal algorithm will scheduled jobs J1, J2, J3, J4, J5, and J6 on the first machine and scheduled job J7 on the second machine, we have CA/Copt≥22/14>20/13. Otherwise, job J7 is scheduled on the first machine, and then we generate job J8=(26,1) and have t(S1)≥40 and Copt=26; hence, CA/Copt>20/13. If job J6 is scheduled on the first machine, we generate job J7=(13,2). If job J7 is scheduled on the second machine, we have t(S2)≥20 and Copt=13, hence, we also have CA/Copt>20/13. Otherwise, job J7 is scheduled on the first machine, and then we generate job J8=(26,1). We have CA/Copt>20/13.
If jobJ4 and job J5 are scheduled on the first machine, we generate jobs J6=(8,2) and J7=(8,2). If job J6 or job J7 is scheduled on the first machine or both of them are scheduled on the first machine, we further generate job J8=(26,1). We have CA/Copt>20/13. Otherwise, if job J6 and job J7 are scheduled on the second machine, we have t(S2)=20 and Copt=13, which lead to CA/Copt=20/13.
Subcase  3.2 (job J3 is scheduled on the first machine). We generate job J4=(2,2). If job J4 is scheduled on the first machine, we generate jobs J5=(10,2) and J6=(10,2). If job J5 and job J6 are scheduled on the second machine, we have t(S2)=22 and Copt=13; thus, CA/Copt=22/13>20/13. Otherwise, if job J5 or job J6 is scheduled on the first machine or both of them are scheduled on the first machine, we further generate job J7=(26,1) and have t(S1)≥40; thus, CA/Copt=20/13.
Otherwise, if jobJ4 is scheduled on the second machine, we generate job J5=(4,2). If job J5 is scheduled on the second machine, we generate job J6=(13,2). If job J6 is scheduled on the second machine, we have t(S2)=21 and Copt=13; hence, CA/Copt=20/13. If job J6 is scheduled on the first machine, we generate job J7=(26,1) and have t(S1)≥41; thus, CA/Copt=41/26>20/13.
Therefore, jobJ5 is scheduled on the first machine. Then we generate jobs J6=(8,2) and J7=(8,2). If job J6 or job J7 is scheduled on the first machine or both of them are scheduled on the first machine, we further generate job J8=(26,1). We will have t(S1)≥40 and Copt=26; hence, CA/Copt>20/13. Otherwise, if job J6 and job J7 are scheduled on the second machine, we have t(S2)=20 and Copt=13; also, we have CA/Copt=20/13. The proof is completed.


### 4.2.  Optimal Semi-Online AlgorithmGoS-TL

In this subsection, we design an optimal algorithm with a competitive ratio of20/13. Let x1 and x2 be the jobs with gj=2 assigned to the first and second machine, respectively, where t(x1)+t(x2)=T2. We define x1j and x2j to be x1 and x2 after we scheduled job Jj. Then, we propose Algorithm GoS-TL.Algorithm  GoS-TL
(1)
Suppose that the incoming job isJj and gj=1; assign job Jj to the first machine.
(2)
Suppose that the incoming job isJj and gj=2.
(2.1)
(Stopping criterion 1). If (3/13)T2≤t(x1j-1)+pj≤(7/13)T2, scheduled job Jj and all the remaining jobs with GoS=1 to the first machine, and then scheduled all the remaining jobs with GoS=2 to the second machine. Stop.
(2.2)
(Stopping criterion 2). If (6/13)T2≤t(x2j-1)+pj≤(10/13)T2, scheduled job Jj to the second machine and scheduled all the remaining jobs to the first machine. Stop.
(2.3)
(Stopping criterion 3). If t(x2j-1)>10/13, scheduled job Jj and the remaining jobs to the first machine. Stop.
(2.4)
Ift(x2j-1)≤(7/26)T2 and (7/13)T2≤t(x2j-1)+pj<(6/13)T2, scheduled job Jj to the first machine. Continue.
(2.5)
Otherwise, scheduled jobJj to the second machine. Continue.Lemma 4.
If(6/13)T2≤t(x2)≤(10/13)T2, then CGoS-TL≤(20/13)Copt.Proof.
SinceCopt≥(1/2)T2, we have t(S2)=t(x2)≤(10/13)T2≤(20/13)Copt. Then, we only need to prove that t(S1)≤(20/13)Copt. We discuss it by the following two cases.
Case  1 (T1≥T2). In this case, we have t(S1)=t(x1)+T1 and T1≥(T1+T2)/2. Since (6/13)T2≤t(x2)≤(10/13)T2, we have t(x1)≤(7/13)T2. Combined with Copt≥T1, we have
(2)CGoS-TLCopt≤(7/13)T2+T1T1≤(7/13)T1+T1T1=2013.
Case  2 (T1<T2). In this case, we have T1<(T1+T2)/2, which leads to Copt≥(T1+T2)/2. Then, we have
(3)CGoS-TLCopt≤(14/13)T2+2T1T1+T2.
Since ((14/13)T2+2T1)/(T1+T2) is increasing function of the variation of T1, thus, we have
(4)CGoS-TLCopt≤(14/13)T2+2T1T1+T2<(14/13)T2+2T2T2+T2=2013.
The proof is completed.Based on Lemma4, we straightforwardly have Corollary 5.Corollary 5.
(1) Ift(x1)≤(7/13)T2, then t(S1)≤(20/13)Copt; (2) if t(x2)≤(10/13)T2, then t(S2)≤(20/13)Copt.Lemma 6.
t
(
x
1
)
≤
(
7
/
13
)
T
2.Proof.
Since AlgorithmGoS-TL will only scheduled a job with gj=2 to the first machine only when t(x1j-1)+pj≤(7/13)T2, the lemma can directly be got from the Algorithm GoS-TL. The proof is completed.By using Corollary5 and Lemma 6, we can obtain the following corollary.Corollary 7.
Ift(x2)≤(10/13)T2, then CGoS-TL≤(20/13)Copt.Based on Lemma6 and Corollary 7, if we prove t(S2)≤(20/13)Copt will hold when t(x2)>(10/13)T2, then we can prove that Algorithm GoS-TL is (20/13)-competitive.Lemma 8.
If jobJj is scheduled on the second machine by Algorithm GoS-TL where t(x2j-1)+pj>(10/13)T2 and t(x2j-1)≤(7/26)T2, then t(S2)<(20/13)Copt.Proof.
Ift(x2j-1)+pj>(10/13)T2 and t(x2j-1)≤(7/13)T2, we have pj>(1/2)T2. Then we have Copt≥pj>(1/2)T2. If job Jj is scheduled on the second machine, Algorithm GoS-TL will scheduled the remaining jobs on the first machine. Thus,
(5)t(S2j)Copt≤t(S2j)pj=t(x2j-1)+pjpj.
Since (t(x2j-1)+pj)/pj is decreasing function of the variation of pj and increasing function of variation of t(x2j-1), we have
(6)t(S2j)Copt≤t(x2j-1)+pjpj<(7/26)T2+(1/2)T2(1/2)T2=2013.
The proof is completed.Lemma 9.
If(6/13)T2≤t(x2j-1)≤(10/13)T2, then t(S2)>(10/13)T2 will never happen.Proof.
If(6/13)T2≤t(x2j-1)≤(10/13)T2, Algorithm GoS-TL will scheduled the remaining jobs on the first machine, so t(S2)=t(x2j-1)≤(10/13)T2. The proof is completed.Lemma 10.
If jobJj is scheduled on the second machine by Algorithm GoS-TL where (7/26)T2<t(x2j-1)<(6/13)T2 and t(x2j)>(10/13)T2, then t(S2)=t(x2j)<(20/13)Copt.Proof.
LetJw be the job that is scheduled on the second machine by Algorithm GoS-TL which satisfies t(x2w-1)≤7/13 and (7/26)T2<t(x2w-1)+pw<(6/13)T2. Since Jw is scheduled on the second machine by Algorithm GoS-TL and (7/26)T2<t(x2w-1)+pw<(6/13)T2, we have t(x1w-1)+pw>(7/13)T2; otherwise, Algorithm GoS-TL will scheduled job Jw on the first machine. Moreover, t(x1w-1)<(3/13)T2 must hold which leads to pw>(4/13)T2. This further implies that t(x2w-1)<(2/13)T2 since t(x2w-1)+pw<(6/13)T2.
Ift(x1w-1)=0, then pw>(7/13)T2 which leads to t(x2w)>(6/13)T2; this is contradicting with the definition of job Jw. Therefore, we have t(x1w-1)>0. Based on step (2.4) of Algorithm GoS-TL, the processing time of the job that is assigned to x1w-1 is larger than (3/26)T2 since t(x2w-1)<(2/13)T2. Combined with t(x1w-1)<(3/13)T2, we know there is only one job in x1w-1, call it job Jv. Since job Jv, job Jw, and t(x2w-1) need to satisfy
(7)pv+pw>713T2,pv+t(x2w-1)>726T2,726T2<t(x2w-1)+pw<613T2,
we can get pv>(9/52)T2, which implies that t(S2)<(43/52)T2.
Since there is no job withgj=2 that will scheduled on the first machine between job Jv and Jj by Algorithm GoS-TL, combined with job Jj being scheduled on the second machine, we have pv+pj>(7/13)T2. Since pj>(4/13)T2, pv, pw, and pj must satisfy
(8)pv+pw>713T2,pv+pj>713T2,pw+pj≥913T2,
which implies that Copt>(7/13)T2, hence,
(9)t(S2)Copt<(43/52)T2(7/13)T2=2013.
The proof is completed.Based on Lemma4 to Lemma 10 and Corollary 5 to Corollary 7, we have the following theorem naturally.Theorem 11.
The competitive ratio of AlgorithmGoS-TL is 20/13 for P2·GoS∣sum·lower∣Cmax⁡.


## 4.1. Lower Bound of Competitive Ratio

Theorem 3.
Any semi-online algorithm forP2·GoS∣sum·lower∣Cmax⁡ has a competitive ratio of at least 20/13.Proof.
We will construct a job sequence withT2=26 to make an arbitrary algorithm A behave poorly. We begin with jobs J1=(1,2) and J2=(1,2). We discuss the following three cases.
Case  1 (J1 and J2 are scheduled on the first machine). We continue to generate jobs J3=(12,2) and J4=(12,2). If job J3 and job J4 are scheduled on the second machine, we have t(S2)=24; thus, CA/Copt=24/14>20/13. Otherwise, if job J3 or job J4 is scheduled on the first machine or both of them are scheduled on the first machine, we further generate job J5=(26,1). We will have t(S1)≥40. Since optimal algorithm will scheduled jobs J1, J2, J3, and J4 on the second machine and scheduled job J5 on the first machine, we have CA/Copt≥20/13.
Case
2 (J1 or J2 is scheduled on the first machine). We continue to generate job J3=(2,2). Then we discuss the following two subcases.
Subcase  2.1 (job J3 is scheduled on the first machine). We continue to generate jobs J4=(11,2) and J5=(11,2). If job J4 and job J5 are scheduled on the second machine, we have t(S2)=23 and t(S1)=2, which lead to CA/Copt=23/13>20/13. Otherwise, if job J4 or job J5 is scheduled on the first machine or both of them are scheduled on the first machine, we further generate job J6=(26,1) which leads to CA/Copt≥20/13.
Subcase  2.2 (J3 is scheduled on the second machine). We generate job J4=(5,2). If job J4 is scheduled on the second machine, we generate job J5=(13,2). If job J5 is scheduled on the second machine, we have t(S2)=21. Since the optimal algorithm will scheduled jobs J1, J2, J3, and J4 on the first machine and scheduled job J5 on the second machine, we have CA/Copt=21/13>20/13. If job J5 is scheduled on the first machine, we generate job J6=(26,1) which leads to CA/Copt≥20/13.
Otherwise, if jobJ4 is scheduled on the first machine, we generate job J5=(8,2). If job J5 is scheduled on the first machine, we generate job J6=(26,1) which leads to CA/Copt≥20/13. If job J5 is scheduled on the second machine, we generate job J6=(9,2). If job J6 is scheduled on the second machine, we have t(S2)=20 and Copt=13; thus, CA/Copt=20/13. If J6 is scheduled on the first machine, we generate job J7=(26,1) and have t(S1)=40 and Copt=26, which also lead to CA/Copt=20/13.
Case  3 (J1 and J2 are scheduled on the second machine). We continue to generate job J3=(2,2). Then we discuss the following two subcases.
Subcase  3.1 (job J3 is scheduled on the second machine). We generate jobs J4=(3,2) and J5=(3,2). If job J4 or job J5 is scheduled on the second machine or both of them are scheduled on the second machine, we further generate job J6=(1,2). If job J6 is scheduled on the second machine, we generate job J7=(14,2). If job J7 is scheduled on the second machine, we have t(S2)=22. Since the optimal algorithm will scheduled jobs J1, J2, J3, J4, J5, and J6 on the first machine and scheduled job J7 on the second machine, we have CA/Copt≥22/14>20/13. Otherwise, job J7 is scheduled on the first machine, and then we generate job J8=(26,1) and have t(S1)≥40 and Copt=26; hence, CA/Copt>20/13. If job J6 is scheduled on the first machine, we generate job J7=(13,2). If job J7 is scheduled on the second machine, we have t(S2)≥20 and Copt=13, hence, we also have CA/Copt>20/13. Otherwise, job J7 is scheduled on the first machine, and then we generate job J8=(26,1). We have CA/Copt>20/13.
If jobJ4 and job J5 are scheduled on the first machine, we generate jobs J6=(8,2) and J7=(8,2). If job J6 or job J7 is scheduled on the first machine or both of them are scheduled on the first machine, we further generate job J8=(26,1). We have CA/Copt>20/13. Otherwise, if job J6 and job J7 are scheduled on the second machine, we have t(S2)=20 and Copt=13, which lead to CA/Copt=20/13.
Subcase  3.2 (job J3 is scheduled on the first machine). We generate job J4=(2,2). If job J4 is scheduled on the first machine, we generate jobs J5=(10,2) and J6=(10,2). If job J5 and job J6 are scheduled on the second machine, we have t(S2)=22 and Copt=13; thus, CA/Copt=22/13>20/13. Otherwise, if job J5 or job J6 is scheduled on the first machine or both of them are scheduled on the first machine, we further generate job J7=(26,1) and have t(S1)≥40; thus, CA/Copt=20/13.
Otherwise, if jobJ4 is scheduled on the second machine, we generate job J5=(4,2). If job J5 is scheduled on the second machine, we generate job J6=(13,2). If job J6 is scheduled on the second machine, we have t(S2)=21 and Copt=13; hence, CA/Copt=20/13. If job J6 is scheduled on the first machine, we generate job J7=(26,1) and have t(S1)≥41; thus, CA/Copt=41/26>20/13.
Therefore, jobJ5 is scheduled on the first machine. Then we generate jobs J6=(8,2) and J7=(8,2). If job J6 or job J7 is scheduled on the first machine or both of them are scheduled on the first machine, we further generate job J8=(26,1). We will have t(S1)≥40 and Copt=26; hence, CA/Copt>20/13. Otherwise, if job J6 and job J7 are scheduled on the second machine, we have t(S2)=20 and Copt=13; also, we have CA/Copt=20/13. The proof is completed.


## 4.2.  Optimal Semi-Online AlgorithmGoS-TL

In this subsection, we design an optimal algorithm with a competitive ratio of20/13. Let x1 and x2 be the jobs with gj=2 assigned to the first and second machine, respectively, where t(x1)+t(x2)=T2. We define x1j and x2j to be x1 and x2 after we scheduled job Jj. Then, we propose Algorithm GoS-TL.Algorithm  GoS-TL
(1)
Suppose that the incoming job isJj and gj=1; assign job Jj to the first machine.
(2)
Suppose that the incoming job isJj and gj=2.
(2.1)
(Stopping criterion 1). If (3/13)T2≤t(x1j-1)+pj≤(7/13)T2, scheduled job Jj and all the remaining jobs with GoS=1 to the first machine, and then scheduled all the remaining jobs with GoS=2 to the second machine. Stop.
(2.2)
(Stopping criterion 2). If (6/13)T2≤t(x2j-1)+pj≤(10/13)T2, scheduled job Jj to the second machine and scheduled all the remaining jobs to the first machine. Stop.
(2.3)
(Stopping criterion 3). If t(x2j-1)>10/13, scheduled job Jj and the remaining jobs to the first machine. Stop.
(2.4)
Ift(x2j-1)≤(7/26)T2 and (7/13)T2≤t(x2j-1)+pj<(6/13)T2, scheduled job Jj to the first machine. Continue.
(2.5)
Otherwise, scheduled jobJj to the second machine. Continue.Lemma 4.
If(6/13)T2≤t(x2)≤(10/13)T2, then CGoS-TL≤(20/13)Copt.Proof.
SinceCopt≥(1/2)T2, we have t(S2)=t(x2)≤(10/13)T2≤(20/13)Copt. Then, we only need to prove that t(S1)≤(20/13)Copt. We discuss it by the following two cases.
Case  1 (T1≥T2). In this case, we have t(S1)=t(x1)+T1 and T1≥(T1+T2)/2. Since (6/13)T2≤t(x2)≤(10/13)T2, we have t(x1)≤(7/13)T2. Combined with Copt≥T1, we have
(2)CGoS-TLCopt≤(7/13)T2+T1T1≤(7/13)T1+T1T1=2013.
Case  2 (T1<T2). In this case, we have T1<(T1+T2)/2, which leads to Copt≥(T1+T2)/2. Then, we have
(3)CGoS-TLCopt≤(14/13)T2+2T1T1+T2.
Since ((14/13)T2+2T1)/(T1+T2) is increasing function of the variation of T1, thus, we have
(4)CGoS-TLCopt≤(14/13)T2+2T1T1+T2<(14/13)T2+2T2T2+T2=2013.
The proof is completed.Based on Lemma4, we straightforwardly have Corollary 5.Corollary 5.
(1) Ift(x1)≤(7/13)T2, then t(S1)≤(20/13)Copt; (2) if t(x2)≤(10/13)T2, then t(S2)≤(20/13)Copt.Lemma 6.
t
(
x
1
)
≤
(
7
/
13
)
T
2.Proof.
Since AlgorithmGoS-TL will only scheduled a job with gj=2 to the first machine only when t(x1j-1)+pj≤(7/13)T2, the lemma can directly be got from the Algorithm GoS-TL. The proof is completed.By using Corollary5 and Lemma 6, we can obtain the following corollary.Corollary 7.
Ift(x2)≤(10/13)T2, then CGoS-TL≤(20/13)Copt.Based on Lemma6 and Corollary 7, if we prove t(S2)≤(20/13)Copt will hold when t(x2)>(10/13)T2, then we can prove that Algorithm GoS-TL is (20/13)-competitive.Lemma 8.
If jobJj is scheduled on the second machine by Algorithm GoS-TL where t(x2j-1)+pj>(10/13)T2 and t(x2j-1)≤(7/26)T2, then t(S2)<(20/13)Copt.Proof.
Ift(x2j-1)+pj>(10/13)T2 and t(x2j-1)≤(7/13)T2, we have pj>(1/2)T2. Then we have Copt≥pj>(1/2)T2. If job Jj is scheduled on the second machine, Algorithm GoS-TL will scheduled the remaining jobs on the first machine. Thus,
(5)t(S2j)Copt≤t(S2j)pj=t(x2j-1)+pjpj.
Since (t(x2j-1)+pj)/pj is decreasing function of the variation of pj and increasing function of variation of t(x2j-1), we have
(6)t(S2j)Copt≤t(x2j-1)+pjpj<(7/26)T2+(1/2)T2(1/2)T2=2013.
The proof is completed.Lemma 9.
If(6/13)T2≤t(x2j-1)≤(10/13)T2, then t(S2)>(10/13)T2 will never happen.Proof.
If(6/13)T2≤t(x2j-1)≤(10/13)T2, Algorithm GoS-TL will scheduled the remaining jobs on the first machine, so t(S2)=t(x2j-1)≤(10/13)T2. The proof is completed.Lemma 10.
If jobJj is scheduled on the second machine by Algorithm GoS-TL where (7/26)T2<t(x2j-1)<(6/13)T2 and t(x2j)>(10/13)T2, then t(S2)=t(x2j)<(20/13)Copt.Proof.
LetJw be the job that is scheduled on the second machine by Algorithm GoS-TL which satisfies t(x2w-1)≤7/13 and (7/26)T2<t(x2w-1)+pw<(6/13)T2. Since Jw is scheduled on the second machine by Algorithm GoS-TL and (7/26)T2<t(x2w-1)+pw<(6/13)T2, we have t(x1w-1)+pw>(7/13)T2; otherwise, Algorithm GoS-TL will scheduled job Jw on the first machine. Moreover, t(x1w-1)<(3/13)T2 must hold which leads to pw>(4/13)T2. This further implies that t(x2w-1)<(2/13)T2 since t(x2w-1)+pw<(6/13)T2.
Ift(x1w-1)=0, then pw>(7/13)T2 which leads to t(x2w)>(6/13)T2; this is contradicting with the definition of job Jw. Therefore, we have t(x1w-1)>0. Based on step (2.4) of Algorithm GoS-TL, the processing time of the job that is assigned to x1w-1 is larger than (3/26)T2 since t(x2w-1)<(2/13)T2. Combined with t(x1w-1)<(3/13)T2, we know there is only one job in x1w-1, call it job Jv. Since job Jv, job Jw, and t(x2w-1) need to satisfy
(7)pv+pw>713T2,pv+t(x2w-1)>726T2,726T2<t(x2w-1)+pw<613T2,
we can get pv>(9/52)T2, which implies that t(S2)<(43/52)T2.
Since there is no job withgj=2 that will scheduled on the first machine between job Jv and Jj by Algorithm GoS-TL, combined with job Jj being scheduled on the second machine, we have pv+pj>(7/13)T2. Since pj>(4/13)T2, pv, pw, and pj must satisfy
(8)pv+pw>713T2,pv+pj>713T2,pw+pj≥913T2,
which implies that Copt>(7/13)T2, hence,
(9)t(S2)Copt<(43/52)T2(7/13)T2=2013.
The proof is completed.Based on Lemma4 to Lemma 10 and Corollary 5 to Corollary 7, we have the following theorem naturally.Theorem 11.
The competitive ratio of AlgorithmGoS-TL is 20/13 for P2·GoS∣sum·lower∣Cmax⁡.


## 5. Optimal Algorithm forP2·GoS∣sum·high&sum·lower∣Cmax

In this section, we show a lower bound of competitive ratio and present an optimal algorithm for the semi-online version asT1 and T2 are known in advance.


### 5.1. Lower Bound of Competitive Ratio

Theorem 12.
Any semi-online algorithm forP2·GoS∣sum·high&sum·lower∣Cmax⁡ has a competitive ratio of at least 4/3.Proof.
The theorem will be proved by adversary method. LetT1=1/3 and T2=5/3 be known in advance. The first job is J1=(1/3,1). Job J1 must be scheduled on the first machine. Then job J2=(1/3,2) arrives. If job J2 is scheduled on the second machine, we further generate jobs J3=(1,2) and J4=(1/3,2). In this situation, we have CA≥4/3 and Copt=1 since the optimal algorithm will scheduled jobs J1, J2, and J4 on the first machine and scheduled job J3 on the second machine. Thus, we have CA/Copt≥4/3. Otherwise, if job J2 is scheduled on the first machine, then we further generate jobs J3=(2/3,2) and J4=(2/3,2). In this situation, we also have CA≥4/3 and Copt=1 since the optimal algorithm will scheduled jobs J1 and J3 on the first machine and scheduled jobs J2 and J3 on the second machine. The proof is completed.


### 5.2.  Optimal Semi-Online AlgorithmGoS-TB

In this subsection, we design an optimal algorithm with a competitive ratio of4/3. Since we know T1 in advance and all the jobs with gj=1 must be scheduled on the first machine, therefore, we can regard them as one job, that is, J0=(T1,1). We scheduled job J0 on the first machine at first and do not need to care about the job with gj=1 later. We present Algorithm GoS-TB as follows.Algorithm GoS-TB
(1)
ScheduledJ0 to the first machine and t(S10)=T1.
(2)
Letpj=0 for all the jobs with gj=1.
(3)
Suppose that the incoming job isJj and gj=1; assign job Jj to the first machine.
(4)
Suppose that the incoming job isJj and gj=2.
(4.1)
Ift(S1)+pj≤(2/3)(T1+T2), scheduled it to the first machine.
(4.2)
(Stopping criterion). Suppose t(S1)+pj>(2/3)(T1+T2).
(4.2.1)
Ift(S1j-1)>(1/3)(T1+T2), scheduled job Jj and the remaining jobs with GoS=2 on the second machine and scheduled the remaining jobs with GoS=1 to the first machine. Stop.
(4.2.2)
Ift(S1j-1)≤(1/3)(T1+T2), scheduled job Jj to the second machine, and scheduled the remaining jobs to the first machine. Stop.Theorem 13.
The competitive ratio of AlgorithmGoS-TH is 4/3 for P2·GoS∣sum·high&sum·lower∣Cmax⁡.Proof.
Since the job withgj=1 is scheduled at first and we do not need to care about them after that. We focus on the jobs with gj=2.
Assume jobJj is the first job with gj=2 to make t(S1)+pj>(2/3)(T1+T2). We prove it by the following two cases.
Case  1 (t(S1j-1)>(1/3)(T1+T2)). In this case, Algorithm GoS-TB schedules job Jj and the remaining jobs with GoS=2 on the second machine. Therefore, t(S1)≤(2/3)(T1+T2) and t(S2)≤T1+T2-t(S1)<(2/3)(T1+T2). Since Copt≥(1/2)(T1+T2), we have CGoS-TH=max⁡{t(S1),t(S2)}≤(2/3)(T1+T2)≤(4/3)Copt.
Case  2 (t(S1j-1)≤(1/3)(T1+T2)). In this case, we have pj>(1/3)(T1+T2). Algorithm GoS-TH will only scheduled job Jj on the second machine and scheduled the remaining jobs on the first machine. If pj≥(1/2)(T1+T2), we have Copt=pj and t(S1)≤pj=t(S2). Therefore, CGoS-TH=Copt. Otherwise, (1/3)(T1+T2)<pj<(1/2)(T1+T2), which leads to t(S1)≤T1+T2-t(S2)<(2/3)(T1+T2). Hence, we have CGoS-TH=max⁡{t(S1),t(S2)}≤(2/3)(T1+T2)≤(4/3)Copt. The proof is completed.


## 5.1. Lower Bound of Competitive Ratio

Theorem 12.
Any semi-online algorithm forP2·GoS∣sum·high&sum·lower∣Cmax⁡ has a competitive ratio of at least 4/3.Proof.
The theorem will be proved by adversary method. LetT1=1/3 and T2=5/3 be known in advance. The first job is J1=(1/3,1). Job J1 must be scheduled on the first machine. Then job J2=(1/3,2) arrives. If job J2 is scheduled on the second machine, we further generate jobs J3=(1,2) and J4=(1/3,2). In this situation, we have CA≥4/3 and Copt=1 since the optimal algorithm will scheduled jobs J1, J2, and J4 on the first machine and scheduled job J3 on the second machine. Thus, we have CA/Copt≥4/3. Otherwise, if job J2 is scheduled on the first machine, then we further generate jobs J3=(2/3,2) and J4=(2/3,2). In this situation, we also have CA≥4/3 and Copt=1 since the optimal algorithm will scheduled jobs J1 and J3 on the first machine and scheduled jobs J2 and J3 on the second machine. The proof is completed.


## 5.2.  Optimal Semi-Online AlgorithmGoS-TB

In this subsection, we design an optimal algorithm with a competitive ratio of4/3. Since we know T1 in advance and all the jobs with gj=1 must be scheduled on the first machine, therefore, we can regard them as one job, that is, J0=(T1,1). We scheduled job J0 on the first machine at first and do not need to care about the job with gj=1 later. We present Algorithm GoS-TB as follows.Algorithm GoS-TB
(1)
ScheduledJ0 to the first machine and t(S10)=T1.
(2)
Letpj=0 for all the jobs with gj=1.
(3)
Suppose that the incoming job isJj and gj=1; assign job Jj to the first machine.
(4)
Suppose that the incoming job isJj and gj=2.
(4.1)
Ift(S1)+pj≤(2/3)(T1+T2), scheduled it to the first machine.
(4.2)
(Stopping criterion). Suppose t(S1)+pj>(2/3)(T1+T2).
(4.2.1)
Ift(S1j-1)>(1/3)(T1+T2), scheduled job Jj and the remaining jobs with GoS=2 on the second machine and scheduled the remaining jobs with GoS=1 to the first machine. Stop.
(4.2.2)
Ift(S1j-1)≤(1/3)(T1+T2), scheduled job Jj to the second machine, and scheduled the remaining jobs to the first machine. Stop.Theorem 13.
The competitive ratio of AlgorithmGoS-TH is 4/3 for P2·GoS∣sum·high&sum·lower∣Cmax⁡.Proof.
Since the job withgj=1 is scheduled at first and we do not need to care about them after that. We focus on the jobs with gj=2.
Assume jobJj is the first job with gj=2 to make t(S1)+pj>(2/3)(T1+T2). We prove it by the following two cases.
Case  1 (t(S1j-1)>(1/3)(T1+T2)). In this case, Algorithm GoS-TB schedules job Jj and the remaining jobs with GoS=2 on the second machine. Therefore, t(S1)≤(2/3)(T1+T2) and t(S2)≤T1+T2-t(S1)<(2/3)(T1+T2). Since Copt≥(1/2)(T1+T2), we have CGoS-TH=max⁡{t(S1),t(S2)}≤(2/3)(T1+T2)≤(4/3)Copt.
Case  2 (t(S1j-1)≤(1/3)(T1+T2)). In this case, we have pj>(1/3)(T1+T2). Algorithm GoS-TH will only scheduled job Jj on the second machine and scheduled the remaining jobs on the first machine. If pj≥(1/2)(T1+T2), we have Copt=pj and t(S1)≤pj=t(S2). Therefore, CGoS-TH=Copt. Otherwise, (1/3)(T1+T2)<pj<(1/2)(T1+T2), which leads to t(S1)≤T1+T2-t(S2)<(2/3)(T1+T2). Hence, we have CGoS-TH=max⁡{t(S1),t(S2)}≤(2/3)(T1+T2)≤(4/3)Copt. The proof is completed.



---

*Source: 576234-2014-02-11.xml*