Semi-online Machine Covering on Two Hierarchical Machines with Discrete Processing Times

Abstract

In this paper, we study the semi-online machine covering problem on two hierarchical machines, whose objective is to maximize the minimum machine load. When the processing times are discrete by $\{1,2,2^{2},\ldots ,2^{k}\}$ with $k\ge 2$, we prove that no algorithm can have a competitive ratio less than $2^{k}$ and present an optimal semi-online algorithm with competitive ratio $2^{k}$.

1 Introduction

Given m hierarchical machines and n jobs, each job can only be processed on a subset of the machines and each job can only be processed on a machines. The hierarchical scheduling problem, denoted by $P|GoS|C_{max}$, is to minimize the maximum load of all machines (makespan). Hwang et al. [2] studied the offline problem $P|GoS|C_{max}$ and designed an approximation algorithm with the mankspan no more than $\frac{5}{4}$-times the optimum for $m=2$, and no more than $2-\frac{1}{m-1}$-times the optimum for $m\ge 3$. Ou et al. [7] designed a 4/3-approximation algorithm and a polynomial time approximation scheme (PTAS, for short) for $P|GoS|C_{max}$. Li et al. [6] designed an efficient PTAS with running time O(nlogn) for a special case of the problem $P|GoS|C_{max}$ and present a simple fully polynomial time approximation scheme (FPTAS, for short) with running time O(n) for the problem $P_m|GoS|C_{max}$, where m is a constant. For the online version, Park et al. [8] and Jiang et al. [3] designed an optimal online algorithm with a competitive ratio of $\frac{5}{3}$ for the case of two machines, respectively. Wu et al. [10] designed several optimal semi-online scheduling algorithm on two hierarchical machines. Zhang et al. [11] designed some optimal online algorithms on two hierarchical machines with tightly-grouped processing times.

Machine covering on hierarchical machines with the objective of maximizing the minimum machine load, denoted by $P|GoS|C_{min}$, is not a well-studied scheduling problem. Li et al. [4] presented a PTAS for $P|GoS|C_{min}$. Wu et al. [9] designed two semi-online optimal algorithms for $P|GoS|C_{min}$ on two hierarchical machines, when both the processing time and the class of the largest job are known. Luo et al. [5] presented an optimal online algorithm with a competitive ratio of $(1+\alpha )$ for $P|GoS|C_{min}$ on two hierarchical machines, when the processing time of each job is bounded by an interval $[1,\alpha ]$. Chassid and Epstein [1] considered the machine covering problem on two hierarchical machines of possibly different speeds.

In this paper, we consider the online machine covering problem on two hierarchical machines with discrete processing times. The processing time of all jobs are discrete by $\{1,2,2^{2},\ldots ,2^{k}\}$, where $k\ge 2$. We prove that no algorithm can have a competitive ratio less than $2^{k}$ and give an optimal algorithm with the competitive ratio of $2^{k}$. The paper is organized as follows. Section 2 gives some basic definitions. Section 3 presents an optimal semi-online algorithm. Section 4 presents concluding remarks.

2 Preliminaries

We are given two machines and a series of jobs arriving online which are to be scheduled irrevocably at the time of their arrivals. The first machine can process all the jobs while the second one can process only part of the jobs. The arrival of a new job occurs only after the current job is scheduled. Let $J=\{J_{1},J_{2},\ldots ,J_{n}\}$ be the set of all jobs arranged in the order of arrival. We denote each job as $J_{i}$ with $p_{i}$ and $g_{i}$, where $p_{i}>0$ is the processing time (also called job size) of the job $J_{i}$ and $g_{i}\in \{1,2\}$ is the hierarchy of the job $J_{i}$. If $g_{i} =1$, the job $J_{i}$ must be processed by the first machine, and if $g_{i}=2$, the job $J_{i}$ can be processed by either of the two machines. $p_{i}$ and $g_{i}$ are not known until the arrival of the job $J_{i}$.

The schedule can be seen as the partition of J into two subsets, we denote as ${<}S_{1},S_{2}{>}$, where $S_{1}$ and $S_{2}$ contain job indices assigned to the first and the second machine, respectively. Let $p(S_{1})=\sum _{J_{i}\in S_{1}} p_{i}$ and $p(S_{2})=\sum _{J_{i}\in S_{2}} p_{i}$ denote the load of the first machine and the second machine, respectively.

For the first i jobs, we define that $T^{i}$ denote total processing time, $TG^{i}_{1}$ is total processing time the jobs with hierarchy 1; $p_{max} ^{i}$ is the largest job time; $p(S_{1} ^{i})$ denote total processing time of the jobs scheduled on $M_{1}$ after the job $J_{i}$ is scheduled; $p(S_{2} ^{i})$ is total processing time of the jobs scheduled on $M_{2}$ after the job $J_{i}$ is scheduled; $V_{i} (opt)$ denote the optimal minimum machine load after scheduling the job $J_{i}$; $V_{opt}$ is the optimal function value of the problem in an offline version; $V_{out}$ denote the output objective function value by a algorithm.

So, according to the define of above, we have $S_{1}=S_{1} ^{n}$ and $S_{2}=S_{2} ^{n}$. The minimum value of $p(S_{1})$ and $p(S_{2})$, i.e., $min\{p(S_{1}), p(S_{2})\}$, is defined as the minimum machine load of the schedule ${<}S_{1},S_{2}{>}$. The objective is to find a schedule ${<}S_{1},S_{2}{>}$ that maximizes the minimum machine load.

For the first i jobs, let $L^{i}=min\{T^{i}-TG^{i}_{1}, \frac{T^{i}}{2}, T^{i}-p^{i}_{max}\}$ and $L^{i}$ is a standard upper bound of the optimal minimum machine load. Then we can get following lemma.

Lemma 1

The optimal minimum machine load is at most $L^{i}$ after scheduling the job $J_{i}$.

Definition 1

For a job sequence J and an algorithm, then the competitive ratio of algorithm is defined as the smallest $\eta$ such that for any J, $V_{opt}\le \eta V_{out}$.

At first, we give a lower bounded for the problem.

Theorem 1

There exists no algorithm with a competitive ratio less than $2^{k}$.

Proof:

Consider an algorithm B and the following job sequence. The first job $J_{1}$ with $p_{1}=1$ and $g_{1}=2$. If algorithm B schedules $J_{1}$ on $M_{1}$, we further generate the last job $J_{2}$ with $p_{2}=2^{k}$ and $g_{2}=1$ must be scheduled on $M_{1}$. Therefore, we have $V_{opt}=1$ and $V_{out}=0$, which lead to the competitive ratio is unbounded.

Otherwise, if algorithm B schedules $J_{1}$ with $p_{1}=1$ and $g_{1}=2$ on $M_{2}$. The job $J_{2}$ with $p_{2}=2^{k}$ and $g_{2}=2$, the algorithm B must schedule $J_{2}$ with $p_{2}=2^{k}$ and $g_{2}=2$ on $M_{1}$. If the algorithm B schedule $J_{2}$ with $p_{2}=2^{k}$ and $g_{2}=2$ on $M_{2}$, we have $V_{opt}=1$ and $V_{out}=0$, which lead to the competitive ratio is unbounded. The job $J_{3}$ with $p_{3}=2^{k}$ and $g_{3}=1$ must be scheduled on $M_{1}$. We have $V_{opt}=2^{k}$ and $V_{out}=1$. Hence, there exists no algorithm with a competitive ratio less than $2^{k}$.

3 An Optimal Semi-online Algorithm

In the section, we consider that the hierarchical load balancing problem on two machines with discrete processing times. All processing times belong to $\{1,2,2^{2},\ldots ,2^{k}\}$, where $k\ge 2$ in this problem. We present an optimal algorithm.

For the problem and the algorithm, we define that $V_{out}= min\{p(S_{1}^{n}),p(S_{2} ^{n})\}$ is the output of the Algorithm A and $V_{opt}$ is the output of the optimal offline algorithm.

Lemma 2

If Algorithm A schedule the job $J_{i}$ with $g_{i}=2$ on $M_{1}$, then $L^{i}\ne T^{i}-TG^{i}_{1}$.

Proof:

According to Algorithm A, if the job $J_{i}$ with $g_{i}=2$ is scheduled on $M_{1}$, we have $p(S_{1} ^{i-1})<\frac{1}{2^{k}} L^{i}.$

If $L^{i}=min\{T^{i}-TG^{i}_{1},\frac{T^{i}}{2},T^{i}-p_{max} ^{i}\}=T^{i}-TG^{i}_{1}$, then we get $T^{i}-TG^{i}_{1}\le \frac{T^{i}}{2},$ which implies $TG^{i}_{1}\ge \frac{T^{i}}{2}$. Since $p(S_{1} ^{i-1})\ge TG^{i-1}_{1}=TG^{i}_{1}$, then we have

$$\begin{aligned} p(S_{1} ^{i-1})\ge \frac{T^{i}}{2}\ge L^{i}>\frac{L^{i}}{2^{k}} \end{aligned}$$

and it is contradictory with $p(S_{1} ^{i-1})<\frac{L^{i}}{2^{k}}$. Thus, the proof is complete.

Lemma 3

If Algorithm A schedule the job $J_{i}$ with $g_{i}=2$ on $M_{1}$ and $L^{i}=T^{i}-p_{max} ^{i}$, then $p(S_{2} ^{i})\ge \frac{1}{2^{k}}(T^{i}-TG^{i}_{1})$.

Proof:

Since $L^{i}=T^{i}-p_{max} ^{i}$, according to the definition of $L^{i}$, we get $T^{i}-p_{max} ^{i}\le \frac{T^{i}}{2},$ which means

$$\begin{aligned} p_{max} ^{i}\ge \frac{T^{i}}{2}. \end{aligned}$$

In the first i jobs, we denote job $J_{j}$ where $j \in \{1,2,3\cdots i\}$ has largest processing time, i.e., $p_{j}=p^{i}_{max}.$ Now, we will discuss two cases:

Case 1. $p_{max}^{i}\ne p_{i}.$

If $J_{j}$ belongs to $S_{1} ^{i-1}$, we have

$$\begin{aligned} p(S_{1} ^{i-1})\ge p_{max} ^{i}\ge \frac{T^{i}}{2}>\frac{1}{2^{k}}L^{i} \end{aligned}$$

and this is contradictory with that Algorithm A schedule the job $J_{i}$ on $M_{1}$.

If $J_{j}$ belongs to $S_{2} ^{i}$, we have

$$\begin{aligned} p(S_{2} ^{i})\ge p_{max} ^{i}\ge \frac{T^{i}}{2}\ge \frac{1}{2^{k}}T^{i}\ge \frac{1}{2^{k}}(T^{i}-TG^{i}_{1}). \end{aligned}$$

(1)

Case 2. $p_{max} ^{i}=p_{i}.$

We have

$$\begin{aligned} T^{i}-p_{max} ^{i}=p(S_{2} ^{i})+p(S_{1} ^{i-1}). \end{aligned}$$

(2)

Since Algorithm A schedule the job $J_{i}$ on $M_{1}$, we have

$$\begin{aligned} p(S_{1} ^{i-1})<\frac{1}{2^{k}}L^{i}=\frac{1}{2^{k}}(T^{i}-p_{max} ^{i}). \end{aligned}$$

(3)

Hence, according to the inequalities of (2), (3), we have

$$\begin{aligned} p(S_{2} ^{i})=T^{i}-p_{max} ^{i}-p(S_{1} ^{i-1}) >T^{i}-p_{max} ^{i}-\frac{1}{2^{k}}(T^{i}-p_{max} ^{i}) =\frac{2^{k}-1}{2^{k}}(T^{i}-p_{max} ^{i}). \end{aligned}$$

Since $k\ge 2$ and according to the inequalities of (3), we have

$$\begin{aligned} p(S_{2} ^{i})>\frac{2^{k}-1}{2^{k}}(T^{i}-p_{max} ^{i})>(2^{k}-1)p(S_{1} ^{i-1})\ge 3p(S_{1} ^{i-1}). \end{aligned}$$

(4)

Since $p(S_{1}^{i-1})\ge 1$, we have $p(S_{2} ^{i})>3$. Since $p_{i}=p^{i}_{max}\ge \frac{T^{i}}{2}>p(S_{1} ^{i-1})$ and $p_{i}\le 2^{k},$ we have

$$\begin{aligned} \frac{T^{i}-TG^{i}_{1}}{p(S_{2} ^{i})}\le \frac{T^{i}}{p(S_{2} ^{i})}=1+\frac{p(S_{1} ^{i-1})+p_{i}}{p(S_{2} ^{i})}<1+\frac{2^{k+1}}{3}<2^{k}. \end{aligned}$$

(5)

The proof is complete.

Lemma 4

If Algorithm A schedule the job $J_{i}$ with $g_{i}=2$ on $M_{1}$ and $L^{i}=\frac{T^{i}}{2}$, then $p(S_{2} ^{i} )\ge \frac{T^{i}-TG^{i}_{1}}{2^{k}}$.

Proof:

Since the job $J_{i}$ with $g_{i}=2$ is scheduled on $M_{1}$, we have $p(S_{1} ^{i-1})< \frac{L^{i}}{2^{k}}=\frac{T^{i}}{2\times 2^{k}}.$ Since

$$\begin{aligned} L^{i}=min\{T^{i}-TG^{i}_{1},\frac{T^{i}}{2},T^{i}-p_{max} ^{i}\}=\frac{T^{i}}{2}. \end{aligned}$$

So, we have $T^{i}-p_{max} ^{i}\ge \frac{T^{i}}{2}$ holds, which implies $p_{max} ^{i}\le \frac{T^{i}}{2}.$ Then, we have $p_{i}\le p_{max} ^{i}\le \frac{T^{i}}{2}$ and

$$\begin{aligned} p(S_{2} ^{i})=T^{i}-p(S_{1} ^{i-1})-p_{i}>T^{i}-\frac{T^{i}}{2\times 2^{k}}-\frac{T^{i}}{2}=\frac{2^{k}-1}{2\times 2^{k}}T^{i}. \end{aligned}$$

Since $k\ge 2$ and $T^{i}\ge T^{i}-TG^{i}_{1}$, we have

$$\begin{aligned} p(S_{2} ^{i})>\frac{2^{k}-1}{2\times 2^{k}}T^{i}>\frac{T^{i}}{2^{k}}\ge \frac{T^{i}-TG^{i}_{1}}{2^{k}}. \end{aligned}$$

We complete the proof.

Theorem 2

If $V_{out}= min\{p(S_{1}^{n}),p(S_{2} ^{n})\}=p(S_{1} ^{n})$, then $\frac{V_{opt}}{V_{out}}\le 2^{k}$.

Proof:

According to the question, we know that $S_{2}^{n}\ne \emptyset .$

We assume that the job $J_{i}$ is the last job that scheduled on $M_{2}$. According to Algorithm A, we have $p(S_{1} ^{i-1})\ge \frac{1}{2^{k}} L^{i}$. Since

$$\begin{aligned} L^{n}-L^{i} \le T^{n}-T^{i} \end{aligned}$$

(6)

and all the jobs arrived after the job $J_{i}$ will be scheduled on $M_{1}$.

According to the definition of $L^{n}$ and $L^{n}\ge V_{opt},$ we have

$$\begin{aligned} \begin{aligned} \frac{1}{2^{k}}L^{i}+(L^{n}-L^{i})&\ge \frac{1}{2^{k}}(L^{i}-L^{n})+\frac{L^{n}}{2^{k}}+(L^{n}-L^{i})\\&\ge (1-\frac{1}{2^{k}})(L^{n}-L^{i})+\frac{L^{n}}{2^{k}}\\&\ge 0. \end{aligned} \end{aligned}$$

(7)

Then, according to inequality (7), we have

$$\begin{aligned} \frac{1}{2^{k}} L^{i}+(L^{n}-L^{i})\ge \frac{1}{2^{k}}L^{n}. \end{aligned}$$

(8)

So, according to the inequalities of (6), (8), we have

$$\begin{aligned} p(S_{1} ^{n})=p(S_{1} ^{i-1})+(T^{n}-T^{i})\ge \frac{1}{2^{k}} L^{i}+(L^{n}-L^{i})\ge \frac{1}{2^{k}}L^{n}\ge \frac{1}{2^{k}}V_{opt}. \end{aligned}$$

(9)

Thus, according to inequality (9), when $V_{out}= min\{p(S_{1} ^{n}),p(S_{2} ^{n})\}=p(S_{1} ^{n})$, we have

$$\begin{aligned} \frac{V_{opt}}{V_{out}}\le 2^{k}. \end{aligned}$$

We complete the proof.

Theorem 3

The competitive ratio of Algorithm A is $2^{k}$.

Proof:

According to Theorem 2, if $V_{out}= min\{p(S_{1}^{n}),p(S_{2} ^{n})\}=p(S_{1} ^{n}),$ then

$$\begin{aligned} \frac{V_{opt}}{V_{out}}\le 2^{k}. \end{aligned}$$

(10)

Therefore, we only need to prove when $V_{out}= min\{p(S_{1}^{n}),p(S_{2} ^{n})\}=p(S_{2} ^{n})$, the inequality (10) holds.

We discuss the following two cases:

Case 1. Algorithm A doesn’t schedule jobs with hierarchy 2 on $M_{1}$.

In this case, according to the definition of $L^{n}$. We have

$$\begin{aligned} p(S_{2} ^{n})=T^{n}-TG^{n}_{1}\ge L^{n}\ge V_{opt}>\frac{1}{2^{k}}V_{opt}. \end{aligned}$$

(11)

Case 2. At least one job with hierarchy 2 is scheduled on $M_{1}.$

Let $J_{a}$ denote the last job with $g_{a}=2$ that scheduled on $M_{1}$. According to Lemmas 2, 3 and 4, we have

$$\begin{aligned} p(S_{2} ^{a})\ge \frac{1}{2^{k}}(T^{a}-TG^{a}_{1}). \end{aligned}$$

Since remaining the jobs with hierarchy 2 are scheduled on $M_{2}$ after job $J_{a}$ and we have $k\ge 2$ and

$$\begin{aligned} T^{n}-TG^{n}_{1}\ge T^{a}-TG^{a}_{1}, \end{aligned}$$

then we get

$$\begin{aligned} \begin{aligned} p(S_{2} ^{n})&=p(S_{2} ^{a})+((T^{n}-TG^{n}_{1})-(T^{a}-TG^{a}_{1}))\\&\ge \frac{1}{2^{k}}(T^{a}-TG^{a}_{1})+((T^{n}-TG^{n}_{1})-(T^{a}-TG^{a}_{1}))\\&= \frac{1-2^{k}}{2^{k}}(T^{a}-TG^{a}_{1})+(T^{n}-TG^{n}_{1})\\&\ge \frac{1-2^{k}}{2^{k}}(T^{n}-TG^{n}_{1})+(T^{n}-TG^{n}_{1})\\&= \frac{1}{2^{k}}(T^{n}-TG^{n}_{1})\\&\ge \frac{1}{2^{k}}L^{n}\\&\ge \frac{1}{2^{k}}V_{opt}. \end{aligned} \end{aligned}$$

(12)

According to the definition of $V_{out}$ and the inequalities of (11), (12). We have the inequality (10) holds.

According to Theorem 1, the optimal competitive ratio of Algorithm A is $2^{k}$. We complete the proof of competitive ratio.

4 Conclusion

In the paper, we study the semi-online version of hierarchical scheduling problem on two parallel machines with the objective of maximizing the minimum machine load. If the processing times are discrete by $\{1,2,2^{2},\ldots ,2^{k}\}$, where $k\ge 2$. We prove the lower bound of the competitive ratio of any online algorithm is $2^{k}$ and present an algorithm which is shown to be optimal.