A best possible online algorithm for parallel batch scheduling with delivery times and limited restart

Abstract

We consider the online scheduling on an unbounded (drop-line) parallel batch machine to minimize the time by which all jobs have been delivered. In this paper, all jobs arrive over time and the running batches are allowed limited restart. Here limited restart means that a running batch which contains restarted jobs cannot be restarted again. A drop-line parallel batch machine can process several jobs simultaneously as a batch, and all jobs in a batch start at the same time, and the completion time of a job equals the sum of its starting time and its processing time. Here we consider the restricted model: all jobs have agreeable processing times and delivery times. We provide a best possible online algorithm H with a competitive ratio of $\frac{3}{2}$ for the problem on an unbounded parallel batch machine and the corresponding problem on an unbounded drop-line parallel batch machine, respectively.

1 Introduction

In the last decade, online scheduling and parallel batch scheduling have been extensively studied. In this paper, online means that jobs arrive over time and the characteristics of a job become known until its arrival time. The quality of an online algorithm is usually assessed by its competitive ratio. An online algorithm is said to be $\rho$-competitive if for any instance, it always returns a schedule whose objective value is not worse than $\rho$ times the objective value of an optimal off-line schedule.

Parallel batch scheduling is largely motivated by burn-in operations in semiconductor manufacturing  [7, 13, 14]. A parallel batch machine is a machine that can process up to b jobs simultaneously as a batch. All jobs in a batch start at the same time and complete at the same time. The processing time of a batch equals the longest processing time of jobs in the batch. There are two models depending on the characteristic of the batch capacity b. One is an unbounded model that means the batch capacity is sufficiently large, i.e., $b=\infty$. The other is a bounded model that means the batch capacity is finite, i.e., $b<\infty$. Here we study the unbounded model. For the online parallel batch scheduling problems to minimize the time by which all jobs have been delivered, there have been some results. Let $p_{j}$ and $q_{j}$ denote the processing time and the delivery time of the job $J_{j}$, respectively. Yuan et al. [17] studied two restricted models on an unbounded parallel batch machine. One is the model with small delivery times which means that the delivery time of each job is no more than its processing time, i.e., $q_{j}\le p_{j}$ holds for all jobs. The other is the agreeable model which means that for any two jobs $J_{i}$ and $J_{j}$, if $p_{i}>p_{j}$, then $q_{i}\ge q_{j}$. They provided a best possible online algorithm with a competitive ratio of $(\sqrt{5}+1)/2$ for the two restricted models. Tian et al. [10] considered the general case on an unbounded parallel batch machine and gave an online algorithm whose competitive ratio is $2\sqrt{2}-1$. For the online scheduling problem on m unbounded batch machines, Liu and Lu [8] gave a $(1+\alpha _{m})$-competitive best possible online algorithm for the agreeable model, where $\alpha _{m}$ is the positive solution of the equation $\alpha _{m}^{2}+m\alpha _{m}-1=0$. A survey of recent researches on parallel batch scheduling can see Tian et al. [11].

Restart (see Hoogeveen et al. [5]) means that we can interrupt a running task and 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 that need to be scheduled anew later. Allowing restarts means that we have a chance to change our mind and make better decisions according to information on newly arrived jobs. So we can obtain better online algorithms by using restarts. For the online scheduling problem of minimizing the time by which all jobs have been delivered on a single machine, Hoogeveen and Vestjens [6] presented a best possible algorithm whose competitive ratio is $\frac{1+\sqrt{5}}{2}$ without restart and Akker et al. [1] presented a best possible algorithm whose competitive ratio is $\frac{3}{2}$ when restarts are allowed. We can find more online scheduling researches with restarts in Epstein and Van Stee [2], Van Stee and Poutré [15], and Yuan et al. [18]. Fu et al. [3] first introduced limited restarts. Limited restarts mean that a running batch containing restarted jobs cannot be interrupted again. Limited restarts imply that a job can be restarted at most once. Limited restarts are of practice value as too many restarts of a job may cause a waste of cost and increase the possibility of spoiling a product.

For the online scheduling problem of minimizing makespan on an unbounded parallel batch machine with restarts, Yuan et al. [18] gave a best possible $(5-\sqrt{5})/2$-competitive online algorithm. Fu et al. [3] studied the online scheduling of minimizing makespan on an unbounded parallel batch machine with limited restarts. They gave a lower bound 3/2 and a best possible 3/2-competitive online algorithm. For the corresponding problem on two unbounded parallel batch machines with limited restarts, Fu et al. [4] gave a best possible online algorithm whose competitive ratio is $(\sqrt{3}+1)/2$ under the second-restart assumption. For minimizing makespan of equal length jobs on m unbounded parallel batch machines with limited restarts, Liu et al. [9] provided a best possible online algorithm.

However, in some practical applications, the above assumption of a parallel batch machine is not suitable, especially the condition of all jobs in a batch having the same completion time. In fact, when the batches are open for finished jobs, a job with a shorter processing time should be completed earlier than a job with a longer processing time in a common batch. Wei [16] first introduced the drop-line parallel batch machine. A drop-line parallel batch machine is a machine that can process several jobs simultaneously as a batch. Jobs in a batch start at the same time and the completion time of a job equals the sum of its starting time and its processing time. A drop-line parallel batch machine means that in a batch, jobs with shorter processing times will be completed earlier than jobs with longer processing times in the batch. Tian et al. [12] studied the online scheduling problem on m unbounded drop-line parallel batch machines to minimize the time by which all jobs have been delivered and gave a best possible $(1+\alpha _{m})$-competitive online algorithm, where $\alpha _{m}$ is the positive solution of the equation $a_{m}^{2}+m\alpha _{m}-1=0$. In this paper, they also gave two examples of drop-line parallel batch scheduling on commodity delivery problems and optimization of network information. In the delivery problem, a truck is used to deliver several products to different destinations. At each destination, the corresponding products are unloaded from the truck. Here a truck is a drop-line parallel batch machine and a product arriving at its destination earlier will be unloaded earlier.

The problem studied in this paper can be described as follows. There is an unbounded parallel batch machine(or an unbounded drop-line parallel batch machine) and sufficiently many vehicles. Jobs arrive over time and all characteristics of a job are unknown until it arrives. Let $r_{j}$, $p_{j}$ and $q_{j}$ denote the release time, the processing time and the delivery time of the job $J_{j}$, respectively. Here we consider the restricted model that all jobs have agreeable processing times and delivery times, which means that for any two jobs $J_{i}$ and $J_{j}$, if $p_{i}>p_{j}$, then $q_{i}\ge q_{j}$. Jobs will be first processed on the batch machine. Once a job is completed, it is immediately delivered to its destination by a vehicle. The running batches on the batch machine are allowed limited restarts, i.e., a running batch containing restarted jobs cannot be interrupted again. The objective is to minimize the time by which all jobs have been delivered. Let $C_{j}$ and $L_{j}$ denote the completion time of $J_{j}$ on the batch machine and the time by which $J_{j}$ has been delivered, respectively. Then $L_{j}=C_{j}+q_{j}$ and the objective function is $L_{\max } =\mathop {\max }\limits _{j}\{L_{j}\}$. The corresponding problem on an unbounded parallel batch machine can be denoted by $1|\text{ online },\; r_j,\; \text{ agreeable },\;\text{ p-batch },\; b=\infty ,\; \text{ L-restart }|L_{\max }$. The corresponding problem on an unbounded drop-line parallel batch machine can be denoted by $1|\text{ online },\; r_j,\; \text{ agreeable },\;\text{ drop-line }$ $\text{ p-batch },\; b=\infty ,\; \text{ L-restart }|L_{\max }$. In this paper, a restricted batch means that the batch contains restarted jobs when the batch starts processing. A free batch means that the batch contains no restarted jobs when the batch starts processing.

The problems considered in this paper are the integration of production and delivery, which are motivated by practical problems. Now we show an example of the drop-line parallel batch scheduling in commodity delivery problems. Suppose that a number of containers are delivered from port O(origin) to different ports (transit points) by a vessel. At each transit point, the containers that are unloaded are individually sent to their destinations by a huge quantity of vehicles. At port O, containers from various merchants arrive and the vessel accommodates them until its capacity is reached. Here each container arrives over time and its characteristics become known until it arrives. The objective of the vessel’s company is to determine the container delivery schedule in order to minimize the time by which all containers have been delivered to their destinations. This is just a drop-line parallel batch scheduling problem with jobs arriving online, where a vessel is a drop-line parallel batch processing machine and a container is a job.

This paper is organized as follows. In Sect. 2, we prove that there is no online algorithm with a competitive ratio less than $\frac{3}{2}$ for the problem $1|\text{ online },\; r_j,\; \text{ agreeable },\text{ p-batch },\; b=\infty ,\; \text{ L-restart }|L_{\max }$ and give a best possible online algorithm H with a competitive ratio of $\frac{3}{2}$. In Sect. 3, we prove that there is no online algorithm with a competitive ratio less than $\frac{3}{2}$ for the problem $1|\text{ online },\; r_j,\; \text{ agreeable },\;\text{ drop-line }$ $\text{ p-batch },\; b=\infty ,\; \text{ L-restart }|L_{\max }$ and prove that Algorithm H is also a best possible online algorithm with a competitive ratio of $\frac{3}{2}$.

2 The problem on an unbounded parallel batch machine

In this section, we study the problem on an unbounded parallel batch machine, i.e., $1|\text{ online },\; r_j,$ $\; \text{ agreeable },\;\text{ p-batch },\; b=\infty ,\; \text{ L-restart }|L_{\max }$.

Theorem 2.1

For the problem $1|\text{ online },\; r_j,\; \text{ agreeable },\;\text{ p-batch },\; b=\infty ,\; \text{ L-restart }|L_{\max }$, there is no online algorithm with a competitive ratio less than $\frac{3}{2}$.

Proof

For the problem $1|\text{ online },\; r_j,\; \text{ p-batch },\; b=\infty ,\; \text{ L-restart }|C_{\max }$, Theorem 2.1 in Fu et al. [3] shows that there does not exist any online algorithm with a competitive ratio less than $\frac{3}{2}$. Note that the problem $1|\text{ online },\; r_j,\; \text{ p-batch },\; b=\infty ,\; \text{ L-restart }|C_{\max }$ is a special case of the problem $1|\text{ online },\; r_j,\; \text{ agreeable },\; \text{ p-batch },\; b=\infty ,\; \text{ L-restart }|L_{\max }$ (by setting $q_{j}=0$ for all jobs). So any online algorithm has a competitive ratio at least $\frac{3}{2}$ for the problem $1|\text{ online },\; r_j,\; \text{ agreeable },\; \text{ p-batch },\;$ $b=\infty ,\; \text{ L-restart }|L_{\max }$. The result follows. $\square$

Now we give some notations used in the following algorithm. Let p(B) be the longest processing time of jobs in a job set B. Let $B_{i}$ denote the i-th starting batch in the schedule generated by the algorithm and $S_{i}$ denote the starting time of $B_{i}$. Let $r(B_{i})$ be the earliest arrival time of jobs in $B_{i}$. Let $p(B_{i})$ and $q(B_{i})$ denote the longest processing time of jobs in the batch $B_{i}$ and the largest delivery time of jobs in the batch $B_{i}$, respectively. Among the jobs with a processing time $p(B_{i})$ in $B_{i}$, select one which arrives latest as the job $J_{i}^{p}$. Let $q_{i}^{p}$ be the delivery time of the job $J_{i}^{p}$ and $r_{i}^{p}$ be the arrival time of the job $J_{i}^{p}$. Among the jobs with a delivery time $q(B_{i})$ in $B_{i}$, select one which arrives latest as the job $J_{i}^{q}$. Let $p_{i}^{q}$ be the processing time of the job $J_{i}^{q}$. We use U(t) to denote the set of unscheduled jobs available at time t.

We can use the following sub-procedure Restart(k, t) when we restart the batch $B_k$ at the time t.

Restart(k, t):  Interrupt $B_k$ at time t and schedule all jobs (or all uncompleted jobs for the drop-line version) in $B_k$ and all jobs in U(t) as a batch $B_{k+1}$ starting at time t. Set $k=k+1$. $\Box$

Fig. 1

restarts on a parallel batch machine and on a drop-line parallel batch machine

Now we show examples of restarts on an unbounded parallel batch machine and on an unbounded drop-line parallel batch machine. See Fig. 1. $B_{1}=\{J_{1},J_{2}\}$ is a free batch with a starting time 0. $B_{1}$ has a processing time $p(B_{1})=\max \{p_{1},p_{2}\}=1$. At the time 0.6, a new job $J_{3}$ arrives with a processing time $p_{3}=1.1$ and a delivery time $q_{3}=1.1$. Assume that we interrupt $B_{1}$ and start a restricted batch $B_{2}$ at the time 0.6. First we see restarts on an unbounded parallel batch machine (see Fig. 1a). Since all jobs in $B_{1}$ will complete at the same time, all jobs in $B_{1}$ are released when $B_{1}$ is interrupted and the restricted batch $B_{2}$ consists of all jobs in $B_{1}$ and the newly arrived jobs $J_{3}$. Thus $B_{2}=\{J_{1},J_{2},J_{3}\}$. $B_{2}$ has a processing time $p(B_{2})=\max \{p_{1},p_{2},p_{3}\}=1.1$. Now we see restarts on an unbounded drop-line parallel batch machine (see Fig. 1b). Since the completion time of a job is equal to its starting time plus its processing time, the job $J_{2}$ has been completed at the time 0.5. Only the job $J_{1}$ is released when $B_{1}$ is interrupted at the time 0.6 and the restricted batch $B_{2}$ consists of all uncompleted jobs in $B_{1}$ at the time 0.6 and the newly arrived jobs $J_{3}$. Thus $B_{2}=\{J_{1},J_{3}\}$. $B_{2}$ has a processing time $p(B_{2})=\max \{p_{1},p_{3}\}=1.1$.

In the following algorithm, we use $\rho =0$ to show that the current batch is a free batch and use $\rho =1$ to show that the current batch is a restricted batch. The symbol $``s''$ means the starting time of the current batch.

• Algorithm H

• Step 0:   Set $t=0$, $s=0$, $\rho =0$, $k=0$.

• Step 1: If $U(t)=\emptyset$, wait until new jobs arrive or stop without new jobs arriving. Otherwise determine p(U(t)).

• Step 2: If $t\ge \frac{1}{2}p(U(t))$, then schedule all jobs in U(t) as a single batch $B_{k+1}$ starting at time t, and set $k=k+1$ and $s=t$. If $t<\frac{1}{2}p(U(t))$, wait until $\frac{1}{2}p(U(t))$ or the next arrival time and go to Step 1.

• Step 3: If no new jobs arrive in the time interval $(s, s +p(B_{k}))$ or $\rho = 1$, then complete the batch $B_{k}$, and set $t=s+p(B_{k})$, $\rho = 0$, and go to Step 1. If $\rho =0$ and some new jobs(or job) arrive at sometime $t'$ in the time interval $(s, s+p(B_{k}))$, then find the job $J_{h}$ whose processing time is the longest among jobs arriving at time $t'$.

• Step 4: If $r_{h}\ge \frac{5}{4}p(B_{k})$, then complete the batch $B_{k}$, set $t=s+p(B_{k})$ and go to Step 1. Otherwise, do the following:

  • Step 4.1: If $p_{h}\ge \frac{3}{2}p(B_{k})$, then complete the batch $B_{k}$, set $t=s+p(B_{k})$ and go to Step 1.

  • Step 4.2: If $p(B_{k})< p_{h}<\frac{3}{2}p(B_{k})$, do the following:

    • Step 4.2.1: If $r_{h}\ge p_{h}$, then set $t=r_{h}$, do Restart(k, t), set $s=t$, $\rho =1$ and go to Step 3.

    • Step 4.2.2: If $r_{h}<p_{h}$, continue to process $B_{k}$ in the time interval $(r_{h}, p_{h}]$ unless a new job $J_{h'}$ with $p_{h'}\ge p_{h}$ arrives.

      If at sometime $t'$ in the time interval $(r_{h}, p_{h}]$, a job set which contains some new job $J_{h'}$ with $p_{h'}\ge p_{h}$ arrives, then update $J_{h}$ to be the job whose processing time is the longest among jobs arriving at time $t'$ and go to Step 4.

      Otherwise, set $t=p_{h}$, do Restart(k, t), set $s=t$, $\rho =1$ and go to Step 3.

  • Step 4.3: If $\frac{3}{4}p(B_{k})<p_{h}\le p(B_{k})$, do the following:

    • Step 4.3.1: If $r_{h}<2p(B_{k})-p_{h}$, continue to process $B_{k}$ in the time interval $(r_{h}, 2p(B_{k})-p_{h}]$ unless a new job $J_{h'}$ with $p_{h'}\ge p_{h}$ arrives.

      If at sometime $t'$ in the time interval $(r_{h}, 2p(B_{k})-p_{h}]$, a job set which contains some new job $J_{h'}$ with $p_{h'}\ge p_{h}$ arrives, then update $J_{h}$ to be the job whose processing time is the longest among jobs arriving at time $t'$ and go to Step 4. Otherwise, (a) if $p_{h}\ge \frac{3}{4}p(B_{k})+\frac{1}{4}q(B_{k})$, then set $t=2p(B_{k})-p_{h}$, do Restart(k, t), set $s=t$, $\rho =1$ and go to Step 3; (b) if $p_{h}<\frac{3}{4}p(B_{k})+\frac{1}{4}q(B_{k})$, go to Step 4.5.

    • Step 4.3.2: If $r_{h}\ge 2p(B_{k})-p_{h}$ and $p_{h}\ge \frac{3}{4}p(B_{k})+\frac{1}{4}q(B_{k})$, then set $t=r_{h}$, do Restart(k, t), set $s=t$, $\rho =1$ and go to Step 3.

    • Step 4.3.3: If $r_{h}\ge 2p(B_{k})-p_{h}$ and $p_{h}<\frac{3}{4}p(B_{k})+\frac{1}{4}q(B_{k})$, go to Step 4.5.

  • Step 4.4: If $p_{h}\le \frac{3}{4}p(B_{k})$, go to Step 4.5.

  • Step 4.5: Continue to process $B_{k}$ unless some new job $J_{h'}$ with $p_{h'}\ge p_{h}$ arrives before the time $\frac{5}{4}p(B_{k})$.

    If at sometime $t'$ before time $\frac{5}{4}p(B_{k})$, a job set which contains some new job $J_{h'}$ with $p_{h'}\ge p_{h}$ arrives, then update $J_{h}$ to be the job whose processing time is the longest among jobs arriving at time $t'$ and go to Step 4.1.

    If there is no new job $J_{h'}$ with $p_{h'}\ge p_{h}$ arriving before the time $\frac{5}{4}p(B_{k})$, then complete the batch $B_{k}$, set $t=s+p(B_{k})$ and go to Step 1. $\square$

Let I be an instance. Let $\sigma$ and $\pi$ be the schedule produced by Algorithm H for the instance I and the off-line optimal schedule of the instance I, respectively. Let $L_{{\text{ on }}}(I)$ be the objective value of the schedule $\sigma$ and $L_{{\text{ opt }}}(I)$ be the objective value of the schedule $\pi$. For simplicity, we write $L_{{\text{ on }}}(I)$ as $L_{{\text{ on }}}$ and write $L_{{\text{ opt }}}(I)$ as $L_{{\text{ opt }}}$. Let $B_{n}$ be the first batch in $\sigma$ satisfying $L_{{\text{ on }}}=S_{n}+p(B_{n})+q(B_{n})$. For the schedule $\sigma$ generated by Algorithm H, we have the following properties.

Observation 2.1

For a free batch $B_i$, we have the following conclusions.

• (1) $S_i\ge \max \{r(B_{i}),\frac{1}{2}p(B_{i})\}$;

• (2) $S_1=\max \{r(B_{1}),\frac{1}{2}p(B_{1})\}$;

• (3) If $S_i>S_{i-1}+p(B_{i-1})$ ($i\ge 2$), then $S_i=\max \{r(B_{i}),\frac{1}{2}p(B_{i})\}$. $\square$

If a restricted batch $B_i$ is got by Step 4.2 of Algorithm H, noting that $p(B_{i-1})< p_{h}<\frac{3}{2}p(B_{i-1})$, then we have $p(B_{i})=\max \{p_{h},p(B_{i-1})\}=p_{h}$ and $S_{i}\ge p_{h}=p(B_{i})$. If a restricted batch $B_i$ is got by Step 4.3 of Algorithm H, noting that $\frac{3}{4}p(B_{i-1})<p_{h}\le p(B_{i-1})$, we have $p(B_{i})=\max \{p_{h},p(B_{i-1})\}=p(B_{i-1})$ and $S_{i}\ge 2p(B_{i-1})-p_{h}\ge p(B_{i-1})=p(B_{i})$. Then the following property holds.

Observation 2.2

For a restricted batch $B_i$, we have $S_i\ge p(B_{i})$. $\square$

From Observations 2.1 and 2.2, we can easily get the following property.

Observation 2.3

$S_i\ge \frac{1}{2}p(B_{i})$ ($1\le i\le n$). $\square$

Lemma 2.1

Let jobs $J'$ and $J''$ have processing times $p'$, $p''$ and delivery times $q'$, $q''$ with $p'\ge p''$ and $q''\ge q'$. We can obtain the following conclusions.

• (1) One of $J'$ and $J''$ has the processing time $p'$ and the delivery time $q''$.

• (2) If both $J'$ and $J''$ start not earlier than time s in the optimal off-line schedule $\pi$, then $L_{{\text{ opt }}}\ge s+p'+q''$.

Proof

• (1) Note that $p'\ge p''$. If $p'= p''$, then the processing time of $J''$ is $p'$. Now the processing time of $J''$ is $p'$ and the delivery time of $J''$ is $q''$. If $p'>p''$, considering that processing times are agreeable with delivery times, we have $q'\ge q''$. Also considering that $q''\ge q'$, then $q'=q''$. Now the delivery time of $J'$ is $q''$ and the processing time of $J'$ is $p'$.

• (2) Considering that both $J'$ and $J''$ start not earlier than time s in the optimal off-line schedule $\pi$ and (1), then $L_{{\text{ opt }}}\ge s+p'+q''$. The result follows. $\square$

Lemma 2.2

• (1) For each batch $B_i$ $(1\le i\le n)$, at least one of the jobs $J_{i}^{p}$ and $J_{i}^{q}$ has the processing time of $p(B_{i})$ and the delivery time of $q(B_{i})$.

• (2) $L_{{\text{ opt }}}\ge r(B_{i})+p(B_{i})+q(B_{i})$ $(1\le i\le n)$.

Proof

• (1) By the definitions of $J_{i}^{p}$ and $J_{i}^{q}$, $J_{i}^{p}$ and $J_{i}^{q}$ satisfy the condition of Lemma 2.1. Note that the processing time of $J_{i}^{p}$ is $p(B_{i})$ and the delivery time of $J_{i}^{q}$ is $q(B_{i})$. So by Lemma 2.1(1), one of $J_{i}^{p}$ and $J_{i}^{q}$ has the processing time $p(B_{i})$ and the delivery time $q(B_{i})$.

• (2) By (1), we can easily get that $L_{{\text{ opt }}}\ge r(B_{i})+p(B_{i})+q(B_{i})$ $(1\le i\le n)$. The result follows. $\square$

Lemma 2.3

• (1) If $n=1$, then ${L_{{\text{ on }}}}/{L_{{\text{ opt }}}}\le \frac{3}{2}$.

• (2) If $S_n > S_{n-1}+p(B_{n-1})$ ($n\ge 2$), then ${L_{{\text{ on }}}}/{L_{{\text{ opt }}}}\le \frac{3}{2}$.

Proof

By Observation 2.1, $S_n=\max \{\frac{1}{2}p(B_n),r(B_{n})\}$ if $n=1$ or $S_n > S_{n-1}+p(B_{n-1})$ ($n\ge 2$). Then $L_{{\text{ on }}}=S_n+ p(B_n)+q(B_n)=\max \{\frac{1}{2}p(B_n),r(B_{n})\}+p(B_n)+q(B_n)$. By Lemma 2.2, we have $L_{{\text{ opt }}}\ge r(B_{n})+p(B_n)+q(B_n)$. Then ${L_{{\text{ on }}}}/{L_{{\text{ opt }}}}\le \frac{\max \{\frac{1}{2}p(B_n),r(B_{n})\}+p(B_n)+q(B_n)}{r(B_{n})+p(B_n)+q(B_n)}\le {3}/{2}$. The result follows. $\square$

If $n=1$ or $S_n > S_{n-1}+p(B_{n-1})$ ($n\ge 2$), by Lemma 2.3, then ${L_{{\text{ on }}}}/{L_{{\text{ opt }}}}\le \frac{3}{2}$. So we only consider that $n\ge 2$ and $S_n\le S_{n-1}+p(B_{n-1})$. Now we distinguish three cases and use three Lemmas to prove that ${L_{{\text{ on }}}}/{L_{{\text{ opt }}}}\le \frac{3}{2}$. To improve the readability and reduce the length of the paper, considering that the proofs of the following three Lemmas are foundational, we move the detailed proofs of the following three Lemmas to Appendix.

Lemma 2.4

If $S_n<S_{n-1}+p(B_{n-1})$, then ${L_{{\text{ on }}}}/{L_{{\text{ opt }}}}\le \frac{3}{2}$. $\square$

Lemma 2.5

If $S_n=S_{n-1}+p(B_{n-1})$ and $B_{n-1}$ is a restricted batch, then ${L_{{\text{ on }}}}/{L_{{\text{ opt }}}}\le \frac{3}{2}$. $\square$

Lemma 2.6

If $S_n=S_{n-1}+p(B_{n-1})$ and $B_{n-1}$ is a free batch, then ${L_{{\text{ on }}}}/{L_{{\text{ opt }}}}\le \frac{3}{2}$. $\square$

From Theorem 2.1 and Lemma 2.3–2.6, we conclude one of main results in this paper as follows.

Theorem 2.2

Algorithm H is a best possible online algorithm for the problem $1|\text{ online },\; r_j, \text{ agreeable },$ $\;\text{ p-batch },\; b=\infty ,\; \text{ L-restart }|L_{\max }$. $\square$

Now we show a case with restarts for better understanding of the considered problem and Algorithm H. See Fig. 2.

Fig. 2

A case with restarts

At the time 0, a job $J_{1}$ arrives with a processing time $p_{1}=1$ and a delivery time $q_{1}$ ($q_{1}<1$). By Step 2 of Algorithm H, we start a free batch $B_{1}=\{J_{1}\}$ on the batch machine with a starting time $S_{1}=\frac{1}{2}p_{1}=\frac{1}{2}$. Now $p(B_{1})=p_{1}=1$ and $q(B_{1})=q_{1}$. Later a new job $J_{2}$ with a processing time $p_{2}$ ($p_{1}> p_{2}>\frac{3}{4}+\frac{1}{4}q_{1}$) and a delivery time $q_{2}$ ($q_{2}\le q_{1}$) arrives at the time $r_{2}=\frac{3}{4}$. Thus $r_{2}<2p(B_{1})-p_{2}$ as $p_{1}>p_{2}$. Since $\frac{3}{4}p(B_{1})+\frac{1}{4}q(B_{1})<p_{2}<p(B_{1})$, $r_{2}<\frac{5}{4}p(B_{1})$ and $r_{2}<2p(B_{1})-p_{2}$, by Step 4.3.1 of Algorithm H, we interrupt the free batch $B_{1}$ and start a restricted batch $B_{2}=\{J_{1}, J_{2}\}$ with a starting time $S_{2}=2p(B_{1})-p_{2}=2-p_{2}$. Now $p(B_{2})=\max \{p_{1},p_{2}\}=1$ and $q(B_{2})=\max \{q_{1},q_{2}\}=q_{1}$. Later, a new job $J_{3}$ with a processing time $p_{3}$ and a delivery time $q_{3}$ arrives at the time $r_{3}$, where $S_{2}<r_{3}<S_{2}+p(B_{2})$ and $q_{1}<p_{3}+q_{3}\le 4$. No new jobs arrive later. Since $B_{2}$ is a restricted batch and cannot be restarted, by Step 2 of Algorithm H, we start a free batch $B_{3}=\{J_{3}\}$ at the time $S_{3}=\max \{S_{2}+p(B_{2}), \frac{1}{2}p_{3}\}$. Note that $\frac{1}{2}p_{3}\le 2$ as $p_{3}+q_{3}\le 4$. Also considering that $S_{2}+p(B_{2})=3-p_{2}>2$, we have $S_{3}=\max \{S_{2}+p(B_{2}), \frac{1}{2}p_{3}\}=S_{2}+p(B_{2})=3-p_{2}$. Considering that $q_{1}<p_{3}+q_{3}$ and $q(B_{2})=\max \{q_{1},q_{2}\}=q_{1}$, we have $L_{{\text{ on }}}=S_{2}+p(B_{2})+\max \{q(B_{2}), p_{3}+q_{3}\}=3-p_{2}+p_{3}+q_{3}$. If $J_{1}$ or $J_{2}$ starts not earlier than the time $S_{2}$ in the off-line optimal schedule, we have $L_{{\text{ opt }}}\ge S_{2}+\min \{p_{1},p_{2}\}=2-p_{2}+p_{2}=2$. Also considering that $L_{{\text{ opt }}}\ge r_{3}+p_{3}+q_{3}>S_{2}+p_{3}+q_{3}=2-p_{2}+p_{3}+q_{3}$ and $L_{{\text{ opt }}}\ge 2$, we have $L_{{\text{ on }}}-L_{{\text{ opt }}}\le 1$ and $\frac{L_{{\text{ on }}}-L_{{\text{ opt }}}}{L_{{\text{ opt }}}}\le \frac{1}{2}$. If both $J_{1}$ and $J_{2}$ start earlier than the time $S_{2}$ in the off-line optimal schedule, considering that $J_{3}$ arrives after the time $S_{2}$, then both $J_{1}$ and $J_{2}$ start before $J_{3}$ in the off-line optimal schedule. Note that the later completion time of $J_{1}$ and $J_{2}$ is not earlier than the time $\min \{p_{1}+p_{2}, S_{1}+p_{1}\}=\frac{3}{2}$ whether $J_{1}$ and $J_{2}$ are in a common batch or not in the off-line optimal schedule. Thus $J_{3}$ starts not earlier than the time $\frac{3}{2}$ in the off-line optimal schedule and $L_{{\text{ opt }}}\ge \frac{3}{2}+p_{3}+q_{3}$. Then $\frac{L_{{\text{ on }}}}{L_{{\text{ opt }}}}\le \frac{3-p_{2}+p_{3}+q_{3}}{\frac{3}{2}+p_{3}+q_{3}}\le \frac{\frac{9}{4}-\frac{1}{4}q_{1}+p_{3}+q_{3}}{\frac{3}{2}+p_{3}+q_{3}}\le \frac{3}{2}$. Here the last but one inequality holds as $p_{2}>\frac{3}{4}+\frac{1}{4}q_{1}$. Thus we have $\frac{L_{{\text{ on }}}}{L_{{\text{ opt }}}}\le \frac{3}{2}$ for the considered case.

3 The problem on an unbounded drop-line parallel batch machine

In this section, we study the problem on an unbounded drop-line parallel batch machine, i.e., $1|\text{ online },\; r_j,\; \text{ agreeable },\;\text{ drop-line } \text{ p-batch },\; b=\infty ,\; \text{ L-restart }|$ $L_{\max }$.

Theorem 3.1

For the problem $1|\text{ online },\; r_j, \text{ agreeable },\;\text{ drop-line } \text{ p-batch },\; b=\infty ,\; \text{ L-restart }|$ $L_{\max }$, there is no online algorithm with a competitive ratio less than $\frac{3}{2}$.

Proof

Similar to the method of proof in Fu et al. [3], we can prove that there is no online algorithm with a competitive ratio less than $\frac{3}{2}$ for the problem $1|\text{ online },\; r_j,\; \text{ drop-line } \text{ p-batch },\; b=\infty ,\;\text{ L-restart }|C_{\max }$. The problem $1|\text{ online },\; r_j,\; \text{ drop-line } \text{ p-batch },\; b=\infty ,\; \text{ L-restart }|C_{\max }$ is a special case of the problem $1|\text{ online },\; r_j,\; \text{ agreeable },\;\text{ drop-line } \text{ p-batch },\; b=\infty ,\; \text{ L-restart }|L_{\max }$ (by setting $q_{j}=0$ for all jobs). Therefore there is no online algorithm with a competitive ratio less than $\frac{3}{2}$ for the problem $1|\text{ online },\; r_j,\; \text{ agreeable },\;$ $\text{ drop-line } \text{ p-batch },\; b=\infty ,\; \text{ L-restart }|L_{\max }$. The result follows. $\square$

Now we will prove that Algorithm H is also a best possible online algorithm for the problem $1|\text{ online },\; r_j,\;$ $\text{ agreeable },\;\text{ drop-line } \text{ p-batch },\; b=\infty ,\; \text{ L-restart }|$ $L_{\max }$. For simplicity, we call the problem $1|\text{ online },\; r_j,\; \text{ agreeable },\;\text{ p-batch },\; b=\infty ,\; \text{ L-restart }|L_{\max }$ as the problem P1 and call the problem $1|\text{ online },\; r_j,\; \text{ agreeable },\;\text{ drop-line } \text{ p-batch },\; b=\infty ,\; \text{ L-restart }|$ $L_{\max }$ as the problem P2.

Let $\sigma _{1}$ and $\sigma _{2}$ be the schedules of an instance I generated by Algorithm H for the problems P1 and P2, respectively. Let $\sigma _{1}^{*}$ and $\sigma _{2}^{*}$ be the optimal off-line schedules of the instance I for the problems P1 and P2, respectively. Note that we may assume that there exist no interrupted batches in $\sigma _{1}^{*}$ and $\sigma _{2}^{*}$ since restarted jobs in $\sigma _{1}^{*}$ and $\sigma _{2}^{*}$ can be removed from the corresponding free batches.

For the schedules $\sigma _{i}$($i=1,2$), we use the following notations.

• $n_{i}$ ($i=1,2$) is the total number of batches in the schedule $\sigma _{i}$.

• $B_{k,i}$ $(i=1,2; 1\le k\le n_{i})$ is the k-th starting batch in the schedule $\sigma _{i}$.

• $S_{k,i}$ ($i=1,2; 1\le k\le n_{i}$) is the starting time of $B_{k,i}$.

• $p(B_{k,i})$($i=1,2; 1\le k\le n_{i}$) is the longest processing time of jobs in the batch $B_{k,i}$.

• $q(B_{k,i})$ ($i=1,2; 1\le k\le n_{i}$) is the largest delivery time of jobs in the batch $B_{k,i}$.

• $J_{k,i}^{p}$ ($i=1,2; 1\le k\le n_{i}$) is got by selecting the latest arriving one from jobs with the processing time $p(B_{k,i})$ in $B_{k,i}$.

• $J_{k,i}^{q}$ ($i=1,2; 1\le k\le n_{i}$) is got by selecting the latest arriving one from jobs with the delivery time $q(B_{k,i})$ in $B_{k,i}$.

Theorem 3.2

Algorithm H is a best possible online algorithm for the problem $1|\text{ online },\; r_j,\;$ $\text{ agreeable },\;\text{ drop-line } \text{ p-batch },\; b=\infty ,\; \text{ L-restart }|$ $L_{\max }$.

Proof

By Theorem 3.1, we just need to prove that for an instance I, the objective value of the schedule $\sigma _{2}$ is no more than $\frac{3}{2}$ times the objective value of the schedule $\sigma _{2}^{*}$.

Similar to the proof of Lemma 2.2, we have the following Claim.

Claim 1

For each batch $B_{k,i}$ $(i=1,2; 1\le k\le n_{i})$, at least one job of $J_{k,i}^{p}$ and $J_{k,i}^{q}$ has the processing time of $p(B_{k,i})$ and the delivery time of $q(B_{k,i})$.

For the number of batches and characteristics of batches in the schedules $\sigma _{i}(i=1,2)$, we have the following property.

Claim 2

• (1) $n_{1}=n_{2}$;

• (2) For $1\le i\le n_{1}$, one of the following two conclusions holds:

  • (a) $B_{i,2}$ and $B_{i,1}$ are both free batches. They have the same jobs and the same starting time.

  • (b) $B_{i,2}$ and $B_{i,1}$ are both restricted batches. They have the same starting time, the same longest processing time, the same largest delivery time and the same unrestarted jobs.

Clearly, $B_{1,1}$ and $B_{1,2}$ are both free batches, and they have the same starting time and the same jobs.

Suppose that $B_{k,1}$ and $B_{k,2}$ are both free batches, and have the same jobs and the same starting time. By Algorithm H, a new batch $B_{k+1,2}$(or $B_{k+1,1}$) starts depending on the information on newly arrived jobs, the longest processing time of $B_{k,2}$(or $B_{k,1}$) and the largest delivery time of $B_{k,2}$(or $B_{k,1}$). So either $B_{k+1,2}$ and $B_{k+1,1}$ are both free batches, and have the same starting time and the same jobs, or $B_{k+1,2}$ and $B_{k+1,1}$ are both restricted batches with the same starting time. If $B_{k+1,2}$ and $B_{k+1,1}$ are both restricted batches, then $B_{k+1,1}$ consists of all jobs in $B_{k,1}$ and newly arrived jobs, and $B_{k+1,2}$ consists of the jobs in $B_{k,2}$ which do not complete at time $S_{k+1,2}$ and newly arrived jobs. As $B_{k+1,2}$ and $B_{k+1,1}$ have the same starting time, then they have the same unrestarted jobs. Note that the jobs in $B_{k,2}$ which do not complete at time $S_{k+1,2}$ contain one of the jobs $J_{k,2}^{p}$ and $J_{k,2}^{q}$ which has the processing time of $p(B_{k,2})$ and the delivery time of $q(B_{k,2})$. Note that $p(B_{k,2})=p(B_{k,1})$ and $q(B_{k,2})=q(B_{k,1})$. So the longest processing time of restarted jobs in $B_{k+1,1}$ is equal to the longest processing time of restarted jobs in $B_{k+1,2}$, and the largest delivery time of restarted jobs in $B_{k+1,1}$ is equal to the largest delivery time of restarted jobs in $B_{k+1,2}$. Also considering that $B_{k+1,2}$ and $B_{k+1,1}$ have the same unrestarted jobs, then the longest processing time of jobs in $B_{k+1,1}$ is equal to the longest processing time of jobs in $B_{k+1,2}$, and the largest delivery time of jobs in $B_{k+1,1}$ is equal to the largest delivery time of jobs in $B_{k+1,2}$. So if $B_{k+1,2}$ and $B_{k+1,1}$ are both restricted batches, then $B_{k+1,2}$ and $B_{k+1,1}$ have the same starting time, the same longest processing time, the same largest delivery time and the same unrestarted jobs.

The above proof also shows that if $B_{m,2}$ and $B_{m,1}$ are the first restricted batches, then $B_{m,2}$ and $B_{m,1}$ have the same starting time, the same longest processing time, the same largest delivery time and the same unrestarted jobs.

Suppose that $B_{k,2}$ and $B_{k,1}$ are both restricted batches, and they have the same starting time, the same longest processing time, the same largest delivery time and the same unrestarted jobs. Then $B_{k,2}$ and $B_{k,1}$ have the same completion time by Algorithm H. Thus $B_{k,2}$ and $B_{k,1}$ have the same starting time and the same completion time. By Algorithm H, $B_{k+1,2}$ and $B_{k+1,1}$ are both free batches and $B_{k+1,2}$( or $B_{k+1,1}$) starts depending on the information on newly arrived jobs. So $B_{k+1,2}$ and $B_{k+1,1}$ are both free batches, and they have the same starting time and the same jobs.

The above proof shows that $n_{1}=n_{2}$ and for $1\le i\le n_{1}$, either $B_{i,2}$ and $B_{i,1}$ are both free batches and have the same jobs and the same starting time, or $B_{i,2}$ and $B_{i,1}$ are both restricted batches and have the same starting time, the same longest processing time, the same largest delivery time and the same unrestarted jobs. Claim 2 follows.

By Claim 2, we may assume that $n=n_{1}=n_{2}$.

Claim 3

The objective value of the schedule $\sigma _{2}$ for the problem P2 is no more than the objective value of the schedule $\sigma _{1}$ for the problem P1.

For any job $J_{j}$ in the instance I, we distinguish the following cases.

If in the schedule $\sigma _{2}$, $J_{j}$ is completed in a batch $B_{k,2}$ which is a free batch uninterrupted or is a restricted batch, by Claim 2, then $J_{j}$ is completed in the batch $B_{k,1}$ in the schedule $\sigma _{1}$. For the problem P1, the time by which $J_{j}$ has been delivered in the schedule $\sigma _{1}$ is $S_{k,1}+p(B_{k,1})+q_{j}$. For the problem P2, the time by which $J_{j}$ has been delivered in the schedule $\sigma _{2}$ is $S_{k,2}+p_{j}+q_{j}$. Note that $p(B_{k,1})\ge p_{j}$ and $S_{k,2}=S_{k,1}$ by Claim 2, then $S_{k,1}+p(B_{k,1})+q_{j}\ge S_{k,2}+p_{j}+q_{j}$. So if in the schedule $\sigma _{2}$, $J_{j}$ is completed in a batch $B_{k,2}$ which is a free batch uninterrupted or is a restricted batch, then the time by which $J_{j}$ has been delivered in the schedule $\sigma _{2}$ for the problem P2 is not later than the time by which $J_{j}$ has been delivered in the schedule $\sigma _{1}$ for the problem P1.

If in the schedule $\sigma _{2}$, $J_{j}$ is completed in a free batch $B_{k,2}$ which is interrupted, then $J_{j}$ is completed in the restricted batch $B_{k+1,1}$ in the schedule $\sigma _{1}$. For the problem P1, the time by which $J_{j}$ has been delivered in the schedule $\sigma _{1}$ is $S_{k+1,1}+p(B_{k+1,1})+q_{j}$. For the problem P2, the time by which $J_{j}$ has been delivered in the schedule $\sigma _{2}$ is $S_{k,2}+p_{j}+q_{j}$. Note that $p(B_{k+1,1})\ge p_{j}$ and $S_{k,2}=S_{k,1}$ by Claim 2. Then $S_{k+1,1}+p(B_{k+1,1})+q_{j}>S_{k,2}+p_{j}+q_{j}$. So if in the schedule $\sigma _{2}$, $J_{j}$ is completed in a free batch $B_{k,2}$ which is interrupted, then the time by which $J_{j}$ has been delivered in the schedule $\sigma _{2}$ for the problem P2 is earlier than the time by which $J_{j}$ has been delivered in the schedule $\sigma _{1}$ for the problem P1.

Then for any job $J_{j}$ in the instance I, the time by which $J_{j}$ has been delivered in the schedule $\sigma _{2}$ for the problem P2 is not later than the time by which $J_{j}$ has been delivered in the schedule $\sigma _{1}$ for the problem P1. Then the objective value of $\sigma _{2}$ for the problem P2 is no more than the objective value of $\sigma _{1}$ for the problem P1. Claim 3 follows.

Claim 4

The objective value of the schedule $\sigma _{2}^{*}$ for the problem P2 is equal to the objective value of the schedule $\sigma _{1}^{*}$ for the problem P1.

In fact, considering that $\sigma _{1}^{*}$ is the optimal off-line schedule of the instance I for the problem P1 and $\sigma _{2}^{*}$ is the optimal off-line schedule of the instance I for the problem P2, obviously the objective value of the schedule $\sigma _{2}^{*}$ for the problem P2 is no more than the objective value of the schedule $\sigma _{1}^{*}$ for the problem P1. Now we just need to prove that the objective value of the schedule $\sigma _{1}^{*}$ for the problem P1 is no more than the objective value of the schedule $\sigma _{2}^{*}$ for the problem P2.

Similar to the proof of Lemma 2.2, for each batch $B_{k}$ in the schedule $\sigma _{2}^{*}$, there exists one job $J_{l}$ with the longest processing time $p(B_{k})$ and the largest delivery time $q(B_{k})$.

If we consider the schedule $\sigma _{2}^{*}$ for the problem P2, then for any job $J_{j}$ in the batch $B_{k}$, the time by which $J_{j}$ has been delivered is $S_{k}+p_{j}+q_{j}\le S_{k}+p(B_{k})+q(B_{k})$ and the equality holds when $j=l$. If we consider the schedule $\sigma _{2}^{*}$ for the problem P1, the time by which all jobs in the batch $B_{k}$ have been delivered is $S_{k}+p(B_{k})+q(B_{k})$. So $S_{k}+p(B_{k})+q(B_{k})$ is the time by which all jobs in $B_{k}$ have been delivered for the schedule $\sigma _{2}^{*}$ for the problem P1 and for the optimal off-line schedule $\sigma _{2}^{*}$ for the problem P2. Thus the objective value of the schedule $\sigma _{2}^{*}$ for the problem P2 is equal to the objective value of the schedule $\sigma _{2}^{*}$ for the problem P1. Because $\sigma _{1}^{*}$ is the optimal off-line schedule of the instance I for the problem P1, the objective value of the schedule $\sigma _{1}^{*}$ for the problem P1 is no more than the objective value of the schedule $\sigma _{2}^{*}$ for the problem P1. So the objective value of the schedule $\sigma _{1}^{*}$ for the problem P1 is no more than the objective value of the schedule $\sigma _{2}^{*}$ for the problem P2. Claim 4 follows.

By Claim 3 and 4, for the problem P2, the ratio of the objective value of $\sigma _{2}$ and the objective value of $\sigma _{2}^{*}$ is no more than the ratio of the objective value of $\sigma _{1}$ for the problem P1 and the objective value of $\sigma _{1}^{*}$ for the problem P1. By Theorem 2.1–2.2, for the problem P1, the ratio of the objective value of $\sigma _{1}$ and the objective value of $\sigma _{1}^{*}$ is no more than $\frac{3}{2}$. Thus for the problem P2, the ratio of the objective value of $\sigma _{2}$ and the objective value of $\sigma _{2}^{*}$ is no more than $\frac{3}{2}$.

By Theorem 3.1, Algorithm H is a best possible online algorithm for the problem $1|\text{ online },\; r_j,$ $\text{ agreeable },\;\text{ drop-line } \text{ p-batch },\; b=\infty ,\; \text{ L-restart }|$ $L_{\max }$. The result follows.$\Box$

4 Conclusions

In this paper, we study the online scheduling problem on an unbounded parallel batch machine (or on an unbounded drop-line parallel batch machine) to minimize the time by which all jobs have been delivered with limited restarts. Here all jobs have agreeable processing times and delivery times. We give an online algorithm H and prove that the online algorithm H is a best possible online algorithm with a competitive ratio of $\frac{3}{2}$ for the two problems considered in this paper, respectively. Note that for the corresponding online scheduling problem on an unbounded parallel batch machine (or on an unbounded drop-line parallel batch machine) without restarts, we can prove that there exists no online algorithm with a competitive ratio less than $\frac{1+\sqrt{5}}{2}\approx 1.618$ by using the proving method of Theorem 1 in Zhang et al. (2001). Thus by using limited restarts, Algorithm H has better performance than the best possible online algorithms of the corresponding problems without restarts.

For online scheduling problems, since we don’t know future arrival jobs’ information beforehand, we usually use a strategy of moderate wait instead of processing a job immediately when the machine is idle. For example, the condition of $t\ge \frac{1}{2}p(U(t))$ in Step 2 of Algorithm H and the restart time $t=2p(B_{k})-p_{h}$ in Step 4.3.1 of Algorithm H mean that the machine will have moderate wait before starting a free batch or a restricted batch. Since our problems are online scheduling problems and the design of our algorithm makes full use of the problems’ structure and properties, we design a best possible online algorithm H. But it isn’t easy that popular deterministic optimization approaches such as relaxation algorithms of integer programming get best possible online algorithms. Since jobs’ information are deterministic when they arrive, our problems are different from stochastic optimization problems. Note that stochastic optimization approaches’ ideas may be used to solve online scheduling problems. In the future we may design a corresponding randomized algorithm which may have better performance than best possible deterministic online algorithms.

Appendix

Proof of Lemma 2.4

Because $S_n<S_{n-1}+p(B_{n-1})$, $B_{n}$ is a restricted batch. Let $p'$ be the longest processing time of jobs arriving in the time interval $(S_{n-1},S_{n}]$ and $q''$ be the largest delivery time of jobs arriving in the time interval $(S_{n-1},S_{n}]$. Among the jobs which arrive in the time interval $(S_{n-1},S_{n}]$ and have the processing time $p'$, select one which arrives latest as the job $J'$. Let $r'$ and $q'$ be the arrival time and the delivery time of $J'$, respectively. Among the jobs which arrive in the time interval $(S_{n-1},S_{n}]$ and have the delivery time $q''$, select one which arrives latest as the job $J''$. Let $r''$ and $q''$ be the arrival time and the delivery time of $J''$, respectively. Thus we have $p'\ge p''$ and $q'\le q''$. Considering that both $J'$ and $J''$ arrive after the time $S_{n-1}$, $p'\ge p''$ and $q'\le q''$, then by Lemma 2.1, we have $L_{{\text{ opt }}}\ge S_{n-1}+p'+q''$. Since $B_{n}$ is a restricted batch, by Step 4.2 and 4.3 of Algorithm H, we have $p(B_{n-1})< p'<\frac{3}{2}p(B_{n-1})$ or $\frac{3}{4}p(B_{n-1})< p'\le p(B_{n-1})$. Note that $r'>S_{n-1}\ge \frac{1}{2}p(B_{n-1})$ by Observation 2.3.

Case 1.$p(B_{n-1})< p'< \frac{3}{2}p(B_{n-1})$.

By Step 4.2 of Algorithm H, we have $p(B_{n})=\max \{p(B_{n-1}), p'\}=p'$, $S_{n}=\max \{p',r'\}$ and $q(B_{n})=\max \{q'',q(B_{n-1})\}$.

As $p(B_{n-1})<p'$, considering that all jobs have agreeable processing times and delivery times, then the largest delivery time of jobs in $B_{n-1}$ is not more than $q'$. Thus $q(B_{n-1})\le q'\le q''$ and $q(B_{n})=\max \{q'',q(B_{n-1})\}=q''$. Now $L_{{\text{ on }}}=S_{n}+p(B_{n})+q(B_{n})=S_{n}+p'+q''$. Now we distinguish the following cases.

If $r'>p'$, then $S_{n}=r'$ and $L_{{\text{ on }}}=S_{n}+p(B_{n})+q(B_{n})=r'+p'+q''$. Note that $q'\le q''$. If $q'=q''$, then $L_{{\text{ opt }}}\ge r'+p'+q'=r'+p'+q''=L_{{\text{ on }}}$, which implies $L_{{\text{ on }}}=L_{{\text{ opt }}}$. If $q'<q''$, noting that all jobs have agreeable processing times and delivery times, then $p'\le p''$. Also considering that $p'\ge p''$, we have $p'=p''$. By the definitions of $J'$ and $J''$ and $p'=p''$, we have $r'\ge r''$. Since $B_{n}$ interrupts $B_{n-1}$ at time $S_{n}=r'$ and $r'>p'$, then by Step 4.2 of Algorithm H, we have $r'<\frac{5}{4}p(B_{n-1})$. Then $r''\le r'<\frac{5}{4}p(B_{n-1})$. If $r''<r'$ and $r''\ge p''$, considering that $p'=p''$ and $r''<\frac{5}{4}p(B_{n-1})$, then by Step 4.2 of Algorithm H, $B_{n}$ will interrupt $B_{n-1}$ at time $r''$, a contradiction to $S_{n}=r'$ and $r''<r'$. If $r''<r'$ and $r''<p''$, considering that $p''=p'$, $r'>p'$ and $p'$ is the longest processing time of jobs arriving in the time interval $(S_{n-1},S_{n}]=(S_{n-1},r']$, then by Step 4.2 of Algorithm H, $B_{n}$ will interrupt $B_{n-1}$ at time $p''=p'$, a contradiction to the fact that $S_{n}=r'$ and $r'>p'$. So the assumption of $r''<r'$ is not right and we have $r''=r'$. So if $q'<q''$, we have $p'=p''$ and $r''=r'$. Then $L_{{\text{ opt }}}\ge r''+p''+q''=r'+p'+q''=L_{{\text{ on }}}$, which implies $L_{{\text{ on }}}=L_{{\text{ opt }}}$.

If $r'\le p'$, then $S_{n}=p'$ and $L_{{\text{ on }}}=S_{n}+p(B_{n})+q(B_{n})=2p'+q''$. Thus $\frac{L_{{\text{ on }}}}{L_{{\text{ opt }}}}\le \frac{2p'+q''}{S_{n-1}+p'+q''}\le \frac{2p'+q''}{\frac{1}{2}p(B_{n-1})+p'+q''}\le \frac{2p'}{\frac{1}{2}p(B_{n-1})+p'}\le \frac{2\times \frac{3}{2}p(B_{n-1})}{\frac{3}{2}p(B_{n-1})+\frac{1}{2}p(B_{n-1})}=\frac{3}{2}$.

Case 2.$\frac{3}{4}p(B_{n-1})< p'\le p(B_{n-1})$.

By Step 4.3 of Algorithm H, we have $p(B_{n})=\max \{p',p(B_{n-1})\}=p(B_{n-1})$, $r'<\frac{5}{4}p(B_{n-1})$ and $S_{n}=\max \{2p(B_{n-1})-p',r'\}$. Note that $S_{n}< \frac{5}{4}p(B_{n-1})$ as $\frac{3}{4}p(B_{n-1})< p'$ and $r'<\frac{5}{4}p(B_{n-1})$. Then $L_{{\text{ on }}}=S_{n}+p(B_{n})+q(B_{n})=S_{n}+p(B_{n-1})+q(B_{n})<\frac{9}{4}p(B_{n-1})+q(B_{n})$.

Subcase 2.1$q''>q(B_{n-1})$.

Then $q(B_{n})=\max \{q(B_{n-1}),q''\}=q''$. Now $L_{{\text{ on }}}=S_{n}+p(B_{n})+q(B_{n})=S_{n}+p(B_{n-1})+q''<\frac{9}{4}p(B_{n-1})+q''$.

Note that $q_{n-1}^{p}$ is the delivery time of $J_{n-1}^{p}$ and $p(B_{n-1})$ is the processing time of $J_{n-1}^{p}$. Considering that $q''>q(B_{n-1})\ge q_{n-1}^{p}$, we have $p''\ge p(B_{n-1})$. Considering that $p''\le p'$, $p'\le p(B_{n-1})$ and $p''\ge p(B_{n-1})$, we have $p''=p'=p(B_{n-1})$. Then $L_{{\text{ opt }}}\ge S_{n-1}+p'+q''\ge \frac{1}{2}p(B_{n-1})+p(B_{n-1})+q''=\frac{3}{2}p(B_{n-1})+q''$ by Observation 2.3. Thus $\frac{L_{{\text{ on }}}}{L_{{\text{ opt }}}}\le \frac{\frac{9}{4}p(B_{n-1})+q''}{\frac{3}{2}p(B_{n-1})+q''}\le \frac{3}{2}$.

Subcase 2.2$q''\le q(B_{n-1})$.

Then $q(B_{n})=\max \{q(B_{n-1}),q''\}=q(B_{n-1})$. Now $L_{{\text{ on }}}=S_{n}+p(B_{n})+q(B_{n})=S_{n}+p(B_{n-1})+q(B_{n-1})$. Since $B_{n}$ interrupts $B_{n-1}$, we have $p'\ge \frac{3}{4}p(B_{n-1})+\frac{1}{4}q(B_{n-1})$ by Step 4.3 of Algorithm H. As $p'\ge \frac{3}{4}p(B_{n-1})+\frac{1}{4}q(B_{n-1})$ and $p'\le p(B_{n-1})$, we have $q(B_{n-1})\le p(B_{n-1})$.

By Lemma 2.2, for the batch $B_{n-1}$, at least one of the jobs $J_{n-1}^{p}$ and $J_{n-1}^{q}$ has the processing time $p(B_{n-1})$ and the delivery time $q(B_{n-1})$ and denote the job by $J_{n-1}^{*}$.

If $S_{n}=2p(B_{n-1})-p'$, then $L_{{\text{ on }}}=S_{n}+p(B_{n-1})+q(B_{n-1})=2p(B_{n-1})-p'+p(B_{n-1})+q(B_{n-1})\le 2p(B_{n-1})-(\frac{3}{4}p(B_{n-1})+\frac{1}{4}q(B_{n-1}))+p(B_{n-1})+q(B_{n-1})= \frac{9}{4}p(B_{n-1})+\frac{3}{4}q(B_{n-1})$. Note that $J'$ arrives after time $S_{n-1}$, and the processing time of $J_{n-1}^{*}$ is $p(B_{n-1})$, and the delivery time of $J_{n-1}^{*}$ is $q(B_{n-1})$. Thus $L_{{\text{ opt }}}\ge \min \{S_{n-1}+p(B_{n-1})+q(B_{n-1}),p(B_{n-1})+p'\}$ whether $J'$ and $J_{n-1}^{*}$ are in a common batch in the optimal off-line schedule $\pi$ or not. Then $L_{{\text{ opt }}}\ge \min \{S_{n-1}+p(B_{n-1})+q(B_{n-1}),p(B_{n-1})+p'\}\ge \min \{\frac{1}{2}p(B_{n-1})+p(B_{n-1})+q(B_{n-1}),p(B_{n-1})+\frac{3}{4}p(B_{n-1})+\frac{1}{4}q(B_{n-1})\}\ge \min \{\frac{3}{2}p(B_{n-1})+q(B_{n-1}),p(B_{n-1})+\frac{2}{4}p(B_{n-1})+\frac{2}{4}q(B_{n-1})\}=\frac{3}{2}p(B_{n-1})+\frac{1}{2}q(B_{n-1})$. Here the last but one inequality hods as $p(B_{n-1})\ge q(B_{n-1})$. Thus $\frac{L_{{\text{ on }}}}{L_{{\text{ opt }}}}\le \frac{\frac{9}{4}p(B_{n-1})+\frac{3}{4}q(B_{n-1})}{\frac{3}{2}p(B_{n-1})+\frac{1}{2}q(B_{n-1})}=\frac{3}{2}$.

If $S_{n}=r'$, then $r'\ge 2p(B_{n-1})-p'$ and $L_{{\text{ opt }}}\ge r'+p'\ge 2p(B_{n-1})$. Now $L_{{\text{ on }}}=S_{n}+p(B_{n-1})+q(B_{n-1})=r'+p(B_{n-1})+q(B_{n-1})$. Considering that $p'\ge \frac{3}{4}p(B_{n-1})+\frac{1}{4}q(B_{n-1})$ and $q(B_{n-1})\le p(B_{n-1})$, we have $\frac{L_{{\text{ on }}}}{L_{{\text{ opt }}}}\le \frac{r'+p(B_{n-1})+q(B_{n-1})}{r'+p'}=1+\frac{p(B_{n-1})+q(B_{n-1})-p'}{r'+p'}\le 1+\frac{\frac{1}{4}p(B_{n-1})+\frac{3}{4}q(B_{n-1})}{2p(B_{n-1})}\le 1+\frac{p(B_{n-1})}{2p(B_{n-1})}=\frac{3}{2}$. The result follows. $\square$

Proof of Lemma 2.5

As $S_n=S_{n-1}+p(B_{n-1})$, then $B_{n}$ is a free batch and all jobs in $B_{n}$ arrive after the time $S_{n-1}$. Now $L_{{\text{ on }}}=S_{n}+p(B_{n})+q(B_{n})=S_{n-1}+p(B_{n-1})+p(B_{n})+q(B_{n})$. By Lemma 2.2, $L_{{\text{ opt }}}\ge r(B_{n})+p(B_n)+q(B_n)>S_{n-1}+p(B_n)+q(B_n)$. Thus

$$\begin{aligned} L_{{\text{ on }}}-L_{{\text{ opt }}}\le p(B_{n-1}). \end{aligned}$$

(1)

Let $p'$ be the longest processing time of jobs arriving in the time interval $(S_{n-2},S_{n-1}]$. Among the jobs which arrive in the time interval $(S_{n-2},S_{n-1}]$ and have a processing time $p'$, select one which arrives latest as the job $J'$. Let $r'$ and $q'$ be the arrival time and the delivery time of $J'$, respectively. Considering that $B_{n-1}$ is a restricted batch, then by Algorithm H, we have $p(B_{n-2})< p'<\frac{3}{2}p(B_{n-2})$ or $\frac{3}{4}p(B_{n-2})<p'\le p(B_{n-2})$. By Lemma 2.2, at least one of the jobs $J_{n}^{p}$ and $J_{n}^{q}$ has the processing time of $p(B_{n})$ and the delivery time of $q(B_{n})$. Let $J_{n}^{*}$ be one of $J_{n}^{p}$ and $J_{n}^{q}$ whose processing time is $p(B_{n})$ and delivery time is $q(B_{n})$.

Case 1.$p(B_{n-2})< p'<\frac{3}{2}p(B_{n-2})$.

Then $p(B_{n-1})=\max \{p(B_{n-2}),p'\}=p'$. By Step 4.2 of Algorithm H, $S_{n-1}=\max \{p',r'\}$.

If $r'\ge p'$, we have $S_{n-1}=r'$ and $L_{{\text{ opt }}}\ge r'+p'\ge 2p'=2p(B_{n-1})$. Then by the inequality (1), we have $\frac{L_{{\text{ on }}}-L_{{\text{ opt }}}}{L_{{\text{ opt }}}}\le \frac{p(B_{n-1})}{2p(B_{n-1})}=\frac{1}{2}$.

If $r'<p'$, we have $S_{n-1}=p'=p(B_{n-1})$. If $J'$ starts not before $J_{n}^{*}$ in the optimal off-line schedule $\pi$, considering that $J_{n}^{*}$ arrives after the time $S_{n-1}$, then $L_{{\text{ opt }}}\ge S_{n-1}+p'=2p(B_{n-1})$. Thus we have $L_{{\text{ on }}}-L_{{\text{ opt }}}\le p(B_{n-1})\le \frac{1}{2}L_{{\text{ opt }}}$. If $J'$ starts before $J_{n}^{*}$ in the schedule $\pi$, then $L_{{\text{ opt }}}\ge r'+p'+p(B_{n})+q(B_{n})>S_{n-2}+p(B_{n-1})+p(B_{n})+q(B_{n})$. Considering that $\frac{1}{3}p(B_{n-1})=\frac{1}{3}p'<\frac{1}{2}p(B_{n-2})$ and $S_{n-2}\ge \frac{1}{2}p(B_{n-2})$, we have $S_{n-2}\ge \frac{1}{3}p(B_{n-1})$. Then $L_{{\text{ opt }}}>S_{n-2}+p(B_{n-1})+p(B_{n})+q(B_{n})\ge \frac{1}{3}p(B_{n-1})+p(B_{n-1})=\frac{4}{3}p(B_{n-1})$ and $L_{{\text{ on }}}-L_{{\text{ opt }}}\le S_{n-1}+p(B_{n-1})+p(B_{n})+q(B_{n})-(S_{n-2}+p(B_{n-1})+p(B_{n})+q(B_{n}))=S_{n-1}-S_{n-2}\le p(B_{n-1})-\frac{1}{3}p(B_{n-1})=\frac{2}{3}p(B_{n-1})$. Thus $\frac{L_{{\text{ on }}}-L_{{\text{ opt }}}}{L_{{\text{ opt }}}}\le \frac{\frac{2}{3}p(B_{n-1})}{\frac{4}{3}p(B_{n-1})}=\frac{1}{2}$.

Case 2.$\frac{3}{4}p(B_{n-2})< p'\le p(B_{n-2})$.

Then $p(B_{n-1})=\max \{p(B_{n-2}),p'\}=p(B_{n-2})$. By Step 4.3 of Algorithm H, we have $S_{n-1}=\max \{2p(B_{n-2})-p',r'\}$. Then $L_{{\text{ on }}}=S_{n-1}+p(B_{n-1})+p(B_{n})+q(B_{n})=S_{n-1}+p(B_{n-2})+p(B_{n})+q(B_{n})$.

If $r'\ge 2p(B_{n-2})-p'$, then $L_{{\text{ opt }}}\ge r'+p'\ge 2p(B_{n-2})=2p(B_{n-1})$. Thus $L_{{\text{ on }}}-L_{{\text{ opt }}}\le p(B_{n-1})\le \frac{1}{2}L_{{\text{ opt }}}$ by the inequality (1).

If $r'<2p(B_{n-2})-p'$, then $S_{n-1}=2p(B_{n-2})-p'<\frac{5}{4}p(B_{n-2})$. Now we distinguish the following cases. If $J_{n-2}^{p}$ or $J'$ starts not before $J_{n}^{*}$ in the schedule $\pi$, considering that $J_{n}^{*}$ arrives after the time $S_{n-1}$, then $L_{{\text{ opt }}}\ge S_{n-1}+\min \{p(B_{n-2}),p'\}=S_{n-1}+p'=2p(B_{n-2})=2p(B_{n-1})$. Thus $L_{{\text{ on }}}-L_{{\text{ opt }}}\le p(B_{n-1})\le \frac{1}{2}L_{{\text{ opt }}}$. If both $J_{n-2}^{p}$ and $J'$ start before $J_{n}^{*}$ in the schedule $\pi$, then $J_{n}^{*}$ starts not earlier than the time $\min \{p(B_{n-2})+p',r'+p(B_{n-2})\}$ in the schedule $\pi$ whether $J_{n-2}^{p}$ and $J'$ are in a common batch or not in the schedule $\pi$. Note that $\min \{p(B_{n-2})+p',r'+p(B_{n-2})\}\ge \min \{p(B_{n-2})+\frac{3}{4}p(B_{n-2}),S_{n-2}+p(B_{n-2})\}\ge \min \{p(B_{n-2})+\frac{3}{4}p(B_{n-2}),\frac{1}{2}p(B_{n-2})+p(B_{n-2})\}= \frac{3}{2}p(B_{n-2})$. Then $J_{n}^{*}$ starts not earlier than the time $\frac{3}{2}p(B_{n-2})$ in the schedule $\pi$ and $L_{{\text{ opt }}}\ge \frac{3}{2}p(B_{n-2})+p(B_{n})+q(B_{n})$. Thus $\frac{L_{{\text{ on }}}}{L_{{\text{ opt }}}}\le \frac{S_{n-1}+p(B_{n-2})+p(B_{n})+q(B_{n})}{\frac{3}{2}p(B_{n-2})+p(B_{n})+q(B_{n})}\le \frac{\frac{5}{4}p(B_{n-2})+p(B_{n-2})+p(B_{n})+q(B_{n})}{\frac{3}{2}p(B_{n-2})+p(B_{n})+q(B_{n})}\le \frac{3}{2}$. The result follows. $\square$

Proof of Lemma 2.6

Since $S_n=S_{n-1}+p(B_{n-1})$, then $B_{n}$ is a free batch, and $r(B_{n})>S_{n-1}$, and $L_{{\text{ on }}}=S_{n-1}+p(B_{n-1})+p(B_{n})+q(B_{n})$. By Lemma 2.2, $L_{{\text{ opt }}}\ge r(B_{n})+p(B_{n})+q(B_{n})>S_{n-1}+p(B_{n})+q(B_{n})$. Then

$$\begin{aligned} L_{{\text{ on }}}-L_{{\text{ opt }}}\le p(B_{n-1}). \end{aligned}$$

(2)

Case 1.$p(B_{n})\ge \frac{3}{2}p(B_{n-1})$.

Note that $L_{{\text{ on }}}-L_{{\text{ opt }}}\le p(B_{n-1})$ and $S_{n-1}\ge \frac{1}{2}p(B_{n-1})$ by Observation 2.3. Then $L_{{\text{ opt }}}>S_{n-1}+p(B_{n})+q(B_{n})\ge \frac{1}{2}p(B_{n-1})+\frac{3}{2}p(B_{n-1})=2p(B_{n-1})$. Thus $\frac{L_{{\text{ on }}}-L_{{\text{ opt }}}}{L_{{\text{ opt }}}}\le \frac{p(B_{n-1})}{2p(B_{n-1})}=\frac{1}{2}$.

Case 2.$p(B_{n-1})< p(B_{n})< \frac{3}{2}p(B_{n-1})$.

Note that the arrival time of $J_{n}^{p}$ is $r_{n}^{p}$ and the processing time of $J_{n}^{p}$ is $p(B_{n})$. Now we prove that $r_{n}^{p}\ge p(B_{n-1})$. If $r_{n}^{p}<p(B_{n-1})$, noting that $r_{n}^{p}<p(B_{n-1})<p(B_{n})$, then $B_{n}$ will interrupt $B_{n-1}$ at time $p(B_{n})$ by Step 4.2 of Algorithm H, a contradiction. So we have $r_{n}^{p}\ge p(B_{n-1})$. Then $L_{{\text{ opt }}}\ge r_{n}^{p}+p(B_{n})\ge 2p(B_{n-1})$. Thus by the inequality (2), $\frac{L_{{\text{ on }}}-L_{{\text{ opt }}}}{L_{{\text{ opt }}}}\le \frac{p(B_{n-1})}{2p(B_{n-1})}=\frac{1}{2}$.

Case 3.$p(B_{n})\le p(B_{n-1})$.

If $r_{n}^{p}+p(B_{n})\ge 2p(B_{n-1})$, we have $L_{{\text{ opt }}}\ge r_{n}^{p}+p(B_{n})\ge 2p(B_{n-1})$. Then $\frac{L_{{\text{ on }}}-L_{{\text{ opt }}}}{L_{{\text{ opt }}}}\le \frac{p(B_{n-1})}{2p(B_{n-1})}=\frac{1}{2}$. Now we assume that $r_{n}^{p}+p(B_{n})<2p(B_{n-1})$, i.e., $r_{n}^{p}< 2p(B_{n-1})-p(B_{n})$.

Subcase 3.1.$p(B_{n})=p(B_{n-1})$.

If $p(B_{n-1})>q(B_{n-1})$, then $\frac{3}{4}p(B_{n-1})+\frac{1}{4}q(B_{n-1})<p(B_{n-1})=p(B_{n})$. Considering that $r_{n}^{p}<2p(B_{n-1})-p(B_{n})=p(B_{n-1})=p(B_{n})$ and $p(B_{n})>\frac{3}{4}p(B_{n-1})+\frac{1}{4}q(B_{n-1})$, then $B_{n}$ will interrupt $B_{n-1}$ at time $2p(B_{n-1})-p(B_{n})=p(B_{n-1})$ by Step 4.3 of Algorithm H, a contradiction. So we have $p(B_{n-1})\le q(B_{n-1})$. By Lemma 2.2, $L_{{\text{ opt }}}\ge p(B_{n-1})+q(B_{n-1})\ge 2p(B_{n-1})$. Then by the inequality (2), we have $\frac{L_{{\text{ on }}}-L_{{\text{ opt }}}}{L_{{\text{ opt }}}}\le \frac{p(B_{n-1})}{2p(B_{n-1})}=\frac{1}{2}$.

Subcase 3.2.$p(B_{n})<p(B_{n-1})$.

By Lemma 2.2, for the batch $B_{n-1}$, at least one of the jobs $J_{n-1}^{p}$ and $J_{n-1}^{q}$ has the processing time of $p(B_{n-1})$ and the delivery time of $q(B_{n-1})$. So let $J_{n-1}^{*}$ be one of the jobs $J_{n-1}^{p}$ and $J_{n-1}^{q}$ whose processing time is $p(B_{n-1})$ and delivery time is $q(B_{n-1})$. Similarly, let $J_{n}^{*}$ be one of the jobs $J_{n}^{p}$ and $J_{n}^{q}$ whose processing time is $p(B_{n})$ and delivery time is $q(B_{n})$.

If $p(B_{n-1})\le q(B_{n-1})$, by Lemma 2.2, we have $L_{{\text{ opt }}}\ge p(B_{n-1})+q(B_{n-1})\ge 2p(B_{n-1})$. Then $\frac{L_{{\text{ on }}}-L_{{\text{ opt }}}}{L_{{\text{ opt }}}}\le \frac{p(B_{n-1})}{2p(B_{n-1})}=\frac{1}{2}$. Now we assume that $p(B_{n-1})>q(B_{n-1})$.

If $\frac{3}{4}p(B_{n-1})+\frac{1}{4}q(B_{n-1})<p(B_{n})<p(B_{n-1})$, considering that $r_{n}^{p}< 2p(B_{n-1})-p(B_{n})<\frac{5}{4}p(B_{n-1})$, then $B_{n}$ will interrupt $B_{n-1}$ by Step 4.3 of Algorithm H, a contradiction. So we have $p(B_{n})\le \frac{3}{4}p(B_{n-1})+\frac{1}{4}q(B_{n-1})$.

If $J_{n-1}^{*}$ starts not earlier than the time $S_{n-1}$ in the schedule $\pi$, then $L_{{\text{ opt }}}\ge S_{n-1}+p(B_{n-1})+q(B_{n-1})$. Note that the processing time of $J_{n}^{q}$ is $p_{n}^{q}$ and the processing time of $J_{n-1}^{p}$ is $p(B_{n-1})$. Then $p_{n}^{q}\le p(B_{n})<p(B_{n-1})$. Considering that $p_{n}^{q}<p(B_{n-1})$, then the delivery time of $J_{n}^{q}$ is not more than the delivery time of $J_{n-1}^{p}$, i.e., $q(B_{n})\le q_{n-1}^{p}$. Then $q(B_{n})\le q_{n-1}^{p}\le q(B_{n-1})$. Thus $L_{{\text{ on }}}-L_{{\text{ opt }}}\le S_{n-1}+p(B_{n-1})+p(B_{n})+q(B_{n})-(S_{n-1}+p(B_{n-1})+q(B_{n-1}))\le p(B_{n})\le \frac{3}{4}p(B_{n-1})+\frac{1}{4}q(B_{n-1})$. Note that $L_{{\text{ opt }}}\ge S_{n-1}+p(B_{n-1})+q(B_{n-1})\ge \frac{1}{2}p(B_{n-1})+p(B_{n-1})+q(B_{n-1})$. Then $\frac{L_{{\text{ on }}}-L_{{\text{ opt }}}}{L_{{\text{ opt }}}}\le \frac{1}{2}$.

Now we assume that $J_{n-1}^{*}$ starts earlier than the time $S_{n-1}$ in the schedule $\pi$. Considering that all jobs in $B_{n}$ arrive after the time $S_{n-1}$, then $J_{n-1}^{*}$ starts before $J_{n}^{*}$ in the schedule $\pi$. Then $L_{{\text{ opt }}}\ge r(B_{n-1})+p(B_{n-1})+p(B_{n})+q(B_{n})$.

As $B_{n-1}$ is a free batch, by Observation 2.1, we have $S_{n-1}=\frac{1}{2}p(B_{n-1})$, or $S_{n-1}=r(B_{n-1})$, or $S_{n-1}=S_{n-2}+p(B_{n-2})$.

If $S_{n-1}=r(B_{n-1})$ or $S_{n-1}=\frac{1}{2}p(B_{n-1})$, then $L_{{\text{ on }}}-L_{{\text{ opt }}}\le S_{n-1}+p(B_{n-1})+p(B_{n})+q(B_{n})-(r(B_{n-1})+p(B_{n-1})+p(B_{n})+q(B_{n}))=S_{n-1}-r(B_{n-1})\le \frac{1}{2}p(B_{n-1})$ and $\frac{L_{{\text{ on }}}-L_{{\text{ opt }}}}{L_{{\text{ opt }}}}\le \frac{1}{2}$.

From now on we assume that $S_{n-1}=S_{n-2}+p(B_{n-2})$. So $L_{{\text{ on }}}=S_{n-2}+p(B_{n-2})+p(B_{n-1})+p(B_{n})+q(B_{n})$. Since $B_{n-1}$ is a free batch, we have $r(B_{n-1})>S_{n-2}$. Thus $L_{{\text{ opt }}}\ge r(B_{n-1})+p(B_{n-1})+p(B_{n})+q(B_{n})>S_{n-2}+p(B_{n-1})+p(B_{n})+q(B_{n})$ and $L_{{\text{ on }}}-L_{{\text{ opt }}}\le p(B_{n-2})$. Noting that $L_{{\text{ on }}}-L_{{\text{ opt }}}\le p(B_{n-1})$, then

$$\begin{aligned} L_{{\text{ on }}}-L_{{\text{ opt }}}\le \min \{p(B_{n-1}),p(B_{n-2})\}. \end{aligned}$$

(3)

By Lemma 2.2, one job of the batch $B_{n-2}$ has the processing time of $p(B_{n-2})$ and the delivery time of $q(B_{n-2})$. Let $J_{n-2}^{*}$ be such a job in $B_{n-2}$ with the processing time $p(B_{n-2})$ and the delivery time $q(B_{n-2})$.

If $B_{n-2}$ is a restricted batch, then we have $S_{n-2}\ge p(B_{n-2})$ by Observation 2.2. Thus $L_{{\text{ opt }}}\ge r(B_{n})>S_{n-1}=S_{n-2}+p(B_{n-2})\ge 2p(B_{n-2})$. Hence $\frac{L_{{\text{ on }}}-L_{{\text{ opt }}}}{L_{{\text{ opt }}}} \le \frac{\min \{p(B_{n-1}),p(B_{n-2})\}}{2p(B_{n-2})}\le \frac{1}{2}$ by the inequality (3).

If $B_{n-2}$ is a free batch, we distinguish the following cases. If $p(B_{n-1})\ge \frac{3}{2}p(B_{n-2})$, we have $L_{{\text{ opt }}}\ge r(B_{n-1})+p(B_{n-1})>S_{n-2}+p(B_{n-1})\ge \frac{1}{2}p(B_{n-2})+\frac{3}{2}p(B_{n-2})=2p(B_{n-2})$. Thus $\frac{L_{{\text{ on }}}-L_{{\text{ opt }}}}{L_{{\text{ opt }}}}\le \frac{\min \{p(B_{n-1}),p(B_{n-2})\}}{2p(B_{n-2})}\le \frac{1}{2}$. If $p(B_{n-2})<p(B_{n-1})< \frac{3}{2}p(B_{n-2})$ or [$\frac{3}{4}p(B_{n-2})<p(B_{n-1})\le p(B_{n-2})$ and $p(B_{n-1})\ge \frac{3}{4}p(B_{n-2})+\frac{1}{4}q(B_{n-2})$], noting that $B_{n-1}$ does not interrupt the free batch $B_{n-2}$, then $r_{n-1}^{p}\ge \frac{5}{4}p(B_{n-2})$ by Step 4.2 and 4.3 of Algorithm H. Note that the arrival time of $J_{n-1}^{p}$ is $r_{n-1}^{p}$ and the processing time of $J_{n-1}^{p}$ is $p(B_{n-1})$. Thus $L_{{\text{ opt }}}\ge r_{n-1}^{p}+p(B_{n-1})\ge \frac{5}{4}p(B_{n-2})+\frac{3}{4}p(B_{n-2})\ge 2\min \{p(B_{n-1}),p(B_{n-2})\}$. So $\frac{L_{{\text{ on }}}-L_{{\text{ opt }}}}{L_{{\text{ opt }}}}\le \frac{\min \{p(B_{n-1}),p(B_{n-2})\}}{2\min \{p(B_{n-1}),p(B_{n-2})\}}\le \frac{1}{2}$. If [$\frac{3}{4}p(B_{n-2})<p(B_{n-1})\le p(B_{n-2})$ and $p(B_{n-1})<\frac{3}{4}p(B_{n-2})+\frac{1}{4}q(B_{n-2})$] or $p(B_{n-1})\le \frac{3}{4}p(B_{n-2})$, we distinguish the following two cases. If $J_{n-1}^{p}$ and $J_{n-2}^{*}$ are not in a common batch in the schedule $\pi$, $L_{{\text{ opt }}}\ge p(B_{n-1})+p(B_{n-2})\ge 2\min \{p(B_{n-1}),p(B_{n-2})\}$. Thus $\frac{L_{{\text{ on }}}-L_{{\text{ opt }}}}{L_{{\text{ opt }}}}\le \frac{\min \{p(B_{n-1}),p(B_{n-2})\}}{2\min \{p(B_{n-1}),p(B_{n-2})\}}=\frac{1}{2}$. If $J_{n-1}^{p}$ and $J_{n-2}^{*}$ are in a common batch in the schedule $\pi$, then $L_{{\text{ opt }}}\ge r_{n-1}^{p}+p(B_{n-2})+q(B_{n-2})>S_{n-2}+p(B_{n-2})+q(B_{n-2})\ge \frac{1}{2}p(B_{n-2})+p(B_{n-2})+q(B_{n-2})= \frac{3}{2}p(B_{n-2})+q(B_{n-2})$. Thus $\frac{L_{{\text{ on }}}-L_{{\text{ opt }}}}{L_{{\text{ opt }}}}\le \frac{p(B_{n-1})}{\frac{3}{2}p(B_{n-2})+q(B_{n-2})}\le \frac{\frac{3}{4}p(B_{n-2})+\frac{1}{4}q(B_{n-2})}{\frac{3}{2}p(B_{n-2})+q(B_{n-2})}\le \frac{1}{2}$. The result follows. $\square$