LPT Algorithm for Jobs with Similar Sizes on Three Machines

Yajie Ma¹, Rongheng Li¹, Yunxia Zhou²

¹Key Laboratory of Computing and Stochastic Mathematics (Ministry of Education), School of Mathematics and Statistics, Hunan Normal University, Changsha, China.
²College of Information Science and Engineering, Hunan Normal University, Changsha, China.

DOI: 10.4236/am.2019.1011066                

Abstract

In this paper, LPT (largest processing time) algorithm is considered for scheduling jobs with similar sizes on three machines. The objective function is to minimize the maximum completion time of all machines. The worst case performance ratio of the LPT algorithm is given as a piecewise linear function of r if job sizes fall in [1, r]. Our result is better than the existing result. Furthermore, the ratio given here is the best. That means our result cannot be improved any more.

Keywords

LPT Algorithm, Parallel Machine, Performance Ratio, Schedule

1. Introduction

The scheduling problem on m parallel identical machines is defined as follows: Given a job set $L=\left\{J_1,J_2,\cdots ,J_n\right\}$ of n jobs where job $J_j$ has non-negative processing time $p_j$, assign the jobs on m machines $\left\{M_1\mathrm{,}{M}_2\mathrm{,}\cdots \mathrm{,}{M}_m\right\}$ so as to minimize the maximum completion times of the jobs on each machine. Since scheduling problem was proposed by Graham [1], it has been studied extensively in many varieties and from many viewpoints. In classic scheduling problem, there is no constraint on the size of jobs. However, in practice, the size of job can neither be too large nor too small. This motivates researchers to study scheduling problems in which the sizes of all jobs fall in $\left[\mathrm{1,}r\right]$ with $r\ge 1$. Researches of such model can be found in [2] - [9] to name a few.

LPT (Largest Processing Time) algorithm is a famous algorithm proposed by Graham [10]. For a given job list $L=\left\{J_1,J_2,\cdots ,J_n\right\}$ of n jobs, LPT algorithm firstly sorts the jobs with a non-increasing order of their sizes. Then LPT algorithm assigns the jobs one by one according to the non-increasing order and always assigns the current job to the machine with least load. The worst case

performance ratio of LPT is $\frac{4}{3}-\frac{1}{3m}$. H.Kellerer [9] gave the following result.

$\begin{array}{l}R\left(m,LPT,\mu \right)\\ \le (\begin{array}{l}\frac{m\left(2k-2\right)-\mu \left(k-2\right)}{km}\mathrm{<mi>\; </mi>\; <mi>\; </mi>}\text{for}\mu \in \left[\frac{1+m\left(k-3\right)}{k-2},\frac{m\left(k^2-2k-2\right)+k}{\left(k-2\right)\left(k+1\right)}\right]\\ \frac{\left(k+2\right)m-1}{\left(k+1\right)m}\mathrm{<mi>\; </mi>\; <mi>\; </mi>}\text{for}\mu \in \left[\frac{m\left(k^2-2k-2\right)+k}{\left(k-2\right)\left(k+1\right)},\frac{1+m\left(k-2\right)}{k-1}\right]\end{array}\end{array}$

where $k\ge \mathrm{3,}k\in N$, $\frac{p_1}{p_n}=2-\frac{\mu }{m}$, ( $1\le \mu <m,\mu \in R$ ). For $\mu \le \left(m+3\right)/4\left(k=3\right)$, the bound of $\left(4m-\mu \right)/3m$ is tight. We use $p_j\in \left[\mathrm{1,}r\right]$ with $r\ge 1$ instead of $\frac{p_1}{p_n}=2-\frac{\mu }{m}$. Then the tight interval for r is $\left[\frac{3}{2}\mathrm{,}\frac{5}{3}\right]$ in Kellerer’s result. In this paper, we will give the tight bound as a piecewise linear function of r for $m=3$ and all $r\ge 1$.

2. Theorem and Its Proof

Before the analysis, we give some symbols used later on.

1) $p_{i\left(j\right)}$ represents the size of the j-th job assigned on machine $M_i$ by LPT algorithm.

2) $S_i=\left\{j\ne n|J_j\text{is assigned on machine}{M}_i\text{by}LPT\text{algorithm}\right\}$.

3) $S_i^{*}=\left\{j|J_j\text{is assigned on machine}{M}_i\text{by optimal algorithm}\right\}$.

4) $C_{\max }^{LPT},C_{\max }^{OPT}$ represent the makespan of optimal algorithm and LPT algorithm, respectively.

In the following of this paper, for a given job list $L=\left\{J_1,J_2,\cdots ,J_n\right\}$, we always assume $p_1\ge p_2\ge \cdots \ge p_n$ and $1\le p_j\le r,j=1,2,\cdots ,n$.

Lemma 1 If $r<2$, then in LPT schedule, the difference of the numbers of jobs on any two machines is at most 1.

Proof: If it is not true, suppose it is the first time that there are k jobs assigned on $M_h$ and there are $k+2$ jobs assigned on $M_i$ in the LPT schedule, then we have

${\displaystyle \underset{s=1}{\overset{k}{\sum }}}{p}_{h\left(s\right)}\ge {\displaystyle \underset{s=1}{\overset{k+1}{\sum }}}{p}_{i\left(s\right)}.$

Hence we get

$p_{h\left(1\right)}\ge {\displaystyle \underset{s=1}{\overset{k-1}{\sum }}}\left(p_{i\left(s\right)}-p_{h\left(s+1\right)}\right)+p_{i\left(k\right)}+p_{i\left(k+1\right)}$

By the assumption that this is the first time of appearing the case, we have $p_{i\left(s\right)}\ge p_{h\left(s+1\right)}$ for $s=1,2,3,\cdots ,k-1$. That means

$p_{h\left(1\right)}\ge p_{i\left(k\right)}+p_{i\left(k+1\right)}\ge 2.$

This is a contradiction to $r<2$.

By Lemma 1, we can conclude that $p_{i\left(s\right)}\ge p_{h\left(s+1\right)}$ for any $1\le i\mathrm{,}h\le m$ in the LPT schedule.

Theorem 2. For any job list $L=\left\{J_1,J_2,\cdots ,J_n\right\}$ and $m=3$, we have

$\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le (\begin{array}{ll}\frac{11}{9};\hfill & r\in \left[\frac{5}{3},+\infty \right),\hfill \\ \frac{\left(2k+1\right)r+k+2}{3k+3};\hfill & r\in \left[\frac{\left(2k+3\right)\left(3k+2\right)}{\left(2k+1\right)\left(3k+4\right)},\frac{6k+5}{6k+3}\right),\hfill \\ \frac{9k+14}{3\left(3k+4\right)};\hfill & r\in \left[\frac{3k+4}{3\left(k+1\right)},\frac{\left(2k+3\right)\left(3k+2\right)}{\left(2k+1\right)\left(3k+4\right)}\right),\hfill \\ \frac{2\left(k+1\right)r+k+2}{3k+4};\hfill & r\in \left[1+\frac{3k+4}{9\left(k+1\right)\left(k+2\right)},\frac{3k+4}{3\left(k+1\right)}\right),\hfill \\ \frac{9k+20}{9\left(k+2\right)};\hfill & r\in \left[\frac{6\left(k+1\right)+5}{3\left[2\left(k+1\right)+1\right]},1+\frac{3k+4}{9\left(k+1\right)\left(k+2\right)}\right),\hfill \\ 1;\hfill & r=1,\hfill \end{array}$

where k is non-negative integer. Furthermore the bound is tight.

Proof: Case 1: $r\ge \frac{5}{3}$. For any $m\ge 1$, Graham [10] proved that

$\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{4}{3}-\frac{1}{3m}$

and the quality can hold. We get the conclusion by letting $m=3$.

For $r<\frac{5}{3}$, if the theorem is not true, then there is a job list $L=\left\{J_1,J_2,\cdots ,J_n\right\}$ with minimal n such that L violates the theorem. We call such a job list as a minimal counter example. For a minimal counter example, it is easy to show that the last job $J_n$ is finished at last. Hence we have

$\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{L_1+L_2+L_3+3p_n}{3C_{\max }^{OPT}\left(L\right)}\le \frac{{\displaystyle {\sum }_{j=1}^n{p}_j}+2p_n}{3C_{\max }^{OPT}\left(L\right)}\le 1+\frac{2p_n}{3C_{\max }^{OPT}\left(L\right)},$ (1)

Case 2: $\frac{\left(2k+3\right)\left(3k+2\right)}{\left(2k+1\right)\left(3k+4\right)}\le r<\frac{6k+5}{3\left(2k+1\right)}$.

In this case, we should prove

$\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{\left(2k+1\right)r+k+2}{3k+3}.$ (2)

If (2) is not true, by (1) we get

$\frac{\left(2k+1\right)r+k+2}{3k+3}<\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le 1+\frac{2p_n}{3C_{\max }^{OPT}\left(L\right)}.$

That means

$C_{\max }^{OPT}\left(L\right)<\frac{2\left(k+1\right)p_n}{\left(2k+1\right)\left(r-1\right)}\le \left(3k+4\right)p_n.$

Hence we get $n\le 9k+9$.

Case 2.1: $n=9k+9$.

In this case we have $\left|S_1\right|=\left|S_2\right|=3k+3$, $\left|S_3\right|=3k+2$, $\left|S_1^{*}\right|=\left|S_2^{*}\right|=\left|S_3^{*}\right|=3k+3$. It is easy to see that there exists $i\in \left\{\mathrm{1,2,3}\right\}$ satisfying $\left|S_i^{\mathrm{<mo>\; *\; </mo>}}\cap S_3\right|\ge k+1$. Without loss of generality, suppose $\left|S_1^{\mathrm{<mo>\; *\; </mo>}}\cap S_3\right|\ge k+1$, then $\left|S_3\backslash S_1^{\mathrm{<mo>\; *\; </mo>}}\right|\le 2k+1$. Therefore we get

$\begin{array}{c}\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{{\displaystyle {\sum }_{j\in S_3}{p}_j}+p_n}{{\displaystyle {\sum }_{j\in S_1^{*}}{p}_j}}=\frac{{\displaystyle {\sum }_{j\in S_3\cap S_1^{*}}{p}_j}+{\displaystyle {\sum }_{j\in S_3\backslash S_1^{*}}{p}_j}+1}{{\displaystyle {\sum }_{j\in S_3\cap S_1^{*}}{p}_j}+{\displaystyle {\sum }_{j\in S_1^{*}\backslash S_3}{p}_j}}\\ \le \frac{\left|S_3\cap S_1^{*}\right|+\left|S_3\backslash S_1^{*}\right|r+1}{\left|S_3\cap S_1^{*}\right|+\left|S_1^{*}\backslash S_3\right|}=\frac{\left|S_3\right|+\left|S_3\backslash S_1^{*}\right|\left(r-1\right)+1}{\left|S_1^{*}\right|}\\ \le \frac{\left(2k+1\right)r+k+2}{3k+3}.\end{array}$

Similarly we can get (2) for the case of $n=9k+7,9k+8$.

Case 2.2: $n=3k^{\prime }+1,k^{\prime }\le 3k+1$.

Let $\left|S_1\right|=\left|S_2\right|=\left|S_3\right|=k^{\prime }$, $\left|S_1^{*}\right|=\left|S_2^{*}\right|=k^{\prime }$, $\left|S_3^{*}\right|=k^{\prime }+1$, or $\left|S_1^{*}\right|=k^{\prime }-1$, $\left|S_2^{*}\right|=\left|S_3^{*}\right|=k^{\prime }+1$. At any case $\left|S_3^{*}\right|=k^{\prime }+1$ holds and there exists $i\in \left\{\mathrm{1,2,3}\right\}$ satisfying $\left|S_i\cap S_3^{\mathrm{<mo>\; *\; </mo>}}\right|\ge \frac{k^{\prime }+1}{3}$. W.l.o.g, suppose $\left|S_1\cap S_3^{\mathrm{<mo>\; *\; </mo>}}\right|\ge \frac{k^{\prime }+1}{3}$, then $\left|S_1\backslash S_3^{\mathrm{<mo>\; *\; </mo>}}\right|\le \frac{2k^{\prime }-1}{3}$. Hence we get

$\begin{array}{c}\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{{\displaystyle {\sum }_{j\in S_1}{p}_j}+p_n}{{\displaystyle {\sum }_{j\in S_3^{*}}{p}_j}}=\frac{{\displaystyle {\sum }_{j\in S_1\cap S_3^{*}}{p}_j}+{\displaystyle {\sum }_{j\in S_1\backslash S_3^{*}}{p}_j}+1}{{\displaystyle {\sum }_{j\in S_1\cap S_3^{*}}{p}_j}+{\displaystyle {\sum }_{j\in S_3^{*}\backslash S_1}{p}_j}}\\ \le \frac{\left|S_1\cap S_3^{*}\right|+\left|S_1\backslash S_3^{*}\right|r+1}{\left|S_1\cap S_3^{*}\right|+\left|S_3^{*}\backslash S_1\right|}=\frac{\left|S_1\backslash S_3^{*}\right|\left(r-1\right)+\left|S_1\right|+1}{\left|S_3^{*}\right|}\\ =\frac{\left(2k^{\prime }-1\right)r+k^{\prime }+4}{2k^{\prime }-1+k^{\prime }+4}\le \frac{\left(2k^{\prime }+1\right)r+k^{\prime }+1+4}{2k^{\prime }+1+k^{\prime }+1+4}\\ =\frac{\left(2k^{\prime }+1\right)r+k^{\prime }+5}{2k^{\prime }+1+k^{\prime }+5}\le \frac{\left(6k+3\right)r+3k+6}{9k+9}\\ =\frac{\left(2k+1\right)r+k+2}{3k+3},\end{array}$

where the last two inequalities result from the facts that function $y=\frac{\left(2x-1\right)r+x+4}{3x+3}$ and $y=\frac{\left(x+1\right)r+x+5}{3x+6}$ are increasing function of x. Similarly we can get (2) for the case of $n=3k^{\prime }+i,k^{\prime }\le 3k+1,i=2,3$.

Case 3: $\frac{3k+4}{3\left(k+1\right)}\le r<\frac{\left(2k+3\right)\left(3k+2\right)}{\left(2k+1\right)\left(3k+4\right)}$.

In this case, if the claim is not true, then by (1) there is a the minimal counter example L satisfying

$\frac{9k+14}{3\left(3k+4\right)}<\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le 1+\frac{2p_n}{3C_{\max }^{OPT}\left(L\right)}.$

Hence we get

$C_{\max }^{OPT}\left(L\right)<\left(3k+4\right)p_n.$

That means $n\le 9k+9$. By the proof of Case 2 we get

$\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{\left(2k+1\right)r+k+2}{3k+3}\le \frac{9k+14}{3\left(3k+4\right)}\mathrm{.}$

Case 4: $1+\frac{3k+4}{9\left(k+1\right)\left(k+2\right)}\le r<\frac{3k+4}{3\left(k+1\right)}$.

In this case, if the claim is not true, then by (1) there is a the minimal counter example L satisfying

$\frac{2\left(k+1\right)r+k+2}{3k+4}<\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le 1+\frac{2p_n}{3C_{\max }^{OPT}(L)}$

Hence we get

$C_{\max }^{OPT}\left(L\right)<\frac{3k+4}{3\left(k+1\right)\left(r-1\right)}\le \left(3k+6\right)p_n.$

That means $n\le 9k+15$.

Case 4.1: $n=9k+15$.

In this case we have $\left|S_1\right|=\left|S_2\right|=3k+5$, $\left|S_3\right|=3k+4$, $\left|S_1^{*}\right|=\left|S_2^{*}\right|=\left|S_3^{*}\right|=3k+5$. It is easy to see that there exists $i\in \left\{\mathrm{1,2,3}\right\}$ satisfying $\left|S_3\cap S_i^{\mathrm{<mo>\; *\; </mo>}}\right|\ge k+2$. W.l.o.g, suppose $\left|S_3\cap S_3^{\mathrm{<mo>\; *\; </mo>}}\right|\ge k+2$. That means $\left|S_3\backslash S_3^{\mathrm{<mo>\; *\; </mo>}}\right|\le 2k+2$. Hence we get

$\begin{array}{c}\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{{\displaystyle {\sum }_{j\in S_3}{p}_j}+1}{{\displaystyle {\sum }_{j\in S_3^{*}}{p}_j}}=\frac{{\displaystyle {\sum }_{j\in S_3\cap S_3^{*}}{p}_j}+{\displaystyle {\sum }_{j\in S_3\backslash S_3^{*}}{p}_j}+1}{{\displaystyle {\sum }_{j\in S_3^{*}\cap S_3}{p}_j}+{\displaystyle {\sum }_{j\in S_3^{*}\backslash S_3}{p}_j}}\\ \le \frac{\left|S_3\cap S_3^{*}\right|+\left|S_3\backslash S_3^{*}\right|r+1}{\left|S_3^{*}\right|}=\frac{\left|S_3\backslash S_3^{*}\right|\left(r-1\right)+\left|S_3\right|+1}{\left|S_3^{*}\right|}\\ \le \frac{\left(2k+2\right)\left(r-1\right)+3k+4+1}{3k+5}\le \frac{\left(2k+2\right)r+k+3}{3k+5}\\ \le \frac{\left(2k+2\right)r+k+2}{3k+4},\end{array}$

where the last inequality results from the fact that $y=\frac{x+b}{x+1}\left(b\ge 1\right)$ is a decreasing function of x.

Similarly we can show that the claim is true for the cases of $n=9k+i,i=13,14$.

Case 4.2: $n=3k^{\prime }+3,k^{\prime }\le 3k+3$.

In this case, let $\left|S_1\right|=\left|S_2\right|=k^{\prime }+1$, $\left|S_3\right|=k^{\prime }$. If There exists $i\in \left\{\mathrm{1,2,3}\right\}$ satisfying $\left|S_3\cap S_i^{\mathrm{<mo>\; *\; </mo>}}\right|\ge \frac{k^{\prime }+1}{3}$, w.l.o.g, suppose $\left|S_3\cap S_1^{\mathrm{<mo>\; *\; </mo>}}\right|\ge \frac{k^{\prime }+1}{3}$, then we have $\left|S_3\backslash S_1^{\mathrm{<mo>\; *\; </mo>}}\right|\le \frac{2k^{\prime }-1}{3}$. Therefore we get

$\begin{array}{c}\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{{\displaystyle {\sum }_{j\in S_3}{p}_j}+p_n}{{\displaystyle {\sum }_{j\in S_1^{*}}{p}_j}}=\frac{{\displaystyle {\sum }_{j\in S_3\cap S_1^{*}}{p}_j}+{\displaystyle {\sum }_{j\in S_3\backslash S_1^{*}}{p}_j}+p_n}{{\displaystyle {\sum }_{j\in S_1^{*}\cap S_3}{p}_j}+{\displaystyle {\sum }_{j\in S_1^{*}\backslash S_3}{p}_j}}\\ \le \frac{\left|S_3\cap S_1^{*}\right|+\left|S_3\backslash S_1^{*}\right|r+1}{\left|S_3\cap S_1^{*}\right|+\left|S_1^{*}\backslash S_3\right|}=\frac{\left|S_3\backslash S_1^{*}\right|\left(r-1\right)+\left|S_3\right|+1}{\left|S_1^{*}\right|}\\ \le \frac{\frac{2k^{\prime }-1}{3}\left(r-1\right)+k^{\prime }+1}{k^{\prime }+1}\le \frac{6kr+5r+3k+7}{3\left(3k+4\right)}\\ \le \frac{\left(2k+2\right)r+k+2}{3k+4}.\end{array}$

If $\left|S_1^{*}\right|=\left|S_2^{*}\right|=\left|S_3^{*}\right|=k^{\prime }+1$, it is easy to see that there exists $i\in \left\{\mathrm{1,2,3}\right\}$ satisfying $\left|S_3\cap S_i^{\mathrm{<mo>\; *\; </mo>}}\right|\ge \frac{k^{\prime }+1}{3}$. Then we get the claim is true by above discussion.

If $\left|S_1^{\mathrm{<mo>\; *\; </mo>}}\right|\ge k^{\prime }+\mathrm{2,}\left|S_3\cap S_1^{\mathrm{<mo>\; *\; </mo>}}\right|\ge \frac{k^{\prime }+1}{3}$, we also get the claim is true by above discussion.

If $\left|S_1^{\mathrm{<mo>\; *\; </mo>}}\right|\ge k^{\prime }+\mathrm{2,}\left|S_3\cap S_1^{\mathrm{<mo>\; *\; </mo>}}\right|<\frac{k^{\prime }+1}{3}$, then there exists $i\in \left\{\mathrm{1,2}\right\}$ satisfying $\left|S_i\cap S_1^{\mathrm{<mo>\; *\; </mo>}}\right|\ge \frac{k^{\prime }+3}{3}$, w.l.o.g, suppose $\left|S_1\cap S_1^{\mathrm{<mo>\; *\; </mo>}}\right|\ge \frac{k^{\prime }+3}{3}$, then $\left|S_1\backslash S_1^{\mathrm{<mo>\; *\; </mo>}}\right|\le \frac{2k^{\prime }}{3}$. Hence we get

$\begin{array}{c}\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{{\displaystyle {\sum }_{j\in S_1}{p}_j}+1}{{\displaystyle {\sum }_{j\in S_1^{*}}{p}_j}}=\frac{{\displaystyle {\sum }_{j\in S_1\cap S_1^{*}}{p}_j}+{\displaystyle {\sum }_{j\in S_1\backslash S_1^{*}}{p}_j}+1}{{\displaystyle {\sum }_{j\in S_1^{*}\cap S_1}{p}_j}+{\displaystyle {\sum }_{j\in S_1^{*}\backslash S_1}{p}_j}}\\ \le \frac{\left|S_1\cap S_1^{*}\right|+\left|S_1\backslash S_1^{*}\right|r+1}{\left|S_1\cap S_1^{*}\right|+\left|S_1^{*}\backslash S_1\right|}=\frac{\left|S_1\backslash S_1^{*}\right|\left(r-1\right)+\left|S_1\right|+1}{\left|S_1^{*}\right|}\\ \le \frac{\frac{2k^{\prime }}{3}\left(r-1\right)+k^{\prime }+1+1}{k^{\prime }+2}\le \frac{\left(6k+6\right)r+3k+9}{3\left(3k+5\right)}\\ \le \frac{\left(2k+2\right)r+k+2}{3k+4},\end{array}$

where the last inequality results from the fact that $y=\frac{x+b}{x+1}\left(b\ge 1\right)$ is a decreasing function of x.

Case 5: $\frac{6\left(k+1\right)+5}{3\left[2\left(k+1\right)+1\right]}\le r<1+\frac{3k+4}{9\left(k+1\right)\left(k+2\right)}$.

In this case we should prove

$\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{9k+20}{9\left(k+2\right)}\mathrm{.}$

If it is not true, then by (1) the minimal counter example satisfies

$\frac{9k+20}{9\left(k+2\right)}<\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{{\displaystyle {\sum }_{i=1}^n{p}_i}+2p_n}{3C_{\max }^{OPT}(L)}$

Hence we get

$C_{\max }^{OPT}\left(L\right)<\left(3k+6\right)p_n.$

That means $n\le 9k+15$. By the proof of Case 4 we get

$C_{\max }^{OPT}\left(L\right)\le \frac{2\left(k+1\right)r+k+2}{3k+4}\le \frac{9k+14}{3\left(3k+4\right)}.$

By the above discussions of Case 1-5, the inequality in Theorem 2 is proved.

Now we prove the tightness of the inequalities. For $\frac{\left(2k+3\right)\left(3k+2\right)}{\left(2k+1\right)\left(3k+4\right)}\le r<\frac{6k+5}{3\left(2k+1\right)}$, let $L=\left\{J_1,J_2,\cdots ,J_{9k+7}\right\}$ with $p_j=r,j=1,2,\cdots ,6k+2$, $p_{6k+3}=p_{6k+4}=r^{\prime }=\frac{r+1}{2}$, $p_j=1,j=6k+5,\cdots ,9k+7$. Then $L_1=\left(2k+1\right)r+k+2$, $L_2=\left(2k+1\right)r+k+1$, $L_3=2kr+k+2r^{\prime }$, $L_1^{*}=3k+3$, $L_2^{*}=L_3^{*}=\left(3k+1\right)r+r^{\prime }$. Hence we get

$\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}=\frac{\left(2k+1\right)r+k+2}{3k+3}.$ (3)

For $\frac{3k+4}{3\left(k+1\right)}\le r<\frac{\left(2k+3\right)\left(3k+2\right)}{\left(2k+1\right)\left(3k+4\right)}$. let $L=\left\{J_1,J_2,\cdots ,J_{9k+10}\right\}$ with $p_j=r,j=1,\cdots ,6$ ; $p_j=r^{\prime }=\frac{3k+4-3r}{3k},j=7,\cdots ,6k+6$, $p_j=1,j=6k+7,\cdots ,9k+10$. Then we have $L_1=2r+2k{r}^{\prime }+k+2$, $L_2=L_3=2r+2k{r}^{\prime }+k+1$, $L_1^{*}=3k+4$, $L_2^{*}=L_3^{*}=3r+3k{r}^{\prime }$. Hence we get

$\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}=\frac{9k+14}{3\left(3k+4\right)}.$ (4)

For $1+\frac{3k+4}{9\left(k+1\right)\left(k+2\right)}\le r<\frac{3k+4}{3\left(k+1\right)}$, let $L=\left\{J_1,J_2,\cdots ,J_{9k+10}\right\}$ with $p_j=r,j=1,2,\cdots ,6k+6$, $p_j=1,j=6k+7,\cdots ,9k+10$. Then we have $L_1=2\left(k+1\right)r+k+2$, $L_2=L_3=2\left(k+1\right)r+k+1$, , . Hence we get

(5)

For, let with , , , . Then we have, , , ,. Hence we get

(6)

Hence Theorem 2 is proved.

3. Conclusion and Future Work

In this paper, LPT algorithm is considered for the scheduling jobs with similar sizes in on three machines. The objective function is to minimize the maximum completion time of all machines. The worst performance ratio of the LPT algorithm is given as a piecewise linear function of r. The result is better than the existing result and cannot be improved any more. It is interesting to consider general number of machines and give tight bound of worst case performance.

Acknowledgements

The authors would like to express their thanks to the National Natural Science Foundation of China for financially supporting under Grant No. 11471110 and the Foundation Grant of Education Department of Hunan (No. 16A126).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Graham, R.L. (1969) Bounds on Multiprocessing Timing Anomalies. SIAM Journal on Applied Mathematics, 17, 416-429. https://doi.org/10.1137/0117039
[2]	Cheng, T.C.E., Kellerer, H. and Kotov, V. (2012) Algorithms Better than LPT for Semi-Online Scheduling with Decreasing Processing Times. Operations Research Letters, 40, 349-352. https://doi.org/10.1016/j.orl.2012.05.009
[3]	He, Y.G. (2005) Semi-Online Scheduling Jobs with Tightly-Grouped Processing Times on Three Identical Machines. Discrete Applied Mathematics, 150, 140-159. https://doi.org/10.1016/j.dam.2004.12.005
[4]	He, Y. and Zhang, G. (1999) Semi On-Line Scheduling on Two Identical Machines. Computing, 62, 179-187. https://doi.org/10.1007/s006070050020
[5]	Kellerer, H., Kotov, V., Speranza, M.G. and Tuza, Z. (1997) Semi On-Line Algorithms for the Partition Problem. Operations Research Letters, 21, 235-242. https://doi.org/10.1016/S0167-6377(98)00005-4
[6]	Li, R.H. and Huang, H.C. (2007) List Scheduling for Jobs with Arbitrary Release Times and Similar Lengths. Journal of Scheduling, 10, 365-373. https://doi.org/10.1007/s10951-007-0042-8
[7]	Lin, L. and Tan, Z. (2014) Inefficiency of Nash Equilibrium for Scheduling Games with Constrained Jobs: A Parametric Analysis. Theoretical Computer Science, 521, 123-134. https://doi.org/10.1016/j.tcs.2013.11.012
[8]	He, Y. and Dosa, G. (2005) Semi-Online Scheduling Jobs with Tightly-Grouped Processing Times on Three Identical Machines. Discrete Applied Mathematics, 150, 140-159. https://doi.org/10.1016/j.dam.2004.12.005
[9]	Kellerer, H. (1991) Bounds for Non-Preemptive Scheduling Jobs with Similar Processing Times on Multiprocessor Systems Using LPT-Algorithm. Computing, 46, 183-191. https://doi.org/10.1007/BF02238297
[10]	Graham, R.L. (1976) Bounds on the Performance of Scheduling Algorithms, Computer and Job-Shop Scheduling Theory. John Wiley Sons, New York, 165-227.