Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart

Abstract

We consider the online scheduling of equal length jobs on unbounded parallel batch processing machines to minimize makespan with limited restart. In the problem $m$ identical unbounded parallel batch processing machines are available to process the equal length jobs arriving over time. The processing batches are allowed limited restart. Here, “restart” means that a running task may be interrupted, losing all the work done on it, and the jobs in the interrupted task are then released and become independently unscheduled jobs, called restarted jobs. “Limited restart” means that only a running batch that contains no restarted jobs can be restarted. For this problem, we present a best possible online algorithm.

1 Introduction

In this paper, we consider the online scheduling of equal length jobs on $m$ identical unbounded parallel batch processing machines with limited restart. In the online version, each job becomes available at its arrival time, which is unknown in advance, and its characteristics become known upon its arrival. A parallel batch processing machine is modeled as a system that can process up to $b$ jobs simultaneously as a batch, where $b$ is the batch capacity. The processing time of a batch is equal to the longest processing time of the jobs in the batch. All jobs processed in a batch start at the same time and complete at the same time. Depending on the characteristic of batch capacity $b$, there are two different models. One is the unbounded model, in which the capacity of batches is sufficiently large, i.e., $b=\infty$. The other is the bounded model, in which the capacity of batches is finite, i.e., $b<\infty$. In this paper we study the unbounded model, i.e., $b=\infty$. In our research, we assume that all jobs have equal processing times. By scaling, we may assume that each job has a processing time $1$. The objective of the problem considered in this paper is to assign jobs to batches and determine their processing sequence on each machine so as to minimize the makespan, namely, the maximum completion time of all jobs.

Restart (see Hoogeveen et al. 2000) means that a running task may be interrupted, losing all the work done on it. The jobs in the interrupted task, which are called restarted jobs, are then released and become independently unscheduled jobs which can be scheduled later from scratch. Allowing restarts may give us a better schedule because we have the chance to change our original mind and make a better decision. For some scheduling models, we can obtain more efficient online algorithms by using restarts. For example, for online minimization of the maximum delivery time on a single machine using restarts, Van der Akker et al. (2003) gave an algorithm with competitive ratio $3/2$; while without restarts, a best possible online algorithm with competitive ratio $(\sqrt{5}+1)/2$ was given in Hoogeveen and Vestjens (2000). We also can see more research on online algorithms using restarts in Epstein and Stee (2003), Van Stee and La Poutré (2005), and Yuan et al. (2011).

Limited restart, which is first introduced in Fu et al. (2008), means that a job can be restarted at most once. So in the online parallel batch scheduling with limited restart, once a running batch contains some restarted jobs, we cannot interrupt the processing of the batch again. The assumption of limited restart is motivated by considering restarts as scarce resources. In practice, too many restarts of a job may cause the waste of resources and increase the probability of a spoiled product.

The quality of an online algorithm is measured by the competitive ratio. An online algorithm is called $\rho$ -competitive if for any input instance, it generates a schedule with an objective value no worse than $\rho$ times the value of an optimal off-line schedule. The nearer the ratio is to $1$, the better the algorithm is.

Parallel batch scheduling is motivated by burn in operations in semiconductor manufacture (see Uzsoy et al. 1992, 1994). Online scheduling on parallel batch processing machines was first studied by Zhang et al. (2001) and Deng et al. (2003). They studied online scheduling problem to minimize makespan on a single unbounded parallel batch processing machine and independently presented the same best possible online algorithm which is $(\sqrt{5}+1)/2$-competitive. For the corresponding problem with bounded batch capacity, Poon and Yu (2005) showed that any FBLPT-based algorithm has competitive ratio at most $2$ and for batch capacity $2$, they gave an $7/4$-competitive online algorithm. Zhang et al. (2003) studied the online scheduling of equal length jobs on $m$ parallel batching machines. They first presented a $(1+\beta _{m})$-competitive optimal online algorithm for the unbounded version, where $\beta _{m}$ is the positive solution of the equation $(1+\beta _{m})^{m+1}=\beta _{m}+2$. They also proposed a $(\sqrt{5}+1)/2$-competitive optimal online algorithm for the bounded version. For the problem of minimizing makespan on two unbounded parallel batch processing machines, Nong et al. (2008) proposed an online algorithm which is $\sqrt{2}$-competitive. And later Tian et al. (2009b) showed that $\sqrt{2}$ is the lower bound for the problem and gave a new optimal online algorithm. For the corresponding problem on $m$ unbounded parallel batch processing machines, Liu et al. (2012) and Tian et al. (2009a) independently presented two different but best possible online algorithms which are $(1+\alpha _{m})$-competitive, where $\alpha _{m}$ is the positive solution of the equation $a_{m}^{2}+m\alpha _{m}-1=0$.

For minimizing makespan on an unbounded parallel batch processing machine using restarts, Fu et al. (2007) showed that there exists no on-line algorithm with a competitive ratio less than $(5-\sqrt{5})/2$ and a best possible online algorithm matching the lower bound was presented in Yuan et al. (2011). Fu et al. (2008) studied the corresponding problem with limited restart and proposed a best possible online algorithm with competitive ratio $3/2$. For minimizing makespan on two unbounded parallel batch processing machines using limited restart, a best possible online algorithm with competitive ratio $(\sqrt{3}+1)/2$ was proposed in Fu et al. (2010) under the second-restart assumption. For minimizing makespan on a bounded parallel batch processing machine using restarts, an online algorithm with competitive ratio $3/2$ was given in Chen et al. (2009). Recently, Liu and Yuan (2014) presented best possible online algorithms for minimizing makespan of equal length jobs on a bounded parallel batch processing machine with limited restart or restarts. More results of online scheduling in parallel batch machines can be found in Tian et al. (2014).

This paper studies online scheduling of equal length jobs on $m$ unbounded parallel batch machines to minimize makespan with limited restart. In the scheduling notation, the problem is denoted by $Pm|\text{ online },\; r_j,\; p_j=1,\;\text{ p-batch },\; b=\infty ,\; \text{ L-restart }|C_{\max }$.

The research approaches in this paper can be stated as follows. For each $\alpha$ with $0<\alpha <1$, we define an online algorithm $\text{ LAZY }(\alpha )$. Based on algorithm $\text{ LAZY }(\alpha )$, we generate a job instance $I(\alpha )$. The candidate choices of $\alpha$ in our research are given by $\alpha {(i,j)}$, where $i,j$ are positive integers with $j<i\le l_{m}$ and $\alpha {(i,j)}$ is the positive solution of equation $(1+x)^{i}-(1+x)^{j}=1$. Here, $l_{m}$ is a positive integer associated with $m$ and will be defined later in the paper. Then we define

$$\begin{aligned} \alpha _m = \min \limits _{0<j<i\le l_{m}}\big \{\alpha (i,j) : \text{ LAZY }(\alpha (i,j)) \text{ is } (1+\alpha (i,j))\text{-competitive } \text{ on } \text{ instance } I(\alpha {(i,j)})\big \}. \end{aligned}$$

It is proved that $\alpha _{m}$ is also the minimum value of $\alpha$ with $0<\alpha <1$ so that $\text{ LAZY }(\alpha )$ is $(1+\alpha )$-competitive on instance $I(\alpha )$. Then we show that any online algorithm for problem $Pm|\text{ online },\; r_j,\; p_j=1,\;\text{ p-batch },\; b=\infty ,\; \text{ L-restart }|C_{\max }$ has a competitive ratio of at least $1+\alpha _{m}$. Finally, we present an $(1+\alpha _{m})$-competitive algorithm $\textsc {ALG}_m$ based on algorithm $\text{ LAZY }(\alpha _{m})$. This implies that $\textsc {ALG}_m$ is the best possible.

In Sect. 2, for each $\alpha$ with $0<\alpha <1$, we first present the online algorithm $\text{ LAZY }(\alpha )$ and, based on the algorithm, we generate a job instance $I(\alpha )$ and a schedule $\sigma _{\alpha }$. Some related properties are presented. In Sect. 3, we present the lower bound $1+\alpha _{m}$ for the problem studied in this paper. In Sect. 4, we present the $(1+\alpha _{m})$-competitive algorithm $\textsc {ALG}_m$.

2 The Algorithm $\textsc {LAZY}(\alpha )$

Throughout this paper, a restricted batch refers to a batch which contains at least one restarted job, and a free batch refers to a batch which contains no restarted jobs. This implies that, in an online algorithm, a running restricted batch cannot be interrupted again. Note that a running free batch can be interrupted freely and the batch capacity is unbounded. Then we take the convention that, in an online algorithm, if we start a restricted batch at a time $S$, then we will interrupt all free batches running at time $S$ and generate a restricted batch which consists of all interrupted jobs and all other unscheduled available jobs at time $S$.

The following notations are used in our discussion:

• $F(i,j) = i+ (i+1)+\cdots + j$ for positive integers $i,j$ with $i\le j$.

• $\beta _{m}$ is the positive solution of equation $(1+x)^{F(1, m+1)}-(1+x)^{m+1}=1$.

• $l_{m}=\min \{ i: i\ge F(1,m+1),\; \beta _{m}(1+\beta _{m})^{i}\ge 1 \}$.

• $\alpha {(i,j)}$ is the positive solution of equation $(1+x)^{i}-(1+x)^{j}=1$ where $i$ and $j$ are both positive integers with $i>j$. Then $\beta _m =\alpha {(F(1,m+1), m+1)}$.

Some properties of the above notations can be observed as follows which will be used in further discussions.

• For every two positive integers $i$ and $j$ with $i>j$, $(1+x)^i - (1+x)^j -1$ is monotonically increasing in $x\ge 0$.

• $\alpha (i,j)$ is the unique positive solution of equation $(1+x)^i - (1+x)^j=1$ with $i>j$. For $0 < \alpha < \alpha (i,j)$, $(1+\alpha )^i -(1+\alpha )^j < 1$.

• $\beta _m = \alpha (F(1, m+1), m+1)$ is monotonically decreasing in $m$.

When an online algorithm starts to process a batch $B$ at a time $t$, we use the terminology “a job $J$ arrives at time $t$” to denote the fact that job $J$ arrives at time $t+\varepsilon$ for some very small positive number $\varepsilon$. In the discussion, we use $t$ to replace $t+\varepsilon$ without loss of validity.

Since a job can be restarted once, the first starting time of a job is defined to be the starting time of the earliest starting batch including the job. Since the jobs have the equal processing time 1, the optimal value of any job instance is given by $r_{\max }+1$ where $r_{\max }$ is the latest arriving time of jobs in the instance. Then we concentrate our attention on the schedules generated by online algorithms. Since the batch capacity is unbounded, we may assume that at most one batch starts at a time instant.

Let $\sigma$ be an online schedule for a job instance. Let $S_1<S_2< \cdots < S_n$ be the sequence of time instants so that for each $i$ with $1\le i\le n$, a batch $B_i$ starts at time $S_i$ in $\sigma$. By omitting the machine information, the online schedule $\sigma$ can be denoted by the sequence $\sigma = ((S_1, B_1), \ldots , (S_n, B_n))$. When no ambiguity can occur, we write $\sigma = (S_1,\ldots ,S_n)$ for simplicity. We take the convention that the information of all starting batches (including the interrupted batches) is implied in $\sigma$. Thus, an online schedule is in fact the record of the implementation of an online algorithm. In the following, we just use “schedule” to denote “online schedule”.

For convenience, we sometimes require that a batch $B_i$ cannot be interrupted, no matter it contains restarted jobs or not. In this case, $B_i$ is called an assigned restricted batch. In an online algorithm, we cannot interrupt the processing of a restricted or assigned restricted batch.

In the following discussion, we assume that $m$ is an arbitrary fixed positive integer. For a given online algorithm $H$, we use the following algorithm, called Generating $\mathcal{I}(H)$, to generate a job instance $\mathcal{I}(H)$ together with the schedule generated by algorithm $H$ on $\mathcal{I}(H)$. We use $B_{i}{(H)}$ to denote the $i$-th starting batch, $S_{i}{(H)}$ the starting time of $B_{i}{(H)}$ and $r_{i}{(H)}$ the latest arriving time of jobs in $B_{i}{(H)}$. $B'_{i}(H)$ is used to denote the $i$-th starting restricted batch, $S'_{i}(H)$ the starting time of $B'_{i}(H)$ and $r'_{i}{(H)}$ the latest arriving time of jobs in $B'_{i}{(H)}$. Furthermore, we use $B_{i,k}(H)$ to denote the $i$-th starting batch after $S'_{k}(H)$, $S_{i,k}(H)$ the starting time of $B_{i,k}(H)$ and $r_{i,k}{(H)}$ the latest arriving time of jobs in $B_{i,k}{(H)}$.

Generating $\mathcal{I}(H)$: Given any online algorithm $H$, we release one job at time $0$, and then greedily release a new job whenever $H$ starts a batch (that is, $\varepsilon$ time after $H$ starts a batch for some very small positive $\varepsilon$). We continue doing this until $n$ jobs have been released in total, where $n$ is sufficiently large for our discussion. The resulting input is denoted by $\mathcal{I}(H)$, and the schedule is denoted by $\sigma _H$. $\Box$

Note that Generating $\mathcal{I}(H)$ generates a job instance $\mathcal{I}(H)= \{J_1(H),\ldots ,J_n{(H)}\}$ together with a schedule $\sigma _H= (S_1(H), \ldots , S_n(H))$ for $\mathcal{I}(H)$. We further define $S_0(H)=0$ and $B_0(H)=\emptyset$.

For an online algorithm $H$ and a positive number $\alpha$, we say that $\sigma _H$ is an $\alpha$ -nice schedule if all batches $B_i(H)$ satisfy $S_i(H)\le (1+\alpha )S_{i-1}(H)+\alpha$, i.e., $S_i(H)+1\le (1+\alpha )(S_{i-1}(H)+1)$. If $S_i(H)= (1+\alpha )S_{i-1}(H)+\alpha$, i.e., $S_i(H)+1= (1+\alpha )(S_{i-1}(H)+1)$, then $B_i(H)$ is called an $\alpha$ -regular batch in $\sigma _H$. Furthermore, $\sigma _H$ is called an $\alpha$ -regular schedule if all batches in $\sigma _H$ are $\alpha$-regular.

Let $U(t)$ be the set of the available unscheduled jobs at time $t$ in an online algorithm. Write $r(t) =\max \{r_{j}:J_{j}\in U(t)\}$. Let $\alpha$ be a real number with $0<\alpha <1$. The online algorithm, called $\textsc {LAZY}(\alpha )$, can be described as follows.

Algorithm LAZY($\alpha )$:

• 1. Wait until the time $t$ so that $U(t)\not =\emptyset$.

• 2. Wait until the current time $t = (1+\alpha )r(t) + \alpha$.

• 3. If all machines are busy at time $t$, stop all free batches (if any).

• 4. Wait until either a machine is available or a new job arrives.

• 5. If no new jobs arrive during the waiting procedure in step 4, start to process all unfinished jobs in one batch on an available machine. Go to step 1.

• 6. If a new job arrives during the waiting procedure in step 4, go to step 2.

$\square$

Note that, for the instance consisting of all jobs released by a time $t$, the optimal off-line schedule has makespan $r(t)+1$. Therefore, if $\textsc {LAZY}(\alpha )$ ever waits in step 4 and a batch is processed in step 5, then some batch starts at a time $t> (1+\alpha )r(t)+\alpha$, and so, $\textsc {LAZY}(\alpha )$ is not $(1+\alpha )$-competitive.

By running algorithm $\textsc {LAZY}(\alpha )$ for instance $\mathcal{I}(\textsc {LAZY}(\alpha ))$, we get a schedule $\sigma _{\mathrm{LAZY}(\alpha )}$. By algorithm $\textsc {LAZY}(\alpha )$, we have $S_i(\textsc {LAZY}(\alpha ))\ge (1+\alpha )S_{i-1}(\textsc {LAZY}(\alpha ))+\alpha$ for $i\ge 1$. Since $S_0(\textsc {LAZY}(\alpha ))=0$, this further implies that $S_i(\textsc {LAZY}(\alpha ))\ge (1+\alpha )^i-1$ for $i\ge 1$.

The following notations are also used in our discussion.

• $\mathcal{I}(\alpha )$ is the job instance consisting of the first $l_{m}$ jobs of $\mathcal{I}(\textsc {LAZY}(\alpha ))$.

• $\sigma _{\alpha }$ is the subschedule of $\sigma _{\mathrm{LAZY}(\alpha )}$ for instance $\mathcal{I}(\alpha )$. Then there are total $l_{m}$ batches in $\sigma _{\alpha }$.

• Based on $\sigma (\alpha )$, we define $B_i(\alpha )$, $S_i(\alpha )$, etc. completely analogously to $B_i(H)$, $S_i(H)$, etc..

• $S_{0}(\alpha )=S'_{0}(\alpha )=0$.

• $S_{0,k}(\alpha )=S'_{k}(\alpha )$.

Note that $\sigma _{\alpha }=(S_1(\alpha ), \ldots , S_{l_m}(\alpha ))$. We first prove several useful inequalities.

Recall that, for every two positive integers $i$ and $j$ with $i>j$, $(1+x)^i - (1+x)^j -1 = (1+x)^j ((1+x)^{i-j} -1)-1$ is monotonically increasing in $x\ge 0$ and $\alpha (i,j)$ is the unique positive solution of equation $(1+x)^j( (1+x)^{i-j} -1)-1=0$. So, if $(i, j)$ and $(i', j')$ are two pairs of positive integers with $i>j$ and $i'>j'$, then $(j, i-j) \le (j', i'-j')$ implies that $\alpha (i, j) \ge \alpha (i', j')$. $(j, i-j) \le (j', i'-j')$ and $(j, i-j) \ne (j', i'-j')$ imply that $\alpha (i, j)> \alpha (i', j')$. Applying this observation to the three pairs $(m+1, 1)$, $(2m+1, 2)$, and $(3m, m+1)$, we can deduce that

$$\begin{aligned} \alpha (m+1,1) > \alpha (2m+1,2) \ge \alpha (3m,m+1). \end{aligned}$$

(1)

Similarly, applying the above observation to the two pairs $(2m+1, 2)$ and $(F(1,m+1), m+1)$ by noting that $2m-1\le F(1,m) = F(1,m+1)- (m+1)$, we can deduce that

$$\begin{aligned} \beta _{m} = \alpha (F(1,m+1), m+1)\le \alpha {(2m+1, 2)}, \end{aligned}$$

(2)

where the equality in (2) follows from the definition of $\beta _{m}$.

Lemma 2.1

Let $\alpha$ be a real number with $0<\alpha < 1$. Then $\sigma _{\alpha }$ has the following properties.

• (i) Every batch $B_k(\alpha )$ with $S_{k}(\alpha ) \le S'_m(\alpha )$ is $\alpha$-regular in $\sigma _{\alpha }$ and $S_{k}(\alpha )=(1+\alpha )^k-1$.

• (ii) If $\alpha \le \alpha {(2m+1,2)}$, then $B_{1}'(\alpha )$ exists and $B_{1}'(\alpha )=B_{m+1}(\alpha )$.

• (iii) If $\alpha \ge \alpha {(2m+1,2)}$, then $\sigma _{\alpha }$ is an $\alpha$-regular schedule.

Proof

By the definition of $\textsc {LAZY}(\alpha )$ and $I(\alpha )$, we have $S_0(\alpha )=0$ and $S_k(\alpha ) = (1+\alpha )S_{k-1}(\alpha )+\alpha$ as long as $\textsc {LAZY}(\alpha )$ does not wait in Step 4. But $\textsc {LAZY}(\alpha )$ only waits in Step 4 if all machines are running restricted batches at the time it enters Step 4, which can happen at the earliest after the $m$th restricted batch has started. Now induction on $k$ proves (i).

To prove (ii), suppose that $\alpha$ is an arbitrary positive number with $\alpha \le \alpha {(2m+1,2)}$. From (1), we have $\alpha {(2m+1,2)}<\alpha (m+1,1)$, and so, $\alpha < \alpha (m+1,1)$. Since $\alpha (m+1,1)$ is the positive solution of equation $(1+x)^{m+1}-(1+x)=1$ and $(1+x)^{m+1}-(1+x)$ is monotonically increasing in $x>0$, we have $(1+\alpha )^{m+1}-(1+\alpha )<1$. From property (i), $B_i(\alpha )$ $(1\le i\le m)$ are all $\alpha$-regular with $S_i(\alpha )=(1+\alpha )^{i}-1$. Thus $(1+\alpha )S_{m}(\alpha )+\alpha -(S_{1}(\alpha )+1)= (1+\alpha )^{m+1}-(1+\alpha )-1<0$. This implies that at time $(1+\alpha )S_{m}(\alpha )+\alpha$, $B_i(\alpha )$ $(1\le i\le m)$ are $m$ free batches running on different machines and all uncompleted. So by algorithm $\textsc {LAZY}(\alpha )$, $B_{m+1}(\alpha )$ is a restricted batch and $B_{1}'(\alpha )=B_{m+1}(\alpha )$.

To prove (iii), let $\alpha$ be a positive number with $\alpha \ge \alpha {(2m+1,2)}$. From (1), we have $\alpha {(2m+1, 2)}\ge \alpha {(3m, m+1)}$, and so, $\alpha \ge \alpha {(3m, m+1)}$. If there are no restricted batches in $\sigma _{\alpha }$, the result holds trivially. Thus we may assume that there are some restricted batches in $\sigma _{\alpha }$. If possible let $k\le l_m$ be the minimum so that $B_k(\alpha )$ is not $\alpha$-regular. Then $S_{k}(\alpha )>(1+\alpha )S_{k-1}(\alpha )+\alpha$ and $B_{i}(\alpha )$, $1\le i\le k-1$, are $\alpha$-regular. From the fact $S_{0}(\alpha )=0$, we can inductively deduce that $S_{i}(\alpha ) =(1+\alpha )^{i}-1$ for $1\le i\le k-1$.

The choice of $k$ also implies that, at time $t=(1+\alpha )S_{k-1}(\alpha )+\alpha$, each machine is occupied by a restricted batch. Suppose that $B_{k_1}(\alpha ), \ldots , B_{k_m}(\alpha )$ are the $m$ restricted batches running at time $t$ with $k_1<\cdots < k_m=k-1$. Then $t<S_{k_1}(\alpha )+1$. By the definition of $\mathcal{I}(\alpha )$, for each $i$ with $2\le i \le m$, $B_{k_i-1}(\alpha )$ is a free batch interrupted by $B_{k_i}(\alpha )$ at time $S_{k_i}(\alpha )$. Then $k_i\ge k_{i-1}+2$ for $2\le i \le m$. It follows that $k_m \ge k_1+ 2(m-1)$.

Now $S_{k-1}(\alpha )+1 =S_{k_m}(\alpha )+1 =(1+\alpha )^{k_m-k_1}(S_{k_1}(\alpha )+1) \ge (1+\alpha )^{2m-2}(S_{k_1}(\alpha )+1)$. Then $t =(1+\alpha )(S_{k-1}(\alpha )+1)-1 \ge (1+\alpha )^{2m-1}(S_{k_1}(\alpha )+1)-1$. Since $t<S_{k_1}(\alpha )+1$, then $((1+\alpha )^{2m-1}-1)(S_{k_1}(\alpha )+1)<1$. As $S_{k_1}(\alpha ) \ge S_{1}'(\alpha )\ge S_{m+1}(\alpha )=(1+\alpha )^{m+1}-1$, we have $(1+\alpha )^{3m} -(1+\alpha )^{m+1}<1$. This implies that $\alpha < \alpha {(3m, m+1)}$, a contradiction. The proof is completed. $\square$

Lemma 2.2

Let $\alpha$ be a real number with $0<\alpha <\beta _{m}$. Then, for every online algorithm $A$, $\sigma _{A}$ is not an $\alpha$-nice schedule. Moreover, $\sigma _{\alpha }$ is not an $\alpha$-nice schedule.

Proof

From (2), we have $\beta _{m}\le \alpha {(2m+1, 2)}$. Let $A$ be an arbitrary online algorithm. We consider the job instance $\mathcal{I}(A)$ and the schedule $\sigma _{A}$ generated by algorithm Generating $\mathcal{I}(A)$ so that we have sufficiently many batches in $\sigma _{A}$.

Let $\sigma ^{1}_{A}$ be the subschedule of $\sigma _{A}$ consisting of the first $l_{m}$ starting batches in $\sigma _{A}$. Note that $l_{m}\ge F(1,m+1)$ by the definition of $l_{m}$. Now we prove that $\sigma ^{1}_{A}$ is not an $\alpha$-nice schedule. Suppose to the contrary that $\sigma ^{1}_{A}$ is an $\alpha$-nice schedule. We claim that the following statements hold for $\sigma ^{1}_{A}$:

• $B'_1(A), \ldots , B'_m(A)$ exist and $S_{i}'(A)\le (1+\alpha )^{m-i+2}(S_{i-1}'(A)+1)-1$ for $i=1,\ldots , m$,

• at time $S'_m(A)$ the $m$ machines are occupied by the $m$ restricted batches, and

• each $B'_i(A)$ ($1\le i\le m$) is just $B_{j_{i}}(A)$ for some $j_{i}\le F(m-i+2,m+1)$.

To this end, we recall that $(1+x)^{m+1}-(1+x)-1$ is monotonically increasing in $x>0$. Then we have

$$\begin{aligned}&S_{m+1}(A)-\big (S_{1}(A)+1\big )\\&\quad \le \big (1+\alpha \big )^{m}\big (S_{1}(A)+1\big )-\big (S_{1}(A)+1\big )-1 \\&\quad \le \big (1+\alpha \big )^{m+1}-\big (1+\alpha \big )-1 \\&\quad < \big (1+\beta _{m}\big )^{m+1}-\big (1+\beta _{m}\big )-1 \\&\quad < \big (1+\alpha {(m+1, 1)}\big )^{m+1}-\big (1+\alpha {(m+1, 1)}\big )-1 \\&\quad = 0, \end{aligned}$$

where the first two inequalities follow from the assumption that $\sigma ^{1}_{A}$ is an $\alpha$-nice schedule, and the rest inequalities hold as $0<\alpha <\beta _{m}\le \alpha {(2m+1, 2)}<\alpha {(m+1,1)}$ from (1) and (2). This implies that $S_{m+1}(A) < S_1(A)+1$, and so, the first $m+1$ batches in $\sigma ^{1}_{A}$ must contain a restricted batch. Hence, $B'_1(A)$ exists and $S_{1}'(A) \le S_{m+1}(A)\le (1+\alpha )^{m+1}-1=(1+\alpha )^{m+1}(S_{0}'(A)+1) -1=(1+\alpha )^{F(m-1+2,m+1)}(S_{0}'(A)+1)-1$. This further implies that $B'_1(A)$ is just $B_{j_{1}}(A)$ for some $j_{1}\le m+1=F(m-1+2,m+1)$.

Let $k\le m$ be the maximum so that $B'_1(A), \ldots , B'_{k-1}(A)$ exist and, at time $S'_{k-1}(A)$, $k-1$ machines are occupied by the $k-1$ restricted batches. For $i=1,\ldots , k-1$, as there are at most $m-i+1$ free batches between $B'_{i-1}(A)$ and $B'_i(A)$, each $B'_i(A)$ ($1\le i\le k-1$) is just $B_{j_{i}}(A)$ for some $j_{i}\le m-i+2+j_{i-1}\le F(m-i+2,m+1)$ and $S'_i(A)\le (1+\alpha )^{m-i+2}(S'_{i-1}(A)+1)-1$.

From the fact that $B_{m-k+2, k-1} (A)$ is some batch $B_{j} (A)$ with $j=m-k+2+j_{k-1}\le m-k+2+F(m-(k-1)+2,m+1)=F(m-k+2,m+1)<F(1,m+1)\le l_{m}$, we have

$$\begin{aligned}&S_{m-k+2, k-1} (A) -\big (S'_1(A)+1\big )\\&\quad \le \big (1+\alpha \big )^{m-k+2}\big ( S'_{k-1}(A)+1\big ) -1 -\big (S'_1(A)+1\big ) \\&\quad \le \big (1+\alpha \big )^{F\big (m-k+2,m\big )}\big (S'_{1}(A)+1\big )-\big (S'_1(A)+1\big )-1 \\&\quad \le \big (1+\alpha \big )^{F\big (m-k+2,m+1\big )}-\big (1+\alpha \big )^{m+1}-1 \\&\quad < \big (1+\alpha \big )^{F\big (1,m+1\big )}-\big (1+\alpha \big )^{m+1}-1 \\&\quad < \big (1+\beta _{m}\big )^{F\big (1,m+1\big )}-\big (1+\beta _{m}\big )^{m+1}-1 \\&\quad = 0, \end{aligned}$$

where the first inequality follows from the assumption that $\sigma ^{1}_{A}$ is an $\alpha$-nice schedule, the next two inequalities follow from the fact that $S'_i(A)\le (1+\alpha )^{m-i+2}(S'_{i-1}(A)+1)-1$ for $i=1,\ldots , k-1$, and the last inequality holds as $0<\alpha <\beta _{m}$. This implies that $S_{m-k+2, k-1}(A) < S'_1(A)+1$.

Suppose to the contrary that all $B_{i,k-1}(A)$, $1\le i \le m-k+2$, are free batches. Since there are only $m-k+1$ idle machines at time $S'_{k-1}(A)$, we have $S_{m-k+2, k-1} (A) \ge S'_1(A)+1$, a contradiction. So some batch in $\{B_{i,k-1}(A), 1\le i \le m-k+2\}$ is a restricted batch. Let $B_{k}'(A)$ be the first starting restricted batch in $\{B_{i,k-1}(A): 1\le i \le m-k+2\}$. Then $B'_k(A)$ is just $B_{j_{k}}(A)$ for some $j_{k}\le m-k+2+j_{k-1}\le F(m-k+2,m+1)$. Therefore, $S_{k}'(A)\le S_{m-k+2,k-1}(A)\le (1+\alpha )^{m-k+2}( S'_{k-1}(A)+1) -1$ and $S_{k}'(A)\le S_{m-k+2,k-1}(A)< S'_1(A)+1$. The claim follows.

To continue the proof, we assume that, at time $S_{m}'(A)$, a new job arrives. Note that

$$\begin{aligned}&\big (1+\alpha \big )S'_m(A)+\alpha -\big (S'_1(A)+1\big )\\&\quad \le \big (1+\alpha \big )^{F(1,m)}\big (S'_{1}(A)+1\big )-\big (S'_1(A)+1\big )-1 \\&\quad \le \big (1+\alpha \big )^{F(1,m+1)}-\big (1+\alpha \big )^{m+1}-1 \\&\quad < \big (1+\beta _{m}\big )^{F(1,m+1)}-\big (1+\beta _{m}\big )^{m+1}-1 \\&\quad = 0, \end{aligned}$$

where the first two inequalities follow from the fact that $S'_i(A)\le (1+\alpha )^{m-i+2}(S'_{i-1}(A)+1)-1$ for $i=1,\ldots , m$, and the last inequality holds as $0<\alpha <\beta _{m}$. Then, from the above claim, at time $(1+\alpha )S'_m(A)+\alpha$, each of $B'_i(A)$, $1\le i \le m$, has not been completed. So $S_{1,m}(A)\ge S'_1(A)+1>(1+\alpha )S'_m(A)+\alpha$. Note that $B_{1,m}(A)$ is $B_{j'}(A)$ with $j'=j_{m}+1\le 1+F(2,m+1)=F(1,m+1)\le l_{m}$. Then $\sigma ^{1}_{A}$ is not an $\alpha$-nice schedule, a contradiction.

The above discussion implies that $\sigma ^{1}_{A}$ (and so, $\sigma _{A}$) is not an $\alpha$-nice schedule. Then $\sigma _{\alpha }$, which is just the schedule $\sigma ^{1}_{\mathrm{LAZY}(\alpha )}$, is not an $\alpha$-nice schedule. The result follows. $\square$

Lemma 2.3

If $\sigma _{\alpha }$ is an $\alpha$-regular schedule, then $\sigma _{\mathrm{LAZY}(\alpha )}$ is also $\alpha$-regular.

Proof

Assume that $\sigma _{\alpha }$ is an $\alpha$-regular schedule. The definitions of $\sigma _{\alpha }$ and $\sigma _{\mathrm{LAZY}(\alpha )}$ imply that the batches $B_i(\textsc {LAZY}(\alpha ))=B_i(\alpha )$, $1\le i \le l_m$, are $\alpha$-regular in $\sigma _{\mathrm{LAZY}(\alpha )}$. From Lemma 2.2, we have $\alpha \ge \beta _m$. For each $i>l_{m}$, we have $(1+\alpha )S_{i-1}(\textsc {LAZY}(\alpha ))+\alpha -(S_{i-1} (\textsc {LAZY}(\alpha ))+1)=\alpha (S_{i-1}(\textsc {LAZY}(\alpha ))+1)-1\ge \alpha (1+\alpha )^{i-1}-1\ge \beta _m(1+\beta _m)^{l_{m}}-1\ge 0$. Thus $B_{i-1}(\textsc {LAZY}(\alpha ))$ completes by time $(1+\alpha )S_{i-1}(\textsc {LAZY}(\alpha ))+\alpha$. Consequently, $B_i(\textsc {LAZY}(\alpha ))$ is a free and $\alpha$-regular batch in $\sigma _{\mathrm{LAZY}(\alpha )}$, as required. Then $\sigma _{\mathrm{LAZY}(\alpha )}$ is $\alpha$-regular. The result follows. $\square$

3 The lower bound

Lemma 3.1

Let $\alpha$ be a real number with $0<\alpha <1$. If there exists an algorithm $A'$ such that $\sigma _{A'}$ is an $\alpha$-nice schedule, then $\sigma _{\alpha }$ is an $\alpha$-regular schedule.

Proof

Assume that $\sigma _{A'}$ is an $\alpha$-nice schedule with sufficiently many batches. Then $S_i(A')\le (1+\alpha )S_{i-1}(A') +\alpha$ for $i\ge 1$. From Lemma 2.2, we have $\alpha \ge \beta _m$. If $\alpha \ge \alpha {(2m+1, 2)}$, the result follows from Lemma 2.1iii. Hence we assume in the following that $\beta _m \le \alpha <\alpha {(2m+1, 2)}$. Suppose to the contrary that $\sigma _{\alpha }$ is not an $\alpha$-regular schedule. Set $n'=\min \{i: 1\le i \le l_{m}, S_{i}(\alpha )>(1+\alpha )S_{i-1}(\alpha )+\alpha$}.

Based on $\sigma _{A'}$, we define a new schedule $\sigma ^*_{A'}$ which consists of $n'$ batches and has the same batch sequence on each machine as $\sigma _{A'}$. The starting time of each batch $B^*_i(A')$ in $\sigma ^*_{A'}$ is given by $S^*_i(A')= (1+\alpha )^i-1$ and, furthermore, $B^*_i(A')$ is (assigned) restricted in $\sigma ^*_{A'}$ if and only if $B_i(A')$ is restricted in $\sigma _{A'}$. Then $S^*_i(A')= (1+\alpha )S^*_{i-1}(A') +\alpha$ for $1\le i\le n'$. Since $S_i(A')\le (1+\alpha )S_{i-1}(A') +\alpha$ for $i\ge 1$, it can be verified that for every batch indexes $i$ and $j$ with $1\le i< j\le n'$, we have $S^*_j(A') - S^*_i(A') \ge S_j(A')- S_i(A')$. It follows that $\sigma ^*_{A'}$ is also a feasible schedule. We also define a new job instance $\mathcal{I}'(\alpha )$ which consists of the first $n'$ jobs in $\mathcal{I}(\alpha )$. Note that $\sigma ^*_{A'}$ can be taken as a feasible schedule for instance $\mathcal{I}'(\alpha )$ in which all batches are $\alpha$-regular. Hence there exists an $\alpha$-regular schedule for instance $\mathcal{I}'(\alpha )$.

It can be observed that, for every $\alpha$-regular schedule for instance $\mathcal{I}'(\alpha )$, the first batch is exactly $B_1(\alpha )$.

Let $\pi$ be an $\alpha$-regular schedule for instance $\mathcal{I}'(\alpha )$. The $i$-th batch in $\pi$ is denoted by $B_i^{\pi }$. Define $e(\pi ) =\max \{k: 1\le k\le n', \; B_i^{\pi } = B_i(\alpha ) \text{ for } i\le k\}$, where we overload the notation “$B_i^{\pi } = B_i(\alpha )$” to indicate that the two batches include the same jobs, have the same starting time and are both free batches or both restricted batches. Then $e(\pi ) \ge 1$. We can choose $\pi$ so that $e(\pi )$ is as large as possible. Since $\pi$ is an $\alpha$-regular schedule, we have $S_i(\alpha ) = S_i^{\pi } =(1+\alpha )^i -1$ for $1\le i\le e(\pi )$. If $e(\pi )=n'$, then $B_i(\alpha )$ $(1\le i\le n')$ are all $\alpha$-regular, a contradiction. So in the following we suppose that $e(\pi ) <n'$. Then $B_i^{\pi }=B_i(\alpha )$ for $1\le i\le e(\pi )$ and $B_{e(\pi )+1}^{\pi }\ne B_{e(\pi )+1}(\alpha )$. From the fact that $\pi$ is an $\alpha$-regular schedule and by the implementation of algorithm $\textsc {LAZY}(\alpha )$, $B_{e(\pi )+1}(\alpha )$ is $\alpha$-regular, and so, $S_{e(\pi )+1}(\alpha ) = S_{e(\pi )+1}^{\pi } =(1+\alpha )^{e(\pi )+1}-1$.

If $B_{e(\pi )}^{\pi }= B_{e(\pi )}(\alpha )$ is a restricted batch, then both $B_{e(\pi )+1}^{\pi }$ and $B_{e(\pi )+1}(\alpha )$ are free batches consisting of only one job $J_{e(\pi )+1}(\alpha )$. But then $B_{e(\pi )+1}^{\pi }= B_{e(\pi )+1}(\alpha )$, a contradiction. Hence $B_{e(\pi )}^{\pi }= B_{e(\pi )}(\alpha )$ is a free batch.

If $B_{e(\pi )+1}^{\pi }$ and $B_{e(\pi )+1}(\alpha )$ are both restricted batches, then both of them consist of the same jobs. Then we have $B_{e(\pi )+1}^{\pi }= B_{e(\pi )+1}(\alpha )$, a contradiction.

If $B_{e(\pi )+1}^{\pi }$ is a free batch, then $B_{e(\pi )+1}^{\pi }=\{J_{e(\pi )+1}(\alpha ) \}$ and at time $(1+\alpha )S_{e(\pi )}^{\pi }+\alpha =(1+\alpha )S_{e(\pi )}(\alpha )+\alpha$, some machine is idle. The implementation of algorithm $\textsc {LAZY}(\alpha )$ implies that $B_{e(\pi )+1}(\alpha ) =\{J_{e(\pi )+1}(\alpha ) \}$ is also a free batch. Thus, $B_{e(\pi )+1}^{\pi }= B_{e(\pi )+1}(\alpha )$, a contradiction.

Hence, the only possibility is that $B_{e(\pi )+1}^{\pi }$ is a restricted batch and $B_{e(\pi )+1}(\alpha )$ is a free batch. Noticing that $B_{e(\pi )}^{\pi }= B_{e(\pi )}(\alpha )$ is a free batch, the implementation of algorithm $\textsc {LAZY}(\alpha )$ implies that $B_{e(\pi )+1}(\alpha )=\{J_{e(\pi )+1}(\alpha )\}$ is also an $\alpha$-regular batch. So in the case $e(\pi )=n'-1$, $B_{n'}(\alpha )$ is $\alpha$-regular, a contradiction.

Suppose that $e(\pi )\le n'-2$. We obtain a new schedule $\pi '$ from $\pi$ so that $B_i^{\pi '} = B_i^{\pi }$ for $1\le i\le e(\pi )$, $B_{e(\pi )+1}^{\pi '} =\{J_{e(\pi )+1}(\alpha ) \}$, and, for each $e(\pi )+2\le i \le n'$, $B_{i}^{\pi '}$ is (assigned) restricted in $\pi '$ if and only if $B_{i-1}^{\pi }$ is restricted in $\pi$. The $\alpha$-regularity of $\pi '$ can be observed from the fact that we can always schedule each batch $B_{i}^{\pi '}$ with $e(\pi )+2\le i \le n'$ (no matter restricted or free) on the machine occupied by $B_{i-1}^{\pi }$ in $\pi$. Now $\pi '$ is $\alpha$-regular and $B_i^{\pi '} = B_i(\alpha )$ for $1\le i\le e(\pi )+1$. This contradicts the choice of $\pi$. The result follows. $\square$

Lemma 3.2

Suppose that $0<\alpha < \beta <1$. If $\sigma _{\alpha }$ is $\alpha$-regular, then $\sigma _{\beta }$ is $\beta$-regular.

Proof

If $\sigma _{\alpha }$ is $\alpha$-regular, then $\sigma _{\mathrm{LAZY}(\alpha )}$ is $\alpha$-regular by Lemma 2.3. Since $\alpha < \beta$, $\sigma _{\mathrm{LAZY}(\alpha )}$ is $\beta$-nice. By Lemma 3.1, $\sigma _{\beta }$ is $\beta$-regular. The result follows. $\square$

We define

$$\begin{aligned} \alpha _{m}=\min \big \{\alpha {(s,t)}:1\le t<s\le l_{m},\; \sigma _{\alpha {(s,t)}} \text{ is } \alpha {(s,t)}\text{-regular }\big \}. \end{aligned}$$

(3)

From Lemmas 2.1iii and 2.2, $\alpha _{m}$ is well defined in (3) and

$$\begin{aligned} \beta _m \le \alpha _{m} \le \alpha {(2m+1,2)}. \end{aligned}$$

(4)

Lemma 3.3

$\alpha _{m}=\min \{\alpha : 0<\alpha <1,\; \sigma _{\alpha } \text{ is } \alpha \text{-regular }\}$.

Proof

Write $\gamma =\min \{\alpha : 0<\alpha <1, \; \sigma _{\alpha } \text{ is } \alpha \text{-regular }\}$. From Lemma 2.2 we have $\gamma \ge \beta _{m}$ and by the definition of $\alpha _{m}$, we have $\gamma \le \alpha _{m}$. We first prove that $\gamma \in \{\alpha {(s,t)}: 1\le t<s \le l_{m} \}$.

Suppose to the contrary that $\gamma \not \in \{\alpha {(s,t)}: 1\le t<s \le l_{m} \}$. Then $\gamma <\alpha _{m}$ by the definition of $\alpha _{m}$ and $\gamma$. Furthermore, the assumption also implies the following Claim 1.

Claim 1 For each pair of positive integers $s$ and $t$ with $1\le t< s\le l_{m}$, we have $(1+\gamma )^{s}-(1+\gamma )^{t}-1\ne 0$.

Since $s$ and $t$ have finitely many choices, from Claim 1, we have the following Claim 2.

Claim 2 There is a positive number $\alpha <\gamma$ such that, for each pair of positive integers $s$ and $t$ with $1\le t< s\le l_{m}$, $(1+\gamma )^{s}-(1+\gamma )^{t}-1>0$ if and only if $(1+\alpha )^{s}-(1+\alpha )^{t}-1>0$.

Let $\alpha$ be given as in Claim 2. Note that the definition of $\gamma$ implies that $\sigma _{\gamma }$ is a $\gamma$-regular schedule. We first show that $\sigma _{\alpha }$ is also an $\alpha$-regular schedule.

We construct a new schedule $\sigma ^*$ from $\sigma _{\gamma }$ by the following way. The batches in $\sigma ^*$ are given by $B_1^*, B_2^*,\ldots , B_{l_m}^*$ so that $B_i^*$ is (assigned) restricted in $\sigma ^*$ if and only if $B_i(\gamma )$ is restricted in $\sigma _{\gamma }$ for each $i$ with $1\le i\le l_m$. Furthermore, each batch $B_i^*$ is processed on the machine occupied by $B_i(\gamma )$ with starting time $S_i^*= (1+\alpha )^i -1$ in $\sigma ^*$. We only need to show that such a schedule $\sigma ^*$ is feasible, or equivalently, there is no violated batch in $\sigma ^*$. Here, a restricted batch $B_i^*$ is called violated if $B_i^*$ overlaps with some restricted batch $B_{i'}^*$ with $i'<i$ on the same machine in $\sigma ^*$, and a free batch $B_i^*$ is called violated if $B_i^*$ overlaps with some batch $B_{i'}^*$ with $i'<i$ on the same machine in $\sigma ^*$.

If possible let $B_s^*$ be the first violated batch in $\sigma ^*$. Then there is a batch $B_t^*$ with $t<s$ on the same machine such that $B_s^*$ overlaps with $B_t^*$ in $\sigma ^*$ but $B_s(\gamma )$ processed after $B_t(\gamma )$ in $\sigma _{\gamma }$. Then we have $S_t^*+1 >S_s^*$ and $S_t(\gamma )+1 \le S_s(\gamma )$, and therefore, $(1+\alpha )^t > (1+\alpha )^s -1$ and $(1+\gamma )^t \le (1+\gamma )^s -1$. From Claim 1, we have $(1+\gamma )^s > (1+\gamma )^t+1$. Then the facts that $(1+\alpha )^s < (1+\alpha )^t+1$ and $(1+\gamma )^s > (1+\gamma )^t+1$ contradict Claim 2.

The above discussion implies that $\gamma \in \{\alpha {(s,t)}: 1\le t<s \le l_{m} \}$. Then the only possibility is that $\gamma =\alpha _m$. The result follows. $\square$

Theorem 3.4

There exists no online algorithm with a competitive ratio of less than $1+\alpha _{m}$.

Proof

Suppose to the contrary that $A$ is an online algorithm with a competitive ratio of $1+\gamma$, where $\gamma <\alpha _{m}$. Then in schedule $\sigma _{A}$ with sufficiently many batches, $S_{i}(A)\le (1+\gamma )S_{i-1}(A)+\gamma$ for each $i\ge 1$, where $S_0(A)=0$. Thus $\sigma _{A}$ is a $\gamma$-nice schedule. From Lemma 3.1, $\sigma _{\gamma }$ is a $\gamma$-regular schedule. This contradicts Lemma 3.3. The result follows. $\square$

4 An online algorithm

The following online algorithm $\textsc {ALG}_m$ is closely related to the $\alpha _{m}$-regular schedule $\sigma _{\mathrm{LAZY}(\alpha _{m})}$ for instance $\mathcal{I}(\textsc {LAZY}(\alpha _{m}))$. The intuition of the algorithm $\textsc {ALG}_m$ can be stated as follows.

According to the arriving of the jobs, we generate a sequence of positive integers $j_1, j_2, \ldots ,j_n$ so that $j_1< j_2 < \cdots < j_n$. When the first job arrives at time $0$, let $j_{1}=1$. When the first job arrives at a time $t_1>0$, we determine $j_1$ so that $t_1 \in ((1+\alpha _m)^{j_1-1}-1,\, (1+\alpha _m)^{j_1}-1]$. Then we start the first batch $B_1^{\mathrm{ALG}}$ as a free batch at time $S_1^{\mathrm{ALG}}= (1+\alpha _m)^{j_1}-1$. Generally, suppose that the first $i-1$ batches $B_1^{\mathrm{ALG}}, B_2^{\mathrm{ALG}}, \ldots , B_{i-1}^{\mathrm{ALG}}$ have been generated and a new job arrives at a time $t_i >S_{i-1}^{\mathrm{ALG}}$. Then we determine $j_i$ so that $t_i \in ((1+\alpha _m)^{j_i-1}-1,\, (1+\alpha _m)^{j_i}-1]$ and generate a batch $B_i^{\mathrm{ALG}}$ with starting time $S_i^{\mathrm{ALG}}= (1+\alpha _m)^{j_i}-1$ in $\textsc {ALG}_m$. Thus we have $S_i^{\mathrm{ALG}}= (1+\alpha _m)^{j_i}-1$ for each $i$. We take the convention that $B_i^{\mathrm{ALG}}$ is an assigned restricted batch in $\textsc {ALG}_m$ if and only if $B_{i}(\textsc {LAZY}(\alpha _{m}))$ is a restricted batch in $\sigma _{\mathrm{LAZY}(\alpha _{m})}$. Note that in algorithm $\textsc {ALG}_m$, an assigned restricted batch can not be restarted again.

Algorithm ALG $_m$:

• 1. Set $i:=0$.

• 2. Wait until $U(t)\not =\emptyset$.

• 3. Set $i:=i+1$. Let $j_i$ be the minimum positive integer so that $t\le (1+\alpha _{m})^{j_i}-1$ and wait until the current time $t=(1+\alpha _{m})^{j_i}-1$.

• 4. If $B_i(\textsc {LAZY}(\alpha _m))$ is a restricted batch in $\sigma _{\mathrm{LAZY}(\alpha _m)}$, interrupt all free batches at time $t$. $B_i^{\mathrm{ALG}}$ will be an assigned restricted batch consisting of all interrupted jobs and all jobs in $U(t)$.

• 5. If $B_i(\textsc {LAZY}(\alpha _m))$ is a free batch in $\sigma _{\mathrm{LAZY}(\alpha _m)}$, set $B_i^{\mathrm{ALG}}=U(t)$ and take $B_i^{\mathrm{ALG}}$ as a free batch.

• 6. Start to process $B_i^{\mathrm{ALG}}$ at time $S_i^{\mathrm{ALG}}=t$ on the machine of $B_i(\textsc {LAZY}(\alpha _m))$ in $\sigma _{\mathrm{LAZY}(\alpha _m)}$.

• 7. Go to step 2. $\Box$

Algorithm $\textsc {ALG}_m$ runs in linear time, since we only take action when a new job arrives.

Theorem 4.1

Algorithm $\textsc {ALG}_m$ has a competitive ratio at most $1+\alpha _{m}$.

Proof

Let $\mathcal{J}$ be an arbitrary job instance. Let $\sigma ^{\mathrm{ALG}}$ be the schedule generated by algorithm $\textsc {ALG}_m$ for instance $\mathcal{J}$. Let $B_1^{\mathrm{ALG}}, B_2^{\mathrm{ALG}}, \ldots , B_{n}^{\mathrm{ALG}}$ be the starting batches in $\sigma ^{\mathrm{ALG}}$, where each $B_i^{\mathrm{ALG}}$ has a starting time $S_i^{\mathrm{ALG}}$. We first show that $\sigma ^{\mathrm{ALG}}$ is feasible (no overlapping batches, and no interruptions of restricted batches).

By the implementation of $\textsc {ALG}_m$, for $1\le i\le n$, $B_i^{\mathrm{ALG}}$ is processed on the machine occupied by $B_i(\textsc {LAZY}(\alpha _m))$ in $\sigma _{\mathrm{LAZY}(\alpha _m)}$ with $S_i^{\mathrm{ALG}}=(1+\alpha _{m})^{j_i}-1$. Moreover, $B_i^{\mathrm{ALG}}$ is an assigned restricted batch in $\sigma ^{\mathrm{ALG}}$ if and only if $B_{i}(\textsc {LAZY}(\alpha _{m}))$ is a restricted batch in $\sigma _{\mathrm{LAZY}(\alpha _{m})}$. Let $i$ and $k$ be any two integers with $1\le i<k\le n$. As there are $k-i$ batches between $B_{i}^{\mathrm{ALG}}$ and $B_{k}^{\mathrm{ALG}}$ in $\sigma ^{\mathrm{ALG}}$, we have $j_{k}-j_{i}\ge k-i$. Thus,

$$\begin{aligned}&S_{k}^{\mathrm{ALG}} -S_{i}^{\mathrm{ALG}}\\&\quad =\big (1+\alpha _{m}\big )^{j_k}-\big (1+\alpha _{m}\big )^{j_i} \\&\quad =\big (1+\alpha _{m}\big )^{j_i}\big ((1+\alpha _{m})^{j_k-j_i}-1\big ) \\&\quad \ge \big (1+\alpha _{m}\big )^{i}\big ((1+\alpha _{m})^{k-i}-1\big )\\&\quad =S_{k}\big (\textsc {LAZY}(\alpha _{m})\big )-S_{i}\big (\textsc {LAZY}(\alpha _{m})\big ). \end{aligned}$$

It follows that $\sigma ^{\mathrm{ALG}}$ is feasible.

Furthermore, it is clear that each job is started (for the first time) early enough so that it can complete in time to maintain the competitive ratio $1+\alpha _m$. The result follows. $\square$

From Theorems 3.4 and 4.1, we conclude the main result of this paper as follows.

Theorem 4.2

Algorithm $\textsc {ALG}_m$ is a best possible online algorithm for problem $Pm|\text{ online },\; r_j,\; p_j=1,\;\text{ p-batch },\; b=\infty ,\; \text{ L-restart }|C_{\max }$. $\square$

As we can see, $\alpha _m$ is not presented as an explicit formulation of $m$ in this paper. We list some values of $\alpha _m$ and the competitive ratio $1+\alpha _m$ in the following table.

$m$	$\alpha _{m}=\alpha (i,j)$	Competitive ratio
$2$	$\alpha (6,3)\approx 0.1740$	$1.1740$
$3$	$\alpha (10,4)\approx 0.0926$	$1.0926$
$4$	$\alpha (17,9)\approx 0.0599$	$1.0599$
$5$	$\alpha (20,6)\approx 0.0421$	$1.0421$
$6$	$\alpha (30,13)\approx 0.0308$	$1.0308$
$7$	$\alpha (44,26)\approx 0.0242$	$1.0242$
$8$	$\alpha (46,17)\approx 0.0190$	$1.0190$
$9$	$\alpha (60,27)\approx 0.0155$	$1.0155$
$10$	$\alpha (60,11)\approx 0.0128$	$1.0128$
$11$	$\alpha (97,57)\approx 0.0109$	$1.0109$
$12$	$\alpha (100,46)\approx 0.0093$	$1.0093$
$13$	$\alpha (101,27)\approx 0.0080$	$1.0080$
$14$	$\alpha (122,42)\approx 0.0070$	$1.0070$