Online unbounded batch scheduling on parallel machines with delivery times

Abstract

We consider the online unbounded batch scheduling problems on $m$ identical machines subject to release dates and delivery times. Jobs arrive over time and the characteristics of jobs are unknown until their arrival times. Jobs can be processed in a common batch and the batch capacity is unbounded. Once the processing of a job is completed it is independently delivered to the destination. The objective is to minimize the time by which all jobs have been delivered. For each job $J_j$, its processing time and delivery time are denoted by $p_j$ and $q_j$ , respectively. We first consider a restricted model: the jobs have agreeable processing and delivery times, i.e., for any two jobs $J_i$ and $J_j\,p_i>p_j$ implies $q_i\ge q_j$ . For the restrict case, we provide a best possible online algorithm with competitive ratio $1+\alpha _m$, where $\alpha _m>0$ is determined by $\alpha _m^2+m\alpha _m=1$. Then we present an online algorithm with a competitive ratio of $1+2/\lfloor \sqrt{m}\rfloor$ for the general case.

1 Introduction

We consider an online scheduling model: online unbounded batch scheduling on parallel machines with delivery times. Here, we have $m$ batch machines and sufficiently many vehicles. There are $n$ jobs $J_1, J_2,\dots ,J_n$. Each job has a release date $r_j$, a processing time $p_j$, and a delivery time $q_j$. These characteristics about a job are unknown until it arrives. In this model, one batch machine can handle up to $B$ jobs simultaneously as a batch, where $B$ is sufficiently large. The processing time for a batch is equal to the longest processing time in the batch. All jobs in a common batch have the same starting time and completion time. Each job needs to be processed on one of the $m$ batch machines, and once the job is completed we deliver it immediately to the destination by a vehicle. The objective is to minimize the time by which all jobs have been delivered. We denote by $S_j, C_j$ and $L_j$, respectively, the starting time, the completion time and the time by which $J_j$ is delivered in a schedule. By using the general notation for a schedule problem, introduced by Graham et al. (1979), this problem is denoted by $Pm|online,r_j,q_j,B=\infty |L_{max}$, where $L_{max}=\max \{L_j:L_j=C_j+q_j, 1\le j\le n\}$.

Batch scheduling was first introduced by Lee et al. (1992), which was motivated by burn-in operations in semiconductor manufacturing. Deng et al. (2003) and Zhang et al. (2001) studied the online scheduling problem on single batch machine. They proved that there is no online algorithm with competitive ratio smaller than $(\sqrt{5} + 1)/2$, and for the case $B = \infty$, they independently gave the same online algorithm with competitive ratio matching the lower bound. For the case $B<n$, the first online algorithm is a greedy heuristic, GRLPT, of Lee and Uzsoy (1999) which was shown to be 2-competitive by Liu and Yu (2000). Zhang et al. (2001) presented two online algorithms with competitive ratio not greater than 2. The above three online algorithms are all based on the ideas of the FBLPT rule. Later, Poon and Yu (2005) presented a class of algorithms called the FBLPT-based algorithms that contains all the above three algorithms as special cases, and showed that any FBLPT-based algorithm has competitive ratio at most 2. In particular, for the case B = 2, they also gave an online algorithm with competitive ratio 7/4.

For the online model of scheduling on $m$ unbounded parallel batch machines, Zhang et al. (2001) gave a lower bound $\root m \of {2}$, and presented an online algorithm with competitive ratio $1+\alpha _m$, where $\alpha _m= (1-\alpha _m)^{m-1}$. For the special case where $m=2$, Nong et al. (2008) gave a $\sqrt{2}$-competitive online algorithm. For the general case, Liu et al. (2012) and Tian et al. (2009) showed the lower bound is $1+(\sqrt{m^2+4}-m)/2$, and gave different optimal algorithms independently.

There have also been some results about online scheduling problems with delivery times. Hoogeveen and Vestjean (2000) first studied the single-machine online scheduling problem with delivery times. They showed the lower bound is $(\sqrt{5}+1)/2$, and gave a best possible deterministic online algorithm. On identical parallel machines, Vestjens (1997) showed that no online algorithms can have competitive ratio smaller than 1.5 and showed the competitive ratio of the LS algorithm is 2. Tian et al. (2007) considered the single batch machine online scheduling problem with delivery times. They gave a 2-competitive algorithm for the unbounded case and a 3-competitive algorithm for the bounded case. In the same paper, they also studied a special model with identical processing times. They provided the best online algorithms with competitive ratio $(\sqrt{5}+1)/2$ for both bounded and unbounded cases. In another paper, Tian et al. (2012) gave an improved online algorithm for the same problem with competitive ratio $2\sqrt{2}-1$. Yuan et al. (2009) also studied the single machine parallel-batch scheduling. They provided a best possible online algorithm for two restricted models. Fang et al. (2011) addressed online scheduling on $m$ unbounded batch machines with delivery times. They gave an online algorithm with competitive ratio $1.5+o(1)$.

In this paper, we investigate online algorithms for parallel machine batch scheduling with delivery times. We first consider a restricted model: the jobs have agreeable processing and delivery times, i.e., for any two jobs $J_i$ and $J_j$, $p_i>p_j$ implies $q_i\ge q_j$ . We provide a best possible online algorithm with competitive ratio $1+\alpha _m$ for the problem, where $\alpha _m^2+m\alpha _m=1$. We also study the general case. We provide an online algorithm with a competitive ratio of $r=1+1/u+1/v$, where $u,v$ are integers and $uv\le m$. Especially if we take $u=v=\lfloor \sqrt{m}\rfloor$ and let $m\rightarrow +\infty$, then $r\rightarrow 1$. This improves the current algorithm with competitive ratio a 1.5+o(1) for this problem in the literature.

Throughout this paper, we use $r(S),p(S),q(S)$ to denote the smallest release date, the largest processing time and the largest delivery time of jobs in $S$, respectively.

2 A lower bound

We first consider the scheduling model $Pm|online, r_j, B =\infty |C_{max}$, which is a special case of the scheduling problems studied in this paper. Hence, its lower bound is also a lower bound of the problems we study. For the former, Liu et al. (2012) and Tian et al. (2009) presented the following lower bound of competitive ratio for all online algorithms independently.

Lemma 1

[Liu et al. (2012), Tian et al. (2009)] There is no online algorithm with competitive ratio less than $1+\alpha _m$ for $Pm|online,r_j,B=\infty |C_{max}$, where $\alpha _m^2+m\alpha _m=1$.

Corollary 1

There is no on-line algorithm with competitive ratio less than $1+\alpha _m$ for the following two problems where $\alpha _m^2+m\alpha _m=1$,

• (1) $Pm|online,r_j, agreeable(p_j, q_j),B=\infty |L_{max}$

• (2) $Pm|online,r_j,B=\infty |L_{max}$

3 A restrict case

In this section, we deal with a restrict model: jobs have agreeable processing and delivery times, i.e., for any two jobs $J_i$ and $J_j\,p_i > p_j$ implies $q_i\ge q_j$ . We provide a best possible online algorithm with competitive ratio $1+\alpha _m$ for the problem, where $\alpha _m = (\sqrt{m^2+4}-m)/2$, i.e. $\alpha _m^2+m\alpha _m=1$.

Let $A(t)$ be the set of the jobs which are available but not yet scheduled at time $t$. Denote by $p(t)$ the largest processing time of jobs in $A(t)$. Denote by $r(t)$ the smallest release date of the jobs in $A(t)$.

Algorithm $H1$ Whenever a machine is idle and $A(t)\not =\emptyset$, make decision as following: If $t\ge (1+\alpha _m)r(t)+\alpha _m p(t)$, then start all the available jobs as a single batch on the idle machine. Otherwise, do nothing but wait.

Now, we will prove that $H1$ has a competitive ratio of $1+\alpha _m$. Let $\sigma$ and $\pi$ denote the schedule generated by algorithm $H1$ and an optimal off-line schedule, respectively. Their objective values are denoted by $L_{max}(\sigma )$ and $L_{max}(\pi )$, respectively. We assume that there are $b$ batches totally in $\sigma$ which are written as $B_1,B_2,\dots ,B_b$. For each $i$, the longest job in batch $B_i$ is denoted by $J_i$(if two or more jobs have the longest processing time in batch $B_i$, let $J_i$ be the job with a larger delivery time) with a release date $r_i$, a processing time $p_i$ and a delivery time $q_i$. Since the jobs have agreeable processing and delivery times, $p_i=p(B_i),q_i=q(B_i)$. Thus we can use $S_i(\sigma )$ and $C_i(\sigma )$ to denote the starting time and the completion time of both job $J_i$ and batch $B_i$ in $\sigma$, respectively. It can be observed that $S_i(\sigma )<S_j(\sigma )$ implies $r(B_j) > S_i(\sigma )$ and $S_j(\sigma )\ge (1+\alpha _m)r(B_j)+\alpha _m p_j> (1+\alpha _m)S_i(\sigma )+\alpha _m p_j$. For any batch $B_i$, if $S_i(\sigma )=(1+\alpha _m)r(B_i)+\alpha _m p(B_i)$, we say that $B_i$ is regular. For convenience, we assume that $S_1(\sigma )<S_2(\sigma )<\cdots <S_b(\sigma )$.

Property 1

For any two batches in $\sigma$, say $B_i$ and $B_j$, if $S_i(\sigma )<S_j(\sigma )$, then $r_j>S_i(\sigma )$ and $S_j(\sigma )\ge (1+\alpha _m)r_j>(1+\alpha _m)S_i(\sigma )$.

Lemma 2

In $\sigma$, if $B_k$ is not regular, then $S_{k-1}(\sigma )> (1-\alpha _m)S_{k}(\sigma )$.

Proof

$B_k$ is not regular means that $S_k(\sigma )>(1+\alpha _m)r(B_k)+\alpha _m p_k$. Then by the algorithm, each machine is busy processing a batch during $[ r_k, S_k(\sigma ))$. Otherwise, $B_k$ will start earlier in $\sigma$. Denote the $m$ batches processed during $[r_k, S_k(\sigma ))$ by $B_{k_1},B_{k_2},\dots ,B_{k_m}$ with $S_{k_1}(\sigma )<S_{k_2}(\sigma )<\dots <S_{k_m}(\sigma )$. It is clear that $k_m=k-1$ and $C_{k_j}(\sigma )=S_{k_j}(\sigma )+p_{k_j}\ge S_{k}(\sigma )(j=1,2,\dots ,m)$, i.e.,

$$\begin{aligned} p_{k_j}\ge S_{k}(\sigma )-S_{k_j}(\sigma ), j=1,2,\dots ,m \end{aligned}$$

(1)

By the algorithm, $S_{k_1}(\sigma )\ge \alpha _m p_{k_1}\ge \alpha _m(S_{k}(\sigma )-S_{k_1}(\sigma ))$. Thus

$$\begin{aligned} S_{k_1}(\sigma )\ge \frac{\alpha _m}{1+\alpha _m} S_{k}(\sigma ) \end{aligned}$$

(2)

In addition, for each $j(2\le j\le m)$, $S_{k_j}(\sigma )\ge (1+\alpha _m)r(B_{k_j})+\alpha _m p(B_{k_j})> (1+\alpha _m)S_{k_{j-1}}(\sigma )+\alpha _m p_{k_j}$. Using the inequality (1), we deduce that $S_{k_j}(\sigma )\ge (1+\alpha _m)S_{k_{j-1}}(\sigma )+\alpha _m (S_{k}(\sigma )-S_{k_j}(\sigma ))$, i.e.,

$$\begin{aligned} S_{k_j}(\sigma )&> S_{k_{j-1}}(\sigma )+\frac{\alpha _m}{1+\alpha _m} S_{k}(\sigma ), 2\le j\le m \end{aligned}$$

(3)

Combining (2) and (3) we have that

$$\begin{aligned} S_{k_m}(\sigma )&> \frac{m\alpha _m}{1+\alpha _m} S_{k}(\sigma )= (1-\alpha _m) S_{k}(\sigma ) \end{aligned}$$

(4)

i.e. $S_{k-1}(\sigma )> (1-\alpha _m) S_{k}(\sigma )$. $\square$

Lemma 3

If $B_j$ is not regular, then $p_j< \alpha _m S_{j}(\sigma )$.

Proof

If $B_j$ is not a regular batch, then from Lemma 2 we have that $S_{j-1}(\sigma )> (1-\alpha _m) S_{j}(\sigma )$. By the algorithm, we know that $S_j(\sigma )>(1+\alpha _m)S_{j-1}(\sigma )+\alpha _m p_j$. Thus, $S_j(\sigma )>(1-\alpha _m^2)S_{j}(\sigma )+\alpha _m p_j$ which implies that $p_j< \alpha _m S_{j}(\sigma )$.

This competes the proof.$\square$

Lemma 4

If $B_k$ is not regular, then each machine is busy processing a regular batch during $[r_k, S_k(\sigma ))$.

Proof

$B_k$ is not regular means that $S_k(\sigma )>(1+\alpha _m)r(B_k)+\alpha _m p_k$. Then by the algorithm, each machine is busy processing a batch during $[r_k, S_k(\sigma ))$. Denote the $m$ batches processed in $[r_k, S_k(\sigma ))$ by $B_{k_1},B_{k_2},\dots ,B_{k_m}$. Then

$$\begin{aligned} S_{k_j}(\sigma )+p_{k_j}\ge S_{k}(\sigma ), j=1,2,\dots ,m \end{aligned}$$

(5)

Suppose for the sake of contradiction that $B_{k_j}$ is not regular for some $j$. Then by Lemma 3, $p_{k_j}<\alpha _m S_{k_j}$. Thus $S_k(\sigma )\ge (1+\alpha _m)r(B_k)>(1+\alpha _m)S_{k_j}(\sigma )>S_{k_j}(\sigma )+p_{k_j}$ which contradicts the inequality (5). Therefore, $B_{k_j}$ is regular for each $j(1\le j\le m)$.

This competes the proof. $\square$

Theorem 1

$L_{max}(\sigma ) \le (1+\alpha _m)L_{max}(\pi )$.

proof

Let $B_l$ denote the first batch in $\sigma$ that assumes the objective value $L_{max}(\sigma )$, i.e.,

$$\begin{aligned} L_{max}(\sigma ) = S_{l}(\sigma )+p_l+q_l \end{aligned}$$

(6)

If $B_l$ is regular, then $S_l(\sigma )=(1+\alpha _m)r({B_l})+\alpha _m p_l$. Thus $L_{max}(\sigma )=(1+\alpha _m)(r(B_l)+p_l)+q_l$. It is clear that $L_{max}(\pi )\ge r(B_l)+p_l+q_l$. Therefore, $L_{max}(\sigma ) \le (1+\alpha _m)L_{max}(\pi )$.

If $B_l$ is not regular, then $S_l(\sigma )>(1+\alpha _m)r(B_l)+\alpha _m p_l$. Thus by the algorithm, each machine is busy processing a batch during $[r_l, S_l(\sigma ))$. Denote the $m$ batches processed in $[r_l, S_l(\sigma ))$ by $B_{l_1},B_{l_2},\dots ,B_{l_m}$ with $S_{l_1}(\sigma )<S_{l_2}(\sigma )<\dots <S_{l_m}(\sigma )$. It is clear that $l_m=l-1$ and

$$\begin{aligned} S_{l}(\sigma )\le S_{l_j}(\sigma )+p_{l_j}, j=1,2,\dots ,m \end{aligned}$$

(7)

According to Lemma 4, $B_{l_j}$ is regular, i.e.

$$\begin{aligned} S_{l_j}(\sigma )= (1+\alpha _m)r(B_{l_j})+\alpha _m p_{l_j}\le (1+\alpha _m)r_{l_j}+\alpha _m p_{l_j} \end{aligned}$$

(8)

Now, we will consider two cases according to the assignment of the $m$ jobs $J_{l_j}(1\le j\le m)$ in the optimal schedule $\pi$.

Case 1 $S_{l_j}(\pi )<S_{l_j}(\sigma )$ for each $j(1\le j\le m)$. Then $r_{l_j}>S_{l_{j-1}}(\sigma )>S_{l_{j-1}}(\pi )$ for each $j(2\le j\le m)$. Hence, the $m$ jobs $J_{l_j}(1\le j\le m)$ are processed in $m$ different batches in $\pi$.

From the inequality (7), (8), we deduce that $S_l(\sigma )\le S_{l_j}(\sigma )+p_{l_j} \le (1+\alpha _m)(r_{l_j}+p_{l_j})$ for each $j=1,2,\dots ,m$. Therefore, $C_{l_j}(\pi )\ge r_{l_j}+p_{l_j}\ge S_l(\sigma )/(1+\alpha _m)>S_{l_m}(\sigma )$. Recall that $S_{l_j}(\pi )< S_{l_m}(\sigma )$ for each $j(1\le j\le m)$. Hence the $m$ jobs $J_{l_j}(1\le j\le m)$ are grouped into $m$ batches which are processed on $m$ different machines in the optimal schedule $\pi$. Recall that $r_l>S_{l_m}(\sigma )\ge S_{l_j}(\pi )$. Thus, in the optimal schedule $\pi$, $J_l$ starts after some job $J_{l_j}$. So

$$\begin{aligned} L_{max}(\pi )\ge \min _{1\le j\le m}\left\{ r_{l_j}+p_{l_j}\right\} +p_l+q_l \end{aligned}$$

(9)

While $L_{max}(\sigma )\le \min _j\{S_{l_j}(\sigma )+p_{l_j}\}+p_l+q_l\le (1+\alpha _m)\min _j\{r_{l_j}+p_{l_j}\}+p_l+q_l$. Therefore, $L_{max}(\sigma ) \le (1+\alpha _m)L_{max}(\pi )$.

Case 2 $S_{l_j}(\pi )\ge S_{l_j}(\sigma )$ for some $j(1\le j\le m)$. Then

$$\begin{aligned} L_{max}(\pi )\ge S_{l_j}(\sigma )+p_{l_j}\ge S_{l}(\sigma ) \end{aligned}$$

(10)

By Lemma 3, we have $S_{l_m}(\sigma )>(1-\alpha _m)S_{l}(\sigma )$. Thus

$$\begin{aligned} L_{max}(\pi )\ge r_l+p_l+q_l>S_{l_m}(\sigma )+p_l+q_l\ge (1-\alpha _m)S_{l}(\sigma )+p_l+q_l \end{aligned}$$

(11)

Then comuting the inequality $\alpha _m\cdot$(10)+ (11) and using (6) we deduce that $L_{max}(\sigma ) \le (1+\alpha _m)L_{max}(\pi )$.

This completes the proof.$\square$

4 The general case

In this section, we present an online algorithm for the general case which has a competitive ratio of $1+1/u+1/v$, where $u,v$ are positive integers and $uv\le m$.

Select $uv$ machines and partition the $uv$ machines into $u$ sets: $M^i$($1\le i\le u$). Each of $M^i$ contains $v$ machines. For convenience, we denote by $M_j^i(1\le j\le v)$ the machines in $M^i(i=1,2,\dots ,u)$. If all machines in $M^i$ are available, we call $M^i$ available.

Denote by $A(t)$ the set containing all jobs that have arrived at or before time $t$ and that have not been started by time $t$. We partition $A(t)$ into $v$ sets: $A_i(t)=\{J_j|\frac{i-1}{v} p(A(t))\le p_j< \frac{i}{v} p(A(t)), J_j\in A(t)\},i=1,2,\dots ,v-1$ and $A_v(t)=\{J_j| p_j\ge (1-\frac{1}{v}) p(A(t)), J_j\in A(t)\}$.

Algorithm $H(u,v)$ Whenever there exists an available machine group $M^i(i=1,2,\dots ,u)$ and $A(t)\ne \emptyset$, make decision as following. If $t\ge (1+\frac{1}{u})r(A(t))+\frac{1}{u}p(A(t))$, start $A_j(t)$ as a batch on $M_j^i$ for each $j(1\le j\le v)$. Otherwise, do nothing but wait.

For convenience, denote by $B^x$ the set of the $v$ batches with the same starting time. Each of the $v$ batches is denoted by $B^x_y$ and $B_y^x$ consists of all jobs in $A_y(t)$. We call $B^x$ a batch group.

Denote by $\sigma$ the schedule produced by $H(u,v)$. For convenience, denote by $S(B^i),C(B^i)$ the starting time and the maximum completion time of the batches in $B^i$. If $S(B^i)=(1+\frac{1}{u})r(B^i)+{\frac{1}{u}}p(B^i)$, we say that $B^i$ is regular.

Property 2

For any two batch groups in $\sigma$, say $B^i$ and $B^j$, if $S(B^i)<S(B^j)$, then $r(B^j)>S(B^i)$ and $S(B^j)\ge (1+\frac{1}{u})r(B^j)$.

Lemma 5

In $\sigma$, any batch group $B^i$ is regular, i.e. $S(B^{i})=(1+{\frac{1}{u}})r(B^{i})+{{\frac{1}{u}}}p(B^i)$.

Proof

Suppose to the contrary that $B^i$ is not regular, i.e. $S(B^{i})>(1+{\frac{1}{u}})r(B^{i})+{{\frac{1}{u}}}p(B^i)$. Thus between $(1+{\frac{1}{u}})r(B^{i})+{{\frac{1}{u}}}p(B^i)$ and $S(B^i)$, there is a batch group which is processed on each machine set $M^j(1\le j\le u)$. Suppose the $u$ batch groups are $B^{i_j}(1\le j\le u)$ with $S(B^{i_1})<S(B^{i_2})<\cdots <S(B^{i_{u}})$. Thus, for each $j(1\le j\le u)$, $S(B^{i_j})+p(B^{i_j})\ge S(B^i)$. Hence,

$$\begin{aligned} S\big (B^{i}\big )\le \frac{1}{u}\sum _{j=1}^u\big (S\big (B^{i_j}\big )+p\big (B^{i_j}\big )\big )=\frac{1}{u}\sum _{j=1}^u C\big (B^{i_j}\big ) \end{aligned}$$

(12)

By the algorithm and Property 2, we have

$$\begin{aligned} S\big (B^{i_1}\big )&\ge {\frac{1}{u}}p\big (B^{i_1}\big )\end{aligned}$$

(13)

$$\begin{aligned} S\big (B^{i_j}\big )&\ge \left( 1+{\frac{1}{u}}\right) r\big (B^{i_j}\big )+{{\frac{1}{u}}}p\big (B^{i_j}\big )\nonumber \\&> \left( 1+{\frac{1}{u}}\right) S\big (B^{i_{j-1}}\big )+{{\frac{1}{u}}}p\big (B^{i_j}\big ) \end{aligned}$$

(14)

Thus

$$\begin{aligned} \sum _{j=1}^u S\big (B^{i_j}\big )&\ge \left( 1+{\frac{1}{u}}\right) \sum _{j=1}^{u-1}S\big (B^{i_{j}}\big )+{{\frac{1}{u}}}\sum _{j=1}^u p\big (B^{i_j}\big ) \end{aligned}$$

i.e.

$$\begin{aligned} S\big (B^{i_u}\big )&\ge {\frac{1}{u}}\sum _{j=1}^{u-1}S\big (B^{i_{j}}\big )+{{\frac{1}{u}}}\sum _{j=1}^u p\big (B^{i_j}\big ) \end{aligned}$$

(15)

Recall that $S(B^{i})>\big (1+{\frac{1}{u}}\big )S(B^{i_u})$. We have that

$$\begin{aligned} S\big (B^{i}\big )&> S\big (B^{i_u}\big )+{\frac{1}{u}}S\big (B^{i_u}\big )\nonumber \\&\ge {\frac{1}{u}}\sum _{j=1}^{u-1}S\big (B^{i_{j}}\big )+{{\frac{1}{u}}}\sum _{j=1}^u p\big (B^{i_j}\big )+{\frac{1}{u}}S\big (B^{i_u}\big )\nonumber \\&= {\frac{1}{u}}\sum _{j=1}^{u}\big (S\big (B^{i_{j}}\big )+p\big (B^{i_j}\big )\big ) \end{aligned}$$

(16)

which contradicts the inequality (12).

Therefore, in $\sigma$, each batch group $B^i$ is regular, i.e. $S(B^{i})=(1+{\frac{1}{u}})r(B^{i})+{{\frac{1}{u}}}p(B^i)$.$\square$

Theorem 2

The competitive ratio of Algorithm $H(u,v)$ is $1+\frac{1}{u}+\frac{1}{v}$.

Proof

Let $\pi$ be an optimal schedule.

In $\sigma$, let $J_k$ be the first job that assumes the objective value $L_{\max }(\sigma )=L_k(\sigma )$. Suppose that $J_k$ belongs to batch $B^l_i$. Since $B^l$ is regular and $p(B^l_i)\le \frac{i}{v} p(B^l)$,

$$\begin{aligned} L_{max}(\sigma )&= S\big (B^l\big )+p\big (B^l_i\big )+q_k\nonumber \\&\le \left( 1+{\frac{1}{u}}\right) r\big (B^l\big )+\frac{1}{u} p\big (B^l\big )+\frac{i}{v} p\big (B^l\big )+q_k \end{aligned}$$

(17)

While in the optimal schedule $\pi$,

$$\begin{aligned}&\displaystyle L_{max}(\pi )\ge r\big (B^l\big )+p_k+q_k\ge r\big (B^l\big )+\frac{i-1}{v} p\big (B^l\big )+q_k\end{aligned}$$

(18)

$$\begin{aligned}&\displaystyle L_{max}(\pi )\ge r\big (B^l\big )+p\big (B^l\big ) \end{aligned}$$

(19)

Thus it is from the inequality (18)+$(\frac{1}{u}+\frac{1}{v})\cdot$(19) and (17) that $L_{max}(\sigma )\le (1+\frac{1}{u}+\frac{1}{v})L_{max}(\pi )$.

Hence, Algorithm $H(u,v)$ is $(1+\frac{1}{u}+\frac{1}{v})$-competitive.

Now, we can present an instance to show that the bound is tight. Let $m=uv\ge 2$, where $u,v$ are integers. Suppose there are two jobs: $J_1(r_1=0,p_1=1,q_1=0),J_2(r_2=0,p_2=1-1/v,q_2=1/v)$. The algorithm will schedule $J_1$ and $J_2$ as a single batch which starts at $1/u$. Thus the object value will be $1+1/u+1/v$. While the optimal schedule will assign $J_1$ and $J_2$ in different batches with starting time 0. Then the optimal value is $1$. Hence the bound is tight.

This completes the proof.$\square$