Online and Semi-online Scheduling

Abstract

During the last two decades, online and semi-online scheduling problems have received considerable research interest. This chapter provides definitions of several online paradigms, including online over list, online over time, and semi-online. This chapter presents details of the basic online algorithms and referencing other significant results.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

¹

1 Introduction

1.1 Scheduling

Scheduling is the earliest studied branch in combinatorial optimization and also one of the problems with the most fruitful results achieved. Early scheduling problems are motivated from manufacturing systems. Later, more and more scheduling problems are formalized in the areas of information science, supply chain management, public management, and so on. In the following, we summarize the basic concepts and notations which will be used later. For more detailed introduction on scheduling theory, please refer to [21, 36, 117, 143].

Scheduling problems can be generally described as follows. There is a sequence $\mathcal{J}$ of n jobs $J_{1},J_{2},\cdots \,,J_{n}$, which need to be processed on a set $\mathcal{M}$ of m machines $M_{1},M_{2},\cdots \,,M_{m}$. A schedule is an assignment for each job to one or more time intervals of one or more machines. Schedules that satisfy various requirements of the problem are called feasible. Scheduling problems are specified by the machine environment, the job characteristics, and an optimality criterion.

There are two basic types of machine systems: single-stage system and multi-stage system. In a single-stage system, each job requires one operation, while in multiple-stage system the jobs may require several operations at different stages. There are also two classical single-stage systems: single machine and parallel machines. In a single machine system, job J _j must be processed on the unique machine M ₁ with a processing timep _{​ j} , j = 1, 2, ⋯, n. In a parallel machines system, each job can be processed by one of the m machines. The time needed for job J _j to be processed on M _i is p _ji , j = 1, ⋯, n, i = 1, ⋯, m. If p _ji = p _{​ j} for any i = 1, ⋯, m and j = 1, ⋯, n, then the machine system is called identical. If there exist s _i , i = 1, ⋯, m such that $\frac{p_{ji_{1}}} {p_{ji_{2}}} = \frac{s_{i_{2}}} {s_{i_{1}}}$ for any j = 1, ⋯, n, then the machine system is called uniform, and s _i is called the speed of M _i , i = 1, ⋯, m. W.l.o.g., we assume $s_{1} \geq s_{2} \geq \cdots \geq s_{m} = 1$ and let p _{​ j} = p _jm , which is the normalized processing time of job J _j . In the case of two uniform machines, it is of more convenience for discussion to replace the speed parameters s ₁ and s ₂( = 1) by the speed ratio $s = \frac{s_{1}} {s_{2}}$, and both are equivalent. Parallel machines system that does not fall into above categories is called unrelated. In a multi-stage system, each operation of a job has a separate processing time, and different operations of the same job cannot be scheduled at the same time. The multi-stage system is usually distinguished into open shop, when different operations of the same job may be scheduled in any order; flow shop, if the order of the operations is fixed and same for all the jobs; and job shop, if the order of the operations is fixed and possibly different for each job.

Apart from the processing time of the jobs, the processing mode can also be classified into the job characteristics. Some scheduling models allow preemption of jobs, that is, the processing of a job may be interrupted and resumed later on possibly a different machine. If each job can be arbitrarily split between the machines and parts of the same job can run on different machines in parallel, this model is called fractional assignment. There is another possibility allowing jobs to restart, which means that a processing job can be stopped and restarted later to finish the full processing time.

Given a schedule σ, let C _j (σ) (or C _j if there is no confusing) be the completion time of J _j , j = 1, 2, ⋯, n. Some commonly used objective functions include:

• The makespan: max_{1 ≤ j ≤ n} C _j (σ).

• The total completion time: $\sum _{j=1}^{n}C_{j}(\sigma )$,

• The total weighted completion time: $\sum _{j=1}^{n}w_{j}C_{j}(\sigma )$, where w _j is the weight of J _j .

All these objectives are for minimization problems. There is another criteria which maximizes the continuous period of time when all machines are busy. Such criteria have applications in the sequencing of maintenance actions for modular gas turbine aircraft engines [49] and fairly allocation of indivisible goods [15]. Problems with this objective are often called machine covering.

The period when one machine is not assigned to any job during the scheduling process is called idle time. For most non-preemptive problems, there is no benefit to introduce idle times. But idle time is of great help if preemption is allowed, especially for uniform machines scheduling. Let L _i be the completion time of machine M _i in schedule σ. The makespan of σ equals to $\max _{i\,=\,1,\cdots \,,m}L_{i}$. However, min _{i = 1, ⋯, m} L _i is not always identical with the objective value of the machine covering problem if idle times exist (Fig. 1).

Fig. 1

Machine completion times and objective value of a schedule

In general, scheduling problems are specified in terms of a three-field notation [88]. Here, we adopt the notation from it. In this chapter, we will use 1, P, Q, R to denote single, identical, uniform, unrelated machine system and F, O, J to denote flow shop, open shop, and job shop system. Problems allowing preemption, fractional assignment, and restart will be denoted by pmtn, frac, and res, respectively. The objectives of minimizing makespan, minimizing the total completion time, and minimizing the total weighted completion time will be shortly denoted by C _max , ∑C _j , and $\sum w_{j}C_{j}$, respectively. The objective of machine covering is denoted C _min .

1.2 Online Problems and Competitive Analysis

Online problems began to draw attention in the middle period of the eighties of the twentieth century. The basic character of online models is “lack of information,” while the previously studied problems having the access to full information are called offline. For more detailed introduction of online theories and variants, please refer to [20, 75].

For scheduling problems, there are a variety of online models, among which the following two are the most common.

Online over list: Jobs are ordered in a list and arrived one by one (at time 0). The information of a job is known to the scheduler only when all the jobs before it have been assigned. And the assignment of jobs is irrevocable.

Online over time: Each job has a release time after which the information of the job is known and can be processed. The release time of J _j is denoted by r _j , j = 1, 2, ⋯, n.

Since almost all problems considered in this chapter are online, we will ignore online over list in the second field of the three-field notation. On the other hand, r _j will be included in the second field of the three-field notation for the online over time model.

The competitive analysis is the most common method in analysis of online algorithms, which is formally introduced by Sleator and Tarjan [161]. The performance of an online algorithm is measured by its competitive ratio, which has some similarity as worst-case ratio for offline problems. For a job sequence $\mathcal{J}$ and an online algorithm A, if A produces a schedule with objective value ${C}^{A}(\mathcal{J} )$ for the minimization (or maximization) problem and the optimal offline objective value is ${C}^{{\ast}}(\mathcal{J} )$, then the competitive ratio of A is defined as

$$r_{A} =\inf _{\mathcal{J}}\{r\vert {C}^{A}(\mathcal{J} ) \leq r{C}^{{\ast}}(\mathcal{J} )\}\ \ (or\ r_{ A} =\inf _{\mathcal{J}}\{r\vert {C}^{{\ast}}(\mathcal{J} ) \leq r{C}^{A}(\mathcal{J} )\}).$$

If there is an online algorithm A for the problem with a competitive ratio r, then A is called an r-competitive algorithm. On the contrary, if no online algorithm has a competitive ratio smaller than ρ, then the problem must have a lower bound ρ. Therefore, an online algorithm is called optimal or best possible for the problem if its competitive ratio just matches the lower bound. Here, optimal does not mean that it always produces an optimal schedule. It only indicates the fact that no online algorithm can be better. An online algorithm is stated to possess competitive ratio 1 if it always produces an optimal schedule, but such algorithm seldom exists. In this chapter, we use optimal bound to denote the competitive ratio of the optimal algorithm of the problem for simplicity. Symmetrically, a problem has upper boundr if there exists an online algorithm for the problem with competitive ratio r.

A randomized algorithm is one which somehow bases its decision making on the outcome of random coin flips. For a randomized algorithm, the objective value ${C}^{A}(\mathcal{J} )$ is a random variable. Thus, the competitive ratio of a randomized algorithm (for a minimization problem) is defined as

$$r_{A} =\inf _{\mathcal{J}}\{r\vert E({C}^{A})(\mathcal{J} ) \leq r{C}^{{\ast}}(\mathcal{J} )\},$$

where the expectation is taken over the random choices of the algorithm. In addition, concepts of randomized upper and lower bound can also be defined accordingly. Algorithms which do not use randomization are called deterministic algorithm. Since deterministic algorithm can be viewed as a special randomized algorithm, the randomized lower bound cannot be larger than deterministic lower bound. In this chapter, without special mention, all algorithms (competitive ratio, lower bound) are deterministic. For a general introduction on randomized algorithms, please refer to [134].

1.3 Structure and Notation

Online scheduling boasts of extensive results; thus, it is impossible to cover all the problems in one chapter, and only part of paradigms together with the according main results is included. There have been two excellent surveys [144, 156] concerning online scheduling, and some paradigms discussed elaborately there will be omitted. We will mainly introduce paradigms approaching classical scheduling problems and withal active in recent research. There are several interesting and important problems not covered due to limited space and number of references, and we will sketch some of them in the following. Firstly, scheduling problems with deadline constraints, including interval scheduling, are not included in this chapter. Secondly, it does not cover problems concerning other objective functions, for example, the (weighted) total flow time and the L _p norm of machine completion times, together with objectives deriving from bicriteria situations, for example, scheduling with rejection and scheduling with machine cost. Thirdly, performance measures other than competitive analysis, including resource argumentation, will not be contained in this chapter. Finally, we skip problems which have specific applications, such as scheduling problems in power management, broadcasting, and supply chain management.

The chapter is organized as follows. In Sect. 2, we survey main results for the online over list model. Section 3 is devoted to semi-online variants of online over list model. In Sect. 4, we introduce online and semi-online problems of the online over time model. Other variants of online scheduling are contained in Sect. 5.

The following notations as well as those defined above will be used frequently in the reminder of this chapter. For any i = 1, ⋯, m, let $S_{i} =\sum _{ l=1}^{i}s_{l}$ be the total speeds of the first i machines in uniform machine system, and we simplify S _m as S. For any j = 1, ⋯, n, let $\mathcal{J}_{j}$ be the subset of $\mathcal{J}$ containing the first j jobs and P _j be the total processing times of the first j jobs. We simplify P _n as P. Let p _(j) be the processing time of the job which has the jth largest processing time, that is, $p_{(1)} \geq p_{(2)} \geq \cdots \geq p_{(n)}$. For any i = 1, ⋯, m and j = 1, ⋯, n, let L _i ^j be the completion time of machine M _i after the job J _j is assigned. L _i ^j is also called the load of M _i if no idle time exists. Clearly, L _i ⁿ equals to L _i .

2 Online Over List

This section summarizes main results for online over list model on parallel machines. In this paradigm, the makespan, which is the most common objective function with no doubt, will be considered throughout this section except the last subsection.

2.1 Non-preemptive Scheduling

2.1.1 Identical Machines

Pm | | C _max is the most studied and historical problem for online scheduling. In his epoch making paper, Graham [86] designed the first approximation algorithm in combinatorial optimization called List Scheduling (LS for short). LS uses greedy idea and has a very simple structure. It always assigns the current job to the machine where it can be started to process the earliest, that is, the machine with the smallest current load, ties are broken arbitrary. Such principle of assigning jobs is sometimes called LS rule in the literature. Graham proved the following result.

Theorem 1 ([86])

The competitive ratio of LS for Pm||C _max is $2 - \frac{1} {m}$.

Proof

(Sketch) Without loss of generalization, the last job J _n determines the makespan. Let s _n be the start time of J _n . By LS rule, no machine will idle during [0, s _n ]. Hence, $s_{n} \leq \frac{P-p_{n}} {m}$. Clearly,

$${C}^{{\ast}}\geq \frac{P} {m}$$

(1)

and

$${C}^{{\ast}}\geq \max _{ 1\leq j\leq n}p_{j}.$$

(2)

Hence,

$${ C}^{LS} = s_{ n}+p_{n} \leq \frac{P - p_{n}} {m} +p_{n} = \frac{P} {m}+\frac{m - 1} {m} p_{n} \leq {C}^{{\ast}}+\frac{m - 1} {m} {C}^{{\ast}} = \left (2 - \frac{1} {m}\right ){C}^{{\ast}}.$$

LS is a typical online algorithm. When assigning a new job, it does not use any information of jobs that have not arrived yet. Not only the rule of LS but also the ideas behind the proof are frequently used in design and analysis of other online algorithms. Twenty years have passed since the appearance of LS, and online problems are drawing more and more attentions. Feigle et al. [74] proved that LS is the optimal algorithm for Pm | | C _max when m = 2, 3. It should be emphasized that no other algorithm has been proved to be optimal for any m ≥ 4 up till now.

Though LS is irreplaceable in online scheduling, it is gradually recognized that LS cannot be the optimal algorithm for Pm | | C _max when m ≥ 4. Hence, algorithms and lower bounds have been refined bit by bit, and brief results and history are summarized in Table 1. In these new algorithms, jobs are not always assigned to the least loaded machine. Sometimes, the current job may be assigned to the second smallest or the machine whose load lies approximately in middle of all machines. Almost all these algorithms contain some parameters which have been carefully selected, and the analysis of the algorithm is much more involved. The instances used to prove the lower bound are likewise very sophisticated. The current best lower bound is obtained even by exhaustive search using computers.

Table 1 Improvement of lower and upper bounds of Pm | | C _max

It seems that improvement of the algorithm could be carried on since there is still a gap 0. 066 between the current best upper and lower bounds. However, there is a turning point when Albers [2] proposed her important results. When proving the competitive ratio of an online algorithm, it is in fact that some lower bounds instead of the exact value of the optimum itself are used. For example, lower bounds (1) and (2) are used in the proof of Theorem 1. Another useful lower bound on the optimum is

$${C}^{{\ast}}\geq 2p_{ (m+1)}.$$

(3)

Theorem 2 ([2])

If only using (1), (2) and (3) as lower bounds on the optimum, it is impossible to prove an online algorithm A has a competitive ratio less than 1.919.

Note that the competitive ratio of the algorithm could be smaller than 1. 919, but it cannot be proved using existing techniques. The bound 1. 919 in Theorem 2 is very close to the current best upper bound 1. 9201. Hence, it seems more urgent to find new lower bounds on the optimum than to designing more delicate algorithms. Though Theorem 2 does not give new lower bounds, it does point out the direction of future research. Such ideas can be adopted to other hard online scheduling problems as well.

When the number of machines is small, better lower bounds and algorithms can be obtained. For example, Chen et al. [31] presented an algorithm with competitive ratio at most

$$\max \left \{\frac{4{m}^{2} - 3m} {2{m}^{2} - 2}, \frac{2{(m - 1)}^{2} + \sqrt{1 + 2m(m - 1)} - 1} {{(m - 1)}^{2} + \sqrt{1 + 2m(m - 1)} - 1} \right \}$$

for Pm | | C _max , m ≥ 4. Rudin III and Chandrasekaran [147] proved the lower bound of P4 | | C _max is at least $\sqrt{3}$, which is in line with the conjecture that the optimal bound of P4 | | C _max is $\sqrt{ 3}$. Numerical bounds are summarized in Table 2.

Table 2 Current best upper and lower bounds for online over list model on identical machines

2.1.2 Uniform and Unrelated Machines

The competitive analysis for Qm | | C _max is even more difficult than that for Pm | | C _max . Both the competitive ratios of online algorithms and lower bounds of the problems are functions of machine speeds s _i , i = 1, ⋯, m. This might be the reason why optimal or tight bounds can only obtained for small values of m. For larger m or arbitrary number of machines, it is of more significance and practical that either to consider some special combinations of s _i or to obtain overall upper and lower bounds, that is, the maximal value among all possible choice of s _i , i = 1, ⋯, m for both.

Since the machines have different speeds, the machine where a job can be started to process the earliest may not be the machine where it can be completed the earliest. Therefore, it is necessary to distinguish two variants of LS, namely, LSc and LSs. LSc and LSs assign the arriving job to the machine which the job can be completed or started the earliest, respectively. It is evident to see that for Qm | | C _max , LSc is better than LSs.

The competitive ratio of LSc for Qm | | C _max is at most

$$\min _{1\leq k\leq m}\left \{\frac{\displaystyle\sum\nolimits _{i=1}^{m}s_{i} + (k - 1)s_{1}} {\displaystyle\sum\nolimits _{i=1}^{k}s_{i}} \right \}$$

[90]. The overall competitive ratio is at most

$$\left \{\begin{array}{ll} \frac{1+\sqrt{5}} {2}, &m = 2, \\ \frac{2+\sqrt{2m-2}} {2},&m \geq 3, \end{array} \right.$$

and the bound is tight in the overall sense when m ≤ 6 [44]. For large m, the bound O(logm) obtained by using an alternative method different from those in Theorem 1 is better [10]. Specifically, for m = 2, the bound is

$$\left \{\begin{array}{lr} \frac{2s+1} {s+1},&1 \leq s \leq \frac{1+\sqrt{5}} {2}, \\ \frac{s+1} {s}, & s> \frac{1+\sqrt{5}} {2}, \end{array} \right.$$

and LSc is the optimal algorithm [72]. For m = 3, the bound is

$$\left \{\begin{array}{ll} \dfrac{s_{1} + s_{2} + s_{3}} {s_{1}}, &s_{1}^{2} \geq s_{2}^{2} + s_{1}s_{2} + s_{2}s_{3}, \\ \dfrac{2s_{1} + s_{2} + s_{3}} {s_{1} + s_{2}},&s_{1}^{2} < s_{2}^{2} + s_{1}s_{2} + s_{2}s_{3}\mbox{ and }s_{1}^{2} + s_{1}s_{2} \geq s_{3}^{2} + s_{1}s_{3} + 2s_{2}s_{3}, \\ \dfrac{3s_{1} + s_{2} + s_{3}} {s_{1} + s_{2} + s_{3}},&s_{1}^{2} + s_{1}s_{2} < s_{3}^{2} + s_{1}s_{3} + 2s_{2}s_{3}, \end{array} \right.$$

and it is tight for any combinations of machine speeds [90]. However, it has been shown that LSc is optimal only for the case when $s_{1} = s_{2} = 1 \geq (\sqrt{2} - 1)s_{3}$ and $s_{1}^{2} \geq s_{2}^{2} + s_{1}s_{2} + s_{2}$ [90, 136], and there does exist another online algorithm which beats LSc when $\frac{1+\sqrt{97}} {8} < \frac{s_{1}} {s_{2}} = \frac{s_{1}} {s_{3}} < 2$ [90]. It implies that the optimality of LS for P3 | | C _max cannot be generalized to the problem with different machine speeds.

Since the competitive ratio of LSc tends to infinite when m becomes very large [44], it is natural to raise the question that whether an algorithm with finite competitive ratio exists. The first such algorithm with competitive ratio 8 was obtained by using a so-called doubling strategy [10]. Their results were later improved by Berman [19], where a new algorithm with overall competitive ratio $3 + \sqrt{8} \approx 5.828$ and a overall lower bound 2. 4380 are given. The lower bound was recently improved to θ by Ebenlendr and Sgall [60], where θ ≈ 2. 564 is the solution of the equation $\int _{0}^{1} \frac{\ln \theta } {\ln (1{-\theta }^{-x})}dx = -1$.

For the most studied special case of $s_{1}> s_{2} = s_{3} = \cdots = s_{m} = 1$, the overall competitive ratio of LSc for Qm | | C _max is at most $\frac{3m-1} {m+1}$, where the maximum value achieves at s ₁ = 2 [44]. The bound matches the overall lower bound 2 when m = 3 [118]. For m ≥ 4, Li and Shi [118] designed a new algorithm which has a smaller competitive ratio around s ₁ = 2. Thus, the overall competitive ratio can be decrease to 2. 8795. Cheng et al. [42] further raised an algorithm which has a competitive ratio of 2. 45 if the speed of the fastest machine is restricted to 1 ≤ s ₁ ≤ 2.

For Rm | | C _max , Aspnes et al. [10] proved that the competitive ratio of LSc is at most m, and thus, LSc is optimal when m = 2. They also designed a new algorithm with competitive ratio O(logm). Since the lower bound of the problem is at least $\lceil \log _{2}(m + 1)\rceil$ [13], their algorithm is optimal up to a constant factor.

2.2 Preemptive Scheduling

Results of preemptive online scheduling are more complete than those of non-preemptive problems. The main reason may be that the optimal offline makespan can be obtained in polynomial time. The following lemma plays an important role in designing online algorithms for Pm | pmtn | C _max and Qm | pmtn | C _max .

Lemma 1 ([84, 101])

For Qm|pmtn|C _max,

$${C}^{{\ast}} =\min \left \{\frac{\displaystyle\sum\nolimits _{j=1}^{n}p_{ j}} {\displaystyle\sum\nolimits _{i=1}^{m}s_{i}},\max _{1\leq l\leq m-1}\frac{\displaystyle\sum\nolimits _{i=1}^{l}p_{(i)}} {\displaystyle\sum\nolimits _{i=1}^{l}s_{i}} \right \}.$$

Chen et al. [33] designed an optimal algorithm preemptive for Pm | pmtn | C _max . Let $\Gamma _{m} = \frac{{m}^{m}} {{m}^{m}-{(m-1)}^{m}}$. Note that $\lim _{m\rightarrow \infty }\Gamma _{m} = \frac{e-1} {e} \approx 1.582$. Recall that for any j, ${C}^{{\ast}}(\mathcal{J}_{j})$ can be calculated by Lemma 1.

Algorithm Preemptive

Let the current job be J _j . Reindex the machines such that $L_{1}^{j-1} \leq L_{2}^{j-1}$ $\leq \cdots \leq L_{m}^{j-1}$. If $L_{m}^{j-1} + p_{j} \leq \Gamma _{m}{C}^{{\ast}}(\mathcal{J}_{j})$, then assign J _j to M _m . Otherwise, let $l =\min \{ i\vert L_{i}^{j-1} + p_{j} \geq \Gamma _{m}{C}^{{\ast}}(\mathcal{J}_{j})\}$. Assign part of J _j of processing time $\Gamma _{m}{C}^{{\ast}}(\mathcal{J}_{j}) - L_{l}^{j-1}$ to M _l and the remaining part of J _j of processing time $L_{l}^{j-1} + p_{j} - \Gamma _{m}{C}^{{\ast}}(\mathcal{J}_{j})$ to M _{l − 1}.

Theorem 3 ([33])

The competitive ratio of Preemptive for Pm|Pmtn|C _max is $\Gamma _{m}$.

Proof

(Sketch) Prove by induction that for any j, the following two inequalities hold

$$L_{m}^{j} \leq \Gamma _{ m}{C}^{{\ast}}(\mathcal{J}_{ j}),$$

$$\displaystyle\sum _{i=1}^{k}L_{ i}^{j} \leq \frac{{( \frac{m} {m-1})}^{k} - 1} {{( \frac{m} {m-1})}^{m} - 1}P_{j},k = 1,\cdots \,,m.$$

Then, it can be confirmed that the schedule produced by Preemptive is feasible, and the competitive ratio holds.

Several attempts have been made to modify and generalize Preemptive to handle uniform machines, which resulted in an optimal algorithm for Q2 | pmtn | C _max with competitive ratio $\frac{{s}^{2}+2s+1} {{s}^{2}+s+1}$ [72, 180] and an optimal algorithm for Qm | pmtn | C _max with nondecreasing speed ratios, that is, $\frac{s_{i-1}} {s_{i}} \leq \frac{s_{i}} {s_{i+1}},$ 2 ≤ i ≤ m − 1 [64]. But it seems difficult to make further generalizations using similar ideas.

Recently, Ebenlendr et al. [62] introduced a novel technique which leads to an optimal algorithm of Qm | pmtn | C _max for any combinations of machine speeds. The competitive ratio $\Gamma (s_{1},\cdots \,,s_{m})$ of the algorithm is the optimal value of the following linear programming with decision variables $q_{1},\cdots \,,q_{m},O_{1},\cdots \,,O_{m}$ and parameters s ₁, ⋯, s _m .

$$\begin{array}{ll} \max &q_{1} + q_{2} + \cdots + q_{m} \\ s.t.&q_{1} + \cdots + q_{k} \leq (s_{1} + s_{2} + \cdots + s_{m})O_{k},\ \ k = 1,\cdots \,,m, \\ &q_{j} + q_{j+1} + \cdots + q_{k} \leq (s_{1} + s_{2} + \cdots + s_{k-j+1})O_{k},2 \leq j \leq k \leq m, \\ &1 = s_{1}O_{m} + s_{2}O_{m-1} + \cdots + s_{m}O_{1}, \\ &q_{j} \leq q_{j+1},j = 2,\cdots \,,m - 1, \\ &q_{1} \geq 0,q_{2} \geq 0. \end{array}$$

(4)

However, it can only be proved that the algorithm is optimal for any m and any combinations of machine speeds, but the concrete expression of the optimal bound Γ(s ₁, ⋯, s _m ) is not known yet, even the overall bounds are hard to get. The currently known best lower and upper bound for arbitrary m is 2. 054 (achieves at m = 100 and is obtained by numerical calculation) and e ≈ 2. 718, respectively [62]. When the number of machines is small or some assumptions are made on the values of s _i , (4) can be solved theoretically [62]. For example, the optimal bounds for Q3 | pmtn | C _max are

$$\Gamma (s_{1},s_{2},s_{3}) = \left \{\begin{array}{ll} {(\frac{s_{1}} {S} + (1 -\frac{s_{1}} {S} )\frac{s_{2}} {S} + {(1 -\frac{s_{1}} {S} )}^{2}\frac{s_{3}} {S} )}^{-1},&\mbox{ if $\frac{s_{1}} {s_{2}} \leq \frac{s_{2}} {s_{3}} + 1$;} \\ \frac{{S}^{2}} {s_{1}^{2}+s_{2}^{2}+s_{3}^{2}+s_{1}s_{2}+s_{1}s_{3}+s_{2}s_{3}}, &\mbox{ if $\frac{s_{1}} {s_{2}} \geq \frac{s_{2}} {s_{3}} + 1$.} \end{array} \right.$$

Another question requiring answer is that whether the optimal bounds will increase if idle time is prohibited. Note that algorithms in [33, 64, 72, 180] all do not introduce idle time, but no algorithm which allows idle time can have a smaller competitive ratio under certain machine environment mentioned there. However, the algorithm given in [62] does use idle time. It is not known yet that whether an algorithm which does not use idle time will necessarily have a strict larger competitive ratio than Γ(s ₁, ⋯, s _m ) for general Qm | pmtn | C _max .

2.3 Randomized Algorithm

As far as ever known results are concerned, for case on parallel machine scheduling problem with objective to minimize makespan, any lower bound for deterministic preemptive online algorithm (allowing idle time) is also a lower bound for randomized preemptive or non-preemptive online algorithms. For example, the randomized lower bound for Pm | | C _max and Qm | | C _max is $\frac{{(m-1)}^{m}} {{m}^{m}-{(m-1)}^{m}}$ [32, 155] and $\Gamma (s_{1},\cdots \,,s_{m})$ [62], respectively. But the converse is not true. Tichý [174] showed that there does not exist a randomized algorithm for P3 | | C _max with competitive ratio $\frac{27} {19}$. However, his proof does not yield a new randomized lower bound with a strict larger value.

The first randomized algorithm for parallel machine scheduling is due to [18], where an optimal randomized algorithm for P2 | | C _max is given. The algorithm was restated in a simpler version in [155] as follows.

Algorithm Random

• 1. If possible, assign the current job J _j randomly so that afterwards the expected makespan equals $\frac{2} {3}P_{j}$.

• 2. Otherwise, assign job J _j always on the less loaded machine.

Theorem 4 ([18, 155])

The competitive ratio of Random for P2||C _max is $\frac{4} {3}$.

Proof

(Sketch) Prove by induction that for any j, the following two invariants hold

$$\begin{array}{l} E({C}^{Random}(\mathcal{J}_{j})) \geq \frac{2} {3}P_{j}, \\ \mbox{ If }E({C}^{Random}(\mathcal{J}_{j}))> \frac{2} {3}P_{j},\mbox{ then }\max _{1\leq l\leq j}p_{l} \geq \frac{3} {4}E({C}^{Random}(\mathcal{J}_{ j})).\end{array}$$

(5)

Clearly, (5) is also valid for j = n. Then, by (1) and (2), the theorem is thus proved.

Design effective randomized algorithm for Pm | | C _max is rather a challenging work. When the number of machines is small, the competitive ratios of algorithms proposed by Seiden [151, 153] can be less than the best known deterministic algorithms (See Table 2). For arbitrary m, Albers [2] designed a randomized algorithm with competitive ratio 1. 916, which is a combination of two deterministic algorithms with equal probability, and it is better than any known deterministic algorithm.

There is even less study on randomized algorithm for uniform machines. For Q2 | | C _max , Epstein et al. [72] showed that randomization does not help when s ≥ 2. They also presented numerical randomized lower bounds for 1 ≤ s ≤ 2 by solving linear programmings and a smaller analytical randomized lower bound $\frac{{(s+1)}^{2}(s+2)} {3{s}^{2}+5s+1}$ for $1 \leq s \leq \sqrt{2}$. Three randomized algorithms are proposed, and thus, an overall upper bound 1. 52778 can be achieved, but the gap between the lower and upper bounds for any s ≥ 1 is still relatively large. For Q3 | | C _max with restricted machine speeds $s_{1} = s_{2} \geq s_{3} = 1$, Musitelli and Nicoletti [136] presented a randomized algorithm with competitive ratio

$$\left \{\begin{array}{ll} \dfrac{4s_{2} + 2} {3s_{2}},&1 \leq s_{2} < \frac{\sqrt{10}+2} {3}, \\ \dfrac{6s_{2} + 2} {3s_{2} + 2},&s_{2} \geq \frac{\sqrt{10}+2} {3}. \end{array} \right.$$

It is only a little smaller than the competitive ratio of LSc, and no randomized lower bound has been reported.

2.4 Other Objectives

2.4.1 Total Completion Time

The property of the objective of minimizing the total completion time is different from that of minimizing makespan. The objective value of the schedule will be affected by not only the set of jobs assigned to each machine but also the process sequence of it. As a result, there exists no algorithm with constant competitive ratio, even for the single machine case.

Theorem 5 ([76])

For every function f : N → R ⁺ that fulfills conditions:

• 1. f(n) is nondecreasing,

• 2. $\sum _{n=1}^{\infty } \frac{1} {nf(n)}$ converges,

there exists an online algorithm for $1\vert \vert \sum C_{j}$ with competitive ratio at most O(f(n)), where n is the number of jobs. On the other hand, let g : N → R ⁺ be a function that fulfills condition:

• 1. g(n) is nondecreasing,

• 2. $\sum _{n=1}^{\infty } \frac{1} {ng(n)}$ diverges,

• 3. $g(n) = O{(\log }^{2}n)$,

• 4. $g\left ({ \frac{n} {\log }^{2}n}\right ) = \Omega (g(n))$,

then there does not exist an online algorithm for $1\vert \vert \sum C_{j}$ with competitive ratio o(f(n)).

By selecting specific functions which satisfy the respective conditions, it can be found that the gap between the lower and upper bounds is rather small.

Corollary 1 ([76])

For every ε > 0, there exists an online algorithm with competitive ratio at most (log n) ^1+ε , but no online algorithm with competitive ratio log n can exist.

2.4.2 Machine Covering

The online version of non-preemptive machine covering problem is relatively easy. It should be mentioned that for machine covering problems, LSs is better than LSc in most cases. Woeginger [181] and Epstein [66] proved that LSs is the optimal algorithm for Pm | | C _min and Q2 | | C _min , respectively. In fact, their analysis can be generalized to Qm | | C _min . LSs remains the optimal algorithm with competitive ratio $\sum _{i=1}^{m}s_{i}$. Azar and Epstein [12] designed a randomized algorithm for Pm | | C _min with an overall competitive ratio $O(\sqrt{m}\log m)$ and proved an overall randomized lower bound $\frac{\sqrt{m}} {4}$.

Surprisingly, machine covering problem becomes much more difficult if preemption is allowed, even though the optimal offline objective value

$$\min _{0\leq j\leq m-1}\frac{\displaystyle\sum\nolimits _{l=j+1}^{n}p_{(l)}} {\displaystyle\sum\nolimits _{l=j+1}^{m}s_{l}}$$

for Qm | pmtn | C _min can be calculated similarly as Qm | pmtn | C _max [108]. Jiang et al. [108] proved that $\sum _{i=1}^{m}\frac{1} {i}$ is a lower bound of Pm | pmtn | C _min and m is an overall lower bound of Qm | pmtn | C _min , but no algorithm with matched competitive ratio has been given. For Q2 | pmtn | C _min , they designed an optimal algorithm with competitive ratio $\frac{2s+1} {s+1}$. However, their algorithm may introduce idle time, even when it assigns the first job. If idle time is not allowed, then no deterministic algorithm can have a smaller competitive ratio than

$$\left \{\begin{array}{ll} \dfrac{2s + 1} {s + 1},&1 \leq s < \frac{1+\sqrt{5}} {2}, \\ s, &s \geq \dfrac{1 + \sqrt{5}} {2}. \end{array} \right.$$

A corresponding algorithm prohibiting idle time with matched competitive ratio was also given in [108]. Therefore, whether idle time is allowed or not does affect the optimal bounds for machine covering problems. It should be noted that different from algorithms allowing idle time, for non-idle time situation, there is no evidence yet that the lower bound also holds for randomized algorithm. Such phenomenon also appears in similar situations in the following.

3 Semi-online Scheduling

3.1 Motivation and Taxonomy

There are two basic characteristics for the online over list model. The first is that jobs arrive one by one and it is required to assign each job without any knowledge of the jobs that arrive later. The second is that the assignment of the job should be determined immediately upon its arrival and cannot be changed later. The reason of the first characteristic is “lack of information,” while the essence of the second is “restriction of scheduling.” There are often voices of criticism on the model for the sake of both theoretical study and practical application. In practice, most problems are not pure offline or online but somehow in between. Theoretically, the competitive ratio of an online algorithm tends to be over large in contract with the actual performance, since offline algorithms are more powerful than online algorithms. Moreover, the lower bound of the problem can also be ineffective, namely, too large, as the adversary can arbitrarily determine the instances without any restriction.

The reasons aforementioned bring semi-online scheduling about an active research area. Semi-online can be looked upon as relaxation of online or an intermediate state of offline and online. The primary significance of study on semi-online settings is as follows. First and foremost, without reasonable understanding of semi-online problems, there will be no more than online algorithm to implement faced with semi-online cases, which will give rise to inevitable loss definitely, just as LS algorithm performs not satisfactorily on offline problems. Furthermore, deep study on semi-online problems will lead to initiative search for crucial factors in algorithm design and improving, which will certainly save the cost and energy on many pointless factors. In theory, research on semi-online scheduling is of help to clarify influence of various restrictions of both information accessed to and algorithm design, and to reveal some deep and dominant properties. For example, it is interesting to consider the question that whether it is possible or under what kind of circumstance that an online approximation scheme, that is, a class of semi-online algorithms with competitive ratio arbitrarily close to 1 can exist. In contrast to PTAS of offline problems, whose time complexity increases as the worst-case ratio of the algorithm decreases, more partial information or more freedom of scheduling is required in online cases when pursuing a better competitive ratio. In fact, one such approximation scheme has already been obtained [160]. Last but not least, it will be meaningful for algorithm design and analysis on online problems when researching on semi-online models, as will see later.

Though semi-online model can be viewed as an intermediate state between online and offline, its properties and research approach are almost the same as the online model. Competitive analysis is still the primary technique adopted, and lower bound of the problem, together with competitive ratio of the algorithm, can be defined accordingly.

The value of a semi-online model, denoted by Π _s , is evaluated by comparing its upper (or lower) bound with that of a corresponding online model reacting to the same machine environment and objective function, which is represented by Π _o . The semi-online model is called valuable if there exists an online algorithm for Π _s whose competitive ratio is smaller than the optimal bound (or lower bound) of the Π _o . On the other hand, if the lower bound of Π _s is no smaller than the competitive ratio of an algorithm for Π _o , it is called valueless. Of course, a semionline model is valuable or may not be determined by certain machine environment or objective functions. In this section, mainly identical and uniform machines, as well as minimizing makespan and maximizing minimum machine load, are considered. It is also possible to compare variants of semi-online models qualitatively, according to the extent to which the optimal bound of pure online problem can be improved. However, the outcomes may be quite sensitive to the machine environment or objective function.

Various semi-online paradigms have been studied in the literature, which can be divided into several categories. The taxonomy and their notations, which will be included in the middle field of the three-field notation, are summarized in the Table 3. Their specific implications will be introduced in the rest of the subsection.

Table 3 Semi-online models

3.1.1 Basic Semi-online Models of Type I

Basic semi-online models of Type I modify the first assumption of the online over list model, that is, some partial information about the future jobs are known in advance. The following four kinds of partial information are the most heated.

decr [154]: The jobs are arriving in nonincreasing order of their processing times, that is, $p_{1} \geq p_{2} \geq \cdots \geq p_{n}$.

sum [111]: The total processing time of all jobs $P =\sum _{ j=1}^{n}p_{j}$ is known before the first job is arrived.

opt [14]: The optimal offline makespan C ^∗ is known before the first job is arrived.

max [111]: The maximal processing time of all jobs $p_{max} =\max _{j=1,\cdots \,,n}p_{j}$ is known before the first job is arrived.

The motivation of decr, sum, and max is obvious, whereas it may seem to be strange at first glance that the optimal offline makespan can be known in advance. In fact, it can be interpreted from the realistic scenario of remote file transfer [14]. Besides, online problems with C ^∗ is known in advance have already been studied before semi-online began to draw attention, since the following lemma is useful in competitive analysis of difficult online problems [10].

Lemma 2

For some scheduling problem of online over list model with objective to minimize makespan, if there exists an algorithm for the opt variant with competitive ratio r, then there exists an algorithm for the pure online model with competitive ratio at most 4r.

Some variants reacting to other partial knowledge of input are also reasonable, which is quite common in practice. For example,

• num: The number of all jobs n is known before the first job is arrived.

• incr: The jobs are arriving in nondecreasing order of their processing times, that is, $p_{1} \leq p_{2} \leq \cdots \leq p_{n}$.

• UB(LB): The upper (lower) bound on the processing time of all jobs $p_{UB} \geq \max _{j=1,\cdots \,,n}p_{j}$ ($p_{LB} \leq \min _{j=1,\cdots \,,n}p_{j}$) is known before the first job is arrived.

• min: The minimal processing time of all jobs $p_{min} =\min _{j=1,\cdots \,,n}p_{j}$ is known before the first job is arrived.

However, such paradigms, which seem worthless under certain machine environment and objective functions discussed so far, have not drawn much attention.

Another kind of partial information which is common in practice is called lookahead [111]. When assigning the current job, the information of the next k jobs is known, where k is a constant number. Lookahead tends to be of benefit for scheduling according to practical experience, whereas it turns out to be still valueless as far as competitive ratio is concerned.

3.1.2 Basic Semi-online Models of Type II

There are other variants which lie between online and offline. However, they have nothing to do with the partial information of the input but more freedom acquired in scheduling. These variants belong to Type II semi-online models. It is a much more potential research area compared with Type I semi-online models, which is fruitful of results.

In the buffer [111] paradigm, there is a buffer of size K which can store at most K jobs. The incoming job can either be scheduled immediately or be stored in the buffer, which enables it to be scheduled later. The root cause of the improved performance attributed to buffer lies in the fact that it can reorder the job sequence. Pure online and offline models are equivalent to problems with buffer size 0 and ∞, respectively. In another related class of models reassignment [160, 167], it is allowed to reassign some of the jobs during or after the process. Recall that in the pure online model, no job can be reassigned.

A technique frequently used in designing algorithm for the offline problems is to run several procedures in parallel and then select the best result as output. However, it does not fit pure online setting. Semi-online variant which allows to use such technique is called parallel. A real-world system which resembles such situation was claimed to exist in [111]. Kellerer et al. [111] proved that the optimal bound of P2 | parallel(2) | C _max is $\frac{4} {3}$; here, parallel(2) means that two procedures are run in parallel.

3.1.3 Combined Semi-online Models

Since some semi-online variants are indeed of value, it is natural to raise the question whether a more efficient algorithm can be designed for a problem possessing characteristics of several semionline variants in the meantime. A combination is useful, if there exists an online algorithm for the combined semi-online problem whose competitive ratio is smaller than the optimal bound (or lower bound) of any one of the basic semi-online model. Otherwise, the combination is useless. The combination could be of two basic semi-online variants of Type I, as well as that of Type I and II, respectively. In spite of the fact that combination consisting of more than three variants can certainly be concerned with, such cases are always quite complicated and seldom studied.

3.1.4 Disturbed Semi-online Models

The disturbed semi-online models were first studied in [165]. In some cases, it is allowed to use some additional information or slightly more resources than the offline algorithm, whereas the information or resources might be unreliable. For example, it is known in advance that the total processing time lies in the interval [P ₀, αP ₀], but the exact value of P is still unknown. It can be believed that the value of inexact partial information lies largely on the value of α, which is called disturbance parameter. For problem with inexact partial information, special stress is laid on determining the value of α which insures the information to be useful and further designing algorithm making use of the beneficial information acquired.

3.2 Results on Basic Semi-online Models of Type I

3.2.1 Identical Machines

It has been widely known for a long time that in combinatorial optimization, the performance of an algorithm can be improved after appropriate preprocessing for the input. Graham [87] proved that the worst-case ratio of algorithm Longest Processing Time first (LPT for short), where LS is implemented after a preprocessing step, namely, reordering the jobs in a nonincreasing sequence of their processing time, is $\frac{4} {3} - \frac{1} {3m}$. However, it is not allowed to reorder the sequence in the pure online setting. But if the jobs are arrived in nonincreasing order of their processing times, the performance of LS will be just the same as that of LPT. Above situation was reformulated as a semi-online variant by Seiden et al. [154]. They proved that LS is the optimal algorithm for P2 | decr | C _max . However, LS is no longer optimal when m ≥ 3, since there exists an algorithm with competitive ratio $\frac{5} {4}$ for m ≥ 4 and an optimal algorithm with competitive ratio $\frac{1+\sqrt{37}} {6}$ for m = 3 [43].

If the total processing time of all jobs P is known in advance, a lower bound $\frac{P} {m}$ on the optimal makespan is readily available, which will be of great help in designing algorithm with a better competitive ratio. Take the optimal algorithm reacting to two machines [111] for example. Jobs are successively assigned to M ₁ until there exists a crucial job, such that the load of M ₁ would exceed a threshold $\frac{4} {3} \cdot \frac{P} {2}$ if the crucial job is still assigned to M ₁; here, $\frac{4} {3}$ is the expected competitive ratio of the algorithm. Then, the crucial job is assigned to M ₂, and the remaining jobs will no longer have any negative effect on the competitive ratio. The core idea of the algorithm is to keep one machine lightly loaded so as to serve the long jobs which might present later. The significance of sum lies in the fact that it is impossible to determine the threshold without access to P.

For Pm | sum | C _max , Angelelli et al. [6] proposed an algorithm with competitive ratio $\frac{\sqrt{ 6}+1} {2} \approx 1.725$ and proved that the lower bound of the problem is 1. 565 for sufficiently large m. The lower bound was recently improved to 1. 585 by Albers and Hellwig [3]. By more careful classification according to the processing time of the jobs as well as the current load of the machines, Cheng et al. [41] designed an improved algorithm with competitive ratio $\frac{8} {5}$. They also showed that $\frac{3} {2}$ is a lower bound of the problem for any m ≥ 6. For the case of m = 3, the current best lower and upper bounds are $\frac{\sqrt{ 129}-3} {6} \approx 1.393$ and $\frac{27} {19} \approx 1.421$, respectively [9].

The semi-online variant opt is closely associated with the variant sum. In fact, many instances used to show the tightness of the competitive ratio of some algorithms satisfy ${C}^{{\ast}} = \frac{P} {m}$. However, the instance with ${C}^{{\ast}}> \frac{P} {m}$ does exist. Therefore, it is not easy to answer whether corresponding two problems regarding sum and opt variants have the same optimal bound. Nevertheless, Dósa et al. [54] proved the following result.

Lemma 3 ([54])

• (i) If ρ is a lower bound of Qm|opt|C_max, then the lower bound of Qm|sum|C_max is at least ρ.

• (ii) If there is an algorithm for Qm|sum|C _max with competitive ratio r, then there also exists an algorithm for Qm|sum|C _opt with competitive ratio at most r.

By Lemma 3, the algorithm for Pm | sum | C _max given in [41] can be modified to solve Pm | opt | C _max with at most the same competitive ratio $\frac{8} {5}$, which improves the former algorithm for Pm | opt | C _max with a competitive ratio of $\frac{13} {8}$ [14]. When the number of machines is small, another algorithm also given in [14] has a smaller competitive ratio of $\frac{5m-1} {3m+1}$. On the other hand, the lower bound of Pm | sum | C _max is no longer valid for Pm | opt | C _max . Though $\frac{4} {3}$ is clearly a lower bound of Pm | opt | C _max for any m ≥ 2 [14], no larger lower bound has been reported for m ≥ 3.

There are fewer results on the max variant. He and Zhang [97] presented an optimal algorithm for P2 | max | C _max with competitive ratio $\frac{4} {3}$. Note that for the max variant, not only the processing times of all jobs are no more than p _max , but also at least one job with processing time p _max will arrive sooner or later. Hence, the first job with processing time p _max , which is denoted as J _max , can be shifted to the beginning of the job sequence by assumption. Thus, the optimal algorithm given in [97] can be simplified by using above idea.

Algorithm PLS

• 1. Let J _max be scheduled on M ₁ from time 0 to p _max .

• 2. Assign the remaining jobs by LS rule.

Theorem 6

The competitive ratio of PLS is $\frac{4} {3}$ for P2|max|C _max.

Proof

If $\max \{L_{1},L_{2}\} \leq \frac{2} {3}P$, then $\frac{{C}^{PLS}} {{C}^{{\ast}}} \leq \frac{\max \{L_{1},L_{2}\}} { \frac{P} {2} } \leq \frac{4} {3}$ by (1). Otherwise,

$$\displaystyle\begin{array}{rcl} \max \{L_{1},L_{2}\} + (L_{1} + L_{2}) + \vert L_{1} - L_{2}\vert & =& 3\max \{L_{1},L_{2}\}> 2P = (L_{1} + L_{2}) \\ & & +\max \{L_{1},L_{2}\} +\min \{ L_{1},L_{2}\}. \end{array}$$

(6)

Since the remaining jobs are assigned by LS rule, $\vert L_{1} - L_{2}\vert \leq p_{max}$. Combining it with  (6), $\min \{L_{1},L_{2}\} < \vert L_{1} - L_{2}\vert \leq p_{max}$. Recall that J _max is assigned to M ₁, L ₁ ≥ p _max . Hence, L ₂ < p _max and thus no job other than J _max will be assigned to M ₁, which implies that PLS produces an optimal schedule.

However, for general m, no algorithm performing better than the best known algorithm for pure online model has been obtained. It is also unknown that whether the partial information is still valuable for sufficiently large m, since the effect of the information about the single job J _max tend to reduce as m increases.

As far as the problem of machine covering is concerned, the four semi-online variants differ hugely both in property and difficulty. Optimal algorithms for Pm | sum | C _min and Pm | max | C _min can be obtained, both having a competitive ratio m − 1 for m ≥ 3 [22, 166]. However, the research on Pm | opt | C _min seems to be much more difficult than that of $Pm\vert sum\vert C_{min}$. Azar and Epstein [12] proposed an algorithm with competitive ratio $2 - \frac{1} {m}$, which is optimal for m = 2, 3, 4. A more involved algorithm with competitive ratio $\frac{11} {6} \approx 1.834$ was given in [61]. The current best lower bound is $\frac{7} {4}$ for m > 4 [12] and $\frac{43} {24} \approx 1.791$ for sufficiently large m [61]. These bounds are far smaller than those for Pm | sum | C _min . For the problem Pm | decr | C _min , LS has a competitive ratio of $\frac{4m-2} {3m-1}$ [47] and is optimal for m = 2, 3 [96].

Tables 4 and 5 summarize the current best results of different semi-online variants on identical machines for arbitrary m and small number of m, respectively. As is shown in the table, different semi-online variants are diverse in value. In addition, optimal algorithm for two machines has almost all been found, whereas for three or more machines, nearly all problems are waiting to be answered, which is quite thought-provoking.

Table 4 Results of semi-online variants on arbitrary m identical machines

Table 5 Results of semi-online variants on a small number of identical machines

3.2.2 Two Uniform Machines

Similarly as pure online problems, the upper and lower bounds for most semi-online problems on two uniform machines are piece-wise rational or irrational functions of s. But the number of the pieces could be considerably large, often exceeding 10. There may be large difference among optimal algorithms for the same problem with different value of s, which make the analysis of these problems extremely difficult. Most results are obtained mainly by case by case analysis. Up till now, no universal or revolutionary method has been developed to handle these problems efficiently.

Among the four basic semi-online variants of Type I, decr is the only one which optimal bounds for all values of s ≥ 1 are obtained for both minimization and maximization problems. Based on the worst-case ratio of LPT for the offline version [133], Epstein and Favrholdt proved that LSc is optimal for the majority value of s. For the remaining two intervals which is close to 1 and nearby 2. 5 where LSc is not optimal, they designed three new algorithms and proved their optimality. Symmetrically, for Q2 | decr | C _min , LSs is also optimal except for two similar intervals of s, and new optimal algorithms have been proposed for these intervals [39]. The figures depicting two optimal bounds (as functions of s) bear some similarities (Fig. 2).

Fig. 2

The optimal bounds (thick) and competitive ratios of LS (dash) for Q2 | decr | C _max (left) and Q2 | decr | C _min (right)

The other two problems which optimal algorithms for any s ≥ 1 have been obtained are $Q2\vert sum\vert C_{min}$ and Q2 | opt | C _min . The optimal bound of Q2 | sum | C _min [163] is

$$\left \{\begin{array}{ll} \frac{s+2} {s+1}, &s \in [1,\sqrt{2}], \\ s, &s \in [\sqrt{2}, \frac{1+\sqrt{5}} {2} ], \\ \frac{{s}^{2}+s+1+\sqrt{5{s}^{4 } +6{s}^{3 } +3{s}^{2 } +2s+1}} {2s(s+1)},&s \in (\frac{1+\sqrt{5}} {2},\infty ),\end{array} \right.$$

while the optimal bound of Q2 | opt | C _min [66] is

$$\left \{\begin{array}{ll} \frac{s+2} {s+1}, &s \in [1,\sqrt{2}], \\ s, &s \in [\sqrt{2}, \frac{1+\sqrt{5}} {2} ], \\ \frac{2s+1} {s+1},&s \in (\frac{1+\sqrt{5}} {2},\infty ).\end{array} \right.$$

Note that the optimal bound of Q2 | sum | C _min is strict smaller than that of Q2 | opt | C _min for $s> \frac{1+\sqrt{5}} {2}$. The overall optimal bound of Q2 | sum | C _min is also strict less than that of Q2 | opt | C _min (See Fig. 3). These conclusions turn out to be opposite to both the results of Lemma 3 concerning problems with objective to minimize makespan and that of machine covering problems on m identical machines.

Fig. 3

Left: the optimal bound of Q2 | | C _max (thick) and the upper bounds (solid) and lower bounds (dash) of Q2 | max | C _max (bottom) and Q2 | eos | C _max (top). Right: the upper bounds (solid) and lower bounds (dash) of Q2 | sum | C _max (top) and Q2 | opt | C _max (bottom)

For the remaining four problems, there are still gaps between upper and lower bounds for some values of s, though ceaseless efforts have been put into narrowing the gap. The gaps of some problems seem to be small, but it is usually the case that the gap might appear exactly be the place where the analysis becomes toughest. For the sake of conciseness, only best known bounds will be listed in the following. General information of these bounds is summarized in Table 6 (also see Figs. 4 and 3). It can be seen that Q2 | sum | C _max and Q2 | opt | C _max are much more complicated than the corresponding machine covering problems. For Q2 | max | C _max , the effect of the information about the single job J _max declines when s is sufficiently large. There is a noteworthy fact that for majority makespan minimization problems, the overall bound is achieved at the point where the argument s values exactly the overall bound itself and lies in the interval [1. 2, 1. 5]. For machine covering problems, the overall bounds all achieve at s = ∞ except Q2 | sum | C _max .

Fig. 4

The optimal bounds (thick) of Q2 | sum | C _min (bottom) and Q2 | opt | C _min (top) and the upper bounds (solid) and lower bounds (dash) of Q2 | max | C _min (bottom) and Q2 | eos | C _min (top)

Table 6 General information and current status of upper and lower bounds on two uniform machines

The lower and upper bounds of Q2 | sum | C _max [54, 65, 137] are

$$\left \{\begin{array}{ll} \dfrac{3s + 1} {3s},&\mbox{ $s \in \left [1, \dfrac{5 + \sqrt{205}} {18} \approx 1.0732\right ]$,} \\ \dfrac{8s + 5} {5s + 5},&\mbox{ $s \in \left [\dfrac{5 + \sqrt{205}} {18}, \frac{1+\sqrt{31}} {6} \approx 1.0946\right ]$,} \\ \dfrac{2s + 2} {2s + 1},&\mbox{ $s \in \left [\dfrac{1 + \sqrt{31}} {6}, \frac{1+\sqrt{17}} {4} \approx 1.280\right ]$} \\ s, &\mbox{ $s \in \left [\frac{1+\sqrt{17}} {4}, \dfrac{1 + \sqrt{3}} {2} \approx 1.36603\right ]$} \\ \dfrac{2s + 1} {2s},&\mbox{ $s \in \left [\dfrac{1 + \sqrt{3}} {2},\sqrt{2} \approx 1.41421\right ]$} \\ \dfrac{3s + 5} {2s + 4},&s \in \left [\sqrt{2}, \dfrac{\sqrt{21}} {3} \approx 1.52753\right ] \\ \dfrac{3s + 3} {3s + 1},&\mbox{ $s \in \left [\dfrac{\sqrt{21}} {3}, \dfrac{5 + \sqrt{193}} {12} \approx 1.57437\right ]$} \\ \dfrac{4s + 2} {2s + 3},&\mbox{ $s \in \left [\dfrac{5 + \sqrt{193}} {12}, \dfrac{7 + \sqrt{145}} {12} \approx 1.5868\right ]$} \\ \dfrac{5s + 2} {4s + 1},&\mbox{ $s \in \left [\dfrac{7 + \sqrt{145}} {12}, \dfrac{9 + \sqrt{193}} {14} \approx 1.63509\right ]$} \\ c(s), &\mbox{ $s \in \left [\dfrac{9 + \sqrt{193}} {14},\sqrt{3}\right ]$} \\ \dfrac{s + 2} {s + 1}, &\mbox{ $s \in [\sqrt{3},\infty )$} \end{array} \right.$$

and

$$\left \{\begin{array}{ll} \dfrac{3s + 1} {3s}, &\mbox{ $s \in \left [1,x_{1} \approx 1.071\right ]$,} \\ \dfrac{7s + 6} {4s + 6}, &\mbox{ $s \in \left [x_{1}, \dfrac{1 + \sqrt{145}} {12} \approx 1.0868\right ]$,} \\ \dfrac{2s + 2} {2s + 1}, &\mbox{ $s \in \left [\dfrac{1 + \sqrt{145}} {12}, \dfrac{1 + \sqrt{17}} {4} \approx 1.280\right ]$} \\ s, &\mbox{ $s \in \left [\dfrac{1 + \sqrt{17}} {4}, \dfrac{1 + \sqrt{3}} {2} \approx 1.36603\right ]$} \\ \dfrac{2s + 1} {2s}, &\mbox{ $s \in \left [\dfrac{1 + \sqrt{3}} {2},x_{2} \approx 1.3915\right ]$} \\ \dfrac{s + \sqrt{29{s}^{2 } + 59s + 30}} {4s + 5}, &\mbox{ $s \in [x_{2},x_{3} \approx 1.5062]$} \\ \dfrac{\sqrt{36{s}^{4 } + 9{s}^{3 } - 32{s}^{2 } - 2s + 9} + 6{s}^{2} + 9s + 3} {9{s}^{2} + 7s},&\mbox{ $s \in [x_{3},x_{4} \approx 1.6932]$} \\ \dfrac{\sqrt{4{s}^{4 } + 8{s}^{3 } + {s}^{2 } + 4} + 2{s}^{2} + 3s + 2} {2{s}^{2} + 6s}, &\mbox{ $s \in [x_{4},\sqrt{3}]$} \\ \dfrac{s + 2} {s + 1}, &\mbox{ $s \in [\sqrt{3},\infty )$}, \end{array} \right.,$$

respectively, where $c(s) = \dfrac{\sqrt{{s}^{2 } {x}^{2 } + 4s(s + 1 - x)} + sx} {2s}$, x is a root of the equation $\dfrac{\sqrt{{s}^{2 } {x}^{2 } + 4s(s + 1 - x)} + sx} {2s} = \dfrac{s(2s + 2 - x)} {(s + 1)(x + 2)}$, $x_{1},x_{2},x_{3},x_{4}$ are the positive roots of

$$3{s}^{2}(9{s}^{2} - s - 5) = (3s + 1)(5s + 5 - 6{s}^{2}),$$

$$\frac{2s + 1} {2s} = \frac{s + \sqrt{29{s}^{2 } + 59s + 30}} {4s + 5},$$

$$\frac{s + \sqrt{29{s}^{2 } + 59s + 30}} {4s + 5} = \frac{\sqrt{36{s}^{4 } + 9{s}^{3 } - 32{s}^{2 } - 2s + 9} + 6{s}^{2} + 9s + 3} {9{s}^{2} + 7s},$$

$$\frac{\sqrt{36{s}^{4 } + 9{s}^{3 } - 32{s}^{2 } - 2s + 9} + 6{s}^{2} + 9s + 3} {9{s}^{2} + 7s}$$

$$= \frac{\sqrt{4{s}^{4 } + 8{s}^{3 } + {s}^{2 } + 4} + 2{s}^{2} + 3s + 2} {2{s}^{2} + 6s},$$

respectively.

The lower and upper bounds of Q2 | opt | C _max [54, 65, 137] are

$$\left \{\begin{array}{ll} \dfrac{3s + 1} {3s},&\mbox{ $s \in \left [1, \frac{5+\sqrt{205}} {18} \approx 1.0732\right ]$,} \\ \dfrac{8s + 5} {5s + 5},&\mbox{ $s \in \left [\frac{5+\sqrt{205}} {18}, \frac{1+\sqrt{31}} {6} \approx 1.0946\right ]$,} \\ \dfrac{2s + 2} {2s + 1},&\mbox{ $s \in \left [\frac{1+\sqrt{31}} {6}, \frac{1+\sqrt{17}} {4} \approx 1.280\right ]$} \\ s, &\mbox{ $s \in \left [\frac{1+\sqrt{17}} {4}, \dfrac{1 + \sqrt{3}} {2} \approx 1.36603\right ]$} \\ \dfrac{2s + 1} {2s},&\mbox{ $s \in \left [\frac{1+\sqrt{3}} {2},\sqrt{2} \approx 1.41421\right ]$} \\ \dfrac{3s + 5} {2s + 4},&\mbox{ $s \in \left [\sqrt{2}, \frac{\sqrt{21}} {3} \approx 1.52753\right ]$} \\ \dfrac{3s + 3} {3s + 1},&\mbox{ $s \in \left [\frac{\sqrt{21}} {3}, \frac{5+\sqrt{193}} {12} \approx 1.57437\right ]$} \\ \dfrac{4s + 2} {2s + 3},&\mbox{ $s \in \left [\frac{5+\sqrt{193}} {12}, \frac{7+\sqrt{145}} {12} \approx 1.5868\right ]$} \\ \dfrac{5s + 2} {4s + 1},&\mbox{ $s \in \left [\frac{7+\sqrt{145}} {12}, \frac{9+\sqrt{193}} {14} \approx 1.63509\right ]$} \\ \dfrac{7s + 4} {7s},&\mbox{ $s \in \left [\frac{9+\sqrt{193}} {14}, \frac{5} {3}\right ]$} \\ \dfrac{7s + 4} {4s + 5},&\mbox{ $s \in \left [\frac{5} {3}, \frac{5+\sqrt{73}} {8} \approx 1.89300\right ]$} \\ \dfrac{s + 1} {2}, &\mbox{ $s \in \left [\frac{5+\sqrt{73}} {8},\sqrt{3}\right ]$} \\ \dfrac{s + 2} {s + 1}, &\mbox{ $s \in [\sqrt{3},\infty )$} \end{array} \right.$$

and

$$\left \{\begin{array}{ll} \dfrac{3s + 1} {3s}, &\mbox{ $s \in [1,s_{8} \approx 1.071]$,} \\ \dfrac{7s + 6} {4s + 6}, &\mbox{ $s \in \left [s_{8}, \dfrac{1 + \sqrt{145}} {12} \approx 1.0868\right ]$,} \\ \dfrac{2s + 2} {2s + 1}, &\mbox{ $s \in \left [\dfrac{1 + \sqrt{145}} {12}, \dfrac{1 + \sqrt{17}} {4} \approx 1.280\right ]$} \\ s, &\mbox{ $s \in \left [\dfrac{1 + \sqrt{17}} {4}, \dfrac{1 + \sqrt{3}} {2} \approx 1.36603\right ]$} \\ \dfrac{2s + 1} {2s}, &\mbox{ $s \in \left [\dfrac{1 + \sqrt{3}} {2}, \dfrac{1 + \sqrt{21}} {4} \approx 1.39562\right ]$} \\ \dfrac{6s + 6} {4s + 5}, &\mbox{ $s \in \left [\dfrac{1 + \sqrt{21}} {4}, \dfrac{1 + \sqrt{13}} {3} \approx 1.535187\right ]$} \\ \dfrac{12s + 10} {9s + 7},&\mbox{ $s \in \left [\dfrac{1 + \sqrt{13}} {3}, \dfrac{5 + \sqrt{241}} {12} \approx 1.71035\right ]$} \\ \dfrac{2s + 3} {s + 3}, &\mbox{ $s \in \left [\frac{5+\sqrt{241}} {12},\sqrt{3}\right ]$} \\ \dfrac{s + 2} {s + 1}, &\mbox{ $s \in [\sqrt{3},\infty )$}, \end{array} \right.$$

respectively.

The lower and upper bounds of Q2 | max | C _max [23, 24, 128] are

$$\left \{\begin{array}{@{}ll@{}} \dfrac{2s + 2} {2s + 1}, &\mbox{ $s\,\in \left [1, \dfrac{1\,+\,\sqrt{17}} {4} \,\approx \,1.280\right ]$,} \\ s, &\mbox{ $s\,\in \left [\frac{1+\sqrt{17}} {4},\sqrt{2}\right ]$,} \\ \dfrac{1 + \sqrt{4{s}^{2 } + 1}} {2s}, &\mbox{ $s\,\in [\sqrt{2},x_{5} \approx 1.558]$} \\ \dfrac{s + 2} {s + 1}, &\mbox{ $s\,\in \,[x_{5},x_{6} \approx 2.292]$} \\ \dfrac{(s + 1)(9s + 5) -\sqrt{(s + 1)(-3{s}^{3 } + 7{s}^{2 } + 7s + 1)}} {2(s + 1)(3s + 2)},&\mbox{ $s\,\in \,[x_{6},x_{7} \approx 2.360]$} \\ \dfrac{s + \sqrt{{s}^{2 } + 4s}} {2s}, &\mbox{ $s\,\in \,[x_{7}, \dfrac{3 + \sqrt{17}} {2} \approx 3.56)$} \\ \dfrac{s + 1} {s}, &\mbox{ $s\,\in \left [\dfrac{3 + \sqrt{17}} {2},\infty \right.)$} \end{array} \right.$$

and

$$\left \{\begin{array}{ll} \dfrac{2s + 2} {2s + 1},&\mbox{ $s \in \left [1, \frac{1+\sqrt{17}} {4} \approx 1.280\right ]$,} \\ s, &\mbox{ $s \in \left [\frac{1+\sqrt{17}} {4},\sqrt{2}\right ]$,} \\ \dfrac{s + 2} {s + 1}, &\mbox{ $s \in [\sqrt{2},2]$} \\ \dfrac{3s + 2} {2s + 2},&\mbox{ $s \in [2,1 + \sqrt{3}]$} \\ \dfrac{s + 1} {s}, &\mbox{ $s \in [1 + \sqrt{3},\infty )$}, \end{array} \right.$$

respectively, where x ₅, x ₆, x ₇ are the roots of

$$2{s}^{4} + 2{s}^{3} - 6{s}^{2} - 5s + 3 = 0,$$

$$\displaystyle\begin{array}{rcl} 12{s}^{6}& & -{s}^{5} - 32{s}^{4} - 12{s}^{3} + 7{s}^{2} + s - 1 = (6{s}^{4} - 3{s}^{3} - 6{s}^{2} - 3s - 1) \\ & & \times \sqrt{(s + 1)(-3{s}^{3 } + 7{s}^{2 } + 7s + 1)}, \\ \end{array}$$

$$8{s}^{3} + 15{s}^{2} + 13s + 4 = (6{s}^{2} + 9s + 3)\sqrt{{s}^{2 } + 4s},$$

respectively.

The lower and upper bounds of Q2 | max | C _min [27, 129] are

$$\left \{\begin{array}{ll} \dfrac{s + 2} {s + 1}, &\mbox{ $s \in [1,\sqrt{2}]$,} \\ s, &\mbox{ $s \in \left [\sqrt{2}, \frac{1+\sqrt{5}} {2} \right ]$,} \\ \dfrac{s + 1} {s}, &\mbox{ $s \in \left [\frac{1+\sqrt{5}} {2},1 + \sqrt{2}\right ]$} \\ \dfrac{{s}^{2} + s + 1 + \sqrt{{s}^{4 } - {s}^{2 } + 2s + 1}} {{s}^{2} + 2s},&\mbox{ $s \in [1 + \sqrt{2},\infty )$} \end{array} \right.$$

and

$$\left \{\begin{array}{ll} \dfrac{s + 2} {s + 1}, &\mbox{ $s \in [1,\sqrt{2}]$,} \\ s, &\mbox{ $s \in \left [\sqrt{2}, \dfrac{1 + \sqrt{5}} {2} \right ]$,} \\ \dfrac{s + 1} {s}, &\mbox{ $s \in \left [\dfrac{1 + \sqrt{5}} {2},x_{8} \approx 2.148\right ]$} \\ \dfrac{s + 1 + \sqrt{5{s}^{2 } + 6s + 1}} {2(s + 1)}, &\mbox{ $s \in [x_{8},x_{9} \approx 3.836]$} \\ \dfrac{{s}^{2} + s + 1 + \sqrt{{s}^{4 } - {s}^{2 } + 2s + 1}} {{s}^{2} + 2s},&\mbox{ $s \in [x_{9},\infty )$}. \end{array} \right.$$

respectively, where x ₈, x ₉ are the positive roots of

$$\frac{s + 1} {s} = \frac{s + 1 + \sqrt{5{s}^{2 } + 6s + 1}} {2(s + 1)}$$

and

$$\frac{s + 1 + \sqrt{5{s}^{2 } + 6s + 1}} {2(s + 1)} = \frac{{s}^{2} + s + 1 + \sqrt{{s}^{4 } - {s}^{2 } + 2s + 1}} {{s}^{2} + 2s},$$

respectively.

3.2.3 Preemption

In regard to preemptive semi-online scheduling problems, there were some results on optimal algorithms [56, 67, 93, 94]. But breakthrough was not made until Ebenlendr and Sgall introduced the general framework for preemptive online scheduling, through which for the majority of semi-online variants, preemptive scheduling problems with the objective function of makespan can be solved. The optimal algorithm for these semi-online problems is identical with the optimal algorithm for the pure online problem; only the optimal bound needs to be recalculated by using the reformed linear programming (Eq. 4). However, as in the pure online case, there are still two points at issue. The first is that the analytically optimal bounds can hardly be obtained when m is large, even for the identical machines case. The second is that it is necessary for the algorithm to use idle times, and whether it is inevitable still remains unknown.

For Qm | pmtn, opt | C _max , there exists an algorithm which always produces an optimal schedule [58]. Similar result for two uniform machines was obtained by Epstein [65] before. Pm | pmtn, sum | C _max also has an algorithm with competitive ratio 1 [98], but it does not hold for Qm | pmtn, sum | C _max [59].

For Pm | pmtn, decr | C _max , Seiden et al. designed an optimal algorithm with competitive ratio $\max _{0\leq k\leq m} \frac{2{m}^{2}+2mk} {2{m}^{2}+{k}^{2}+k}$ [154]. The bound tends to $\frac{1+\sqrt{3}} {2}$ when $m \rightarrow \infty$, and the algorithm does not introduce idle times. Interestingly, it is also the optimal algorithm for Pm | pmtn, max | C _max . However, above two variants do not share optimal algorithm for uniform machines. The optimal bounds for Q2 | pmtn, decr | C _max [67] and Q2 | pmtn, max | C _max [94] are

$$\left \{\begin{array}{ll} \dfrac{3s + 3} {3s + 2}, &\mbox{ $1 \leq s \leq 3$}, \\ \dfrac{2{s}^{2} + 2s} {2{s}^{2} + s + 1},&\mbox{ $ s> 3$} \end{array} \right.$$

and $\frac{2{s}^{2}+3s+1} {2{s}^{2}+2s+1}$, respectively (Fig. 5). Moreover, no deterministic algorithm that never uses idle time can have the same competitive ratio as those use idle time when s > 2 for the former problem and $s> \frac{1+\sqrt{5}} {2}$ for the latter. But the corresponding lower and upper bounds are still unknown. More optimal bounds for different semi-online variants on m = 2, 3, 4 uniform machines can be found in [57, 59].

Fig. 5

Left: the optimal bounds of Q2 | pmtn | C _max (top), Q2 | max, pmtn | C _max (middle), and Q2 | decr, pmtn | C _max (bottom). Right: the optimal bounds of Q2 | pmtn | C _min (top), Q2 | max, pmtn | C _min (middle), and Q2 | decr, pmtn | C _min (bottom). Thick segments represent the intervals of s where idle time is necessary

Preemptive machine covering problems are much more complicated than corresponding makespan minimization problems. Due to the particularity of the definition of the objective, whether idle time is allowed should be taken into special consideration. The lower bound of Pm | pmtn, sum | C _min is $\frac{2m-3} {m-1}$, and there exists optimal algorithm with matched competitive ratio when m = 2, 3 [98]. For Q2 | pmtn, max | C _min , the optimal bound is $\frac{{s}^{2}+3s+1} {{s}^{2}+2s+1}$ [99]. However, the algorithm may introduce idle time before J _max arrives when s > s′ ≈ 1. 247. Here, s′ is the positive root of s ³ + s ² − 2s − 1 = 0. For Q2 | pmtn, decr | C _min , the optimal bound is

$$\left \{\begin{array}{ll} \dfrac{2s + 3} {2s + 2}, &\mbox{ $1 \leq s \leq 3$}, \\ \dfrac{{s}^{2} + 3s} {{s}^{2} + 2s + 1},&\mbox{ $ s> 3$}. \end{array} \right.$$

The optimal algorithm also needs to introduce idle time when assigning the first job if $s> \frac{\sqrt{6}} {2}$. Whether there exist algorithms for Q2 | pmtn, sum | C _min and Q2 | pmtn, opt | C _min that can always obtain the optimal schedule remains open (Fig. 5).

3.2.4 Other Results

Due to the difficulty in competitive analysis with multiple parameters, there is little study on non-preemptive semi-online problems on more than two uniform machines. Azar and Epstein [11] proposed algorithms with competitive ratio both m for Qm | opt | C _min and Qm | decr | C _min , respectively. These algorithms are optimal in the overall sense.

Even less is known about randomized algorithms for semi-online problems. Seiden et al. [154] proposed a barely random algorithm for P2 | decr | C _max with competitive ratio $\frac{8} {7}$, and no randomized algorithm can achieve a better competitive ratio.

3.3 Results on Basic Semi-online Models of Type II

3.3.1 Buffer

Evidently, it is more likely to design algorithm with a better performance if larger buffer is allowed. However, a buffer of size more than 1 is dispensable for two identical machines. That is to say, the lower bound of the problem with a buffer of size arbitrary large equals to the competitive ratio of an algorithm using a buffer of size only 1, which is $\frac{4} {3}$ [111, 187]. However, such phenomenon does not occur in the case where there are more than two machines or machines have different speeds. Therefore, the algorithm, as well as its corresponding competitive ratios, may be relevant to the size of the buffer. However, it seems impossible and also redundant to obtain optimal algorithms for any values of K. An alternate way is to find an algorithm satisfying super optimality. An algorithm with competitive ratio r which uses a buffer of size K is super optimal if no algorithm which uses a buffer of size arbitrary large can have a competitive ratio smaller than r, where K is a constant number. Clearly, if two algorithms are both super optimal, then the algorithm which uses a smaller buffer is better. However, research on the problem with a buffer of limited size is also of significance, since in practical application, the buffer size is limited by the cost, space, or other additional restrictions.

Main results on the buffer variant on arbitrary number of machines are summarized in Table 7. For Pm | buffer | C _max [63], Pm | pmtn, buffer | C _max [51], and Qm | buffer | C _min [73], super optimal algorithms have been obtained (in the overall sense for the last problem on uniform machines). Note that the super optimal bound for Pm | pmtn, buffer | C _max is not an increasing function of m, and the problem cannot be solved by using the general framework included in [59].

Table 7 Main results for the buffer variant on arbitrary number of machines

For Q2 | buffer | C _max , it is possible to obtain lower and upper bounds as functions of s [52]. A buffer of size 2 is enough to achieve the super optimal bound

$$\left \{\begin{array}{ll} \dfrac{{s}^{2} + 2s + 1} {{s}^{2} + s + 1},&\mbox{ $1 \leq s \leq \frac{1+\sqrt{5}} {2} $}, \\ \dfrac{{s}^{2}} {{s}^{2} - s + 1}, &\mbox{ $\frac{1+\sqrt{5}} {2} \leq s \leq 2$}, \\ \dfrac{s + 2} {s + 1}, &\mbox{ $s \geq 2$}. \end{array} \right.$$

Moreover, the optimal algorithm only needs a buffer of size 1 when s ≥ 2. However, when the buffer size reduces to 1, the optimal bound increases to $\dfrac{s + 2} {s + 1}$ for $\sqrt{2} < s < 2$, and there exists an algorithm with competitive ratio $\dfrac{2(s + 1)} {s + 2}$ while the lower bound is $\max \left \{s, \dfrac{{s}^{2} + 2s + 1} {{s}^{2} + s + 1} \right \}$ $1 \leq s \leq \sqrt{2}$.

3.3.2 Reassignment

Recall that the online over list model is typically characterized by the disallowance of reassignment. Since semi-online can be viewed as relaxation of online, it is natural to consider the situation where some jobs can be actually reassigned, which is also of realistic interest from an application perspective.

Variants in this category can be classified into two main types: sequential reassignment and final one-off reassignment. For the first type, reassignment can be done when every new job arrives, while for the second one, reassignment can only be done after all jobs have been assigned. For both cases, however, there should be some constraints on the reassignment; otherwise, the problem will reduce to an offline fashion.

In [160], Sanders et al. considered the proportional sequential reassignment model. When a job with processing time p _{​ j} arrives, some jobs with total processing time at most δp _{​ j} can be reassigned, where δ is the migration factor. Obviously, the competitive ratio r of an algorithm will decrease when δ increases. For identical machines with objective to minimize makespan, they designed algorithms for different value of δ. Some combinations of r and δ are $(r,\delta ) = \left (\frac{3} {2}, \frac{4} {3}\right )$, $(r,\delta ) = \left (\frac{3} {2} - \frac{1} {2m},2\right )$, and $(r,\delta ) = \left (\frac{4} {3}, \frac{5} {2}\right )$, respectively. They even obtained a family of online algorithms with competitive ratio $1 + \varepsilon$, where $\varepsilon> 0$ can be arbitrarily close to 0, while δ only depends exponentially on $\frac{1} {\epsilon }$. However, only for the case of m = 2 and δ = 1, an algorithm with competitive ratio $\frac{7} {6}$ has been proved to be optimal. For the machine covering problem, they obtained an algorithm with competitive ratio 2 for δ = 1.

Epstein and Levin [71] studied the above variants in a preemptive setting. Since a job can be split, the scheduler is allowed to reassign only part of the job. As a result, the migration factor does not reckon in the entire processing time but rather only the reassigned fraction of that. They presented a $(r,\delta ) = (1,1 - \frac{1} {m})$ algorithms for m identical machines, and the migration factor cannot be improved. For m uniform machines, a migration factor at least m − 1 is needed to obtain an algorithm with competitive ratio 1.

The restriction of reassigned job can be made through numbers of jobs instead of total processing times. That is at most G already assigned jobs can be reassigned when a new job arrives. Such variant can be called as sequential reassignment with quantitative restriction and is denoted reassignSQ. It is stronger than buffer since the former can simulate the latter by the following steps: First, temporarily set the jobs on any one of the machines as if they were stored in a buffer. And then reassign them on the machine as if jobs in the buffer were assigned. Contrariwise, a job can no longer be reassigned unless it is in the buffer. In brief, reassignSQ can do what buffer can, but not vice versa.

For Q2 | reassignSQ | C _max , Dósa et al. [55] proved that the optimal bound when G ≥ 2 coincides with the optimal bound of Q2 | buffer | C _max with buffer size K ≥ 2. However, when G = 1, the lower bound is

$$\left \{\begin{array}{ll} \dfrac{{s}^{2} + 2s + 1} {{s}^{2} + s + 1},&\mbox{ $1 \leq s \leq \dfrac{1 + \sqrt{5}} {2} $}, \\ \dfrac{s + 1} {2}, &\mbox{ $\dfrac{1 + \sqrt{5}} {2} \leq s \leq \sqrt{3}$}, \\ \dfrac{s + 2} {s + 1}, &\mbox{ $s \geq \sqrt{3}$}, \end{array} \right.$$

while the upper bound is

$$\left \{\begin{array}{ll} \dfrac{{s}^{2} + 2s + 1} {{s}^{2} + s + 1}, &\mbox{ $1 \leq s \leq s''$}, \\ \dfrac{s + \sqrt{5{s}^{2 } + 8s + 4}} {2(s + 1)},&\mbox{ $s'' \leq s \leq \sqrt{3}$}, \\ \dfrac{s + 2} {s + 1}, &\mbox{ $s \geq \sqrt{3}$}, \end{array} \right.$$

where s′′ is the root of equation s ³ − s − 1 = 0. The algorithm is not optimal when $s \in [s'',\sqrt{3}]$, and it is not identical with the bound of Q2 | buffer | C _max with buffer size K = 1 (Fig. 6).

Fig. 6

The optimal bounds (thick) of Q2 | | C _max (top), Q2 | reassignFE | C _max (middle), and Q2 | buffer | C _max with K ≥ 2 (also Q2 | reassignSQ | C _max with G ≥ 2 and Q2 | reassignFA | C _max with H ≥ 2) (bottom), the upper bounds (solid) and lower bounds (dash) of Q2 | buffer | C _max with K = 1 (also Q2 | reassignFA | C _max with H = 1) (top) and Q2 | reassignSQ | C _max with G = 1 (bottom)

Several final one-off reassignment models were first proposed by Tan and Yu [167]. One is that when all jobs have been assigned, at most H arbitrary jobs can be reassigned. The model is denoted as reassignFA. Tan and Yu proved that optimal bound for two identical machines with objective to minimize makespan is $\frac{4} {3}$, and the optimal algorithm only needs to reassign at most one job. Albers and Hellwig [4] generalized the model to m identical machines. Interestingly, the competitive ratio γ _m of the given algorithm is the same as that of the optimal algorithm for Pm | buffer | C _max , and the algorithm only reassigns at most $\left (\lceil \frac{2-\gamma _{m}} {{(\gamma _{m}-1)}^{2}} \rceil + 4\right )m$ jobs. Moreover, no algorithm can achieve a better competitive ratio if H = o(n). They also obtained algorithms with different value of r and H, such as $(r,H) = \left (\frac{5} {3},4m\right )$ and $(r,H) = \left (\frac{7} {4}, \frac{5} {2}m\right )$. For two uniform machines, the optimal bound of Q2 | reassignFA | C _max when H ≥ 2 is again the same as that of Q2 | buffer | C _max when K ≥ 2. Also, the optimal algorithm reassigns at most one job when s > 2. However, if only one job can be reassigned, the competitive ratio of the best known algorithm is also the same as that of Q2—buffer | C _max with buffer size K = 1, but it is larger than that of Q2 | reassignSQ | C _max with G = 1 (Fig. 6).

Another final one-off reassignment model is denoted reassignFE. After all jobs have been arrived, the last job assigned to each machine can be reassigned. For two identical machines with objective to minimize makespan, the optimal bound is $\sqrt{ 2}$ [167]. In fact, in such situation at most one job is needed to be reassigned [132]. Cao and Liu [25] generalized the result to two uniform machines and obtain the optimal bound

$$\left \{\begin{array}{ll} \sqrt{s + 1},&\mbox{ $1 \leq s \leq \frac{1+\sqrt{5}} {2} $}, \\ \frac{s+1} {s}, &\mbox{ $ s> \frac{1+\sqrt{5}} {2} $}. \end{array} \right.$$

Comparing it with the optimal bound of the pure online problem [72], reassignment is useless when $s> \frac{1+\sqrt{5}} {2}$(Fig. 6).

3.4 Results on Combined Semi-online Models

3.4.1 UB and LB

Though UB and LB are both valueless, their combination can be valuable. Such situation is very common in practice, since schedulers tend to estimate the processing time of jobs. However, it would be of little significance if the estimation is too rough to neglect the error. Hence, it is necessary to take influence of a parameter β, defined as $\beta = \frac{UB} {LB} \geq 1$, into consideration when dealing with competitive analysis. Main results of this variant are summarized in Table 8.

Table 8 Main results for the UB&LB variant

Note that LS remains optimal for any value of β for P2 | UB&LB | C _max and Pm | UB&LB | C _min . It is not true for P3 | UB&LB | C _max , though LS is also the optimal algorithm for P3 | | C _max . He and Dósa [92] proved the competitive ratio of LS is

$$\left \{\begin{array}{ll} \frac{2\beta +1} {3}, &\beta \in [1, \dfrac{3} {2}], \\ \frac{2\beta +3} {\beta +3}, &\mbox{ $\beta \in [\dfrac{3} {2},\sqrt{3}]$}, \\ \frac{\beta +1} {2}, &\mbox{ $\beta \in [\sqrt{3},2]$}, \\ 2 -\frac{1} {\beta },&\mbox{ $\beta \in [2,3]$}, \\ \frac{5} {3}, &\mbox{ $\beta \in [3,+\infty )$, }\end{array} \right.$$

and LS is optimal only when $\beta \in [1, \frac{3} {2}] \cup [\sqrt{3},2] \cup [6,+\infty )$. When β ∈ [2, 6], there exists an improved algorithm with competitive ratio

$$\left \{\begin{array}{ll} \dfrac{3} {2}, &\mbox{ $\beta \in \left [2, \frac{5} {2}\right ]$}, \\ \dfrac{4\beta + 2} {2\beta + 3}, &\mbox{ $\beta \in \left [\frac{5} {2},3\right ]$}, \\ \dfrac{5} {3} - \dfrac{1} {18}\min \left \{\dfrac{6-\beta } {18}, \dfrac{3} {103}\right \},&\mbox{ $\beta \in [3,6]$}.\end{array} \right.$$

Nevertheless, the new upper bound matches the lower bound of the problem only when $\beta \in [2, \frac{5} {2}]$. By the definition of the paradigm, the lower bound of the problem is obviously a nondecreasing function of β. For the remaining intervals of β where optimal algorithm has not been obtained, nonconstant lower bound of the problem, equaling to $\frac{7\beta +4+\sqrt{{\beta }^{2 } +8\beta +4}} {2\beta +2+2\sqrt{{\beta }^{2 } +8\beta +4}}$, can be found only in the situation where $\beta \in [\frac{5} {2},3]$. It is implied again from the results stated above that scheduling for two machines is of enormous difference in essence from that of three machines, while the latter is much more complicated.

A similar model of LB and max is proposed by Cao et al. [26]. It is assumed that $\frac{p_{max}} {\beta } \leq p_{j} \leq p_{max}$ for any j, and there always exists a job of processing time p _max . They proved that the optimal bound of P2 | LB&max | C _max is

$$\left \{\begin{array}{ll} \frac{\beta +1} {2}, &\mbox{ $\beta \in [1, \frac{4} {3}]$}, \\ \frac{4\beta +4} {3\beta +4},&\mbox{ $\beta \in [\frac{4} {3},\sqrt{2}]$}, \\ \frac{2\beta } {\beta +1}, &\mbox{ $\beta \in [\sqrt{2},2]$}, \\ \frac{4} {3}, &\mbox{ $\beta \in [2,+\infty )$. } \end{array} \right.$$

It is smaller than that of P2 | LB&UB | C _max for some value of β (Fig. 7).

Fig. 7

The optimal bounds of $P2\vert \mathcal{M}_{j}(GoS),LB\&UB\vert C_{max}$ (top), P2 | LB&UB | C _max (middle), and P2 | LB&max | C _max (bottom)

3.4.2 sum ∕ optand max ∕ UB

Angelelli et al. [7, 8] studied the problem P2 | sum&UB | C _max . Lower bounds as functions of $\gamma = \frac{2UB} {P}$ and several algorithms are proposed. Optimal bounds are achieved for majority value of γ (see Figs. 4–6 of [8]).

There are other papers considering the combination of sum(opt) and max. However, only overall bounds (the maximum bound among all combinations of P (or C ^∗) and p _max ) are obtained. For example, the optimal bound for Pm | sum&max | C _min [166] is

$$\left \{\begin{array}{ll} \dfrac{5} {4}, &m = 2, \\ \dfrac{3} {2}, &m = 3, \\ m - 2,&m \geq 4. \end{array} \right.$$

For the makespan minimization problem, optimal bounds are obtained only on a small number of machines (See Table 5). If preemption is allowed, optimal bound of Q3 | pmtn, sum&max | C _max for any combinations of P and p _max and any values of s _i , i = 1, 2, 3, can be obtained by using the general framework included in [59].

3.4.3 End of Sequence

Zhang and Ye [190] proposed an interesting semi-online variant, which was called “end of sequence” (eos for short) later [70]. It is known that the last job has the largest processing time, and the scheduler will be informed whether the current arrived job is the last one. Such variant can be viewed as a weaker version of the combined semi-online variant num&incr. Recall that both num and incr are valueless if they are considered solely. Thus, it is likely that eos is adjacent to the boundary between valuable semi-online variants and valueless ones.

Zhang and Ye [190] proved the optimal bounds of P2 | eos | C _max and P3 | eos | C _max are $\sqrt{ 2}$ and $\frac{3} {2}$, respectively. Note that the lower bound of P2 | eos | C _max does not hold for P2 | num&incr | C _max , the optimal bound for the latter problem remains open. Epstein and Ye considered the problems Q2 | eos | C _max and Q2 | eos | C _min . Optimal algorithms for almost all values of s are given [70] (Table 6, Figs. 3 and 4).

3.4.4 Miscellanies

The optimal bounds of P2 | decr&sum | C _max and P2 | decr&opt | C _max are both $\frac{10} {9}$ [65, 164]. Azar and Epstein [11] designed an algorithm for Qm | decr&opt | C _min with an overall competitive ratio 2, which is optimal in the overall sense.

By using the general framework included in [59], it can be proved that the overall optimal bound of Qm | pmtn, decr&sum | C _max is $\frac{12} {11}$ when m = 3 and $\frac{10} {9}$ when m = 4. For the problem Pm | pmtn, decr&buffer | C _max , Dósa and Epstein [51] proved that a buffer of size m − 1 is enough for an online algorithm to produce the optimal schedule, and the optimal bounds for any buffer size K < m − 1 is $\max _{0\leq \mu \leq m-K-1} \frac{2m(m+\mu )} {2{m}^{2}+2K\mu {+\mu }^{2}+\mu }$.

Dósa and He [53] studied two problems P2 | sum&buffer | C _max and P2 | sum&parallel(2) | C _max . They designed two optimal algorithms with competitive ratio $\frac{5} {4}$ and $\frac{6} {5}$, respectively. Min et al. [132] studied the problem P2 | sum&reassignFE | C _max and proposed an optimal algorithm with competitive ratio $\frac{5} {4}$.

3.5 Results on Disturbed Semi-online Models

In regard to disturbed semi-online model, there are fewer variants brought forward and results achieved. Study on problems with inexact partial information is much more difficult than the problem with exact partial information. One reason is that it is expected to find the upper and lower bound as functions of disturbance parameter α. If preemption is not allowed, only problems on two identical machines have been studied [165]. Related results are summarized in Table 9, and the detailed bounds are omitted here. If preemption is allowed, some research approaches and techniques of previous variants can be generalized to m identical machines or two uniform machines [106]. These results are summarized in Table 10. By using the general framework included in [59], even the optimal bound of Q3 | pmtn, inexact sum | C _max for any α and any values of s _i , i = 1, 2, 3 can be obtained. However, the known algorithms for the non-preemptive problem are not optimal for all values of α, and also there is no study on the problems of Pm | pmtn, inexact max | C _max , Pm | pmtn, inexact sum | C _max , Q2 | pmtn, inexact sum | C _max .

Table 9 Results for the non-preemptive problems with inexact partial information

Table 10 Results for the preemptive problems with inexact partial information

4 Online Over Time

Scheduling jobs that arrive over time is usually called online over time model. A number of researches are done with respect to the minimization problems for the three following classical objective functions: the makespan C _max , the total completion time $\sum _{j=1}^{n}C_{j}$, and the total weighted completion time $\sum _{j=1}^{n}w_{j}C_{j}$. For these objective functions, and some special cases, deterministic and randomized online algorithms are analyzed deriving different approximation guarantees. Results on online over time model are summarized in Table 11.

Table 11 The best known results on over time model

4.1 Single Machine Scheduling

4.1.1 Minimize the Total Completion Time

Problems of minimizing the total completion time on a single machine are extensively studied. Phillips et al. [142] presented a 2-competitive algorithm based on the optimal preemptive schedule, which can be found by the SRPT (Shortest Remaining Processing Time first) rule in polynomial time [148]. There is another 2-competitive algorithm, namely, delayed SPT (D − SPT), provided by Hoogeveen and Vestjens [100].

Algorithm D-SPT

At any time t a machine is idle and a job is available, choose a job with shortest processing time, say J _i . If there are more than one job with the same processing time, choose the one with the smallest release time. If p _i ≤ t, then process J _i ; otherwise, wait until time p _i or until a new job arrives, whichever happens first.

A very important idea in D − SPT algorithm is to shift the release time of jobs before scheduling, which was adopted by Stougie as well (cited in [176]). Lu et al. [127] generalized this idea and proposed a class of online algorithms that have the same competitive ratio of 2. Note that for this problem, it is shown by Hoogeveen and Vestjens [100] that any online algorithm must have a competitive ratio no smaller than 2, and hence, all above algorithms are best possible.

In online over time problems, it is commonly interesting to know whether or how much the competitive ratio would decrease if restarts are allowed. Vestjens [176] first showed a lower bound for the competitive ratio of any online algorithm. Later, Epstein and van Stee [69] improved the bound from 1. 112 to 1. 2108. The algorithm provided by van Stee and Poutré [175] indicates that the upper bound of the problem allowing restarts is at most $\frac{3} {2}$.

In contrast with online over list, only a few researches are found involving in semi-online variants, even though there are actually more semi-online models than those in online over list model. Tao et al. [170] investigated the problem with the knowledge of the upper and lower bounds of the processing times, UB&LB. A semi-online algorithm with competitive ratio $\frac{\sqrt{ 1+\beta (\beta -1)}+\beta -1} {\beta }$, as well as a lower bound

$$\Phi =\min _{s\geq 0}\max \left \{1 + s,\max _{k\in {Z}^{+}}\left \{1 + \frac{2k(\beta -1)} {2\beta (k + 1)s + 2\beta + {k}^{2} + 3k}\right \}\right \},$$

is proposed, where $\beta = \frac{UB} {LB} \geq 1$.

4.1.2 Minimize the Total Weighted Completion Time

Indeed, the weighted problem is more general and hence more difficult. Anderson and Potts [5] considered the delayed weighted shortest processing time rule (D − WSPT), which is a direct generalization of the D − SPT algorithm. By introducing a new proof technique, they showed that D − WSPT has a competitive ratio of 2 and therefore matches the known lower bound [100]. If restarts are allowed, the lower and upper bounds of this problem are 1. 2232 and 2, respectively [5, 69].

If preemption is allowed, unlike the unweighted version, Vestjens [176] showed that any preemptive algorithm must have a competitive ratio no smaller than 1. 0333. The lower bound is later improved to 1. 0730 by Epstein and van Stee [69]. Several algorithms are proved to be 2-competitive, including D − WSPT, P − WSPT, and WSRPT [130, 146]. Here, P − WSPT (preemptive WSPT) schedules at any time the job with the largest ratio of weight over processing time, while WSRPT (weighted shortest remaining processing time first) schedules at any time the job with the largest ratio of weight over remaining processing time. The instance given by Xiong and Chung [184] recently showed that the competitive ratio of WSRPT cannot be smaller than 1. 215. Though there is a big gap between the lower and upper bounds, developing an online algorithm with a competitive ratio better than 2 is a hard work. Breakthrough on this problem is finally made by Sitters [158]. By using a parameter c ≥ 1 and applying the P − WSPT rule with a restriction that a job cannot be preempted at time t if it can be completed before time ct, a class of online algorithms, namely, ONLINE(c), are obtained and shown to be c-competitive for any c ≥ ξ, where ξ ≈ 1. 57 is the real root of 2ξ ³ − 4ξ ² + 2ξ − 1 = 0. Hence, there exists a ξ-competitive algorithm for the preemptive problem.

If the release times of all jobs are known in advance, Hall et al. [89] showed that the problem has a lower bound of

$$\Psi =\max _{1\leq j\leq n}\min _{0\leq l\leq j-1}\frac{r_{l+1} + r_{l} + \sqrt{{(r_{l+1 } - r_{l } )}^{2 } + 4r_{j } r_{l+1}}} {2r_{l+1}}$$

where $r_{1} \leq r_{2}\cdots \leq r_{n}$ are the release times of all jobs. It can be proved that Ψ is in between $\frac{\sqrt{5}+1} {2}$ and 2. An online algorithm with matched competitive ratio is provided as well. Clearly, this variant will never be classified into online over list model. The semi-online problem UB&LB is considered by Tao et al. [171], where they presented an optimal algorithm with competitive ratio $1 + \frac{\sqrt{{4\beta }^{2 } +1}-1} {2\beta }$.

4.1.3 Randomized Algorithm and Lower Bound

Chekuri et al. [29] designed a randomized algorithm to minimize the total completion time with competitive ratio $\frac{e} {e-1}$. Their algorithm is intriguing as it beats the lower bound 2 for deterministic online algorithms [100]. Moreover, it is also optimal since its competitive ratio matches the randomized lower bound given by Stougie and Vestjens [162]. If restarts are permitted, Epstein and van Stee [69] proved that any randomized algorithm must have a competitive ratio at least 1. 1068. In the same paper, they also considered problems aiming at minimizing the total weighted completion time, where a lower bound 1. 0389 and a lower bound 1. 1161 for the preemptive problem and the problem allowing restarts are proposed, respectively. Regarding the upper bounds, Schulz and Skutella [149] provided a $\frac{4} {3}$-competitive randomized algorithm for the preemptive problem. Goemans et al. [83] presented a randomized algorithm with competitive ratio 1. 6853 for the problem allowing restarts.

4.2 Results on Parallel Machine Scheduling

4.2.1 Minimize the Makespan

For the makespan minimization problems, it should be emphasized that Shmoys et al. [157] have described a general method to use offline algorithms to obtain online algorithms for problems of online over time model. However, the method always produces a competitive ratio at least 2, even if the corresponding offline problem can be solved to optimality. In the same paper [157], Shmoys et al. proved a lower bound of $\frac{10} {9}$ for the problem on m identical machines. Chen and Vestjens [30] improved the lower bound to 1 + α for m ≥ 3 and to $\frac{5-\sqrt{5}} {2}$ for m = 2, where α ≈ 0. 3473 is the solution of α ³ − 3α + 1 = 0. Moreover, they proposed a simple algorithm, namely, online Longest Processing Time first (online LPT).

Algorithm Online LPT

At any time a machine becomes idle for processing, schedule an available job with the longest processing time.

The competitive ratio of online LPT is shown to be $\frac{3} {2}$. As far as we know, this is the best result on this problem except that in [138], where Noga and Seiden presented an improved algorithm SLEEP for m = 2. The difference between SLEEP and online LPT is that it might wait for some time even when there is an idle machine and an available job. The idea makes the algorithm optimal for m = 2 and, hence, beat online LPT. For further study, one may ask how to extend the algorithm and whether it can beat online LPT for a general number of machines. Nevertheless, there are still no such study by now. The randomized lower bounds on makespan minimization problem are studied in [162] and [138], where a lower bound of $4 - 2\sqrt{2}$ for a general number of machines and a lower bound of 1. 21207 for m = 2 are provided, respectively.

4.2.2 Minimize the Total (Weighted) Completion Time

For the problem of minimizing the total completion time, any deterministic algorithm is at least $\frac{21} {19} \approx 1.105$-competitive for the preemptive version and is at least 1. 309-competitive for the non-preemptive version [176, 184]. Moreover, any randomized algorithm is at least 1. 047-competitive for the preemptive version and is at least 1. 157-competitive for the non-preemptive version [176].

The simple and well-known SRPT algorithm plays a significant rule in preemptive scheduling of minimizing the total completion time. As we have seen before, it produces an optimal schedule for the single machine case [148]. The upper bound of SRPT for m identical machines was known to be 2 [142] for a long time until recently, Chung et al. [45] claimed that it is at most 1. 86. Shortly after that, Sitters [159] improved it to $\frac{5} {4}$.

For the preemptive problem of minimizing the total weighted completion time, 2-competitive online algorithm is found in [131]. The lower bound of the problem is proved to be $\frac{16-\sqrt{14}} {11} \approx 1.114$ [184]. For the non-preemptive version, a randomized algorithm with competitive ratio 2 as well as a deterministic algorithm with competitive ratio 2. 62 are obtained by Schulz and Skutellathe [150] and Correa and Wagner [46], respectively. The best known result for this objective is due to Sitters [159], who gave a deterministic algorithm with competitive ratio of 1. 791 + o(m) for both versions. Even applying the algorithm to unweighted problem, the competitive ratio remains the same, and the algorithm beats the previously best one with competitive ratio 2 [121]. If the number of machines is small, randomized algorithms with smaller competitive ratios are found in [46].

With respect to machines with different speeds, Liu and Lu [122] studied the two machine case. They presented a $\frac{\sqrt{ 5}+3} {2}$-competitive algorithm for the non-preemptive problem of minimizing the total completion time. If preemption is allowed, they gave an algorithm with competitive ratio of 2 to minimize the total weighted completion time. The non-preemptive algorithm in [122] for two uniform machines was extended to m uniform machines by Liu et al. [124], who established a competitive ratio of $\frac{\sqrt{ 4m-3}+3} {2}$.

5 Other Variants of Online Scheduling

5.1 Online Shop Scheduling

Researches on online shop scheduling are mainly focused on two or three machines. Chen and Woeginger [34] considered the two-machine open shop scheduling of online over list model. A 1. 875-competitive algorithm, as well as a lower bound $\frac{1+\sqrt{5}} {2} \approx 1.618$, was given. By restricting to permutation algorithms that always produce schedules with the same job sequence on both machines, the upper and lower bound can be further improved to 1. 848 and $\frac{23-2\sqrt{13}} {9} \approx 1.754$ [37], respectively. If preemption is allowed, Chen and Woeginger [34] presented a $\frac{4} {3}$-competitive algorithm for two machines, and a $\frac{27} {19}$-competitive algorithm for three machines was provided by Chen et al. [37]. Since the lower bound Γ _m of Pm | pmtn | C _max is also a lower bound of Om | pmtn | C _max [155], both algorithms are optimal. For two-machine flow shop and job shop problems, optimal algorithms were proven to have a competitive ratio of 2 by Chen and Woeginger [34].

If jobs arrive over time, Chen et al. [35] considered the two-machine open shop scheduling and proved that greedy-like algorithm has a competitive ratio $\frac{3} {2}$ and is optimal for non-preemptive version. Another algorithm, namely, SLICE, was shown to have a competitive ratio of $\frac{5} {4}$ and best possible for preemptive version. Liu et al. [125] further extended SLICE to the semi-online problem UB & LB. They proved the corresponding algorithm is $\frac{5\beta -1} {4\beta }$-competitive and matches the lower bound of the considered problem with $\beta = \frac{UB} {LB}$. Stougie and Vestjens [162] proved that 1. 25 is a randomized lower bound of O2 | r _j | C _max .

Recently, Zhang and Velde [188, 189] investigated problems with time lags, where the time lag of a job is defined as the maximum allowable delay between the completion time of the first and the start time of the second operation of the job. For these problems, it might benefit from allowing a machine to be idle while an operation is available for assignment. Such algorithms are called delay algorithms. The greedy-like algorithm has a competitive ratio 2 for two-machine open shop, job shop, and flow shop problems [188, 189]. However, the lower bound of delay algorithms is only proved to be $\sqrt{ 2}$ for open shop [189] and $\frac{1+\sqrt{5}} {2}$ for job shop or flow shop [188]. It is hopeful that a delay algorithm might beat the greedy algorithm in this model. Nevertheless, it is still an open question so far.

5.2 Batch Scheduling

In this problem, jobs arrive over time and can be processed together by a batch processing machine which can handle up to B jobs simultaneously. All jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. There are two models considered in the literature: the unbounded model where B = ∞ and the bounded model where B is bounded. For both models, problems of minimizing makespan on single or parallel identical machines are widely studied.

5.2.1 Unbounded and Bounded Model on a Single Machine

Suppose that there is a single batch processing machine, Deng et al. [48] and Zhang et al. [191] independently provided an optimal online algorithm (denoted as H ^∞) with competitive ratio $\frac{\sqrt{5}+1} {2}$.

Algorithm H ^∞

• 0. Set t = 0.

• 1. Let U(t) be the set of all unscheduled jobs available at time t and J _k be the job with the longest processing time in U(t), compute $\alpha _{k} = \frac{\sqrt{5}+1} {2} r_{k} + \frac{\sqrt{5}-1} {2} p_{k}$ and s = max{t, α _k }.

• 2. In the time interval [t, s], whenever a new job J _h arrives (at time t′) with p _h > p _k , then reset k = h and reset α _k and s accordingly. Let U(t′) = U(t) ∪{ J _h }. Reset t = t′.

• 3. At time s, schedule all jobs in U(s) as a single batch. If some new jobs arrives by s + p _k , let t = s + p _k ; otherwise, wait until a new job arrives and let t be the arrival time of such a job. Go to Step 1.

In fact, the lower bound $\frac{\sqrt{5}+1} {2}$ even holds when B = 2, and all jobs have only two distinct arrival times [191]. It seems much more challenging to derive optimal algorithms for the bounded model. When all jobs have exactly two distinct arrival time, Zhang et al. [191] gave an optimal one with competitive ratio $\frac{\sqrt{5}+1} {2}$. When jobs have arbitrary arrival times, Poon and Yu [145] obtained a $\frac{7} {4}$-competitive algorithm for B = 2. For the general B, we note there exist several 2-competitive algorithms. The first one is the greedy-like algorithm GRLPT, which was proposed by Lee and Uzsoy [113], and was shown to be 2-competitive by Liu and Yu [123]. Another two are due to Zhang et al. [191], which can be seen as a generalization of H ^∞. Finally, Poon and Yu [145] claimed all the FBLPT-based (full-batch longest processing time) algorithms, including the above three, can achieve the same competitive ratio of 2.

5.2.2 Unbounded and Bounded Model on Identical Machines

For batch scheduling on m parallel identical machines, researches are mostly focused on the unbounded model. Zhang et al. [191] gave a lower bound $\root{m + 2}\of{2}$ and an online algorithm PH(β _m ) with a competitive ratio 1 + β _m , where 0 < β _m < 1 is a solution to the equation $\beta _{m} = {(1 -\beta _{m})}^{m-1}$. In the same paper, the dense algorithms, which always immediately assign the currently available job to one idle machine as long as there are two or more idle machines, are proposed. Zhang et al. proved that the competitive ratio of any dense algorithm is no smaller than $\sqrt{ 2}$ and there exists one dense algorithm with competitive ratio $\frac{\sqrt{ 5}+1} {2}$. In a later paper [192], Zhang et al. gave an optimal algorithm with competitive ratio 1 + ξ _m for the special case that all jobs have unit processing time, where ξ _m is the positive solution of the equation ${(1 +\xi _{m})}^{m+1} =\xi _{m} + 2$.

When jobs have arbitrary processing times, the optimal algorithm for two-machine case has a competitive ratio of $\sqrt{ 2}$ [139, 173]. The optimal algorithm for the general case is due to Liu et al. [126] and Tian et al. [172] independently, who both proved the competitive ratio to be $1 + \frac{\sqrt{{m}^{2 } +4}-m} {2}$. In addition, Tian et al. [172] provided a dense algorithm with competitive ratio $\frac{3} {2}$ and showed it is best possible.

For the bounded model, Zhang et al. [192] observed that the optimal algorithm is $\frac{\sqrt{ 5}+1} {2}$-competitive if all jobs have equal processing times. Apart from this, neither algorithm results nor lower bounds are found in the literature.

5.2.3 Other Variants

There are some other discussions with respect to the online batch scheduling problems. One interesting variant is allowing to restart a batch, which means a running batch may be interrupted, losing all the work done on it, and the jobs in the interrupted batch are released and become independently unscheduled. Allowing restarts reduces the impact of a wrong decision. For the unbounded model on single machine, Fu et al. [78] showed the competitive ratio of any online algorithm is no less than $\frac{5-\sqrt{5}} {2}$ and gave a $\frac{3} {2}$-competitive algorithm. Shortly after that, Yuan et al. [185] gave a $\frac{5-\sqrt{5}} {2}$-competitive algorithm for the problem, and thus it is optimal. Fu et al. [79] studied the same problem with an additional assumption that any job cannot be restarted twice. Optimal algorithm with competitive ratio $\frac{3} {2}$ is obtained. In another paper [81], Fu et al. extended the result to identical machines, where a lower bound of 1. 298, as well as a $\frac{1+\sqrt{3}} {2}$-competitive online algorithm, was given.

Nong et al. [140] introduced job families to the batch scheduling problem, which means jobs from different families cannot be processed in the same batch. Online algorithms with competitive ratio 2 are presented for both bounded and unbounded models on single machine. Besides, they showed that the algorithm is best possible for the unbounded model in the sense that jobs consist of an infinite number of families. For the bounded model, there is no online algorithm with competitive ratio smaller than $\max \{ \frac{2B} {B+1}, \frac{1+\sqrt{5}} {2} \}$. Fu et al. [80] revisited the unbounded model and gave a best possible algorithm with competitive ratio $\frac{\sqrt{17}+3} {4}$ for the special case of two families of jobs.

Yuan et al. [186] and Li et al. [119] studied a lookahead semi-online model. Yuan et al. [186] considered the unbounded problem on a single batch machine. With the information of the next longest job at any time t, they presented a best possible online algorithm with competitive ratio $\frac{5-\sqrt{5}} {2}$. If jobs are of unit length and an online algorithm can foresee all the jobs that will arrive in the time segment (t, t + β] at any time t, Li et al. [119] presented a best possible online algorithm for the unbounded problem on m parallel-batch machines.

Chen et al. [38] considered a batch scheduling problem on single machine to minimize the total weighted completion times of jobs. They developed a linear time online algorithm with competitive ratio of $\frac{10} {3}$ for the unbounded model and an efficient algorithm with competitive ratio 4 + ε for any ε > 0 for the bounded model. Also, they observed that there exists a 2. 89-competitive and a (2. 89 + ε)-competitive randomized algorithm for unbounded and bounded models, respectively.

5.3 Online Scheduling with Machine Eligibility

Online scheduling with machine eligibility constraints has received much attention in recent years. Unlike the classical parallel machine scheduling, job J _j cannot be processed on any one among the machine set $\mathcal{M}$ in this model. Instead, it has a specific set $\mathcal{M}_{j} \subseteq \mathcal{M}$ that can be assigned to. Set $\mathcal{M}_{j}$ is so-called the eligible processing set of job J _j . Depending on the structure of $\mathcal{M}_{j}$, j = 1, ⋯, n, there are five classes of eligibility constraints that have been studied extensively [116]:

• 1. Arbitrary eligible processing sets

• 2. Tree-hierarchical processing sets

• 3. Grade of Service (GoS) processing sets

• 4. Interval processing sets

• 5. Nested processing sets.

With tree-hierarchical processing sets, each machine is represented by a node, and the nodes are connected in the form of a rooted tree. Any job assignable to a node is also assignable to the node’s ancestors in the tree. The GoS processing set structure can be seen as a special case of the tree-hierarchical processing set structure where the rooted tree actually forms a chain. Problems with a GoS processing set are also called online hierarchical scheduling in the literature. With regard to interval processing sets, job J _j is associated with two integers a _j and b _j ≥ a _j such that $\mathcal{M}_{j} =\{ M_{a_{j}},M_{a_{j}+1},\cdots \,,M_{b_{j}}\}$. A special case of interval processing set structure is a nested processing set structure, where, for any pair of jobs J _j and J _k , we either have $\mathcal{M}_{j} \subseteq \mathcal{M}_{k}$ or $\mathcal{M}_{k} \subseteq \mathcal{M}_{j}$ or $\mathcal{M}_{j} \cap \mathcal{M}_{k} = \varnothing$. Clearly, the GoS processing set structure is also a special case of nested processing set structure.

Problems with one of the above classes of eligibility constraints will be denoted as “$\mathcal{M}_{j}$,” “$\mathcal{M}_{j}(tree)$,” “$\mathcal{M}_{j}(GoS)$,” “$\mathcal{M}_{j}(interval)$” and “$\mathcal{M}_{j}(nested)$” in the middle field of the three-field notation, respectively. It is clear that P | | C _max (Q | | C _max ) is a special case of $P\vert \mathcal{M}_{j}\vert C_{max}$ ($Q\vert \mathcal{M}_{j}\vert C_{max}$) with $\mathcal{M}_{j} = \mathcal{M}$ for all J _j , while $R\vert \mathcal{M}_{j}\vert C_{max}$ is a special case of R | | C _max . However, in the rest of this subsection, we will mostly consider the identical machine environment, unless stated otherwise.

5.3.1 Online Over List

For arbitrary eligibility, Azar et al. [13] contributed the first result. They consider a greedy algorithm, namely, AW, as follows: When a job arrives the algorithm assigns it to an eligible machine that has the smallest current load among all eligible machines. The competitive ratio of AW is shown to be at most $\lceil \log _{2}m\rceil + 1$, and the lower bound is proved to be at least $\lceil \log _{2}(m + 1)\rceil$. Hwang et al. [102] improved the analysis of AW and obtained a slightly smaller competitive ratio of log₂ m + 1. The best known upper and lower bounds for this problem are found by Lim et al. [120] recently. They showed that AW has a competitive ratio no greater than $EU_{m} = \lfloor \log _{2}m\rfloor + \frac{m} {{2}^{\lfloor \log _{2}m\rfloor }}$, and the lower bound of the problem is EL _m , where EL ₁ = 1 and

$$EL_{m} = EL_{\theta _{m}} + \frac{1} {\lfloor \frac{\theta _{m}} {m-\theta _{m}}\rfloor },\theta _{m} =\mathrm{ argmax}_{\lfloor \frac{m} {2} \rfloor \leq i\leq m-1}\left \{EL_{i} + \frac{1} {\lfloor \frac{i} {m-i}\rfloor }\right \}.$$

The gap between the two bounds does not exceed 0. 1967 and AW is optimal when the number of machines can be written as a sum of two powers of 2. Lee et al. [114] proved the optimal bound of $Q2\vert \mathcal{M}_{j}\vert C_{max}$ is $1 +\min \{ s, \frac{1} {s}\}$. Note that for $Q2\vert \mathcal{M}_{j}\vert C_{max}$, the index of M ₁ and M ₂ cannot be reordered, and thus the speed ratio s can be an arbitrary positive number.

Bar-Noy et al. [16] analyzed online scheduling problem subject to tree-hierarchical eligibility. A 5-competitive online algorithm is proposed. Furthermore, if jobs are of unit size, then the competitive ratio can be improved to 4. Randomized algorithms are also proposed, where the competitive ratios are shown to be e + 1 and e, respectively. A lower bound of $1 + \frac{1} {2}\lfloor \log _{2}m\rfloor$ for $Pm\vert \mathcal{M}_{j}(nested)\vert C_{max}$ was given in [120].

There is a large number of researches discussing problems with a GoS eligibility, since it is very natural and has application in the service industry [103]. In [16], Bar-Noy et al. gave an algorithm with competitive ratio e + 1 for the general problem $P\vert \mathcal{M}_{j}(GoS)\vert C_{max}$ and showed that it is e-competitive if either jobs have unit size or can be fractionally processed. Moreover, they proved a lower bound of e for the fractional assignment case. However, the lower bound is valid only in the case when the number of machines tends to infinity. If the number of machines is fixed, Tan and Zhang [169] proposed an improved algorithm with competitive ratio GU _m and lower bound GL _m for the fractional assignment case; both are based on the solutions of mathematical programming. The algorithm can be modified to solve the general problem $Pm\vert \mathcal{M}_{j}(GoS)\vert C_{max}$ by using the same technique included in [16]. When the number of machines is small, algorithms for the general problem can be further improved. For m = 5 and 4, Tan and Zhang [169] proposed two algorithms with competitive ratios of 2. 610 and $\frac{7} {3}$, respectively. Lim et al. [120] improved the two results to 2. 501 and 2. 294. For m = 3, Zhang et al. [193] showed that there exists an optimal algorithm with competitive ratio 2. For m = 2, Park et al. [141] and Jiang et al. [109] independently proposed an optimal algorithm with competitive ratio $\frac{5} {3}$. If machines have different speeds, the optimal bound

$$h_{1}(s) = \left \{\begin{array}{ll} \min \{1 + s, \frac{2+2s+{s}^{2}} {1+s+{s}^{2}} \},&\mbox{ $0 < s \leq 1$,} \\ \min \{\frac{1+s} {s}, \frac{1+3s+{s}^{2}} {1+s+{s}^{2}} \}, &\mbox{ $1 \leq s < \infty $,} \end{array} \right.$$

of $Q2\vert \mathcal{M}_{j}(GoS)\vert C_{max}$ was given by Tan and Zhang [169] (Fig. 8).

Fig. 8

The optimal bounds of $Q2\vert \mathcal{M}_{j}\vert C_{max}$, $Q2\vert \mathcal{M}_{j}(GoS)\vert C_{max}$, $Q2\vert \mathcal{M}_{j}(GoS)$, pmtn | C _max , and $Q2\vert \mathcal{M}_{j}(GoS)$, frac | C _max (from top to bottom)

If preemption is allowed, Jiang et al. [109] designed a $\frac{3} {2}$-competitive algorithm for the problem $P2\vert \mathcal{M}_{j}(GoS)$, pmtn | C _max and showed that it is optimal if idle time is not allowed. For general m, Dósa and Epstein [50] proved that $\frac{2m} {m+1}$ is a lower bound even if idle time is allowed. An algorithm for three machines with matched competitive ratio was also given. In the same paper, they also studied the problem $Q2\vert \mathcal{M}_{j}(GoS),pmtn\vert C_{max}$. An online algorithm with competitive ratio

$$h_{2}(s) =\max \left \{ \frac{{(1 + s)}^{2}} {1 + s + {s}^{2}}, \frac{s{(1 + s)}^{2}} {1 + {s}^{2} + {s}^{3}}\right \}$$

is proposed and is shown to be optimal. Both algorithms need to introduce idle time. For $Q2\vert \mathcal{M}_{j}(GoS),frac\vert C_{max}$, Chassid and Epstein [28] designed an optimal algorithm with competitive ratio $\frac{{(1+s)}^{2}} {1+s+{s}^{2}}$ (Fig. 8).

For semi-online scheduling, Park et al. [141] studied the problem on two machines with the knowledge of the total processing time of jobs, where an optimal algorithm with competitive ratio $\frac{3} {2}$ is presented. Wu et al. [183] considered two semi-online problems on two machines. The first one is known the optimal makespan, for which they showed an optimal algorithm with competitive ratio $\frac{3} {2}$. The second is known the maximum processing time, for which an algorithm with competitive ratio $\frac{\sqrt{5}+1} {2}$, as well as a matched lower bound, is given. Liu et al. [125] considered the semi-online problem on two machines where upper and lower bounds on the processing time of jobs are known in advance. An online algorithm, as well as a lower bound of the problem, was presented. Optimal bound of the problem

$$h_{3}(\beta ) = \left \{\begin{array}{llll} \frac{2\beta +1} {\beta +1}, &\mbox{ $1 \leq \beta < \frac{\sqrt{5}-1} {2} $,} \\ \frac{\sqrt{5}+1} {2},&\mbox{ $\frac{\sqrt{5}+1} {2} \leq \beta < \frac{3\sqrt{5}-1} {2} $,} \\ \frac{\beta +2} {3}, &\mbox{ $\frac{3\sqrt{5}-1} {2} \leq \beta < 3$,} \\ \frac{5} {3}, &\mbox{ $r \geq 3$,} \end{array} \right.$$

is given by Jiang and Zhang [107], where $\beta = \frac{UB} {LB}$ (Fig. 7).

There are several researches considering problems with two GoS levels (denoted as 2GoS). In this problem, jobs that can be processed on first k machines are called high level and the other jobs which can run on all m machines are called low level. Jiang [104] first showed that the AW algorithm is at least $(4 - \frac{1} {m})$-competitive and then provided an online algorithm with a competitive ratio of $\frac{12+4\sqrt{2}} {7} \approx 2.522$. Later, Zhang et al. [194] improved the result to $1 + \frac{{m}^{2}-m} {{m}^{2}-km+{k}^{2}} < \frac{7} {3}$.

For machine covering problems, Chassid and Epstein [28] proved that no algorithm can have a constant competitive ratio even for the most special problem $Q2\vert \mathcal{M}_{j}(GoS)\vert C_{min}$. For problems $Q2\vert \mathcal{M}_{j}(GoS),frac\vert C_{min}$ and $Q2\vert \mathcal{M}_{j}(GoS),sum\vert C_{min}$, they gave optimal bounds of $\frac{2s+1} {s+1}$ and $\max \{1,s\} + \frac{1} {s}$, respectively. Main results on online over list scheduling with machine eligibility are summarized in Tables 12–14.

Table 12 Results of online over list scheduling with machine eligibility on two identical and uniform machines

Table 13 Results of online over list scheduling with machine eligibility on a small number of identical machines

Table 14 Main results on online over list scheduling with machine eligibility on general number of machines

5.3.2 Online Over Time

In contrast with problems of online over list, there are very few results concerning problems of online over time. Lee et al. [115, 116] considered the problems allowing restart or preemption of jobs. Various lower bounds, as well as a full study on two machines, are given. They also observed that the general method introduced by Shmoys et al. [157] that uses offline algorithms to obtain online algorithms for problems with job release times can work for scheduling with machine eligibility as well [116], although it produces algorithms with competitive ratio at least 2. All related results are summarized in Table 15.

Table 15 Main results on online over time scheduling with machine eligibility

Wang et al. [178] introduced another interesting problem with respect to scheduling with GoS eligibility, which is so-called online service scheduling. The problem arises from the service industry where customers (jobs) are classified as either “ordinary” or “special.” Ordinary customers can be served on any service facility (machines), while special customers can be served only on a flexible service facility. The difference between their model and the problem with two GoS levels is that customers arrive over time and the order of the assignment should be consistent with the order of arrival time of jobs in the same class. For several service policies used in practice, Wang et al. [178] and Wang and Xing [177] analyzed and compared their performance in the sense of competitive ratios.

6 Conclusion

This chapter surveyed different paradigms of online scheduling, including online over list and online over time, and gave a relatively complete picture to the semi-online scheduling problem. Most of detailed algorithms and proofs are not given in the chapter; please refer to the reference for more details. Online and semi-online scheduling is relatively young when compared to offline scheduling. Yet they have generated tremendous interest and promise to have more results in the future.

7 Cross-References

Advances in Scheduling Problems

Greedy Approximation Algorithms

Job Shop Scheduling with Petri Nets