Online scheduling on an unbounded parallel-batch machine to minimize the weighted makespan

Abstract

In this paper we study the online over-time scheduling on an unbounded parallel-batch machine to minimize the weighted makespan. First, we show that the general problem has a low bound 2 and then design a 4-competitive online algorithm. Furthermore, we consider a special case in which the jobs have agreeable processing times and weights. When all jobs have the same weights (the task is to minimize the makespan), an online algorithm with the best possible competitive ratio $\frac{\sqrt{5}+1}{2}\approx 1.618$ has been established in the literature. We show that, after a slightly modification, this known online algorithm also has the best possible competitive ratio $\frac{\sqrt{5}+1}{2}\approx 1.618$ for our problem. Finally, we introduce limited restarts into the above special case and present an online algorithm with a better competitive ratio $\frac{11}{7}\approx 1.571$.

Introduction

Parallel-batch scheduling, which was first introduced in Lee et al. (1992), has become a fast developing area of scheduling research in the past few decades. According to Lee et al. (1992), parallel-batch scheduling is motivated by burn-in operations in semi-conductor manufacturing. In this model, we have a parallel-batch machine which can process several jobs as a batch at the same time, as long as its batch capacity is not exceeded. We use b to denote the batch capacity. If $b=\infty$, the parallel-batch machine is called unbounded; and if $b<\infty$, it is called bounded. The processing time of a batch is equal to the longest processing time of the jobs in this batch, and all the jobs in this batch have the same starting time and the same completion time. In this paper, we only consider schedules on an unbounded parallel-batch machine, and hence, $b=+\infty$.

Online scheduling is also a hot topic in scheduling research. In the online scheduling, we do not know any information of future jobs in advance. The quality of an online algorithm is usually evaluated by its competitive ratio. Suppose that A is an online algorithm for solving a given scheduling problem. For an instance I of this scheduling problem, A(I) and OPT(I) are used to denote the objective function values obtained by the algorithm A and an optimal off-line schedule on instance I, respectively. The online algorithm A is called $\rho$-competitive if $A(I)\le \rho OPT(I)$ holds for every instance I. The competitive ratio ${\rho }_A$ of A is defined as the minimum value of $\rho$ such that A is $\rho$-competitive. If there is no other online algorithm which has a competitive ratio of less than ${\rho }_A$, then we say that A is a best possible online algorithm.

Let $\mathcal{J}=\{J_1,J_2,\cdots ,J_n\}$ be a set of jobs to be scheduled on a parallel-batch machine. For a schedule $\sigma$ of $\mathcal{J}$, we use $C_j(\sigma )$ to denote the completion time of each job $J_j\in \mathcal{J}$. The makespan (i.e., the maximum completion time of the jobs) under schedule $\sigma$ is defined by $C_{max}(\sigma )=max\{C_j(\sigma ):j=1,2,\cdots ,J_n\}$. The weighted makespan (i.e., the maximum weighted completion time of the jobs) under schedule $\sigma$ is defined by $W{C}_{max}(\sigma )=max\{w_j{C}_j(\sigma ):j=1,2,\cdots ,J_n\}$. Notice that $C_{max}$ is widely studied in the literature. However, as an extension of makespan, the weighted makespan $W{C}_{max}$ is relatively less studied in the literature. In the off-line setting, research for the objective function $W{C}_{max}$ can be found in Feng and Yuan (2007), Oron et al. (2015), and Yuan et al. (2020).

There are rich achievements on the online scheduling in the literature. Here we mainly review some results on the objective functions $C_{max}$ or $W{C}_{max}$. Zhang et al. (2001) and Deng et al. (2003) gave the same best possible online algorithm with the competitive ratio $\frac{1+\sqrt{5}}{2}\approx 1.618$ for problem $1|\text{online},r_j,\text{p-batch},b=\infty |C_{max}$. For problem $Pm|\text{online},r_j,\text{p-batch},b=\infty |C_{max}$, Tian et al. (2009) and Liu et al. (2012) independently provided their own best possible online algorithms with the competitive ratio $1+{\alpha }_m$, where ${\alpha }_m$ is the positive root of the equation ${\alpha }_m^2+m{\alpha }_m=1$.

For problem $1|\text{online},r_j|W{C}_{max}$, Li (2015) presented a lower bound 2 and an online algorithm with the competitive ratio 3. For the same problem, Chai et al. (2018) further provided two best possible online algorithms with the competitive ratio 2. For problem $P|\text{online},r_j,p_j=p|W{C}_{max}$, Li (2015) presented a best possible online algorithm with the competitive ratio $\frac{1+\sqrt{5}}{2}$. Li and Chai (2018) further studied the more general problem $P|\text{online},r_j,p_j=p,\text{p-batch},b<\infty |W{C}_{max}$ and provided a best possible online algorithm with the competitive ratio $\frac{1+\sqrt{5}}{2}$ and a best possible dense algorithm with the competitive ratio 2.

Due to the lack of the information of future jobs, an online algorithm often makes some wrong decisions. To avoid these wrong decisions, an effective way is to allow restarts. This means that, if an urgent job arrives while the machine is still busy, then we can break off the processing of the current job and start to process the urgent one. Clearly, allowing restarts can reduce the impact of the wrong decisions. However, it also brings another disadvantage, i.e., the previous processing of the current job is wasted.

To the best of our knowledge, van den Akker et al. (2000) introduced the conception of “restarts” into online scheduling. For problem $1|\text{online},r_j,\text{p-batch},b=\infty ,\text{restarts}|C_{max}$, Fu et al. (2007) provided a lower bound $\frac{5-\sqrt{5}}{2}\approx 1.382$ and presented an online algorithm with the competitive ratio $\frac{3}{2}$. For the same problem, Yuan et al. (2011) further provided a best possible online algorithm with the competitive ratio $\frac{5-\sqrt{5}}{2}$. Limited restarts were first introduced by Fu et al. (2008), which mean that any job can be restarted only once. For problem $1|\text{online},r_j,\text{p-batch},b=\infty ,\text{L-restart}|C_{max}$, Fu et al. (2008) gave a best possible online algorithm with the competitive ratio $\frac{3}{2}$.

In this paper, we study the online (over-time) scheduling on an unbounded parallel-batch machine for minimizing the weighted makespan. First, we show that the general problem has a low bound 2 and then design a 4-competitive online algorithm. Furthermore, we consider a special case in which the jobs have agreeable processing times and weights. When all jobs have the same weights (the task is to minimize the makespan), an online algorithm with the best possible competitive ratio $\frac{\sqrt{5}+1}{2}\approx 1.618$ has been established in the literature. We show that, after a slightly modification, this known online algorithm also has the best possible competitive ratio $\frac{\sqrt{5}+1}{2}\approx 1.618$ for our problem. Finally, we introduce limited restarts into the above special case and present an online algorithm with a better competitive ratio $\frac{11}{7}\approx 1.571$.

The rest of this paper is organized as follows. In Sect. 2, we formulate the problem studied in this paper. In Sect. 3, we study the general online scheduling problem. In Sect. 4, we consider the special online scheduling problem without restarts. In Sect. 5, we study the special online scheduling with limited restarts. Finally, some conclusions and future research are provided in Sect. 6.

Problem formulation

In this paper, we consider the online (over-time) scheduling on an unbounded parallel-batch machine to minimize the weighted makespan. This problem can be stated as follows: There are n jobs $J_1,J_2,\cdots ,J_n$ which should be scheduled on an unbounded parallel-batch machine. Each job $J_j$ has an arrival time $r_j$, a processing time $p_j$ and a weight $w_j$. The jobs arrive online over time, and so, the processing time $p_j$ and weight $w_j$ of job $J_j$ become known at its arrival time $r_j$. The weighted makespan of a schedule $\pi$ of the n jobs is given by $W{C}_{max}(\pi )=max\{w_j{C}_j(\pi ):j=1,2,\cdots ,n\}.$ Then this online scheduling problem can be denoted by

1

$$\begin{array}{c}\hfill 1|\text{online},r_j,\text{p-batch},b=\infty |W{C}_{max}.\end{array}$$Furthermore, we consider a special case in which all jobs have agreeable processing times and weights in our problem. That is, $p_i<p_j$ implies $w_i\le w_j$. This assumption for processing times and weights is also called agreeability condition in this paper. Then the online scheduling problem is denoted by

2

$$\begin{array}{c}\hfill 1|\text{online},r_j,\text{agreeable,}\text{p-batch},b=\infty |W{C}_{max}.\end{array}$$We also introduce limited restarts into the above special case, the corresponding problem is denoted by

3

$$\begin{array}{c}\hfill 1|\text{online},r_j,\text{agreeable,}\text{p-batch},b=\infty ,\text{L-restart}|W{C}_{max}.\end{array}$$For convenience, we use ${\beta }^{\ast }$ to indicate the items “$r_j$, agreeable, p-batch, $b=\infty$” in the $\beta$-field. Then the two problems (2) and (3) can be shortly denoted by $1|\text{online},{\beta }^{\ast }|W{C}_{max}$ and $1|\text{online},{\beta }^{\ast },\text{L-restart}|W{C}_{max}$, respectively.

The general online scheduling problem

In this section, we consider the general problem in (1). We show that this problem has a low bound 2 and then design a 4-competitive online algorithm.

Lemma 3.1

The problem in (1) has a low bound 2 and admits a 4-competitive online algorithm.

Proof

The low bound 2 is proved by a simple adversary method. At time 0, job $J_1$ with $(p_1,w_1)=(1,1)$ arrives. Suppose that an online algorithm processes $J_1$ at some time $t\ge 0$. If $t\ge 1$, then no jobs will arrive later. If $t<1$, then job $J_2$ with $(p_2,w_2)=(0,2)$ arrives at time $t+ϵ$ and no jobs will arrive later. Let $W{C}_{\mathit{on}}$ and $W{C}_{\mathit{opt}}$ be the online objective value and the off-line optimal objective value of the job instance. In the case where $t\ge 1$, we have $W{C}_{\mathit{opt}}=1$ and $W{C}_{\mathit{on}}=t+1\ge 2$, and so, $W{C}_{\mathit{on}}/W{C}_{\mathit{opt}}\ge 2$. In the case where $t<1$, we have $W{C}_{\mathit{opt}}=t+1$ and $W{C}_{\mathit{on}}\ge 2(t+1)$, and so, $W{C}_{\mathit{on}}/W{C}_{\mathit{opt}}\ge 2$. Consequently, 2 is a low bound of the problem in (1).

We now consider the following simple online algorithm for the problem in (1).

$\bullet$ At the current time t, let $U^{\ast }(t)$ be the set of all unscheduled available jobs and each of them has a processing time at most t. If $U^{\ast }(t)\ne \mathrm{\varnothing }$, then process $U^{\ast }(t)$ as a single batch at time t. Otherwise, do nothing but wait.

Let $\sigma$ be the schedule generated by the above online algorithm, let $J_j$ be an arbitrary job, let B be the batch containing $J_j$ in $\sigma$, and let t be the starting time of B in $\sigma$. From the algorithm design, we have $t\ge p(B)\ge p_j$. If either $p_j=t$ or $r_j=t$, then $C_j(\sigma )=t+p(B)\le 2t=2·max\{r_j,p_j\}\le 2(r_j+p_j)$. If $p_j<t$ and $r_j<t$, from the algorithm design, another batch $B^{\prime }$ is processed directly before batch B in $\sigma$ such that $t^{\prime }\ge p(B^{\prime })$, where $t^{\prime }=t-p(B^{\prime })$ is the starting time of $B^{\prime }$ in $\sigma$. In the case where $p_j>t^{\prime }$, we have $C_j(\sigma )=t+p(B)\le 2t=2(t^{\prime }+p(B^{\prime }))\le 4t^{\prime }<4p_j\le 4(r_j+p_j)$. In the case where $p_j\le t^{\prime }$, we must have $r_j>t^{\prime }$, and so, $C_j(\sigma )\le 4t^{\prime }<4r_j\le 4(r_j+p_j)$.

The above discussion shows that, in schedule $\sigma$, every job $J_j$ completes at a time less than $4(r_j+p_j)$. Consequently, the above online algorithm is 4-competitive. $\square$

The special online scheduling problem

In this section, we consider problem $1|\text{online},{\beta }^{\ast }|W{C}_{max}$ in (2). In order to analyse the competitive ratio of the proposed online algorithms, we first consider the corresponding off-line version of the problem in (2), which is denoted by $1|{\beta }^{\ast }|W{C}_{max}$. We use $W{C}_{\mathit{opt}}$ to denote the optimal objective value for the corresponding off-line problem $1|{\beta }^{\ast }|W{C}_{max}$. Next, we establish a useful lemma to estimate the low bound of $W{C}_{\mathit{opt}}$.

Lemma 4.1

Suppose that $J_x$ and $J_y$ are two jobs with $r_x\le r_y$. Then we have the following two statements:

1. If there is an off-line optimal schedule $\pi$ such that $J_x$ and $J_y$ are processed in the same batch in $\pi$, then we have $W{C}_{\mathit{opt}}\ge max\left\{w_x,,,w_y\right\}·(r_y+max\left\{p_x,,,p_y\right\})$.

2. If $J_x$ and $J_y$ are processed in different batches in all off-line optimal schedules, then we have $W{C}_{\mathit{opt}}\ge w_y(r_x+p_x+p_y)$.

Proof

(i) Since $J_x$ and $J_y$ are processed in the same batch in $\pi$, we have $C_x(\pi )=C_y(\pi )\ge r_y+max\left\{p_x,,,p_y\right\}$. Consequently,$$\begin{array}{cc}\hfill W{C}_{\mathit{opt}}=& W{C}_{max}(\pi )\ge max\{w_x{C}_x(\pi ),w_y{C}_y(\pi )\}\hfill \\ \hfill \ge & max\left\{w_x,,,w_y\right\}·(r_y+max\left\{p_x,,,p_y\right\}).\hfill \end{array}$$Statement (i) follows.

(ii) Let $\pi$ be an off-line optimal schedule. Then $J_x$ and $J_y$ are processed in different batches in $\pi$. We distinguish the following three possibilities.

If $J_x$ is processed before $J_y$ in $\pi$, then we have $W{C}_{\mathit{opt}}\ge w_y{C}_y(\pi )\ge w_y(r_x+p_x+p_y)$.

If $J_x$ is processed after $J_y$ in $\pi$ and $w_x\ge w_y$, then we have $W{C}_{\mathit{opt}}\ge w_x{C}_x(\pi )\ge w_x(r_y+p_x+p_y)\ge w_y(r_x+p_x+p_y)$.

If $J_x$ is processed after $J_y$ in $\pi$ and $w_x<w_y$, by the agreeability condition, we have $p_x\le p_y$. Note that $r_x\le r_y$. Thus, $J_x$ is available at time starting time of $J_y$. Let ${\pi }^{\prime }$ be the schedule obtained from $\pi$ by shifting $J_x$ into the batch containing $J_y$. Since $p_x\le p_y$, we have $C_x({\pi }^{\prime })<C_x(\pi )$ and $C_j({\pi }^{\prime })=C_j(\pi )$ for each $j\ne x$. Thus, ${\pi }^{\prime }$ is also an optimal schedule. But then, $J_x$ and $J_y$ are processed in the same batch in ${\pi }^{\prime }$. This contradicts the assumption that $J_x$ and $J_y$ are processed in different batches in all off-line optimal schedules. This proves Statement (ii) and gives the lemma. $\square$

Let U be a set of jobs. A job $J_k\in U$ is called a critical job in U if $p_k=max\left\{p_j,|,J_j,\in ,U\right\}$ and $w_k=max\left\{w_j,|,J_j,\in ,U\right\}$. In our problem, the jobs have agreeable processing times and weights. Then the following lemma can be easily verified.

Lemma 4.2

Under the agreeability condition in our problem, every set of jobs must has a critical job, and moreover, every two critical jobs must have the same processing time and the same weight.

The result in Lemma 4.2 enables us to just pick one critical job in a set of jobs under consideration. This will be reflected in our algorithm designs.

Suppose that $\alpha$ is the positive root of $\alpha (\alpha +1)=1$. Thus, we have $\alpha =\frac{\sqrt{5}-1}{2}\approx 0.618$. For problem $1|\text{online},r_j,\text{p-batch},b=\infty |C_{max}$, Zhang et al. (2001) proved that $1+\alpha$ is a lower bound of the competitive ratio for all deterministic online algorithms and proposed an online algorithm $H^{\infty }$ with the best possible competitive ratio $1+\alpha$. Note that the above problem is a special version of our problem $1|\text{online},{\beta }^{\ast }|W{C}_{max}$. Thus, we have the following result.

Theorem 4.1

For problem $1|\text{online},{\beta }^{\ast }|W{C}_{max}$, there is no deterministic online algorithm with a competitive ratio of less than $1+\alpha$.

Next, we will make a slight modification on the online algorithm $H^{\infty }$ proposed in Zhang et al. (2001). We will show that the modified online algorithm has the best possible competitive ratio $1+\alpha \approx 1.618$ for our problem $1|\text{online},{\beta }^{\ast }|W{C}_{max}$. At a time t, we use U(t) to denote the set of all unscheduled jobs which are available at time t.

Algorithm$H_1^{\infty }$: For problem $1|\text{online},{\beta }^{\ast }|W{C}_{max}$.

Step 0: Set $t:=0$.

Step 1: Do the following.

(1.1) If $U(t)=\mathrm{\varnothing }$, then wait until a new job arrives at some time $t^{\prime }>t$. Reset $t:=t^{\prime }$ and go to Step (1.2).

(1.2) If $U(t)\ne \mathrm{\varnothing }$, then find a critical job $J_k\in U(t)$. Go to Step 2.

Step 2: Do the following.

(2.1) If $t<(1+\alpha )r_k+\alpha p_k$, then reset $t:=(1+\alpha )r_k+\alpha p_k$ and update the critical job $J_k$ in U(t). This procedure is repeated until the condition $t\ge (1+\alpha )r_k+\alpha p_k$ is satisfied. Go to Step 3.

(2.2) If $t\ge (1+\alpha )r_k+\alpha p_k$, then go to Step 3 directly.

Step 3: At time t, schedule all jobs in U(t) as a single batch. Reset $t:=t+p_k$ and go to Step 1.

Let I be an instance of problem $1|\text{online,}{\beta }^{\ast }|W{C}_{max}$. Let $\pi$ be an off-line optimal schedule of instance I and let $W{C}_{\mathit{opt}}$ be the the weighted makespan of $\pi$. Furthermore, we assume that $\sigma$ is the schedule generated by Algorithm $H_1^{\infty }$ and $W{C}_{\mathit{on}}$ is the the weighted makespan of $\sigma$. We also assume that $B_1,B_2,\cdots ,B_m$ are all the batches generated by Algorithm $H_1^{\infty }$. Let $s_i$ be the starting time of $B_i$ in $\sigma$, $i=1,2,\cdots ,m$. Without loss of generality, we assume that $s_1<s_2<\cdots <s_m$. Note that $B_i=U(s_i)$. Let $J_i\in B_i$ be the critical job in $B_i=U(s_i)$. That is, $p_i=max\left\{p_j,|,J_j,\in ,B_i\right\}$ and $w_i=max\left\{w_j,|,J_j,\in ,B_i\right\}$. By the design of Algorithm $H_1^{\infty }$, we can easily observed that $s_1=(1+\alpha )r_1+\alpha p_1$ and, for each batch $B_i$ with $i\in \{2,3,\cdots ,m\}$, we have $s_i=max\{(1+\alpha )r_i+\alpha p_i,s_{i-1}+p_{i-1}\}$. For convenience, we call $B_i$ a regular batch if $s_i=(1+\alpha )r_i+\alpha p_i$, and a delayed batch if $s_i=s_{i-1}+p_{i-1}>(1+\alpha )r_i+\alpha p_i$.

It is easy to verify that if we delete all jobs in $B_i\backslash J_i$, then the ratio of $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}$ will not decrease. Thus, in the sequel, we assume that $B_i=\left\{J_i\right\}$ in $\sigma$. Suppose that $B_k$ is the first batch in $\sigma$ such that $W{C}_{\mathit{on}}=w_k(s_k+p_k)$. We have the following lemmas.

Lemma 4.3

$B_1$ must be a regular batch. Furthermore, if $B_i$ is a regular batch, then $B_{i+1}$ or $B_{i+2}$ is also a regular batch.

Proof

The first statement follows from the fact that $s_1=(1+\alpha )r_1+\alpha p_1$. The second statement can be proved by the same way as that in Zhang et al. (2001). For completeness, we borrow the proof of Lemma 2 in Zhang et al. (2001) as follows: Otherwise, we assume that $B_i$ is a regular batch, but $B_{i+1}$ and $B_{i+2}$ are delayed batches. Clearly, all jobs in $B_{i+1}$ come later than $s_i$. Thus, we have $r_{i+1}>s_i=(1+\alpha )r_i+\alpha p_i$. Since $B_{i+1}$ is a delayed batches, we have$$\begin{array}{cc}& (1+\alpha )(r_i+p_i)>(1+\alpha )r_{i+1}+\alpha p_{i+1}>(1+\alpha )[(1+\alpha )r_i+\alpha p_i]+\alpha p_{i+1}\hfill \\ \hfill & =(2+\alpha )r_i+p_i+\alpha p_{i+1}.\hfill \end{array}$$It follows that $\alpha p_i>r_i+\alpha p_{i+1}$ and $p_i>p_{i+1}$.

Similarly, all jobs in $B_{i+2}$ come later than $s_i+p_i$. Thus, we have $r_{i+2}>(1+\alpha )(r_i+p_i)$. Since $B_{i+2}$ is a delayed batches, we have$$\begin{array}{cc}& (1+\alpha )(r_{i+1}+p_{i+1})>(1+\alpha )r_{i+2}+\alpha p_{i+2}>(1+\alpha )[(1+\alpha )(r_i+p_i)]+\alpha p_{i+2}\hfill \\ \hfill & =(2+\alpha )(r_i+p_i)+\alpha p_{i+1}.\hfill \end{array}$$It follows that $p_{i+1}>r_i+p_i+\alpha p_{i+2}$ and $p_{i+1}>p_i$. This contradicts the fact that $p_i>p_{i+1}$. Lemma 4.3 follows. $\square$

Lemma 4.4

If $B_k$ is a regular batch, then we have $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le 1+\alpha$.

Proof

Since $B_k$ is a regular batch, we have $s_k=(1+\alpha )r_k+\alpha p_k$. By noting that $B_k$ completes at time $s_k+p_k$, it holds that $W{C}_{\mathit{on}}=w_k(s_k+p_k)=w_k(1+\alpha )(r_k+p_k)$. Since $W{C}_{\mathit{opt}}\ge w_k(r_k+p_k)$, we have $\frac{WC\mathit{on}}{W{C}_{\mathit{opt}}}\le 1+\alpha$. The lemma follows. $\square$

Lemma 4.5

If $B_k$ is a delayed batch, then we have $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le 1+\alpha$.

Proof

Since $B_k$ is a delayed batch, we have $s_k=s_{k-1}+p_{k-1}$. By Lemma 4.3, there do not exist two successive delayed batches. Thus, $B_{k-1}$ must be a regular batch, i.e., $s_{k-1}=(1+\alpha )r_{k-1}+\alpha p_{k-1}$. By noting that $B_k$ completes at time $s_k+p_k=s_{k-1}+p_{k-1}+p_k$, it follows that

4

$$\begin{array}{c}\hfill W{C}_{\mathit{on}}=w_k(s_{k-1}+p_{k-1}+p_k)=w_k[(1+\alpha )(r_{k-1}+p_{k-1})+p_k].\end{array}$$We consider the following two cases.

Case 1.$J_{k-1}$ and $J_k$ are processed in the same batch in an off-line optimal schedule $\pi$. Then the batch containing $J_{k-1}$ and $J_k$ completes at a time no earlier than $r_k+p_k$ and $r_k+p_{k-1}$. Since $r_k>s_{k-1}$ and $s_{k-1}=(1+\alpha )r_{k-1}+\alpha p_{k-1}$, from Lemma 4.1(i), we have

5

$$\begin{array}{c}\hfill W{C}_{\mathit{opt}}\ge w_k(r_k+p_k)\ge w_k[(1+\alpha )r_{k-1}+\alpha p_{k-1}+p_k]\end{array}$$and

6

$$\begin{array}{c}\hfill W{C}_{\mathit{opt}}\ge w_{k-1}(r_k+p_{k-1})\ge w_{k-1}[(1+\alpha )(r_{k-1}+p_{k-1})].\end{array}$$If $p_k\ge p_{k-1}$, from (4) and (5), we have$$\begin{array}{cc}\hfill \frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}& \le \frac{w_k[(1+\alpha )(r_{k-1}+p_{k-1})+p_k]}{w_k[(1+\alpha )r_{k-1}+\alpha p_{k-1}+p_k]}\hfill \\ \hfill & =1+\frac{p_{k-1}}{(1+\alpha )r_{k-1}+\alpha p_{k-1}+p_k}\hfill \\ \hfill & \le 1+\frac{p_{k-1}}{(1+\alpha )p_{k-1}}\hfill \\ \hfill & =1+\alpha .\hfill \end{array}$$If $p_k<p_{k-1}$, from the agreeability condition, we have $w_k\le w_{k-1}$. From (6), we further have $W{C}_{\mathit{opt}}\ge w_{k-1}[(1+\alpha )(r_{k-1}+p_{k-1})]\ge w_k[(1+\alpha )(r_{k-1}+p_{k-1})].$ By using (4), we have$$\begin{array}{cc}\hfill \frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}& \le \frac{w_k[(1+\alpha )(r_{k-1}+p_{k-1})+p_k]}{w_k[(1+\alpha )(r_{k-1}+p_{k-1})]}\hfill \\ \hfill & =1+\frac{p_k}{(1+\alpha )(r_{k-1}+p_{k-1})}\hfill \\ \hfill & \le 1+\frac{p_k}{(1+\alpha )p_k}\hfill \\ \hfill & =1+\alpha .\hfill \end{array}$$Case 2.$J_{k-1}$ and $J_k$ are processed in different batches in all off-line optimal schedules. From Lemma 4.1(ii), we have $W{C}_{\mathit{opt}}\ge w_k(r_{k-1}+p_{k-1}+p_k)$. By using (4), we have$$\begin{array}{cc}\hfill \frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}& \le \frac{w_k[(1+\alpha )(r_{k-1}+p_{k-1})+p_k]}{w_k(r_{k-1}+p_{k-1}+p_k)}\hfill \\ \hfill & \le \frac{(1+\alpha )(r_{k-1}+p_{k-1}+p_k)}{r_{k-1}+p_{k-1}+p_k}\hfill \\ \hfill & =1+\alpha .\hfill \end{array}$$From the discussions in Case 1 and Case 2, the lemma follows. $\square$

Combining Lemmas 4.4 and 4.5 together, we conclude the following theorem.

Theorem 4.2

For problem $1|\text{online},{\beta }^{\ast }|W{C}_{max}$, Algorithm $H_1^{\infty }$ has a best possible competitive ratio $1+\alpha$.

The special problem with limited restarts

To improve the competitive ratio $1+\alpha$, we introduce “limited restarts" into the special problem, where each job can be restarted only once when it is processed on the machine. The corresponding problem is denoted by $1|\text{online},{\beta }^{\ast },\text{L-restart}|W{C}_{max}$. For problem $1|\text{online},r_j,\text{p-batch},b=\infty ,\text{L-restart}|C_{max}$, Fu et al. (2008) proved that $\frac{3}{2}$ is a lower bound of the competitive ratio for all deterministic online algorithms. Note that the above problem is a special version of our problem $1|\text{online},{\beta }^{\ast },\text{L-restart}|W{C}_{max}$. Thus, we have the following theorem.

Theorem 5.1

For problem $1|\text{online},{\beta }^{\ast },\text{L-restart}|W{C}_{max}$, there exists no deterministic online algorithm with a competitive ratio of less than $\frac{3}{2}$.

For a time instant t, let U(t) be the set of unscheduled jobs which are available at time t. If the machine is busy at time t, let $B_k$ be the currently processing batch at time t. If there is some restarted jobs in $B_k$, we set $\tau =1$; otherwise, we set $\tau =0$. Thus, the current batch $B_k$ can be restarted if and only if $\tau =0$.

Algorithm$H_2^{\infty }$: For problem $1|\text{online},{\beta }^{\ast },\text{L-restart}|W{C}_{max}$.

Step 1: Set $t:=0$ and $\tau :=0$.

Step 2: If $U(t)=\mathrm{\varnothing }$, go to Step 6. If $U(t)\ne \mathrm{\varnothing }$, then find the critical job $J_k\in U(t)$ and go to Step 3.

Step 3: If $t<\frac{4}{7}{p}_k$, then reset $t:=\frac{4}{7}{p}_k$ and go to Step 2. If $t\ge \frac{4}{7}{p}_k$, then schedule all the jobs in U(t) as a single batch $B_k$ at time t and go to Step 4.

Step 4: If there are no new jobs arriving in the time interval $(t,t+p_k)$ or $\tau =1$, then reset $t:=t+p_k$ and $\tau :=0$ and go to Step 2. If $\tau =0$ and a new job $J_h$ arrives at time $r_h$ with $r_h\in (t,t+p_k)$, go to Step 5.

Step 5: Do the following.

(5.1) If either $r_h\ge \frac{72}{49}{p}_k$ or $p_h\ge \frac{33}{28}{p}_k$, then reset $t:=t+p_k$. Go to Step 2.

(5.2) If $p_k<p_h<\frac{33}{28}{p}_k$, then do the following:

(5.2.1) If $r_h<\frac{4}{3}{p}_h$, then go on processing the current batch $B_k$ in the time interval $[r_h,\frac{4}{3}{p}_h]$. If there is a new job $J_{h^{\prime }}$ with $p_{h^{\prime }}>p_h$ or $w_{h^{\prime }}>w_h$ arriving in the time interval $[r_h,\frac{4}{3}{p}_h]$, then reset $h:=h^{\prime }$ and run Step 5 again. Otherwise, restart the current batch $B_k$ at time $\frac{4}{3}{p}_h$. Reset $t:=\frac{4}{3}{p}_h$ and $\tau :=1$, update the critical job $J_k$ in $B_k=U(t)$, and go to Step 4.

(5.2.2) If $r_h\ge \frac{4}{3}{p}_h$, then restart the current batch $B_k$ at time $r_h$. Reset $t:=r_h$ and $\tau :=1$, update the critical job $J_k$ in $B_k=U(t)$, and go to Step 4.

(5.3) If $\frac{3}{4}{p}_k<p_h\le p_k$, then do the following.

(5.3.1) If $w_h\ge \frac{44}{49}{w}_k$, then go on processing the current batch $B_k$ in the time interval $[r_h,\frac{72}{49}{p}_k]$. If there is a new job $J_{h^{\prime }}$ with $p_{h^{\prime }}>p_h$ or $w_{h^{\prime }}>w_h$ arriving in the time interval $[r_h,\frac{72}{49}{p}_k]$, then reset $h:=h^{\prime }$ and run Step 5 again. Otherwise, restart the current batch $B_k$ at time $\frac{72}{49}{p}_k$. Reset $t:=\frac{72}{49}{p}_k$ and $\tau =1$, update the critical job $J_k$ in $B_k=U(t)$, and go to Step 4.

(5.3.2) If $w_h<\frac{44}{49}{w}_k$, then complete the current batch $B_k$. Reset $t:=t+p_k$ and go to Step 2.

(5.4) If $p_h\le \frac{3}{4}{p}_k$, then continue to process the current batch $B_k$. Go to Step 4.

Step 6: If there exist some new jobs arriving after time t, then let $t^{\prime }$ be arrival time of the first new job. Reset $t:=t^{\prime }$ and go to Step 2. Otherwise, stop the algorithm and output the current schedule.

Let I be a job instance, let $\sigma$ be the schedule obtained by Algorithm $H_2^{\infty }$ on instance I, and let $B_1,B_2,\cdots ,B_m$ be all the batches in $\sigma$. For each batch $B_i$, let $r(B_i)=min\{r_j:J_j\in B_i\}$ be the earliest arrival time of the jobs in $B_i$, let $s_i$ be the starting time of $B_i$ in $\sigma$, and let $J_i$ be the critical job in $B_i$. Assume that $s_1<s_2<\cdots <s_m$. For each $i\in \{1,2,\cdots ,m\}$, we call $B_i$ a free batch if there are no restarted jobs in $B_i$, and call $B_i$ a restricted batch otherwise. Assume that $B_k$ is the first batch in $\sigma$ such that $W{C}_{\mathit{on}}=w_k(s_k+p_k)$. Throughout our discussions, we use $\pi$ to denote an off-line optimal schedule of instance I.

Next, we give four observations about Algorithm $H_2^{\infty }$, all of which can be directly obtained from the implementation of the algorithm.

Observation 5.1

For each batch $B_i$$(1\le i\le m)$ in $\sigma$, we have $s_i\ge max\left\{r,(B_i),,,\frac{4}{7},p_i\right\}$.

Observation 5.2

If there exists an idle time directly before $s_i$ in $\sigma$, then we have $s_i=max\left\{r,(B_i),,,\frac{4}{7},p_i\right\}$.

Observation 5.3

If $B_i$ is a free batch in $\sigma$, then we have $s_i=r(B_i)$ or $s_i=\frac{4}{7}{p}_i$ or $s_i=s_{i-1}+p_{i-1}$.

Observation 5.4

If $B_i$ is a restricted batch in $\sigma$, then we have $s_i=max\left\{r_h,,,\frac{4}{3},p_h\right\}$ or $s_i=\frac{72}{49}{p}_{i-1}$, where $J_h$ is the job with the longest processing time and the maximum weight which arrives in the time interval $(s_{i-1},s_i]$.

Lemma 5.1

If $B_i$ is a restricted batch, then we have $s_i\ge \frac{4}{3}{p}_i$.

Proof

Since $B_i$ is a restricted batch, we have $s_i=max\left\{r_h,,,\frac{4}{3},p_h\right\}$ or $s_i=\frac{72}{49}{p}_{i-1}$ by Observation 5.4. Note that $p_{i-1}<p_h<\frac{33}{28}{p}_{i-1}$ by Step 5.2 of Algorithm $H_2^{\infty }$. If $s_i=max\left\{r_h,,,\frac{4}{3},p_h\right\}$, then we have $p_i=max\left\{p_{i-1},,,p_h\right\}=p_h$ and $s_i\ge \frac{4}{3}{p}_h=\frac{4}{3}{p}_i$. Note further that $\frac{3}{4}{p}_{i-1}<p_h\le p_{i-1}$ by Step 5.3 of Algorithm $H_2^{\infty }$. If $s_i=\frac{72}{49}{p}_{i-1}$, then we have $p_i=max\left\{p_{i-1},,,p_h\right\}=p_{i-1}$ and $s_i=\frac{72}{49}{p}_{i-1}\ge \frac{4}{3}{p}_i$. The lemma follows. $\square$

Lemma 5.2

If $B_k$ is a restricted batch, then we have $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$.

Proof

Denote by $J^{\prime }$ the job with the longest processing time and the maximum weight which arrives latest in the time interval $(s_{k-1},s_k]$. Let $r^{\prime }$, $p^{\prime }$ and $w^{\prime }$ be the arrival time, the processing time and the weight of $J^{\prime }$, respectively. By Observation 5.4, we have $s_k=max\left\{r^{\prime },,,\frac{4}{3},p^{\prime }\right\}$ or $s_k=\frac{72}{49}{p}_{k-1}$. Note that $r^{\prime }>s_{k-1}$. We consider the following two cases in our discussion.

Case 1.$s_k=max\left\{r^{\prime },,,\frac{4}{3},p^{\prime }\right\}$. By Step 5.2 of Algorithm $H_2^{\infty }$, we have $p_{k-1}<p^{\prime }<\frac{33}{28}{p}_{k-1}$. It follows that $p_k=max\left\{p_{k-1},,,p^{\prime }\right\}=p^{\prime }$. Since $p^{\prime }>p_{k-1}$, we have $w^{\prime }\ge w_{k-1}$ by the agreeability condition. Thus, we have $w_k=max\left\{w_{k-1},,,w^{\prime }\right\}=w^{\prime }$. Furthermore, we have $W{C}_{\mathit{on}}=w_k(s_k+p_k)=w^{\prime }(s_k+p^{\prime })$.

If $s_k=r^{\prime }$, then $W{C}_{\mathit{opt}}\ge w^{\prime }(r^{\prime }+p^{\prime })=W{C}_{\mathit{on}}$. In this situation, the schedule generated by Algorithm $H_2^{\infty }$ is optimal. If $s_k=\frac{4}{3}{p}^{\prime }$, then $W{C}_{\mathit{on}}=\frac{7}{3}{w}^{\prime }{p}^{\prime }$. Note that $s_{k-1}\ge \frac{4}{7}{p}_{k-1}$ and $p^{\prime }<\frac{33}{28}{p}_{k-1}$. Thus, we have $s_{k-1}\ge \frac{16}{33}{p}^{\prime }$. Since $r^{\prime }>s_{k-1}$, we have $W{C}_{\mathit{opt}}\ge w^{\prime }(r^{\prime }+p^{\prime })\ge w^{\prime }(s_{k-1}+p^{\prime })\ge \frac{49}{33}{w}^{\prime }{p}^{\prime }$. Consequently, we have $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$.

Case 2.$s_k=\frac{72}{49}{p}_{k-1}$. By Step 5.3 of Algorithm $H_2^{\infty }$, we have $\frac{3}{4}{p}_{k-1}<p^{\prime }\le p_{k-1}$ and $w^{\prime }\ge \frac{44}{49}{w}_{k-1}$. It follows that $p_k=max\left\{p_{k-1},,,p^{\prime }\right\}=p_{k-1}$ and $W{C}_{\mathit{on}}=w_k(s_k+p_k)=\frac{121}{49}{w}_k{p}_{k-1}$. We distinguish two subcases in the following discussion.

Case 2.1.$w^{\prime }\ge w_{k-1}$. In this subcase, $w_k=max\left\{w^{\prime },,,w_{k-1}\right\}=w^{\prime }$ and $W{C}_{\mathit{on}}=\frac{121}{49}{w}^{\prime }{p}_{k-1}$. Since $w^{\prime }\ge w_{k-1}$, we have $p^{\prime }\ge p_{k-1}$. Note that $p_{k-1}\ge p^{\prime }$. Thus, we have $p^{\prime }=p_{k-1}$, Note further that $r^{\prime }>s_{k-1}$ and $s_{k-1}\ge \frac{4}{7}{p}_{k-1}$. It follows that $W{C}_{\mathit{opt}}\ge w^{\prime }(r^{\prime }+p^{\prime })\ge \frac{11}{7}{w}^{\prime }{p}_{k-1}$. Therefore, we have $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$.

Case 2.2.$\frac{44}{49}{w}_{k-1}\le w^{\prime }<w_{k-1}$. In this subcase, $w_k=max\left\{w^{\prime },,,w_{k-1}\right\}=w_{k-1}$ and $W{C}_{\mathit{on}}=\frac{121}{49}{w}_{k-1}{p}_{k-1}$. By Lemma 4.1, we have$$\begin{array}{c}\hfill W{C}_{\mathit{opt}}\ge min\left\{max,\left\{w_{k-1},,,w^{\prime }\right\},·,(r^{\prime }+max\left\{p_{k-1},,,p^{\prime }\right\}),,,w^{\prime },(r_{k-1}+p_{k-1}+p^{\prime })\right\}.\end{array}$$If $W{C}_{\mathit{opt}}\ge max\left\{w_{k-1},,,w^{\prime }\right\}·(r^{\prime }+max\left\{p_{k-1},,,p^{\prime }\right\})$, then we have $W{C}_{\mathit{opt}}\ge \frac{11}{7}{w}_{k-1}{p}_{k-1}$ since $r^{\prime }>s_{k-1}\ge \frac{4}{7}{p}_{k-1}$. Furthermore, we have $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$. If $W{C}_{\mathit{opt}}\ge w^{\prime }(r_{k-1}+p_{k-1}+p^{\prime })$, since $w^{\prime }\ge \frac{44}{49}{w}_{k-1}$ and $p^{\prime }>\frac{3}{4}{p}_{k-1}$, then we have $W{C}_{\mathit{opt}}\ge \frac{44}{49}{w}_{k-1}\times \frac{7}{4}{p}_{k-1}=\frac{11}{7}{w}_{k-1}{p}_{k-1}$. Thus, we also have $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$. The lemma follows. $\square$

Lemma 5.2 enables us only to consider the case where $B_k$ is a free batch in the sequel.

Lemma 5.3

If $B_k$ is a free batch, then we have the following three statements.

1. If $s_k=r(B_k)$, then the schedule generated by Algorithm $H_2^{\infty }$ is optimal.

2. If $s_k=\frac{4}{7}{p}_k$, then $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$.

3. If $s_k=s_{k-1}+p_{k-1}$, then we have $W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}\le w_k{p}_{k-1}$. Furthermore, if $s_{k-1}=s_{k-2}+p_{k-2}$, then we have $W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}\le w_k{p}_{k-2}$.

Proof

By Observation 5.3, we have $s_k=r(B_k)$ or $s_k=\frac{4}{7}{p}_k$ or $s_k=s_{k-1}+p_{k-1}$.

1. If $s_k=r(B_k)$, then we have $r_k=r(B_k)$. Thus, $W{C}_{\mathit{opt}}\ge w_k(r_k+p_k)=w_k(s_k+p_k)=W{C}_{\mathit{on}}$. It means that the schedule generated by Algorithm $H_2^{\infty }$ is optimal.

2. If $s_k=\frac{4}{7}{p}_k$, then $W{C}_{\mathit{on}}=w_k(s_k+p_k)=\frac{11}{7}{w}_k{p}_k$. Note that $W{C}_{\mathit{opt}}\ge w_k{p}_k$. Thus, we have $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$.

3. If $s_k=s_{k-1}+p_{k-1}$, then $W{C}_{\mathit{on}}=w_k(s_{k-1}+p_{k-1}+p_k)$. From the fact that $r_k>s_{k-1}$, we have $W{C}_{\mathit{opt}}\ge w_k(r_k+p_k)\ge w_k(s_{k-1}+p_k)$. Thus, we have $W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}\le w_k{p}_{k-1}$. Furthermore, if $s_{k-1}=s_{k-2}+p_{k-2}$, then we have $W{C}_{\mathit{on}}=w_k(s_{k-2}+p_{k-2}+p_{k-1}+p_k)$. Notice that $r_{k-1}>s_{k-2}$ and $W{C}_{\mathit{opt}}\ge w_k(r_{k-1}+p_{k-1}+p_k)$. Thus, we have $W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}\le w_k{p}_{k-2}$. The lemma follows.

$\square$

By Lemma 5.3, we need only to show that $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$ under the following assumption.

Assumption 5.1

$B_k$ is a free batch, $s_k=s_{k-1}+p_{k-1}$, and $W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}\le w_k{p}_{k-1}$.

By assumption  5.1, if $W{C}_{\mathit{opt}}\ge \frac{7}{4}{w}_k{p}_{k-1}$, then $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le 1+\frac{W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$. Let us take our discussions by the status of batch $B_{k-1}$.

Lemma 5.4

If $B_{k-1}$ is a free batch, then we have $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$.

Proof

By Assumption 5.1, we have $s_k=s_{k-1}+p_{k-1}$ and $W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}\le w_k{p}_{k-1}$. Thus, $W{C}_{\mathit{on}}=w_k(s_{k-1}+p_{k-1}+p_k)$. Four cases will be discussed in the following.

Case 1.$p_k\ge \frac{33}{28}{p}_{k-1}$. Note that $r_k>s_{k-1}\ge \frac{4}{7}{p}_{k-1}$ and $p_k\ge \frac{33}{28}{p}_{k-1}$. Thus, we have $W{C}_{\mathit{opt}}\ge w_k(r_k+p_k)\ge \frac{7}{4}{w}_k{p}_{k-1}$. Furthermore, we have $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$.

Case 2.$p_{k-1}<p_k<\frac{33}{28}{p}_{k-1}$. Since $B_k$ is a free batch and $B_{k-1}$ is a free batch, we have $r_k\ge \frac{72}{49}{p}_{k-1}$. Note that $r_k\ge \frac{72}{49}{p}_{k-1}$ and $p_k>p_{k-1}$. Thus, we have $W{C}_{\mathit{opt}}\ge w_k(r_k+p_k)\ge \frac{7}{4}{w}_k{p}_{k-1}$. It follows that $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$.

Case 3.$\frac{3}{4}{p}_{k-1}<p_k\le p_{k-1}$. Since $B_k$ is a free batch and $B_{k-1}$ is a free batch, we have $r_k\ge \frac{72}{49}{p}_{k-1}$ or $w_k<\frac{44}{49}{w}_{k-1}$. We first assume that $r_k\ge \frac{72}{49}{p}_{k-1}$. Note that $r_k\ge \frac{72}{49}{p}_{k-1}$ and $p_k>\frac{3}{4}{p}_{k-1}$. Then we have $W{C}_{\mathit{opt}}\ge w_k(r_k+p_k)\ge \frac{7}{4}{w}_k{p}_{k-1}$. Furthermore, we have $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$. Next, we assume that $w_k<\frac{44}{49}{w}_{k-1}$. By Lemma 4.1, we have$$\begin{array}{c}\hfill W{C}_{\mathit{opt}}\ge min\left\{max,\left\{w_{k-1},,,w_k\right\},·,(r_k+max\left\{p_{k-1},,,p_k\right\}),,,w_k,(r_{k-1}+p_{k-1}+p_k)\right\}.\end{array}$$Note that $r_k>s_{k-1}\ge \frac{4}{7}{p}_{k-1}$ and $w_{k-1}>\frac{49}{44}{w}_k$. Thus, we have$$\begin{array}{cc}\hfill max\left\{w_{k-1},,,w_k\right\}·(r_k+max\left\{p_{k-1},,,p_k\right\})\ge & w_{k-1}(r_k+p_{k-1})\hfill \\ \hfill \ge & \frac{49}{44}{w}_k\times \frac{11}{7}{p}_{k-1}=\frac{7}{4}{w}_k{p}_{k-1}.\hfill \end{array}$$Furthermore, since $p_k>\frac{3}{4}{p}_{k-1}$, we also have $w_k(r_{k-1}+p_{k-1}+p_k)\ge \frac{7}{4}{w}_k{p}_{k-1}.$ Thus, we have $W{C}_{\mathit{opt}}\ge \frac{7}{4}{w}_k{p}_{k-1}$. Furthermore, we conclude that $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$.

Case 4.$p_k\le \frac{3}{4}{p}_{k-1}$. Since $p_k\le \frac{3}{4}{p}_{k-1}$, we have $w_{k-1}\ge w_k$. By Lemma 4.1, we have$$\begin{array}{c}\hfill W{C}_{\mathit{opt}}\ge min\left\{max,\left\{w_{k-1},,,w_k\right\},·,(r_k+max\left\{p_{k-1},,,p_k\right\}),,,w_k,(r_{k-1}+p_{k-1}+p_k)\right\}.\end{array}$$Note that $r_k>s_{k-1}\ge \frac{4}{7}{p}_{k-1}$. If $W{C}_{\mathit{opt}}\ge max\left\{w_{k-1},,,w_k\right\}·(r_k+max\left\{p_{k-1},,,p_k\right\})$, then we have $W{C}_{\mathit{opt}}\ge \frac{11}{7}{w}_k{p}_{k-1}$. Since $W{C}_{\mathit{on}}=w_k(s_{k-1}+p_{k-1}+p_k)$ and $W{C}_{\mathit{opt}}\ge w_{k-1}(r_k+p_{k-1})\ge w_k(s_{k-1}+p_{k-1})$, we have $W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}\le w_k{p}_k$. Note further that $p_k\le \frac{3}{4}{p}_{k-1}$. Thus, we have $\frac{W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}}{W{C}_{\mathit{opt}}}\le \frac{\frac{3}{4}{w}_k{p}_{k-1}}{\frac{11}{7}{w}_k{p}_{k-1}}\le \frac{4}{7}$. It follows that $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$.

Suppose that $W{C}_{\mathit{opt}}\ge w_k(r_{k-1}+p_{k-1}+p_k)$ in the following. Since $B_{k-1}$ is a free batch, we have $s_{k-1}=r(B_{k-1})$ or $s_{k-1}=\frac{4}{7}{p}_{k-1}$ or $s_{k-1}=s_{k-2}+p_{k-2}$ by Observation 5.3. Thus, we distinguish the following three subcases.

Case 4.1.$s_{k-1}=r(B_{k-1})$. In this subcase, we have $W{C}_{\mathit{on}}=w_k(s_{k-1}+p_{k-1}+p_k)=w_k(r(B_{k-1})+p_{k-1}+p_k)$. Note that $r_{k-1}=r(B_{k-1})$. Thus, we have $W{C}_{\mathit{opt}}\ge w_k(r_{k-1}+p_{k-1}+p_k)=W{C}_{\mathit{on}}$. That is, the schedule generated by Algorithm $H_2^{\infty }$ is optimal.

Case 4.2.$s_{k-1}=\frac{4}{7}{p}_{k-1}$. In this subcase, we have $W{C}_{\mathit{on}}=w_k(s_{k-1}+p_{k-1}+p_k)=w_k(\frac{11}{7}{p}_{k-1}+p_k)$. Note that $W{C}_{\mathit{opt}}\ge w_k(p_{k-1}+p_k)$. Thus, we have $W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}\le \frac{4}{7}{w}_k{p}_{k-1}$. Since $W{C}_{\mathit{opt}}\ge w_k{p}_{k-1}$, we have $\frac{W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}}{W{C}_{\mathit{opt}}}\le \frac{4}{7}$. It follows that $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$.

Case 4.3.$s_{k-1}=s_{k-2}+p_{k-2}$. In this subcase, we have $W{C}_{\mathit{on}}=w_k(s_{k-2}+p_{k-2}+p_{k-1}+p_k)$. Notice that $r_{k-1}>s_{k-2}$ and $W{C}_{\mathit{opt}}\ge w_k(r_{k-1}+p_{k-1}+p_k)$. Thus, we have $W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}\le w_k{p}_{k-2}$. To show that $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$, it is sufficient to show that $W{C}_{\mathit{opt}}\ge \frac{7}{4}{w}_k{p}_{k-2}$.

Since $J_{k-2}$ and $J_{k-1}$ are processed in different batches in $\sigma$, $B_{k-2}$ is a restricted batch or $r_{k-1}\ge \frac{72}{49}{p}_{k-2}$ or $p_{k-1}\ge \frac{33}{28}{p}_{k-2}$ or $\frac{3}{4}{p}_{k-2}<p_{k-1}\le p_{k-2}$ and $w_{k-1}<\frac{44}{49}{w}_{k-2}$ or $p_{k-1}\le \frac{3}{4}{p}_{k-2}$. These possibilities are distinguished in the sequel discussions.

$\bullet$$B_{k-2}$ is a restricted batch in $\sigma$. By Lemma 5.1, we have $s_{k-2}\ge \frac{4}{3}{p}_{k-2}$. It follows that $W{C}_{\mathit{opt}}\ge w_k{r}_k\ge w_k{s}_{k-1}=w_k(s_{k-2}+p_{k-2})\ge \frac{7}{3}{w}_k{p}_{k-2}>\frac{7}{4}{w}_k{p}_{k-2}$. Thus, we have $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$.

$\bullet$$r_{k-1}\ge \frac{72}{49}{p}_{k-2}$. If $p_{k-1}\ge p_{k-2}$, then we have $W{C}_{\mathit{opt}}\ge w_k(r_{k-1}+p_{k-1}+p_k)\ge \frac{7}{4}{w}_k{p}_{k-2}$. Note that $W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}\le w_k{p}_{k-2}$. Thus, we have $\frac{W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}}{W{C}_{\mathit{opt}}}\le \frac{4}{7}$. If $p_{k-2}>p_{k-1}$, then we have $r_{k-1}\ge \frac{72}{49}{p}_{k-2}>\frac{72}{49}{p}_{k-1}$ and $W{C}_{\mathit{opt}}\ge w_k(r_{k-1}+p_{k-1}+p_k)\ge \frac{7}{4}{w}_k{p}_{k-1}$. Thus, we have $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$.

$\bullet$$p_{k-1}\ge \frac{33}{28}{p}_{k-2}$. Note that $r_{k-1}>s_{k-2}\ge \frac{4}{7}{p}_{k-2}$. Thus, we have $W{C}_{\mathit{opt}}\ge w_k(r_{k-1}+p_{k-1}+p_k)\ge \frac{7}{4}{w}_k{p}_{k-2}$. It follows that $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$.

$\bullet$$\frac{3}{4}{p}_{k-2}<p_{k-1}\le p_{k-2}$ and $w_{k-1}<\frac{44}{49}{w}_{k-2}$. By Lemma 4.1, we have$$\begin{array}{cc}\hfill W{C}_{\mathit{opt}}\ge & min\left\{max,\left\{w_{k-2},,,w_{k-1}\right\}\right)\hfill \\ \hfill & \left(·,(r_{k-1}+max\left\{p_{k-2},,,p_{k-1}\right\}),,,w_{k-1},(r_{k-2}+p_{k-2}+p_{k-1})\right\}.\hfill \end{array}$$Note that$$\begin{array}{c}\hfill r_{k-1}>s_{k-2}\ge \frac{4}{7}{p}_{k-2},w_{k-2}>\frac{49}{44}{w}_{k-1}\text{and}{w}_{k-1}\ge w_k.\end{array}$$If $W{C}_{\mathit{opt}}\ge max\left\{w_{k-2},,,w_{k-1}\right\}·(r_{k-1}+max\left\{p_{k-2},,,p_{k-1}\right\})$, then we have$$\begin{array}{c}\hfill W{C}_{\mathit{opt}}\ge w_{k-2}(r_{k-1}+p_{k-2})\ge \frac{49}{44}{w}_k\times \frac{11}{7}{p}_{k-2}=\frac{7}{4}{w}_k{p}_{k-2}.\end{array}$$Note further that $w_{k-1}\ge w_k$ and $p_{k-1}>\frac{3}{4}{p}_{k-2}$. If $W{C}_{\mathit{opt}}\ge w_{k-1}(r_{k-2}+p_{k-2}+p_{k-1})$, then we also have $W{C}_{\mathit{opt}}\ge \frac{7}{4}{w}_k{p}_{k-2}$. It follows that $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$.

$\bullet$$p_{k-1}\le \frac{3}{4}{p}_{k-2}$. By Lemma 4.1, it is easy to obtain that$$\begin{array}{cc}\hfill W{C}_{\mathit{opt}}\ge & min\left\{max,\left\{w_{k-2},,,w_{k-1}\right\}\right)\hfill \\ \hfill & \left(·,(r_{k-1}+max\left\{p_{k-2},,,p_{k-1}\right\}),,,w_{k-1},(r_{k-2}+p_{k-2}+p_{k-1})\right\}.\hfill \end{array}$$Note that $w_{k-1}\ge w_k$ and $r_{k-1}>s_{k-2}\ge \frac{4}{7}{p}_{k-2}$. If $W{C}_{\mathit{opt}}\ge max\left\{w_{k-2},,,w_{k-1}\right\}·(r_{k-1}+max\left\{p_{k-2},,,p_{k-1}\right\})$, then we have $W{C}_{\mathit{opt}}\ge \frac{11}{7}{w}_k{p}_{k-2}$. Note further that $p_{k-1}\le \frac{3}{4}{p}_{k-2}$ and $W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}\le w_k{p}_{k-1}$. Thus, we have $W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}\le \frac{3}{4}{w}_k{p}_{k-2}$. It follows that $\frac{W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}}{W{C}_{\mathit{opt}}}\le \frac{\frac{3}{4}{w}_k{p}_{k-2}}{\frac{11}{7}{w}_k{p}_{k-2}}\le \frac{4}{7}$. If $W{C}_{\mathit{opt}}\ge w_{k-1}(r_{k-2}+p_{k-2}+p_{k-1})$, then we have $W{C}_{\mathit{opt}}\ge 2min\left\{w_k,p_{k-1},,,w_k,p_{k-2}\right\}\ge \frac{7}{4}min\left\{w_k,p_{k-1},,,w_k,p_{k-2}\right\}$ since $w_{k-1}\ge w_k$. Thus, we also have $\frac{W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}}{W{C}_{\mathit{opt}}}\le \frac{4}{7}$.

Summing up the above discussions, the lemma follows. $\square$

Lemma 5.5

If $B_{k-1}$ is a restricted batch, then we have $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$.

Proof

Denote by $J^{\prime \prime }$ the job with the longest processing time and the maximum weight which arrives latest in the time interval $(s_{k-2},s_{k-1}]$. Let $r^{\prime \prime }$, $p^{\prime \prime }$ and $w^{\prime \prime }$ be the arrival time, processing time and weight of $J^{\prime \prime }$, respectively. Since $B_{k-1}$ is a restricted batch, we have $s_{k-1}=max\left\{r^{\prime \prime },,,\frac{4}{3},p^{\prime \prime }\right\}$ or $s_{k-1}=\frac{72}{49}{p}_{k-2}$ by Observation 5.4. We next distinguish the following two cases.

Case 1.$s_{k-1}=max\left\{r^{\prime \prime },,,\frac{4}{3},p^{\prime \prime }\right\}$. By Step 5.2 of Algorithm $H_2^{\infty }$, we can get that $p_{k-2}<p^{\prime \prime }<\frac{33}{28}{p}_{k-2}$. Note that $p_{k-1}=max\left\{p_{k-2},,,p^{\prime \prime }\right\}=p^{\prime \prime }$. Two subcases are considered below.

Case 1.1.$s_{k-1}=r^{\prime \prime }$. In this subcase, we have $W{C}_{\mathit{on}}=w_k(s_{k-1}+p_{k-1}+p_k)=w_k(r^{\prime \prime }+p^{\prime \prime }+p_k)$. By Lemma 4.1, we have$$\begin{array}{c}\hfill W{C}_{\mathit{opt}}\ge min\left\{max,\left\{w^{\prime \prime },,,w_k\right\},·,(r_k+max\left\{p^{\prime \prime },,,p_k\right\}),,,w_k,(r^{\prime \prime }+p^{\prime \prime }+p_k)\right\}.\end{array}$$Notice that $r_k>s_{k-1}=r^{\prime \prime }>\frac{4}{3}{p}^{\prime \prime }=\frac{4}{3}{p}_{k-1}$. If $W{C}_{\mathit{opt}}\ge max\left\{w^{\prime \prime },,,w_k\right\}·(r_k+max\left\{p^{\prime \prime },,,p_k\right\})$, then we have $W{C}_{\mathit{opt}}\ge \frac{7}{4}{w}_k{p}_{k-1}$. By Assumption 5.1, we have $W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}\le w_k{p}_{k-1}$. Consequently, $\frac{W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}}{W{C}_{\mathit{opt}}}\le \frac{4}{7}$. Note further that $W{C}_{\mathit{on}}=w_k(r^{\prime \prime }+p^{\prime \prime }+p_k)$. If $W{C}_{\mathit{opt}}\ge w_k(r^{\prime \prime }+p^{\prime \prime }+p_k)$, then the schedule generated by Algorithm $H_2^{\infty }$ is optimal.

Case 1.2.$s_{k-1}=\frac{4}{3}{p}^{\prime \prime }$. In this subcase, we have $W{C}_{\mathit{on}}=w_k(\frac{7}{3}{p}^{\prime \prime }+p_k)$. By Lemma 4.1, it’s easy to obtain that $W{C}_{\mathit{opt}}\ge min\left\{max,\left\{w^{\prime \prime },,,w_k\right\},·,(r_k+max\left\{p^{\prime \prime },,,p_k\right\}),,,w_k,(r^{\prime \prime }+p^{\prime \prime }+p_k)\right\}$. Note that $r_k>s_{k-1}=\frac{4}{3}{p}^{\prime \prime }$ and $p^{\prime \prime }=p_{k-1}$. If $W{C}_{\mathit{opt}}\ge max\left\{w^{\prime \prime },,,w_k\right\}·(r_k+max\left\{p^{\prime \prime },,,p_k\right\})$, then we have $W{C}_{\mathit{opt}}\ge \frac{7}{4}{w}_k{p}_{k-1}$. By Assumption 5.1, we have $W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}\le w_k{p}_{k-1}$. Consequently, $\frac{W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}}{W{C}_{\mathit{opt}}}\le \frac{4}{7}$. Note further that $r^{\prime \prime }>s_{k-2}\ge \frac{4}{7}{p}_{k-2}$ and $p^{\prime \prime }<\frac{33}{28}{p}_{k-2}$. If $W{C}_{\mathit{opt}}\ge w_k(r^{\prime \prime }+p^{\prime \prime }+p_k)$, then we have $r^{\prime \prime }>\frac{16}{33}{p}^{\prime \prime }$ and $W{C}_{\mathit{opt}}\ge w_k(\frac{49}{33}{p}^{\prime \prime }+p_k)$. Consequently, $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{w_k(\frac{7}{3}{p}^{\prime \prime }+p_k)}{w_k(\frac{49}{33}{p}^{\prime \prime }+p_k)}\le \frac{11}{7}$.

Case 2. $s_{k-1}=\frac{72}{49}{p}_{k-2}$. By Step 5.3 of Algorithm $H_2^{\infty }$, we can get that $\frac{3}{4}{p}_{k-2}<p^{\prime \prime }\le p_{k-2}$. Note that $p_{k-1}=max\left\{p_{k-2},,,p^{\prime \prime }\right\}=p_{k-2}$ and $W{C}_{\mathit{on}}=w_k(\frac{121}{49}{p}_{k-1}+p_k)$. If $J^{\prime \prime }$ and $J_k$ are processed in the same batch in $\pi$, then we have $W{C}_{\mathit{opt}}\ge max\left\{w^{\prime \prime },,,w_k\right\}·(r_k+max\left\{p^{\prime \prime },,,p_k\right\})$. Note further that $r_k>s_{k-1}=\frac{72}{49}{p}_{k-2}$, $p^{\prime \prime }>\frac{3}{4}{p}_{k-2}$ and $p_{k-2}=p_{k-1}$. Thus, we have $W{C}_{\mathit{opt}}\ge \frac{7}{4}{w}_k{p}_{k-1}$. By Assumption 5.1, we have $W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}\le w_k{p}_{k-1}$. Consequently, we have $\frac{W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}}{W{C}_{\mathit{opt}}}\le \frac{4}{7}$.

In the following, we assume that $J^{\prime \prime }$ and $J_k$ are processed in different batches in $\pi$. If $w_k\ge w^{\prime \prime }$, then $p_k\ge p^{\prime \prime }$. Note that $r_k>s_{k-1}=\frac{72}{49}{p}_{k-1}$ and $p^{\prime \prime }>\frac{3}{4}{p}_{k-1}$. Then we have $W{C}_{\mathit{opt}}\ge w_k(r_k+p_k)\ge \frac{7}{4}{w}_k{p}_{k-1}$. By Assumption 5.1, we have $W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}\le w_k{p}_{k-1}$. Consequently, we have $\frac{W{C}_{\mathit{on}}-W{C}_{\mathit{opt}}}{W{C}_{\mathit{opt}}}\le \frac{4}{7}$.

If $w^{\prime \prime }>w_k$ and $J_k$ is processed earlier than $J^{\prime \prime }$, then $W{C}_{\mathit{opt}}\ge w^{\prime \prime }(r_k+p_k+p^{\prime \prime })$. Note that $w^{\prime \prime }>w_k$, $r_k>s_{k-1}=\frac{72}{49}{p}_{k-2}=\frac{72}{49}{p}_{k-1}$ and $p^{\prime \prime }>\frac{3}{4}{p}_{k-2}=\frac{3}{4}{p}_{k-1}$. Thus, $W{C}_{\mathit{opt}}\ge w_k(\frac{11}{7}{p}_{k-1}+p_k)$. Since $W{C}_{\mathit{on}}=w_k(\frac{121}{49}{p}_{k-1}+p_k)$, we have $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$. Without loss of generality, we assume that $w^{\prime \prime }>w_k$ and $J^{\prime \prime }$ is processed earlier than $J_k$ in $\pi$. If $J_{k-1}$ and $J^{\prime \prime }$ are processed in the same batch in $\pi$, then we have $W{C}_{\mathit{opt}}\ge w_k(r^{\prime \prime }+max\left\{p^{\prime \prime },,,p_{k-1}\right\}+p_k)$. Note that $r^{\prime \prime }>s_{k-2}\ge \frac{4}{7}{p}_{k-2}=\frac{4}{7}{p}_{k-1}$. Thus, we have $W{C}_{\mathit{opt}}\ge w_k(\frac{11}{7}{p}_{k-1}+p_k)$. Since $W{C}_{\mathit{on}}=w_k(\frac{121}{49}{p}_{k-1}+p_k)$, we have $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$. If $J_{k-1}$ and $J^{\prime \prime }$ are processed in different batches in $\pi$, then there are three possibilities. The first possibility, $J_{k-1}$ is processed earlier than $J^{\prime \prime }$ and $J^{\prime \prime }$ is processed earlier than $J_k$ in $\pi$. Then we have $W{C}_{\mathit{opt}}\ge w_k(r_{k-1}+p_{k-1}+p^{\prime \prime }+p_k)\ge w_k(p^{\prime \prime }+p_{k-1}+p_k)$. The second possibility, $J^{\prime \prime }$ is processed earlier than $J_{k-1}$ and $J_{k-1}$ is processed earlier than $J_k$ in $\pi$. Then we have $W{C}_{\mathit{opt}}\ge w_k(r^{\prime \prime }+p^{\prime \prime }+p_{k-1}+p_k)\ge w_k(p^{\prime \prime }+p_{k-1}+p_k)$. The three possibility, $J^{\prime \prime }$ is processed earlier than $J_k$ and $J_k$ is processed earlier than $J_{k-1}$ in $\pi$. If $w^{\prime \prime }\ge w_{k-1}$, then $p^{\prime \prime }\ge p_{k-1}$. Thus, we have $W{C}_{\mathit{opt}}\ge w_k(r^{\prime \prime }+p^{\prime \prime }+p_k)\ge w_k(r^{\prime \prime }+p_{k-1}+p_k)$. If $w_{k-1}>w^{\prime \prime }$, note that $w^{\prime \prime }>w_k$, then we have $W{C}_{\mathit{opt}}\ge w_{k-1}(r^{\prime \prime }+p^{\prime \prime }+p_k+p_{k-1})\ge w_k(p^{\prime \prime }+p_{k-1}+p_k)$. Since $p^{\prime \prime }>\frac{3}{4}{p}_{k-1}$ and $r^{\prime \prime }>s_{k-2}\ge \frac{4}{7}{p}_{k-2}=\frac{4}{7}{p}_{k-1}$, we have $W{C}_{\mathit{opt}}\ge w_k(\frac{11}{7}{p}_{k-1}+p_k)$. Note that $W{C}_{\mathit{on}}=w_k(\frac{121}{49}{p}_{k-1}+p_k)$. Thus, we have $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$. $\square$

From Lemmas 5.4 and 5.5, the relation $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}\le \frac{11}{7}$ holds under Assumption 5.1. Combining Lemmas 5.2 and 5.3, we conclude the following theorem.

Theorem 5.2

For problem $1|\text{online},{\beta }^{\ast },\text{L-restart}|W{C}_{max}$, Algorithm $H_2^{\infty }$ has a competitive ratio $\frac{11}{7}$.

Next, we present a job instance I to show that the bound $\frac{11}{7}$ is tight. Let $ϵ$ be a sufficiently small positive number. The instance I consists of two jobs $J_1$ and $J_2$ with $(r_1,p_1,w_1)=(0,1,1)$ and $(r_2,p_2,w_2)=(1,\frac{3}{4}+ϵ,\frac{44}{49})$. By Algorithm H, $J_1$ is first processed at time $\frac{4}{7}$ and then restarted at time $\frac{72}{49}$. That is, the batch $\{J_1,J_2\}$ is processed at time $\frac{72}{49}$. Thus, we have $W{C}_{\mathit{on}}=1\times (\frac{72}{49}+max\left\{1,,,\frac{3}{4},+,ϵ\right\})=\frac{121}{49}$. Note that the off-line optimal schedule will first schedule $J_1$ at time 0 and then schedule $J_2$ at time 1. Thus, we have $W{C}_{\mathit{opt}}=\frac{44}{49}\times (1+\frac{3}{4}+ϵ)=\frac{44}{49}\times (\frac{7}{4}+ϵ)$. Consequently, we have $\frac{W{C}_{\mathit{on}}}{W{C}_{\mathit{opt}}}=\frac{\frac{121}{49}}{\frac{44}{49}\times (\frac{7}{4}+ϵ)}\to \frac{11}{7}$.

Conclusions and future research

In this paper we study the online over-time scheduling on an unbounded parallel-batch machine to minimize the weighted makespan. We show that the general problem has a low bound 2 and then design a 4-competitive online algorithm. For the special case with the agreeable processing times and weights, we present an online algorithm with the best possible competitive ratio $\frac{\sqrt{5}+1}{2}\approx 1.618$. We also introduce limited restarts into the above special case and present an online algorithm with a better competitive ratio $\frac{11}{7}\approx 1.571$.

For future research, it is worthwhile to study the general online scheduling problem with or without restarts. Furthermore, it is challenging to develop a better online algorithm to improve the current competitive ratio $\frac{11}{7}\approx 1.571$ if limited restarts are allowed. Finally, it is also interesting to expand the problem with limited restarts by considering individual cases based on whether rescheduling occurs periodically, arbitrarily, or in response to changing conditions.

Funding

This work was supported by the National Natural Science Foundation of China under grant numbers 12271491, 12471305, 12071442 and 12371318.

Data availibility

Not applicable.

Declarations

Conflict of interest

The authors report no Conflict of interest.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

References

Chai, X; Lu, LF; Li, WH; Zhang, LQ. Best-possible online algorithms for single machine scheduling to minimize the maximum weighted completion time. Asia-Pacific J Oper Res; 2018; 35, 6 1850048.3884863 [DOI: https://dx.doi.org/10.1142/S0217595918500483] 1407.90144

Deng, XT; Poon, CK; Zhang, YZ. Approximation algorithms in batch processing. J Comb Optim; 2003; 7, pp. 247-257.2024885 [DOI: https://dx.doi.org/10.1023/A:1027316504440] 1053.90033

Feng, Q; Yuan, JJ. NP-hardness of a multicriteria scheduling on two families of jobs. OR Trans; 2007; 11, pp. 121-126.1232.91552

Fu, RY; Tian, J; Yuan, JJ; He, C. On-line scheduling on a batch machine to minimize makespan with limited restarts. Oper Res Lett; 2008; 36, pp. 255-258.2396576 [DOI: https://dx.doi.org/10.1016/j.orl.2007.07.001] 1144.90378

Fu, RY; Tian, J; Yuan, JJ; Lin, YX. Online scheduling in a parallel batch processing system to minimize makespan using restarts. Theor Comput Sci; 2007; 374, 1–3 pp. 196-202.2317480 [DOI: https://dx.doi.org/10.1016/j.tcs.2006.12.040] 1162.90452

Lee, CY; Uzsoy, R; Martin-Vega, LA. Efficient algorithms for scheduling semi-conductor burn-in operations. Oper Res; 1992; 40, pp. 764-775.1179802 [DOI: https://dx.doi.org/10.1287/opre.40.4.764] 0759.90046

Li, WH; Chai, X. Online scheduling on bounded batch machines to minimize the maximum weighted completion time. J Oper Res Soc Chin; 2018; 6, 3 pp. 455-465.3832166 [DOI: https://dx.doi.org/10.1007/s40305-017-0179-x] 1413.90095

Li, WJ. A best possible online algorithm for the parallel-machine scheduling to minimize the maximum weighted completion time. Asia-Pacific J Oper Res; 2015; 32, 4 1550030.3372680 [DOI: https://dx.doi.org/10.1142/S021759591550030X] 1325.90046

Liu, PH; Lu, XW; Fang, Y. A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines. J Sched; 2012; 15, 1 pp. 77-81.2896972 [DOI: https://dx.doi.org/10.1007/s10951-009-0154-4] 1280.68298

Oron, D; Shabtay, D; Steiner, G. Single machine scheduling with two competing agents and equal job processing times. Euro J Oper Res; 2015; 244, pp. 86-99.3320768 [DOI: https://dx.doi.org/10.1016/j.ejor.2015.01.003] 1346.90378

Tian, J; Cheng, TCE; Ng, CT; Yuan, JJ. Online scheduling on unbounded parallel-batch machines to minimize the makespan. Inf Process Lett; 2009; 109, 21 pp. 1211-1215.2573323 [DOI: https://dx.doi.org/10.1016/j.ipl.2009.08.008] 1206.68072

van den Akker, M; Hoogeveen, H; Vakhania, N. Restarts can help in the on-line minimization of the maximum delivery time on a single machine. J Sched; 2000; 3, 6 pp. 333-341.2006888 [DOI: https://dx.doi.org/10.1002/1099-1425(200011/12)3:6<333::AID-JOS53>3.0.CO;2-8] 0966.90033

Yuan, JJ; Fu, RY; Ng, CT; Cheng, TCE. A best possible online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan. J Sched; 2011; 14, pp. 361-369.2818764 [DOI: https://dx.doi.org/10.1007/s10951-010-0172-2] 1229.90067

Yuan, JJ; Ng, CT; Cheng, TCE. Scheduling with release dates and preemption to minimize multiple max-form objective functions. Euro J Oper Res; 2020; 280, pp. 860-875.4011138 [DOI: https://dx.doi.org/10.1016/j.ejor.2019.07.072] 1430.90296

Zhang, GC; Cai, XQ; Wong, CK. Online algorithms for minimizing makespan on batch processing machines. Naval Res Logist; 2001; 48, pp. 241-258.1817652 [DOI: https://dx.doi.org/10.1002/nav.5] 1018.90017