Online Scheduling on Two Parallel Identical Machines Under a Grade of Service Provision

Abstract

In this paper, we investigate online scheduling problems on two parallel identical machines under a grade of service provision with makespan as the objective function. The jobs arrive over time and each job can be scheduled only when it has already been arrived. We consider three different versions: (i) the two machines cannot be idle at the same time until all arrived jobs have been processed; (ii) further to the first problem, jobs are processed on a first-come, first-serviced basis; (iii) each job must be assigned to one of the two machines as soon as it arrives. Respectively for three online scheduling problems, optimal online algorithms are proposed with competitive ratio $(\sqrt 5 + 1)/2$, $(\sqrt 5 + 1)/2$ and $5/3$.

1 Introduction

Enterprise competition is becoming more and more fierce; lots of papers have studied the supply chain management [1]. Meanwhile, production and manufacturing become most important and complex. Parallel machine scheduling is one of the most common scheduling problems, which has been studied widely since 50 years ago [2]. Quite rich studies have been published for the offline scheduling problem on parallel machines, but rather few researches for the online scheduling problems. For the sake of simplicity, we use the 3-field notation of Graham et al. [3]. To evaluate the performance of an online algorithm, researchers use the competitive ratio of this algorithm, which is obtained by makespan of the online schedule divided by the minimum makespan of the schedule generated by the offline version of the problem, e.g. $c^{A} = \max_{I} (C_{I}^{A} /C_{I}^{*} )$, where $c^{A}$, $C_{I}^{A}$ and $C_{I}^{*}$ namely the competitive ratio of algorithm $A$, the makespan by algorithm $A$ and the optimal makespan for instance $I$ [2, 4,5,6,7,8,9,10,11].

Machine eligibility constraints are very common in the parallel machine scheduling and it is a common practice in any service industry to provide differentiated services to the customers based on their entitle privileges, i.e., jobs are assigned according to their grade of services (GoS) levels [4]. GoS means that customers with a higher level will receive better services by assigning a customer (job) to a server only when the GoS of the customer is no less than the GoS of the server. A few researches have been published for online and semi-online scheduling (see “Appendix A”) on parallel machines under a grade of service provision. Lee et al. [2] provided a survey of online scheduling in parallel machine environments with machine eligibility constraints and the makespan as objective function.

When dealing with online scheduling problems on parallel machines, there are two basic online scheduling paradigms, namely online over list and online over time. For the version of online over list, lots of papers have been published [4,5,6,7,8,9,10,11]. Both Park et al. [4] and Jiang et al. [5] gave optimal algorithms with competitive ratio 5/3 and 3/2 for the online ($P2\left| {{\text{online}},M_{j} ({\text{GoS}})\left| {C_{\hbox{max} } } \right.} \right.$) and semi-online (for explanation, see “Appendix B”) problems. Wu et al. [6] proposed two optimal algorithms for two different semi-online versions on two machines: The optimal offline value of the instance is known in advance or the largest processing time of all jobs is known in advance. Lu and Liu [12] studied the semi-online scheduling on two uniform machines under a GoS provision. The authors proposed optimal algorithms for three variants, where the optimal makespan, the total size of jobs, and the largest job size are known in advance, respectively.

A great amount of work has been done for the version of online over list, but very few researches have been published for the second version, despite the fact that it is more common and more realistic in our lives. For the online scheduling problem on parallel machines $Pm\left| {{\text{online}},r_{j} } \right.\left| {C_{\hbox{max} } } \right.$, Chen and Vestjens [13] proved that the algorithm of LPT has 3/2-competitive performance and the best ratio is 1.347; and Noga and Seiden [14] proposed an optimal algorithm for the two machine scheduling problem $P2\left| {{\text{online}},r_{j} } \right.\left| {C_{\hbox{max} } } \right.$ with competitive ratio 1.382. When preemption is allowed, Hong and Leung [15] provided an optimal algorithm for the problem $P2\left| {{\text{online}},r_{j} } \right.,pmtn\left| {C_{\hbox{max} } } \right.$ with a competitive ratio of 1. Lee et al. [16] proposed optimal algorithms for two problems concerning online scheduling of equal-length jobs on two machines subject to arbitrary eligibility constraints and GoS eligibility constraints, i.e., $P2\left| {{\text{online}},r_{j} } \right.,M_{j} ,p_{j} = p\left| {C_{\hbox{max} } } \right.$ and $P2\left| {{\text{online}},r_{j} } \right.,M_{j} ({\text{GoS}}),p_{j} = p\left| {C_{\hbox{max} } } \right.$. Xu et al. [17] proposed an optimal algorithm for the online scheduling problem $P2\left| {r_{j} } \right.,M_{j} ({\text{GoS}}),{\text{online}}\left| {C_{\hbox{max} } } \right.$ with competitive ratio 1.555 0. Li and Zhang [18] considered two scheduling problems $Q2\left| {r_{j} } \right.,{\text{online}}\left| {C_{\hbox{max} } } \right.$ and $Pm\left| {r_{j} } \right.,{\text{online}}\left| {C_{\hbox{max} } } \right.$ and proposed better algorithms for each of them. There are also some papers for parallel-batch machines scheduling. Recently, Yuan et al. [19] studied online scheduling on two uniform parallel-batch machines to minimize makespan. Cai and Liu [20] proposed heuristic algorithms for parallel machine scheduling problem $Pm\left| {r_{j} } \right.,{\text{online}},M_{j} ({\text{GoS}})\left| {C_{\hbox{max} } } \right.$.

In this paper, we consider three different versions for the online scheduling problem on two parallel identical machines under a grade of service provision (online over time), which have never been studied before. The first one is that we require the two machines cannot be idle at the same time until all arrived jobs have already completed. This constraint is more reasonable for real lives, e.g., the banks and the barber shop. It is because customer experience comes first and the persons with higher grade probably do not have a better experience than the ones with lower grade. Another important reason is that the average competitive ratio is usually lower. At the same time it usually adds the total completion time (the sum of two machines’ completion times) when we let some customer wait while the two servers are both idle. The second problem is that we must assign jobs with the same GoS (1 or 2) to the two machines according to their arriving times, i.e., job $i$ will be processed earlier than job $j$ when job $i$ arrives earlier and they have the same GoS, which is more equitable as it satisfies the method of FCFS (first-come-first-service). The third problem is that we must assign a job to its available machine as soon as it arrives. Respectively for the three problems, we propose algorithms which are proved to have optimal competitive ratios.

The rest of this paper is organized as follows: in Sect. 2, we give a detailed description of the first problem; then the best possible performance of any online algorithm is analyzed at the last of this section; we propose an online algorithm and it is proved with the best competitive ratio. In Sect. 3 (Sect. 4), the second (third) problem is studied with the same structure as Sect. 2. Finally, we give the conclusions and future research in Sect. 5.

2 Optimal Algorithm for the First Problem

In this section, firstly we describe the first problem; then, the lower bound of this problem is analyzed; at last, we propose an online algorithm, which is proved to be optimal.

2.1 Problem Description

The considered online scheduling problem can be described as: there are $n$ different jobs $J_{i}$ $(i = 1, \cdots ,n)$, which have to be processed on one of the two parallel machines $M_{i}$ $(i = 1,2)$ without preemption. The GoS of machine $M_{i}$ is $i$. Jobs are arrived over time with GoS (1 or 2). The two machines can be idle at the same time only when all the jobs arrived are completed.

The GoS of Job $J_{i}$ is denoted as $g_{i}$, which is 1 if the job must be processed on the first machine $M_{1}$ or 2 if the job can be processed on both the two machines. The processing (arriving) time of job $J_{i}$ is $p_{i} \,(r_{i} )$. The constraint that the two machines can be idle at the same time only when all the jobs arrived are completed is denoted as no-delay1. The maximum complete time (makespan) is denoted as $C_{\hbox{max} }$. Then, the considered problem in this paper can be described as $P2\left| {{\text{online}},\;r_{i} } \right.,\;M({\text{GoS}}),\; {\text{no-delay1}}\left| {C_{\hbox{max} } } \right.$. A job which is to be processed can be denoted by $(J,\;r,\;p,\;g)$. For example, (4, 3, 7, 1) represents that it is job $J_{4}$ with $r_{4} = 3,\;p_{4} = 7,\;g_{4} = 1.$

To get the minimum makespan, we need to decide the assignment of each job after it arrives. The schedule can be seen as the partition of $J$ into two sets, denoted by $S_{1}$ and $S_{2}$, where $S_{1}$ and $S_{2}$ contain jobs indices assigned to machine $M_{1}$ and $M_{2}$ respectively.

2.2 The Lower Bound of the First Problem

In this subsection, we give the lower bound of any online algorithm for the problem.

Theorem 1

Any online algorithm for the first problem has a competitive ratio at least $(\sqrt 5 + 1)/2$.

Proof

Note that $\lambda = (\sqrt 5 - 1)/2$, $C^{*}$ represents the optimal solution and $C^{A}$ represents the solution of an online algorithm. At time $t = 0$, we generate $J_{1}$ arrives with $p_{1} = 1$ and $g_{1} = 2$. If job $J_{1}$ is assigned to the first machine, we generate $J_{2}$ with $p_{2} = 1$, $r_{2} = \varepsilon$($\varepsilon$ sufficiently small) and $g_{2} = 1$, then the competitive ratio $C^{A} /C^{*} \approx 2/1 = 2$. If $J_{1}$ be assigned to machine $M_{2}$, we generate $J_{3}$ with $p_{3} = 1 + \lambda$, $r_{3} = \varepsilon$ and $g_{3} = 2$, the competitive ratio $C^{A} /C^{*} = (1 + \lambda )/1 = 1 + \lambda$ if job $J_{3}$ is assigned to machine $M_{2}$; if $J_{3}$ is assigned to machine $M_{1}$ at time a(a < 1), we generate $J_{4}$ with $p_{4} = 1 + \lambda - a$, $r_{4} = a + \varepsilon$ and $g_{4} = 1$, the competitive ratio $C^{A} /C^{*} \approx (2 + \lambda )/(1 + \lambda ) = 1 + \lambda$. Above all, we can conclude that the lower bound is at least $1 + \lambda = (\sqrt 5 + 1)/2$.

2.3 An Online Algorithm of the Problem

Here, we show an online algorithm which is proved to have the optimal performance. In order to describe the algorithm (or for the algorithm Alg_P2 and Alg_P3) clearly, we make some parameters in Table 1, which will be used later.

Table 1 Parameters used in the proposed algorithm

First we give the update algorithm UA_P1 for decision moment. Here $C_{i}$ is the time machine $M_{i}$ become idle. Then, the online algorithm Alg_P1 is proposed based on UA_P1.

Algorithm UA_P1

• Step 1 Let $t$ be the current decision time, $C_{i}$ be the time machine $M_{i}$ become idle after the decision at time $t$, $A_{1} (t),A_{2} (t)$ be updated after the decision at time $t$($A_{1} (t)$ must be empty after updated).

• Step 2 If $A_{2} (t) = \varnothing$ and at least one of the two machines is idle, the decision moment is the arriving time of the next job (if all jobs have arrived, stop the algorithm);

• Step 3 Else if both $A_{1} (t)$ and $A_{2} (t)$ do not decrease after the decision at time t, the decision moment is the smaller one of the arriving time of the next job and $C_{2}$ (if all jobs have arrived, stop the algorithm).

• Step 4 Else the decision moment is the smaller time of time $\hbox{min} (C_{1} ,\;C_{2} )$ and the arriving time of the next job.

Algorithm Alg_P1

• Step 1 Set the arriving time of the first job is zero, $t: = 0$, $A_{1} (t): = \varnothing$, $A_{2} (t): = \varnothing$, $J_{l}^{t} : = \varnothing$, $S(t): = 0$.

• Step 2 Update $A_{1} (t)$, $A_{2} (t)$, $t$ and $S(t)$ in turn. Then update $A_{1} (t)$, $A_{2} (t)$ again when there are new jobs arriving.

• Step 3 If the two machines are both busy at time t and $A_{1} (t) = \varnothing$, go to Step 2. Else if $A_{1} (t) \cup A_{2} (t) = \varnothing$ and there exist jobs arriving after $t$, go to Step 2; once all the jobs are scheduled, end the algorithm.

• Step 4 Else if $A_{1} (t) \ne \varnothing$, let all jobs of $A_{1} (t)$ be assigned to machine $M_{1}$, go to Step 2.

• Step 5 Else if $A_{2} (t) \ne \varnothing$ and machine $M_{2}$ is idle, let the first job of $A_{2} (t)$ be assigned to machine $M_{2}$, go to Step 2.

• Step 6 Else if $A_{1} (t) = \varnothing$ and machine $M_{1}$ is idle:

  • 6.1. If $\left| {A_{2} (t)} \right| \geqslant 2$, let the second job of $A_{2} (t)$ be assigned to machine $M_{1}$.

  • 6.2. Else $\left| {A_{2} (t)} \right| = 1$, assign job $J_{l}^{t}$ to machine $M_{1}$ if $p_{l}^{t} /(L_{2,t} - S(t)) \leqslant (1 + \sqrt 5 )/2$. Go to Step 2.

2.4 Competitive Ratio of the Proposed Algorithm

Firstly, when an instance is scheduled by the proposed algorithm and the two machines are both idle at a time interval [a, b], then we only need to consider the jobs arriving after time b by the following lemma.

Lemma 1

For the proposed algorithm, if a jobs arrives at time $t$ and all the jobs arrive before time $t$ have been completed before $t$, then this algorithm has the optimal solution if it has the best scheduling decision for jobs arriving after time $t$ (including time $t$).

Proof

For any optimal schedule of any instance, as a job arrives at time $t$ and all other jobs arriving before time $t$ are completed before time $t$, it is obviously that the two machines are idle at time $t$ and the jobs arriving after time $t$ cannot be processed before time $t$ by the optimal algorithm.

We supposed that the two machines cannot be idle at the same time interval in the following analysis. Then, we give a lemma which shows that the total remaining processing time of jobs with GoS 1 and the remaining processing time of each job with GoS 2 are not too big. According to Lemma 1, we just need to prove the case that the two machines cannot be idle at the same time until all jobs are finished (Fig. 1).

Fig. 1

Illustration for Lemma 2

Lemma 2

For any instance ${\text{I}}$, the sum of total remaining processing time of unprocessed jobs with GoS 1 and the remaining processing time of the processing job on machine$M_{1}$ at time $C^{*}$ is no more than $\lambda C^{*}$ at time $C^{*}$; the remaining processing time of each job with GoS 2 at time $C^{*}$ is no more than $\lambda C^{*}$ at time $C^{*}$. Here $\lambda = (\sqrt 5 - 1)/2$.

Proof

Without loss of generality, let $C^{*} = 1$. As the optimal offline algorithm has makespan 1, we denote the processing job on machine $M_{1}$ and the unprocessed jobs with GoS 1 is $J_{i}$($i = 1,2, \cdots ,s$), the total remaining processing time of these jobs is $p_{1}^{\prime } + \sum\nolimits_{i = 2}^{s} {p_{i} }$($p_{1}^{'}$ represents the remaining processing time of $J_{1}$). If $p_{1}^{\prime} + \sum\nolimits_{i = 2}^{s} {p_{i} } > \lambda$, then there must exist a job $J_{k}$ which is processed on machine $M_{1}$ with $g_{k} = 2$ and $p_{k} \geqslant p_{1}^{\prime} + \sum\nolimits_{i = 2}^{s} {p_{i} } > \lambda$. If the starting time of $J_{k}$ is $t$, there must exist time $t_{0}$ that the two machines are both busy at time interval [$t_{0} ,\;t_{0} + 1 - \lambda$] according to Step 6 of the algorithm. The total processing time of two machines is more than $1 - \lambda + 1 + \lambda = 2$, which contradicts the fact that makespan is 1.

For the remaining processing job $J_{{1^{{\prime }} }}$ with GoS 2, if $J_{{1^{{\prime }} }}$ is processing on machine $M_{1}$ in time 1, its remaining processing time is no more than $\lambda$ according to the first part of proving. There are also two remaining cases:

Case 1′

$J_{{1^{{\prime }} }}$ is processing on machine $M_{2}$ at time 1.

Let the remaining processing time of $J_{{1^{{\prime }} }}$ be $x$(its total processing time is $p_{{1^{{\prime }} }}$). Suppose that $x > \lambda$. Machine $M_{2}$ must be busy in time interval [$1 - p_{{1^{{\prime }} }} ,\;1$] and machine $M_{1}$ must be busy in time interval [$1 - p_{{1^{{\prime }} }} ,\;1 - p_{{1^{{\prime }} }} + x$]. Then we have $1 + x + x \leqslant 2$, e.g. $x \leqslant 1/2$, which is contracted with the assumption.

Case 2′

$J_{{1^{{\prime }} }}$ is unprocessed at time 1.

With the same analysis with Case 1′, we can obtain $p_{{1^{{\prime }} }} \leqslant \lambda$.

Using Lemma 2, we can get the competitive ratio of the proposed algorithm.

Theorem 2

The competitive ratio of Algorithm Alg_P 1 is at most $1 + \lambda$.

Proof

Without loss of generality, let $C^{*} = 1$. There are two cases:

Case 1

$C_{1}^{A} \leqslant C_{2}^{A}$, e.g. $C^{A} = C_{2}^{A}$. If there just exists one job on machine $M_{2}$ which isn’t completed at time 1, we have $C^{A} \leqslant 1 + \lambda$ according to Lemma 2. When there are at least two jobs processed on machine $M_{2}$, let the last job be $J_{k}$ and $C_{2}^{A} > 1 + \lambda$. As $C^{*} = 1$, the arriving time of $J_{k}$ is before time $1 - p_{k}$. Machine $M_{2}$ must be busy between time $1 - p_{k}$ and time $C_{2}^{A} - p_{k}$ according to Step 5 of Algorithm Alg_P1 and machine $M_{1}$ must be busy between time $1 - p_{k}$ and time $C_{2}^{A} - p_{k}$. Then, the total processing time of two machines is at least $C_{2}^{A} + (C_{2}^{A} - 1) > 2$, which contract with the fact that $C^{*} = 1$.

Case 2

$C_{1}^{A} > C_{2}^{A}$, e.g. $C^{A} = C_{1}^{A}$. If the last job $J_{k}$ which is processed on machine $M_{1}$ has GoS 1, we have $C_{1}^{A} \leqslant 1 + \lambda$ according to Step 4 of Algorithm Alg_P1 and Lemma 2. If the GoS of $J_{k}$ is 2 and $C_{1}^{A} > 1 + \lambda$, machine $M_{2}$ must be busy between time $1 - p_{k}$ and time $C_{1}^{A} - p_{k}$ as the arriving time of $J_{k}$ is before time $1 - p_{k}$. Machine $M_{1}$ must be busy between time $1 - p_{k}$ and time $C_{1}^{A} - p_{k}$ according to Step 6. Then, the total processing time of two machines is at least $C_{1}^{A} + C_{1}^{A} - p_{k} > 2$, which contract with the fact that $C^{*} = 1$.

3 Optimal Algorithm for the Second Scheduling Problem

In this section, with the same contracture as Sect. 2, firstly we describe the second scheduling problem; then, the lower bound of this problem is analyzed; at last, we propose an online algorithm, which is proved to be optimal.

3.1 Problem Description

The considered problem can be described as: there are $n$ different jobs $J_{i}$ $(i = 1, \cdots ,n)$, which have to be processed on one of the two parallel machines $M_{i}$ $(i = 1,2)$ without preemption. The GoS of machine $M_{i}$ is $i$. Jobs are arrived over time with GoS (1 or 2). The two machines can be idle at the same time only when all the jobs arrived are completed. The jobs will be processed on a first-come-first-serviced (FCFS) basis. The notations are the same with Sect. 2.1. Then, the second problem can be described as $P2\left| {{\text{online}},\;r_{i} } \right.,\;M({\text{GoS}}),\;{\text{no-delay1, FIFS}}\left| {C_{\hbox{max} } } \right.$. To get the minimum makespan, we need to decide the assignment of each job after it arrives. As the second problem add a new requirement FCFS compared with the first one, with the same analysis as Theorem 1, we can obtain the lower bound of the second problem.

Theorem 3

Any online algorithm for the second problem has a competitive ratio of at least $(\sqrt 5 + 1)/2$.

3.2 An Online Algorithm of the Second Problem

In this subsection, an online algorithm is proposed based on the algorithm of Sect. 2.3. The notations are the same as subsection 2.3 except $A_{2} (t)$, which is defined as: The set of jobs with GoS 2 which are not processed on the two machines before time $t$, the sequence of $A_{2} (t)$ is according to the rule of ERT (earliest releasing time first).

The proposed algorithm is almost the same as the algorithm in subsection 2.3 except Step 6.

Algorithm Alg_P2

• Step 1 Set the arriving time of the first job is zero, $t: = 0$, $A_{1} (t): = \varnothing$, $A_{2} (t) = \varnothing$, $J_{l}^{t} : = \varnothing$ and $S(t): = 0$.

• Step 2 Update $A_{1} (t)$, $A_{2} (t)$, $t$ and $S(t)$ in turn. Then update $A_{1} (t)$, $A_{2} (t)$ again when there are new jobs arriving.

• Step 3 If the two machines are both busy at time t and $A_{1} (t) = \varnothing$, go to Step 2. Else if $A_{1} (t) \cup A_{2} (t) = \varnothing$ and there exist jobs arriving after $t$, go to Step 2; once all the jobs are scheduled, end the algorithm.

• Step 4 Else if $A_{1} (t) \ne \varnothing$, let all jobs of $A_{1} (t)$ be assigned to machine $M_{1}$, go to Step 2.

• Step 5 Else if $A_{2} (t) \ne \varnothing$ and machine $M_{2}$ is idle, let the first job of $A_{2} (t)$ be assigned to machine $M_{2}$, go to Step 2.

• Step 6 Else if $A_{1} (t) = \varnothing$ and machine $M_{1}$ is idle:

  • 6.1. If $p_{a}^{1} /(L_{2,t} + \sum\nolimits_{i \in I,i \ne 1} {p_{a}^{i} } - S(t)) \leqslant (\sqrt 5 + 1)/2$, assign $J_{a}^{1}$ to machine $M_{1}$. Here $p_{a}^{i}$ is the processing time of $J_{a}^{i}$ which is the $i$-th element of set $A_{2} (t)$. Go to Step 2.

3.3 Competitive Ratio of the Proposed Algorithm

It is obviously that Lemma 1 is also correct for the second problem. The following analysis supposes that the two machines won’t be both idle at the same time until all jobs are completed.

Lemma 3

If $J_{n}$ is processed on machine $M_{2}$, we have $C/C^{*} \leqslant (\sqrt 5 + 1)/2$.

Proof

Without loss of generality, let $C^{*} = 1$. Note that $\lambda = (\sqrt 5 - 1)/2$. As $J_{n}$ is the last job on machine $M_{2}$, then $S_{n} = C - p_{n}$. Suppose that $C > 1 + \lambda$, we have $r_{n} \leqslant 1 - p_{n}$ and machine $M_{2}$ must be busy between time interval $[1 - p_{n} ,C -$$p_{n} ]$. If machine $M_{1}$ is busy between time interval $[1 - p_{n} ,1 + \lambda^{2} - p_{n} ]$, then the total processing time of the two machines satisfies $\lambda^{2} + C > 2$. We let the first idle time of machine $M_{1}$ after time $(1 - p_{n} )$ is $1 - p_{n} + x$ ($0 \leqslant x < \lambda^{2}$), so $A_{1} (1 - p_{n} + x) = \varnothing$. Let the processing job at time $1 - p_{n} + x$ on machine $M_{2}$ be $J_{a}$ and the first job of $A_{2} (1 - p_{n} + x)$(after assigning job $J_{a}$)be $J_{k}$. If $S_{k} < C_{a}$, then $J_{k}$ is processed on machine $M_{1}$ and $p_{k} > (C - 1 + p_{n} )/\lambda \geqslant 1$ according to Step 6 of the proposed algorithm. Then, we can obtain that $S_{k} = C_{a}$. If $J_{n}$ and $J_{k}$ are the same job, then $p_{n} > (C - 1)/\lambda \geqslant 1$. If $J_{n}$ and $J_{k}$ are different jobs, then $p_{k} > (C - 1 + p_{n} - p_{k} )/\lambda$, i.e. $p_{k} > \lambda^{2}$. Then, we can obtain machine $M_{1}$ is busy between time interval $[S_{k} ,C_{k} ]$, so the total processing time of the two machines is more than 2. So we can conclude that $C \leqslant (1 + \lambda )C^{*}$.

Lemma 4

If $J_{n}$ is processed on machine $M_{1}$, we have $C/C^{*} \leqslant (\sqrt 5 + 1)/2$.

Proof

Without loss of generality, let $C^{*} = 1$. Note that $\lambda = (\sqrt 5 - 1)/2$. Suppose that $C > 1 + \lambda$. There are two cases:

Case 1

The GoS of $J_{n}$ is 2.

We have $C - L \leqslant p_{n}$, so machine $M_{2}$ must be busy at time interval $[1 - p_{n} ,C - p_{n} ]$. If machine $M_{1}$ is also busy at the above time interval, it can be easily obtained that the total processing time of the two machines is more than 2. We let the first idle time of machine $M_{1}$ after time ($1 - p_{n}$) be $1 - p_{n} + x$. Let the processing job on machine $M_{2}$ at time $1 - p_{n} + x$ be $J_{a}$ and the first job of $A_{2} (1 - p_{n} + x)$ (after assigning job $J_{a}$) be $J_{k}$. If $J_{n}$ and $J_{k}$ are the same job, we can obtain that $p_{n} > (C - 1)/\lambda \geqslant 1$. If $J_{n}$ and $J_{k}$ are different jobs, then $p_{k} > (C - 1 + p_{n} - p_{k} )/\lambda$, i.e. $p_{k} > \lambda^{2}$. If $J_{k}$ is processed on machine $M_{1}$, the total processing time of the two machines is more than 2, so $J_{k}$ is processed on machine $M_{2}$. Then, we have machine $M_{1}$ is busy between time interval $[S_{k} ,C_{k} ]$, which can also result that the total processing time of the two machines is more than 2.

Case 2

The GoS of $J_{n}$ is 1.

If there are no jobs with GoS 2 processed on machine $M_{1}$, we have $C = C^{*} = 1$. Let the last job with GoS 2 processed on machine $M_{1}$ be $J_{k}$, so $C - C^{*} \leqslant p_{k}$, i.e.$p_{k} > \lambda$. According to Step 6, we can obtain that the total processing time of the two machines is more than 2.

Theorem 4

The competition ratio of the proposed algorithm for the first problem is $(\sqrt 5 + 1)/2$.

Proof

Combing Lemmas 3 and 4.

4 Optimal Algorithm for the Third Problem

In this section, with the same contracture as Sects. 2 and 3, firstly we describe the third scheduling problem; then, the lower bound of this problem is analyzed; at last, we propose an online algorithm, which is proved to be optimal.

4.1 Problem Description

The considered online scheduling problem can be described as: there are $n$ different jobs $J_{i}$ $(i = 1, \cdots ,n)$ which have to be processed on one of the two parallel machines $M_{i}$ $(i = 1,2)$ without preemption. The GoS of machine $M_{i}$ is $i$. Jobs are arrived over time with GoS (1 or 2). A job must be assigned to one of the two machines as soon as it arrives, which can be denoted as $no - delay2$. Then, we can describe the second problem as $P2\left| {online,\;r_{i} } \right.,\;M(GoS),\;no - delay2\left| {C_{\hbox{max} } } \right.$. With the same mark as Sect. 2.1, a job which is to be processed can be denoted by $(J,\;r,\;p,\;g)$. To get the minimum makespan, we need to decide the assignment of each job as soon as it arrives.

4.2 The Lower Bound of the Third Problem

In this subsection, we give the lower bound of any online algorithm for the second problem.

Theorem 5

. Any online algorithm for the second problem has a competitive ratio of at least $5/3$.

Proof

$C^{*}$ represents the optimal solution and $C^{A}$ represents the solution of an online algorithm. At time $t = 0$, $J_{1}$ arrives with $p_{1} = 1$ and $g_{1} = 2$. If $J_{1}$ is scheduled on machine $M_{1}$, we generate $J_{2}$ with $p_{2} = 1$, $g_{2} = 1$ and $r_{2} = \varepsilon$(sufficiently small), and its competitive ratio is $C^{A} /C^{*} \approx 2/1 = 2$. If $J_{1}$ is scheduled on machine $M_{2}$, we generate $J_{3}$ with $p_{3} = 1$, $g_{3} = 2$ and $r_{3} = \varepsilon$. With the same analysis, $J_{3}$ should be scheduled to machine $M_{1}$(otherwise its competitive ratio is 2 when scheduled to machine $M_{2}$). We generate $J_{4}$ with $p_{4} = 1$, $g_{4} = 2$ and $r_{4} = 2\varepsilon$. If $J_{4}$ is scheduled to machine $M_{1}$, we generate $J_{5}$ with $p_{5} = 3$, $g_{5} = 1$ and $r_{5} = 3\varepsilon$, which has competitive ratio $C^{A} /C^{*} \approx 5/3$. If $J_{4}$ is scheduled to machine $M_{2}$, we generate $J_{6}$ with $p_{6} = 3$, $g_{6} = 2$ and $r_{5} = 3\varepsilon$. If $J_{6}$ is scheduled to machine $M_{2}$, it has competitive ratio $C^{A} /C^{*} \approx 5/3$. If $J_{6}$ is scheduled to machine $M_{1}$, we generate $J_{7}$ with $p_{7} = 6$, $g_{7} = 1$ and $r_{5} = 4\varepsilon$, which has competitive ratio $C^{A} /C^{*} \approx 10/6 = 5/3$.

4.3 An Online Algorithm for the Third Problem

Here, we show an online algorithm which is proved to have the optimal competitive ratio. The notations are almost the same with Sect. 2.3 except that $A_{i} (t)$ does not need to be sequenced. The decision moment is the arriving time of each job.

Algorithm Alg_P3

• Step 1 Set the arriving time of the first job is zero, $t: = 0$, $A_{1} (t): = \varnothing$, $A_{2} (t) = \varnothing$, $J_{l}^{t} : = \varnothing$, $S(t): = 0$, $C_{1}^{A} : = 0$, $C_{2}^{A} : = 0$.

• Step 2 Update $t$, $A_{2} (t)$, $A_{1} (t)$ and $S(t)$ in turn.

• Step 3 If $A_{1} (t) \ne \varnothing$, put all jobs in $A_{1} (t)$ to machine $M_{1}$ and update $C_{1}^{A}$.

• Step 4 While $A_{2} (t) \ne \varnothing$

• Step 5 Pick the first job $J_{k}$ in $A_{2} (t)$ and delete it from $A_{2} (t)$.

• Step 6 If $C_{1}^{A} \geqslant C_{2}^{A}$ or machine $M_{2}$ is idle or $C_{1}^{A} - S(t) + p_{t} > 2(C_{2}^{A} - S(t))$, put $J_{k}$ to machine $M_{2}$ and update $C_{2}^{A}$.

• Step 7 Else, put $J_{k}$ to machine $M_{1}$ and update $C_{1}^{A}$.

• Step 8 end

• Step 9 Go to Step 2 until all jobs are scheduled.

4.4 Competitive Ratio of the Proposed Algorithm

It is apparently that Lemma 1 is also correct for the third problem, so we suppose that the two machines won’t be both idle at the same time interval. To simplify the analysis, Lemma 5 is used to limit the range of instances.

Lemma 5

If the competitive ratio of Algorithm Alg_P3 is $\alpha$ when we consider all instances with the condition that there is at most one job arrived at any time, its competitive ratio must be $\alpha$ for all instance (without the condition).

Proof

For any instance $I$, we add $i\varepsilon_{k}$ to $r_{i}$, $i = 1,2 \cdots ,n$, and $\varepsilon_{k} \to 0,\;k \to \infty$. When $k \to \infty$, the new instance $I_{k}$ satisfies the condition that there is at most one job arrived at any time. It is obviously that Lemma 5 is correct.

For any instance (the following analysis just considers the instances with the above condition), we cannot have the structure the jobs with GoS 1 are processed before the jobs with GoS 2 after time $C^{*}$ on machine $M_{1}$. The following lemma just considers the jobs on machine $M_{2}$.

Lemma 6

For any instance $I$, the remaining processing time of each job on machine $M_{2}$ at time $C^{*}$ is no more than $2C^{*} /3$ at time $C^{*}$.

Proof

Without loss of generality, let $C^{*} = 1.$ For any instance $I$, suppose that the remaining processing time ($p_{k}^{'}$) of $J_{k}$ on machine $M_{2}$ at time $C^{*}$ is more than $2/3$ at time 1. As $r_{k} \leqslant 1 - p_{k}$ and the starting time of $J_{k}$ is $S_{k} > 5/3 - p_{k}$, then the two machines must be both busy at time interval [$1 - p_{k} ,4/3 - p_{k}$] according to Steps 6 and 7. Then, we get the total processing time of all jobs must be more than 2, i.e. $C_{2}^{A} + 1/3 > 2$, which contract with the fact that $C^{*} = 1.$

Then, the competitive ratio of Algorithm Alg_P3 is proved to be 5/3 by Theorem 6.

Theorem 6

The competitive ratio of Algorithm Alg_P3 is at most $5/3$ for the third problem.

Proof

Let $C^{*} = 1$. There are two cases:

Case 1

$C_{1}^{A} \leqslant C_{2}^{A} = C^{A}$.

We denote the last completed job as $J_{l}$. If there is only an uncompleted job on machine $M_{2}$ at time 1, we have $C^{A} \leqslant 5/3$ according to Lemma 6. When there are at least two uncompleted jobs on machine $M_{2}$ at time 1, suppose that $C_{2}^{A} > 5/3$. As $r_{l} \leqslant 1 - p_{l}$ and the starting time of $J_{l}$ is $C_{2}^{A} - p_{l}$, we have $[1 - p_{l} ,4/3 - p_{l} ]$ according to Steps 6 and 7 of Algorithm Alg_P3. Then, we get the total processing time of all jobs must be more than 2, i.e. $C_{2}^{A} + 1/3 > 2$, which contract with the fact that $C^{*} = 1.$

Case 2

$C_{2}^{A} < C_{1}^{A} = C^{A}$.

Let the last job processed on machine $M_{1}$ be $J_{l}$. If the GoS of $J_{l}$ is 2 and $C_{1}^{A} > 5/3$, we can conclude that machine $M_{1}$ and $M_{2}$ are both busy at time interval $[1 - p_{l} ,C_{1}^{A} - p_{l} ]$. Then, we get the total processing time of all jobs must be more than 2, i.e. $sum \geqslant C_{1}^{A} + 2/3 > 2$, which contract with the fact that $C^{*} = 1.$ If the GoS of $J_{l}$ is 1 and $C_{1}^{A} > 5/3$, machine $M_{1}$ processes jobs with GoS 2 with total processing time more than 2/3 (put these jobs to set $B$). For the first processed job in set $B$, denoted as $J_{1}$, machine $M_{2}$ must process jobs with total processing time at least $p_{1} /2$. For the second processed job in set $B$, if machine $M_{2}$ is busy at time interval [$S_{1} ,S_{2}$]($S_{i}$ is the starting time of $J_{i}$), then the total processing time of machine $M_{2}$ is at least $(p_{1} + p_{2} )/2$ according to Steps 6 and 7; else, the total processing time is at least the sum of two parts, i.e. $(p_{1} + p_{2} )/2$. Then, we obtain that the total processing time of machine $M_{2}$ is at least 1/3. As the processing time that we compute on machine $M_{2}$ makes sure that the two machines are both busy, the total processing time of all jobs must be more than 2, i.e. $sum \geqslant C_{1}^{A} + 1/3 > 2$, which contract with the fact that $C^{*} = 1.$

5 Conclusion and Future Research

In this paper, we investigate three online scheduling problems on two parallel identical machines under a grade of service provision. The jobs arrive over time in all the three problems. The first problem requires that the two machines cannot be idle at the same time until all arrived jobs have been processed, and the second problem further requires that jobs are processed by the rule of FCFS, while the third problem has the requirement that each job must be assigned to one of the two machines as soon as it arrives. We propose optimal algorithms for all the three problems. The three algorithms and the analysis are very novel and simple.

The future research mainly includes two parts: (1) the algorithm designing can be used for both two types of online scheduling problem: over time or over list; (2) the proving method can be used to analysis the competitive ratio of online scheduling problem.

Appendices

Appendix A: Notations

In “Appendix A”, some common notations in this article are introduced in detail, especially notations in the section of introduction.

$\alpha \left| {\beta \left| \gamma \right.} \right.$: the 3-field notation proposed by Graham et al. [2]. This notation can uniquely characterize a scheduling problem. $\alpha$ represents the machine environment, which contains only one item. $\beta$ represents processing features and constraints, etc. $\gamma$ describes minimization goal. In this paper, $\alpha$ includes the following situations:

$Pm$:

$m$ parallel machines. Here $m$ machines have the same speed. $m = 2$ means there are two available machines;

$Qm$:

$m$ uniform machines. Here $m$ machines have the different speed. $m = 2$ means there are two available machines;

$\beta$:

field may include multiple processing features and constraints. In this paper, we use the following notations;

$online$:

represents that each job information is known only after it arrivals, which is the antonym of offline. Semi-online means that some information is known such as maximum processing time of all jobs. Semi-online scheduling need to add the additional information in $\beta$ field such as using $\hbox{max}$ when maximum processing time of all jobs is known in advance;

$M_{j}$:

machine eligibility constraints, i.e., not all machines can process job $j$. It means that each job must be processed in some machines. $M_{j} (GoS)$ is a special case of $M_{j}$, which means that a job can only be processed in the machine whose grade is not higher than the its grade;

$r_{j}$:

release time. It means that a job $j$ cannot be processed before time $r_{j}$;

$pmtn$:

preemption is allowed, which means that the jobs can be rescheduled to other machines even when they have not been finished;

$\gamma$:

is used to describe the minimizing objectives. In this paper, only makespan is involved;

$C_{\hbox{max} }$:

makespan, its definition is $\hbox{max} (C_{1} ,C_{2} , \cdots ,C_{n} )$.

Appendix B: Competitive Ratios of Online Scheduling

In “Appendix B”, we mainly introduce the research situation of the related problems in this paper (online over times and not batch scheduling).

Scheduling problem	Reference	Competitive ratio	Best ratio?
$P2\left| {{\text{online}},r_{j} ,M_{j} ,p_{j} = p\left| {C_{\hbox{max} } } \right.} \right.$	[15]	1.618 0	Yes
$P2\left| {{\text{online}},r_{j} ,M_{j} ({\text{GoS}}),p_{j} = p\left| {C_{\hbox{max} } } \right.} \right.$	[15]	1.414 2	Yes
$P2\left| {{\text{online}},r_{j} ,M_{j} ({\text{GoS}})\left| {C_{\hbox{max} } } \right.} \right.$	[16]	1.555 0	Yes
$Q2\left| {r_{j} } \right.,{\text{online}}\left| {C_{\hbox{max} } } \right.$	[17]	1.618 0	No
$Pm\left| {r_{j} } \right.,{\text{online}}\left| {C_{\hbox{max} } } \right.$	[17]	1.359 6	No
$P2\left| {{\text{online}},r_{j} } \right.\left| {C_{\hbox{max} } } \right.$	[13]	1.382	Yes
$P2\left| {{\text{online}},r_{j} } \right.,pmtn\left| {C_{\hbox{max} } } \right.$	[14]	1	Yes