Semi-online Algorithms for Hierarchical Scheduling on Three Parallel Machines with a Buffer Size of 1

Abstract

In this paper, we study the online problem on three hierarchical machines with a buffer size of 1, and have two hierarchy, the objective is to minimize the maximum machine load. When there is only one low-hierarchy machine, we give a low bound $\frac{3}{2}$ and present an online algorithm with competitive ratio at most $\frac{5}{3}$. When there are two low-hierarchy machines, we give a lower bound $\frac{3}{2}$ and present an online algorithm with competitive ratio at most $\frac{12}{7}$.

1 Introduction

Given m hierarchical machines and n independent jobs, each job can be processed on some machines and each job only be processed by a machine. The hierarchical scheduling problem, with the objective is to maximize the minimum machine load [14, 15].

When the objective is to minimize the makespan, denoted by $P|GoS|C_{max}$. Hwang et al. [1] investigated the offline problem $P|GoS|C_{max}$ and proposed a $\frac{5}{4}$-competitive algorithm for $m = 2$; also designed a $2-\frac{1}{m-1}$-competitive algorithm for $m\ge 3$. Then, Ou et al. [2] designed a $\frac{4}{3}$-competitive algorithm and obtain a polynomial time approximation scheme (PTAS, for short) for $P|GoS|C_{max}$. For a special case of the problem $P|GoS|C_{max}$, Li et al. [3] presented an efficient polynomial time approximation scheme (EPTAS, for short) with running time O(nlogn); for the problem $Pm|GoS|C_{max}$, and m is a constant, they also designed a fully polynomial time approximation scheme (FPTAS, for short) with running time O(n).

Online scheduling over list is a scheduling that jobs arrive one by one, any new incoming job will be scheduled only according to the information of arrived jobs. An online algorithm’s performance is measured by the competitive ratio. For any given instance I, let $C_A(I)$ ($C_A$, for short) be the objective value of algorithm A, for a minimization scheduling problem and a corresponding online algorithm A, the competitive ratio of the online algorithm A is defined as $\rho =\sup _I \frac{C_{A}(I)}{C_{OPT}(I)}$, i.e., $\rho C_{OPT}(I)\ge C_{A}(I)$ for any instance I, where $C_{OPT}(I)$ ($C_{OPT}$, for short) is the optimal offline objective value of the instance I. For the problem, if there is no online algorithm make the competitive ratio less than $\rho$, the $\rho$ is called a lower bound of this problem. If an online algorithm has a lower bound equal to its competitive ratio, it is called an optimal online algorithm.

For the online problem, Park et al. [4] and Jiang et al. [5] presented an optimal online algorithm for two hierarchical machines with competitive ratio of $\frac{5}{3}$ respectively. Lim et al. [6] presented an optimal online algorithm with a competitive ratio of 2 on three hierarchical machines. Wu et al. [7] designed some optimal semi-online scheduling algorithms for two hierarchical machines. Zhang et al. [8] first designed an online algorithm with a competitive ratio of $1+\frac{m^2-m}{m^2-km+k^2}<\frac{7}{3}$ for any k and m, the k is the number of high-hierarchy machine, and got a competitive ratio of 1.857 for $m=3$. For jobs have tightly-grouped processing time, Zhang et al. [9] designed some optimal online algorithms on the two hierarchical machines.

For the online problem $Pm|buffer|C_{max}$, Englert et al. [10] gave a lower bound of $\frac{3}{2}$ with a buffer size of $\lfloor \frac{m}{2}\rfloor -1$, Lan et al. [11] gave a 1.5-competitive online algorithm with a buffer size of 1.5m. When $m=2$, Zhang [12] presented an optimal online algorithm with competitive ratio of $\frac{4}{3}$ and the buffer size of 1. For the online problem $P2|GoS,buffer|C_{max}$, Chen et al. [13] designed an optimal online algorithm with competitive ratio of $\frac{3}{2}$ and the buffer size of 1.

In this paper, we consider the online problem on three hierarchical machines with a buffer size of 1. There are two cases for this problem, when there is one machine of hierarchy 1 and two machines of hierarchy 2, we denote it as $P3(1,2,2)|buffer|C_{max}$. When there are two machines of hierarchy 1 and one machine of hierarchy 2, we denote it as $P3(1,1,2)|buffer|C_{max}$. Results of lower bound and the competitive ratio of buffer size of 0 and 1 can be found in Table 1. The rest of the paper is organized as follows. In Sect. 2, we define some basic notations. In Sect. 3, we consider the $P3(1,2,2)|buffer|C_{max}$, we give a lower bound $\frac{3}{2}$ and propose an online algorithm of competitive ratio at most $\frac{5}{3}$. In Sect. 4, we consider the $P3(1,1,2)|buffer|C_{max}$, we give a lower bound $\frac{3}{2}$ and propose an online algorithm of competitive ratio at most $\frac{12}{7}$. Finally, we make a summary.

Table 1. Buffer size of 0 and 1

2 Preliminaries

We are given three identical parallel machines $M_1$, $M_2$, $M_3$ and a job set $J=\{J_{1},J_{2},\ldots ,J_{n}\}$. All jobs arrive online and all be scheduled irrevocably in their order of arrival. A new job arrives only after the current job is scheduled. We denote the j-th job in the arrival list as $J_{j}=(p_{j},g_{j})$, $p_{j}>0$ is the processing time(also called the job’s size) of the job $J_{j}$, and $g_{j}\in \{1,2\}$ is the hierarchy of the job $J_{j}$. Each machine $M_k$ has a hierarchy $g(M_k)$ and $g(M_k)\in \{1,2\}$, $k\in {\{1,2,3}\}$. For any job $J_j$, only can be processed by the machines which the hierarchy no more than it. $p_{j}$ and $g_{j}$ are not known until the job $J_{j}$ arrives. If $g_j=i$, job $J_j$ is called the job of hierarchy i, $i\in {\{1,2}\}$.

A schedule can be regard as a partition $(S_1,S_2,S_3)$ of J, where $S_{k}$ ($k=1,2,3$) contains the all jobs assigned to $M_k$. Let $L_{k}=\sum _{J_{j}\in S_{k}} p_{j}$ be the load of $M_k$, and $T_i$ be the total processing time of the jobs of hierarchy i, $i=1,2$. Our goal is to find a schedule such that $\max \{L_{1},L_{2},L_{3}\}$ is minimized.

For each $j\in {\{1,2,\ldots ,n}\}$, $k\in {\{1,2,3}\}$ and $i\in {\{1,2}\}$, we define the following notions.

$T^{j}_i$: the total processing time of the first j jobs of hierarchy i.

$L^j_{k}$: the total processing time of the first j jobs scheduled on machine $M_k$ after assigning job $J_j$.

$p^j_{max}$: the maximum processing time of the first j jobs of hierarchy 1.

$q^j_{max}$: the maximum processing time of the first j jobs of hierarchy 2.

$B^j$: the job in the buffer after scheduling the first j jobs.

For convince, we also let $L^n_{k}=L_{k}$, $T^n_{i}=T_{i}$, $p^n_{max}=p_{max}$ and $q^n_{max}=q_{max}$.

3 One Machine with Hierarchy 1

In this section, we consider the hierarchy of machine $M_1$ is 1, the hierarchy of machine $M_2$, $M_3$ is 2, and a buffer is available for storing at most one job. When a new job arrives, we have to assign it on a machine irrecoverably, or temporarily store it in the buffer. We give a lower bound $\frac{3}{2}$ and design an online algorithm with the competitive ratio at most $\frac{5}{3}$. In this section, for $j=1,2,\ldots ,n$, we let

$$\begin{aligned} LB^ j=\max {\{T^j_1,q^j_{max},\frac{T^j_1+T^j_2}{3}}\}. \end{aligned}$$

(1)

Lemma 1

For the online problem $P3(1,2,2)|buffer|C_{max}$, the optimal makespan is at least $LB^j$ after scheduled the first j jobs.

Proof

Let $C_{OPT}^j$ be the optimal makespan after scheduled the first j jobs. For the online problem $P3(1,2,2)|buffer|C_{max}$, after the job $J_j$ be scheduled, it is clearly that the $C^j_{OPT}\ge {\max {\{\frac{T^j_1+T^j_2}{3},q^j_{max}}\}}$. Note that all jobs with hierarchy 1 only be processed on machine $M_1$, which implies $C^j_{OPT}\ge {T^j_1}$. So, the lemma holds.

Lemma 1 implies

$$\begin{aligned} C_{OPT}\ge {\max {\{T_1,q_{max},\frac{T_1+T_2}{3}}\}}. \end{aligned}$$

(2)

Theorem 2

Any online algorithm A for $P3(1,2,2)|buffer|C_{max}$ has a competitive ratio at least $\frac{3}{2}$.

Proof

For any online algorithm A, the first two jobs in the sequence are $J_1=(1, 2)$ and $J_2=(1, 2)$, where the first number in brackets is the size and the second number is the hierarchy. We first consider algorithm A schedules the first two jobs to the machines. If A assigns both of them to the same machine, the last job $J_3=(1,1)$ arrives, it’s implies $C_A\ge 2$, $C_{OPT}=1$. Else, the first two jobs are assigned to different machines, then, the last two jobs $J_3=(2,1)$ and $J_4=(2,2)$ arrive, then $C_{A}\ge 3$ and $C_{OPT}=2$.

Next, we consider algorithm A stores a job in the buffer, without loss of generality, we consider A stores $J_1=(1, 2)$ into the buffer and assigns $J_2=(1, 2)$ to someone machine. If A assigns $J_2=(1, 2)$ to $M_1$, the last job is $J_3=(1,1)$, then $C_{A}\ge 2$ and $C_{OPT}=1$. If A not assigns $J_2=(1, 2)$ to $M_1$, the next job is $J_3=(2,2)$, and we distinguish three cases for the storage of the buffer.

Case 1. $B^3=\phi$, which means that A assigns first three jobs to the machines.

Case 1.1. A assigns $J_1=(1,2)$ and $J_3=(2,2)$ to the same machine.

The sequence stops, then $C_{A}\ge 3$ and $C_{OPT}=2$.

Case 1.2. A does’t assign $J_1=(1,2)$ and $J_3=(2,2)$ to the same machine.

If A assigns $J_3=(2,2)$ to $M_1$, the last job is $J_4=(2,1)$, then $C_{A}\ge 4$ and $C_{OPT}=2$. If A assigns $J_3=(2,2)$ to the machine which $J_2=(1,2)$ is assigned in $M_2$ and $M_3$, the sequence stops, then $C_{A}\ge 3$ and $C_{OPT}=2$. If A assigns $J_3=(2,2)$ to the machine that is not assigned $J_2=(1,2)$ in $M_2$ and $M_3$, and assigns $J_1=(1,2)$ to $M_1$, the last job is $J_4=(2,1)$, then $C_{A}\ge 3$ and $C_{OPT}=2$. If A assigns $J_3=(2,2)$ to the machine that is not assigned $J_2=(1,2)$ in $M_2$ and $M_3$, and assigns $J_1=(1,2)$ to the machine which $J_2=(1,2)$ is assigned in $M_2$ and $M_3$, the last two jobs are $J_4=(4,2)$ and $J_5=(4,2)$, then $C_{A}\ge 6$ and $C_{OPT}=4$, implies $\frac{C_A}{C_{OPT}}\ge {\frac{3}{2}}$.

Case 2. $B^3=J_3=(2,2)$, and A assigns $J_1=(1,2)$ to someone machine.

Case 2.1. A assigns the $J_1=(1,2)$ to $M_1$.

The last job is $J_4=(2,1)$, then $C_{A}\ge 3$ and $C_{OPT}=2$.

Case 2.2. A assigns $J_1=(1,2)$ to the machine that is not assigned $J_2=(1,2)$ in $M_2$ and $M_3$.

The last job is $J_4=(2,2)$, then $C_{A}\ge 3$ and $C_{OPT}=2$.

Case 2.3. A assigns $J_1=(1,2)$ to the machine which $J_2=(1,2)$ is assigned in $M_2$ and $M_3$.

Next job is $J_4=(2,2)$, then one of $J_3=(2,2)$ and $J_4=(2,2)$ must be assigned, without loss of generality, we assume that $J_4=(2,2)$ be assigned. If A assigns $J_4=(2,2)$ to $M_1$, the last job is $J_5=(3,1)$ and the sequence stops, then $C_{A}\ge 5$ and $C_{OPT}=3$. If A assigns $J_4=(2,2)$ to the machine that is not assigned $J_1=(1,2)$ and $J_2=(1,2)$ in $M_2$ and $M_3$, the last two jobs are $J_5=(2,1)$ and $J_6=(4,2)$, then $C_{A}\ge 6$ and $C_{OPT}=4$. If A assigns $J_4=(2,2)$ to the machine which $J_1=(1,2)$ and $J_2=(1,2)$ is assigned in $M_2$ and $M_3$, the sequence stops, then $C_{A}\ge 4$ and $C_{OPT}=2$.

Case 3. $B^3=J_1=(1,2)$, and assigns $J_3=(2,2)$ to someone machine.

Case 3.1. A assigns $J_3=(2,2)$ to $M_1$.

The last job $J_4=(2,1)$ arrives, then $C_{A}\ge 4$ and $C_{OPT}=2$.

Case 3.2. A assigns $J_3=(2,2)$ to the machine which $J_2=(1,2)$ is assigned in $M_2$ and $M_3$.

The sequence stops, then $C_{A}\ge 3$ and $C_{OPT}=2$.

Case 3.3. A assigns $J_3=(2,2)$ to the machine that is not assigned $J_2=(1,2)$ in $M_2$ and $M_3$. The next job $J_4=(2,2)$ arrives.

Case 3.3.1. $B^4=\phi$, which means that A schedules first four jobs to the machines.

If A assigns $J_4=(2,2)$ to $M_1$, and assigns $J_1=(1,2)$ to the machine which $J_2=(1,2)$ is assigned in $M_2$ and $M_3$. The last job is $J_5=(3,1)$, then $C_{A}\ge 5$ and $C_{OPT}=3$. Otherwise, the sequence stops, then $C_{A}\ge 3$ and $C_{OPT}=2$.

Case 3.3.2. $B^4=J_1=(1,2)$, and A assigns $J_4=(2,2)$ to someone machine.

If A assigns $J_4=(2,2)$ to $M_1$, the last job $J_5=(3,1)$ arrives, then $C_{A}\ge 5$ and $C_{OPT}=3$. If A not assigns $J_4=(2,2)$ to $M_1$, the sequence stops, then $C_{A}\ge 3$ and $C_{OPT}=2$.

Case 3.3.3. $B^4=J_4=(2,2)$, and A assigns $J_1=(1,2)$ to someone machine.

If A assigns $J_1=(1,2)$ to $M_1$, the sequence stops, then $C_{A}\ge 3$ and $C_{OPT}=2$. If A assigns $J_1=(1,2)$ to the machine which $J_2=(1,2)$ is assigned in $M_2$ and $M_3$, the last two jobs $J_5=(2,1)$ and $J_6=(4,2)$ arrive, then $C_{A}\ge 6$ and $C_{OPT}=4$. If A assigns $J_1=(1,2)$ to the machine which $J_3=(2,2)$ is assigned in $M_2$ and $M_3$, the sequence stops, then $C_{A}\ge 3$ and $C_{OPT}=2$.

Our algorithm is a modified version of the algorithm proposed in [13].

Theorem 3

Algorithm $H_1$ for $P3(1,2,2)|buffer|C_{max}$ has a competitive ratio at most $\frac{5}{3}$.

Proof

Proof by contradiction, we assume this theorem does not hold, then, we consider three cases according to which machine $B^n$ is assigned to. Remember also using $B^n$ to denote its size and $B^n=q_{max}$.

First, by algorithm $H_1$, we can get $L^{n-1}_2\le {\frac{5}{3}LB^n}$ and $L^{n-1}_3\le {\frac{5}{3}LB^n}$.

Case 1. $B^n$ is assigned to $M_1$.

This means $L^{n-1}_1\le \min {\{L^{n-1}_2,L^{n-1}_3}\}$ and $L_1=L^{n-1}_1+q_{max}$, $L_2=L^{n-1}_2$, $L_3=L^{n-1}_3$. By the assumption of this theorem does not hold, we have $L^{n-1}_1+q_{max}>\frac{5}{3}LB^n$. Since $q_{max}\le {LB^n}$, we have $L^{n-1}_1>\frac{2}{3}LB^n$. By the definition of $LB^n$, we have $T^n=L^{n-1}_1+L^{n-1}_2+L^{n-1}_3+q_{max}\le {3LB^n}$, so $L^{n-1}_2+L^{n-1}_3<\frac{4}{3}LB^n$, implies $\min {\{L^{n-1}_2,L^{n-1}_3}\}<\frac{2}{3}LB^n$. Then $L^{n-1}_1>\frac{2}{3}LB^n>\min {\{L^{n-1}_2,L^{n-1}_3}\}$, which contradicts with $L^{n-1}_1\le \min {\{L^{n-1}_2,L^{n-1}_3}\}$.

Case 2. $B^n$ is assigned to $M_2$. This means $L^{n-1}_2\le {\min {\{L^{n-1}_1,L^{n-1}_3}\}}$ and $L_1=L^{n-1}_1$, $L_2=L^{n-1}_2+q_{max}$, $L_3=L^{n-1}_3$.

Case 2.1. $L_2\ge {\max {\{L_1,L_3}\}}$. If $L_2=L^{n-1}_2+q_{max}>\frac{5}{3}LB^n$, since $q_{max}\le {LB^n}$, we have $L^{n-1}_2>\frac{2}{3}LB^n$. Then by $T=T^n=L^{n-1}_1+L^{n-1}_2+L^{n-1}_3+q_{max}\le {3LB^n}=3LB$, so $L^{n-1}_1+L^{n-1}_3<\frac{4}{3}LB^n$, implying that $\min {\{L^{n-1}_1,L^{n-1}_3}\}<\frac{2}{3}LB^n$, which contradicts with $L^{n-1}_2>\frac{2}{3}LB^n$ and $L^{n-1}_2\le {\min {\{L^{n-1}_1,L^{n-1}_3}\}}$.

Case 2.2. $L_1\ge {\max {\{L_2,L_3}\}}$.

If $L_1>\frac{5}{3}LB^n$, since $T_1=T^{n}_1\le {LB^n}$, there must exist at least one job with $g_j=2$ scheduled on $M_1$. Let job $J_t$ be the last job of hierarchy 2 scheduled on $M_1$. Let $T^{'}_1$ be the total size of the jobs on $M_1$ after assigned job $J_t$, and the hierarchy of these jobs is 1. When job $J_t$ is assigned on $M_1$, by algorithm $H_1$, we have $L^{t-1}_2+p_t>\frac{5}{3}LB^t$ and $L^{t-1}_3+p_t>\frac{5}{3}LB^t$, implies $L^{t-1}_2>\frac{2}{3}LB^t$ and $L^{t-1}_3>\frac{2}{3}LB^t$. Since $T^t=L^{t-1}_1+L^{t-1}_2+L^{t-1}_3+p_t+q^t_{max}\le {3LB^t}$, so $L^{t-1}_1+q^t_{max}<\frac{2}{3}LB^t$, implies $L^{t-1}_1+p_t<\frac{2}{3}LB^t\le {\frac{2}{3}LB^n}$. Since $L_1=L^n_1=L^{t-1}_1+p_t+T^{'}_1>\frac{5}{3}LB^n$ and $T^{'}_1\le {T_1}\le {LB^n}$, we have $L^{t-1}_1+p_t>\frac{2}{3}LB^n$, which cause a contradiction with the $L^{t-1}_1+p_t<\frac{2}{3}LB^n$.

Case 3. $B^n$ is assigned to $M_3$. This case is similar as the Case 2.

Thus, this theorem holds, we get $\frac{C_{H_1}}{C_{OPT}}\le {\frac{5}{3}}$.

4 Two Machines with Hierarchy 1

In this section, we consider the hierarchy of machine $M_1$ and $M_2$ is 1, the hierarchy of machine $M_3$ is 2, and a buffer can temporarily store at most one job. When a new job arrives, we have to assign it on a machine irrecoverably; or temporarily store it in the buffer. We give a lower bound $\frac{3}{2}$ and design an online algorithm with the competitive ratio at most $\frac{12}{7}$. In this section, we let

$$\begin{aligned} LB^j=\max {\{\frac{T^j_1}{2},p^j_{max},q^j_{max},\frac{T^j_1+T^j_2}{3}}\}, \end{aligned}$$

(3)

clearly, $LB=LB^n$.

Lemma 4

For the online problem $P3(1,1,2)|buffer|C_{max}$, the optimal maximum machine load is at least $LB^j$ after scheduled the job $J_j$ for $j=1,2, \ldots ,n$.

Proof

We denote the optimal maximum machine load after scheduled $J_j$ as $C_{OPT}^j$. For the online problem $P3(1,1,2)|buffer|C_{max}$, after the job $J_j$ be scheduled, it is clearly that the $C_{OPT}^j\ge {\max {\{\frac{T^j_1+T^j_2}{3},p^j_{max},q^j_{max}}\}}$. Note that all jobs with hierarchy 1 can be processed on machine $M_1$ and $M_2$, which implies $C_{OPT}^j\ge {\frac{T^j_1}{2}}$. So, the lemma holds.

Lemma 4 implies

$$\begin{aligned} C_{OPT}\ge LB={\max {\{\frac{T_1}{2},p_{max},q_{max},\frac{T_1+T_2}{3}}\}}. \end{aligned}$$

(4)

Theorem 5

Any online algorithm A for $P3(1,1,2)|buffer|C_{max}$ has a competitive ratio at least $\frac{3}{2}$.

Proof

For any algorithm A, the first three jobs in the sequence are $J_1=(1,2)$, $J_2=(1,1)$ and $J_3=(1,1)$.

Case 1. $B^3=\phi$, that means A assigns first three jobs to the machines.

If A assigns at least two jobs to $M_1$ or $M_2$, the sequence stops, we have $C_A\ge {2}$, $C_{OPT}=1$. Else, the last job $J_4=(2,1)$ arrives, then $C_A=3$, $C_{OPT}=2$, implies $\frac{C_A}{C_{OPT}}\ge {\frac{3}{2}}$.

Case 2. $B^3=J_1=(1,2)$.

If A assigns $J_2=(1,1)$ and $J_3=(1,1)$ to $M_1$ or $M_2$, the sequence stops, then $C_A\ge {2}$, $C_{OPT}=1$. If A assigns $J_2=(1,1)$ and $J_3=(1,1)$ to $M_1$ and $M_2$ respectively, the last job $J_4=(2,1)$ arrives, then $C_A\ge {3}$, $C_{OPT}=2$.

Case 3. $B^3=J_2=(1,1)$ ($B^3=J_3=(1,1)$ that is same as $B^3=J_2=(1,1)$).

Case 3.1. A assigns $J_3=(1,1)$ and $J_1=(1,2)$ to $M_1$ and $M_2$. The sequence stops, we have $C_A\ge {2}$, $C_{OPT}=1$.

Case 3.2. A assigns $J_3=(1,1)$ to $M_1$ or $M_2$ and assigns $J_1=(1,2)$ to $M_3$. Next job $J_4=(2,2)$ arrives.

Case 3.2.1. $B^4=\phi$.

If A assigns the $J_4=(2,2)$ and at least one another job to the same machine, the sequence stops, we have $C_A\ge {3}$, $C_{OPT}=2$. Else, the last job is $J_5=(1,1)$, we have $C_A=3$, $C_{OPT}=2$.

Case 3.2.2. $B^4=J_2=(1,1)$.

If A assigns $J_4=(2,2)$ to machine that is assigned one job, sequence stops, we have $C_A\ge {3}$, $C_{OPT}=2$. If A assigns job $J_4=(2,2)$ to the machine that is not assigned a job, the last job $J_5=(1,1)$ arrives, then $C_A\ge {3}$, $C_{OPT}=2$.

Case 3.2.3. $B^4=J_4=(2,2)$.

If A assigns $J_2=(1,1)$ to $M_1$ and $M_2$ that is not assigned job $J_3=(1,1)$, the sequence stops, we have $C_A=3$, $C_{OPT}=2$. If A assigns the $J_2=(1,1)$ to the machine which $J_3=(1,1)$ is assigned in $M_1$ and $M_2$, the last job $J_5=(1,1)$ arrives, then $C_A\ge {3}$, $C_{OPT}=2$.

The main ideal of algorithm $H_2$ is to schedule as many jobs with hierarchy 2 as possible to $M_3$, the details of algorithm $H_2$ are as follows.

Theorem 6

The competitive ratio of Algorithm $H_2$ for $P3(1,1,2)|buffer|C_{max}$ at most $\frac{12}{7}$.

Proof

Consider three cases according to which machine $B^n$ is assigned to. We denote the total processing time of the jobs of hierarchy 2 that assigned to $M_i$ as $L_i(2)$, for $i=1,2$, and remember $B^n=q_{max}$.

Case 1. $B^n$ is assigned to $M_3$.

Case 1.1. $L_3>\max {\{L_1,L_2}\}$, this means $L^{n-1}_3\le \min {\{L^{n-1}_1,L^{n-1}_2}\}$ and $L_1=L^{n-1}_1$, $L_2=L^{n-1}_2$, $L_3=L^{n-1}_3+q_{max}$. Since $L^{n-1}_3\le \min {\{L^{n-1}_1,L^{n-1}_2}\}$, we have

$$\begin{aligned} C_{H_2}=L_3=L^{n-1}_3+q_{max}\le {\frac{T_1+T_2-q_{max}}{3}+q_{max}}=\frac{T_1+T_2}{3}+\frac{2}{3}q_{max}. \end{aligned}$$

Following (4), we have

$$\begin{aligned} C_{OPT}\ge {\max {\{\frac{T_1}{2},p_{max},q_{max},\frac{T_1+T_2}{3}}\}}. \end{aligned}$$

So the competitive ratio $\frac{C_{H_2}}{C_{OPT}}\le {\frac{5}{3}}$.

Case 1.2. $L_3\le \max {\{L_1,L_2}\}$.

If no jobs of hierarchy 2 be assigned to $M_1$ and $M_2$, then $L_3=L^{n-1}_3+q_{max}=T_2$. By algorithm $H_2$, in this situation, the load between the $M_1$ and $M_2$ not exceed $p_{max}$, so

$$\begin{aligned} C_{H_2}=\max {\{L_1,L_2}\}\le {\frac{T_1-p_{max}}{2}+p_{max}}=\frac{T_1}{2}+\frac{p_{max}}{2}. \end{aligned}$$

We get $\frac{C_{H_2}}{C_{OPT}}\le {\frac{3}{2}}$.

Else, we let the last job of hierarchy 2 that be assigned to $M_1$ and $M_2$ is $J_t$, by algorithm $H_2$, we have $L^{t-1}_3+q^t_{max}\ge L^{t-1}_3+p_t>\frac{4}{7}T^t_2$. If there exist jobs of hierarchy 2 after $J_t$, them will all be assigned to $M_3$. Hence, $L_3>\frac{4}{7}T_2$, implies $L_1(2)+L_2(2)<\frac{3}{7}T_2$. By algorithm $H_2$, in any time, we know the load between the $M_1$ and $M_2$ not exceed $\max {\{p_{max},q_{max}}\}$, so

$$\begin{aligned} C_{H_2}=\max {\{L_1,L_2}\}\le & {} {\frac{3T_2/7+T_1-\max {\{p_{max},q_{max}}\}}{2}}+\max {\{p_{max},q_{max}}\}\\= & {} \frac{3}{14}(T_1+T_2)+\frac{2}{7}T_1+\frac{\max {\{p_{max},q_{max}}\}}{2}. \end{aligned}$$

Following (4), we know $C_{OPT}\ge {\max {\{T_1/2,p_{max},q_{max},(T_1+T_2)/3}\}}$, then, we get $\frac{C_{H_2}}{C_{OPT}}\le {\frac{12}{7}}$.

Case 2. $B^n$ is assigned to $M_1$. This means $L^{n-1}_1\le \min {\{L^{n-1}_2,L^{n-1}_3}\}$ and $L_1=L^{n-1}_1+q_{max}$, $L_2=L^{n-1}_2$, $L_3=L^{n-1}_3$.

Case 2.1. $L_1\ge {\max {\{L_2,L_3}}\}$. Since $L^{n-1}_1\le \min {\{L^{n-1}_2,L^{n-1}_3}\}$, by algorithm $H_2$, we get

$$\begin{aligned} C_{H_2}=L_1\le {\frac{T_1+T_2-q_{max}}{3}+q_{max}}=\frac{T_1+T_2}{3}+\frac{2}{3}q_{max}, \end{aligned}$$

By (4), implying that $\frac{C_{H_2}}{C_{OPT}}\le {\frac{5}{3}}$.

Case 2.2. $L_1<\max {\{L_2,L_3}\}$. If $L_2<L_3$, by algorithm $H_2$, we know $C_{H_2}=L_3\le {\frac{4}{7}T_2}$, following (4), we get $\frac{C_{H_2}}{C_{OPT}}\le \frac{L_3}{T_2/3}\le {\frac{12}{7}}$. If $L_2\ge {L_3}$, we assume $L_2>\frac{12}{7}LB$, because $B^n$ is assigned to $M_1$ and the load between the $M_1$ and $M_2$ not exceed $\max {\{p_{max},q_{max}}\}$, we have $L_1\ge L_2-\max {\{p_{max},q_{max}}\}$. By algorithm $H_2$, because $B^n$ is not assigned to $M_3$, we get $L_3>L_2-B^n=L_2-q_{max}$. Hence,

$$\begin{aligned} T_1+T_2=L_1+L_2+L_3> & {} 3L_2-\max {\{p_{max},q_{max}}\}-q_{max}\\\ge & {} \frac{36}{7}LB-2LB\\= & {} \frac{22}{7}LB\\> & {} \, T_1+T_2. \end{aligned}$$

Contradiction, so $L_2\le \frac{12}{7}LB$, and $\frac{C_{H_2}}{C_{OPT}}\le \frac{L_2}{LB}\le \frac{12}{7}$.

Case 3. $B^n$ is assigned to $M_2$. This case is similar as the Case 2.

Hence, this theorem holds, obtain $\frac{C_{H_2}}{C_{OPT}}\le {\frac{12}{7}}$.

5 Conclusion

We consider two cases for the online problem $P3|Gos,buffer|C_{max}$, but we can’t get optimal online algorithms. It’s valuable to design their optimal algorithms in future.