ABSTRACT

Ordinal online schedule for jobs with similar sizes in $\left[\mathrm{1,}r\right]\left(1\le r\le 2\right)$ on two parallel machines system is considered. Firstly it is proved that the worst case performance ratio of the existing algorithm P₂ cannot be improved even if the job processing times are known in $\left[\mathrm{1,}r\right]$ for any $r\ge 1$ . Then a better algorithm named S is developed and its worst case performance ratio is given for $1\le r\le 2$ .

Keywords:

Semi-Online Scheduling, P_m Algorithm, S Algorithm, Worst Performance Ratio

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. The earliest algorithm for on-line scheduling jobs on parallel machines is the List Scheduling (LS) algorithm, which was introduced by Graham [1] . Many models and algorithms for online scheduling are proposed later on. In classic scheduling problem, there is no constraints on the size of job. However, in practice, the size of job can neither be too large nor too small. This motivates researchers to study scheduling problems when the sizes of all jobs are known in $\left[\mathrm{1,}r\right]$ with $r\ge 1$ [2] - [7] .

In this paper, we will consider ordinal online scheduling jobs with sizes in $\left[\mathrm{1,}r\right]\left(1\le r\le 2\right)$ on two parallel machines. The model of ordinal online scheduling was proposed by Liu et al. [8] . It is assumed that the values of the processing times are unknown, but that the order of the jobs by non-increasing processing time is known, i.e., without loss of generality that $p_1\ge p_2\ge \cdots \ge p_n$ . An algorithm named P_m was developed for the system of m machines and it is proved that the algorithm is the best online algorithm for $m=2,3$ . In current research, it will be proved that, for $m=2$ , the worst case performance ratio of algorithm P₂ can not be improved even if the sizes of all jobs are known in $\left[\mathrm{1,}r\right]$ for any $r\ge 1$ . Then a better algorithm named S is proposed for $r\in \left[\mathrm{1,2}\right]$ and its worst case performance ratio is given.

The rest of the paper is organized as follows. In Section 2, some definitions and the algorithm S and P₂ are given. Section 3 analyzes the competitive ratio of the algorithm S. Finally, some concluding remarks are given in Section 4.

2. Some Definitions and Algorithms

Definition 1. Given m parallel machines, let $L=\left\{J_1,J_2,\cdots ,J_n\right\}$ be any list of jobs. Algorithm A is a heuristic algorithm. Let $C_{\max }^A\left(L\right)$ and $C_{\max }^{OPT}\left(L\right)$ be the makespan of algorithm A and the makespan of an optimal off-line algorithm respectively. We refer to

$R\left(m,A\right)=\underset{L}{\sup }\frac{C_{\max }^A\left(L\right)}{C_{\max }^{OPT}(L)}$

as the worst case performance ratio of algorithm A.

In the following of this paper, we always assume that the number of machines is two (i.e. $m=2$ ) and the sizes of job list $L=\left\{J_1,J_2,\cdots ,J_n\right\}$ satisfies $p_1\ge p_2\ge \cdots \ge p_n$ and $p_j\in \left[1,r\right]\left(j=1,2,\cdots ,n,1\le r\le 2\right)$ if no specific explanation is given.

Algorithm P₂ [8] . Jobs are assigned to machines as follows:

$\begin{array}{l}{M}_1\mathrm{<mo>\; :\; </mo>}\left\{J_{3k+1}\mathrm{<mo>\; |\; </mo>}k\ge 0\right\}\mathrm{,}\\ M_2\mathrm{<mo>\; :\; </mo>}\left\{J_{3k-1}\mathrm{,}{J}_{3k}\mathrm{<mo>\; |\; </mo>}k\ge 1\right\}\mathrm{.}\end{array}$

i.e.

$\begin{array}{l}{M}_1\mathrm{<mo>\; :\; </mo>}{J}_1{J}_4{J}_7{J}_{10}\cdots \\ M_2\mathrm{<mo>\; :\; </mo>}{J}_2{J}_3{J}_5{J}_6{J}_8{J}_9\cdots \end{array}$

Algorithm S.

Jobs are assigned to machines as follows:

$\begin{array}{l}{M}_1\mathrm{<mo>\; :\; </mo>}\left\{J_1\right\}\cup \left\{J_{4k}\mathrm{,}{J}_{4k+1}\mathrm{<mo>\; |\; </mo>}k\ge 1\right\},\\ M_2\mathrm{<mo>\; :\; </mo>}\left\{J_{4k-2}\mathrm{,}{J}_{4k-1}\mathrm{<mo>\; |\; </mo>}k\ge 1\right\}\mathrm{.}\end{array}$

i.e.

$\begin{array}{l}{M}_1\mathrm{<mo>\; :\; </mo>}{J}_1{J}_4{J}_5{J}_8{J}_9{J}_{12}\cdots \\ M_2\mathrm{<mo>\; :\; </mo>}{J}_2{J}_3{J}_6{J}_7{J}_{10}{J}_{11}\cdots \end{array}$

The two algorithms are the same for assigning the first four jobs. The differences are that P₂ assign the first two jobs on M₂ and the third on M₁ for job set $\left\{J_j|j=3k+2,3k+3,3k+4\right\}\left(k\ge 1\right)$ . However algorithm S assign the two consecutive job $J_{2k+1}\mathrm{,}{J}_{2k+2}\left(k\ge 2\right)$ on two machines alteratively.

In the following, we consider the worst case performance ratio of algorithm P₂ and S. We will show that algorithm S is better than P₂ under the assumption of $p_j\in \left[\mathrm{1,}r\right]$ for $r\le 2$ .

3. Main Results

Theorem 1. For algorithm P₂, its worst case performance ratio is $\frac{4}{3}$ . Furthermore, its worst case performance ratio can not be improved if $p_j\left(j=1,2,\cdots ,n\right)$ satisfy $p_j\in \left[\mathrm{1,}r\right]$ for any $r\ge 1$ .

Proof: The first conclusion is a direct result from Liu et al. [8] . For the second conclusion, consider job list $L=\left\{J_1,J_2,\cdots ,J_{6k+4}\right\}$ satisfying

$p_1=p_2=p_3=p_4=r\ge 1,p_5=p_6=\cdot \cdot \cdot =p_{6k+4}=1.$

By the rules of P₂, we get

$\begin{array}{l}{M}_1\mathrm{<mo>\; :\; </mo>}rr11\cdots \\ M_2\mathrm{<mo>\; :\; </mo>}rr1111\cdots \end{array}$

It is obvious that $C_{\max }^{P_2}\left(L\right)=2r+4k$ and $C_{\max }^{OPT}\left(L\right)=2r+3k$ . Hence

$\frac{C_{\max }^{P_2}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}=\frac{2r+4k}{2r+3k}\to \frac{4}{3}\left(k\to \infty \right).$

In the following of this paper, let $L_i\left(i=1,2\right)$ to denote the completion time of machine M_i in the schedule assigned by algorithm S.

Lemma 2. Given any job list $L=\left\{J_1,J_2,\cdots ,J_n\right\}$ , the following inequality holds

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

Proof: By the rules of S algorithm, we get

$\begin{array}{c}\frac{C_{\max }^S\left(L\right)}{C_{\max }^{OPT}\left(L\right)}=\frac{\max \left\{L_1,L_2\right\}}{C_{\max }^{OPT}\left(L\right)}\\ =\frac{L_1+L_2+\max \left\{L_1,L_2\right\}-\min \left\{L_1,L_2\right\}}{2C_{\max }^{OPT}\left(L\right)}\\ \le 1+\frac{\left|L_1-L_2\right|}{2C_{\max }^{OPT}\left(L\right)}.\end{array}$

That means it is enough to prove $\left|L_1-L_2\right|\le r$ . We consider it according to the four cases of $n=4k$ , $n=4k+1$ , $n=4k+2$ , $n=4k+3$ .

Case 1: $n=4k$ . In this case,

$L_1=p_1+{\displaystyle \underset{j=1}{\overset{k-1}{\sum }}}\left(p_{4j}+p_{4j+1}\right)+p_{4k};L_2={\displaystyle \underset{j=1}{\overset{k}{\sum }}}\left(p_{4j-2}+p_{4j-1}\right).$

Hence the following inequalities hold:

$\begin{array}{l}{L}_1-L_2=p_1+{\displaystyle \underset{j=1}{\overset{k-1}{\sum }}}\left(p_{4j}+p_{4j+1}-p_{4j-2}-p_{4j-1}\right)+p_{4k}-p_{4k-2}-p_{4k-1}\le p_1\le r,\\ L_2-L_1=p_2+p_3-p_1+{\displaystyle \underset{j=1}{\overset{k-1}{\sum }}}\left(p_{4j+2}+p_{4j+3}-p_{4j}-p_{4j+1}\right)-p_{4k}\le p_2\le r.\end{array}$

That means $\left|L_1-L_2\right|\le r$ .

Case 2: $n=4k+1$ . In this case,

$L_1=p_1+{\displaystyle \underset{j=1}{\overset{k}{\sum }}}\left(p_{4j}+p_{4j+1}\right),L_2={\displaystyle \underset{j=1}{\overset{k}{\sum }}}\left(p_{4j-2}+p_{4j-3}\right).$

Hence the following inequalities hold:

$\begin{array}{l}{L}_1-L_2=p_1+{\displaystyle \underset{j=1}{\overset{k}{\sum }}}\left(p_{4j}+p_{4j+1}-p_{4j-2}-p_{4j-1}\right)\le p_1\le r,\\ L_2-L_1=p_2+p_3-p_1+{\displaystyle \underset{j=1}{\overset{k-1}{\sum }}}\left(p_{4j+2}+p_{4j+3}-p_{4j}-p_{4j+1}\right)-p_{4k}-p_{4k+1}\le p_2\le r.\end{array}$

That means $\left|L_1-L_2\right|\le r$ . Similarly it is easy to show that the conclusion is true for the case of $n=4k+2$ and $n=4k+3$ .

Theorem 3. For any job list $L=\left\{J_1,J_2,\cdots ,J_n\right\}$ with $p_1\ge p_2\ge \cdots \ge p_n$ and $p_j\in \left[\mathrm{1,}r\right]\left(1\le r\le 2\right)$ , algorithm S has worst case performance ratio

$\frac{C_{\max }^S\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le (\begin{array}{l}\frac{2+r}{3},\frac{3}{2}<r\le 2\\ \frac{7}{6}\mathrm{<mi>\; </mi>\; <mi>\; </mi>},\frac{4}{3}\le r\le \frac{3}{2}\\ \frac{r+1}{2},1\le r<\frac{4}{3}\end{array}$ (1)

Proof: Suppose (1) is not true. For $\frac{3}{2}\le r\le 2$ the following inequalities hold by Lemma 2:

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

That means $C_{\max }^{OPT}\left(L\right)<\frac{3r}{2\left(r-1\right)}<5$ . Similarly $C_{\max }^{OPT}\left(L\right)<5$ also holds for $\frac{4}{3}\le r<\frac{3}{2}$ . That means there are at most four jobs assigned on any machine in

any optimal schedule, i.e., $n\le 8$ . It is easy to prove that algorithm S is optimal if $n<5$ . Now consider $n=5$ . In this case

$\begin{array}{l}{L}_1=p_1+p_4+p_5\ge p_2+2\ge p_2+p_3=L_2,\\ C_{\max }^{OPT}\left(L\right)\ge p_3+p_4+p_5.\end{array}$

Hence

$\frac{C_{\max }^S\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{p_1+p_4+p_5}{p_3+p_4+p_5}\le \frac{p_1+\left(p_4+p_5\right)}{p_3+\left(p_4+p_5\right)}\le \frac{p_1+2}{p_3+2}\le \frac{r+2}{3}.$

For the case of $n=6$ , there are exactly three jobs on each machine in any optimal schedule. If $L_1>L_2$ , we get

$\frac{C_{\max }^S\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{p_1+p_4+p_5}{p_1+p_5+p_6}\le \frac{p_4+p_1+p_5}{p_6+p_1+p_5}\le \frac{r+2}{3}$

If $L_1\le L_2$ we have

$\frac{C_{\max }^S\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{p_2+p_3+p_6}{p_1+p_5+p_6}\le \frac{p_2+\left(p_3+p_6\right)}{p_5+\left(p_3+p_6\right)}\le \frac{p_2+2}{p_3+2}\le \frac{r+2}{3}.$

For the case of $n=7$ , the following holds

$L_2=p_2+p_3+p_6+p_7\ge p_2+p_3+2\ge p_1+p_2+p_3=L_1.$

In any optimal schedule, exactly four jobs are assigned on one machine and exactly three jobs are assigned on another. If the machine assigned four jobs in optimal schedule has at least one job from set $\left\{J_1\mathrm{,}{J}_2\mathrm{,}{J}_3\right\}$ , then the following inequality holds:

$C_{\max }^{OPT}\left(L\right)\ge p_3+p_5+p_6+p_7.$

Hence we get

$\frac{C_{\max }^S\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{p_2+p_3+p_6+p_7}{p_3+p_5+p_6+p_7}\le \frac{p_2+3}{p_5+3}\le \frac{r+3}{4}\le \frac{r+2}{3}.$

Otherwise the optimal schedule is that $\left\{J_1\mathrm{,}{J}_2\mathrm{,}{J}_3\right\}$ and $\left\{J_4\mathrm{,}{J}_5\mathrm{,}{J}_6\mathrm{,}{J}_7\right\}$ are assigned separately on two machines. Let $a=\frac{p_2+p_3}{2}$ , $b=\frac{p_4+p_5}{2}$ , $c=\frac{p_6+p_7}{2}$ . It is easy to see that $a\ge b\ge c$ holds. We analyze the following two cases. In the case of $3a\le 2b+2c$ , we get

$\frac{C_{\max }^S\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{p_2+p_3+p_6+p_7}{p_4+p_5+p_6+p_7}=\frac{a+c}{b+c}\le \frac{2b+5c}{3b+3c}=\frac{2}{3}+\frac{c}{b+c}\le \frac{7}{6},$

the last inequality results from $b\ge c$ .

In the case of $3a>2b+2c$ we get

$\frac{C_{\max }^S\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{p_2+p_3+p_6+p_7}{p_1+p_2+p_3}=\frac{2a+2c}{3a}=\frac{2}{3}+\frac{2c}{3a}\le \frac{2}{3}+\frac{2c}{2b+2c}\le \frac{7}{6}.$

For $n=8$ , there are exactly four jobs assigned on each machine and there is a machine on which at least two jobs from $\left\{J_1\mathrm{,}{J}_2\mathrm{,}{J}_3\right\}$ are assigned in any optimal schedule. Hence the following inequality holds:

$C_{\max }^{OPT}\left(L\right)\ge \max \left\{p_2+p_3+p_7+p_8,p_1+p_6+p_7+p_8\right\}.$

Therefore if $L_1\ge L_2$ we get

$\frac{C_{\max }^S\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{p_1+p_4+p_5+p_8}{p_2+p_3+p_7+p_8}\le \frac{p_1+p_4+p_5+p_8}{p_7+p_4+p_5+p_8}\le \frac{r+3}{4}\le \frac{r+2}{3}.$

If $L_1\le L_2$ we get

$\frac{C_{\max }^S\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{p_2+p_3+p_6+p_7}{p_1+p_6+p_7+p_8}\le \frac{p_2+p_3+p_6+p_7}{p_8+p_3+p_6+p_7}\le \frac{r+3}{4}\le \frac{r+2}{3}.$

By the conclusions above, we get

$\frac{C_{\max }^S\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \max \left\{\frac{7}{6},\frac{r+2}{3}\right\}=(\begin{array}{l}\frac{2+r}{3},\frac{3}{2}<r\le 2\\ \frac{7}{6},\frac{4}{3}\le r\le \frac{3}{2}\end{array}$

Hence (1) is true for $\frac{4}{3}\le r\le 2$ .

Now we consider the case of $1\le r\le \frac{4}{3}$ according to the four cases of

$n=4k+1,4k+2,4k+3,4k+4,k=0,1,2,\cdots$ . In the following, we will use $S_i$

and $S_i^{\mathrm{<mo>\; *\; </mo>}}$ to denote the job set assigned on machine M_i by algorithm S and optimal algorithm, respectively.

For the case of $n=4k+1$ , we have $\left|S_1\right|=2k+1$ , $\left|S_2\right|=2k$ , $\max \left\{\left|S_1^{*}\right|,\left|S_2^{*}\right|\right\}\ge 2k+1$ . Without loss of generality, suppose $\left|S_1^{\mathrm{<mo>\; *\; </mo>}}\right|\ge 2k+1$ . Then it is easy to see that there exists $i\in \left\{\mathrm{1,2}\right\}$ satisfying $\left|S_1^{\mathrm{<mo>\; *\; </mo>}}\cap S_i\right|\ge k+1$ . If $\left|S_1^{\mathrm{<mo>\; *\; </mo>}}\cap S_1\right|\ge k+1$ , then $\left|S_1\backslash S_1^{\mathrm{<mo>\; *\; </mo>}}\right|\le k$ . By

$L_2-L_1=p_2+p_3-p_1+{\displaystyle \underset{j=1}{\overset{k-1}{\sum }}}\left(p_{4j+2}+p_{4j+3}-p_{4j}-p_{4j+1}\right)-p_{4k}-p_{4k+1}\le 0,$

we get $L_1\ge L_2$ . Therefore

$\begin{array}{c}\frac{C_{\max }^S\left(L\right)}{C_{\max }^{OPT}\left(L\right)}=\frac{L_1}{C_{\max }^{OPT}\left(L\right)}\le \frac{{\displaystyle \underset{j\in S_1}{\sum }}{p}_j}{{\displaystyle \underset{j\in S_1^{\mathrm{<mo>\; *\; </mo>}}}{\sum }}{p}_j}\le \frac{{\displaystyle \underset{j\in S_1\cap S_1^{\mathrm{<mo>\; *\; </mo>}}}{\sum }}{p}_j+{\displaystyle \underset{j\in S_1\backslash S_1^{\mathrm{<mo>\; *\; </mo>}}}{\sum }}{p}_j}{{\displaystyle \underset{j\in S_1\cap S_1^{\mathrm{<mo>\; *\; </mo>}}}{\sum }}{p}_j+{\displaystyle \underset{j\in S_1^{\mathrm{<mo>\; *\; </mo>}}\backslash S_1}{\sum }}{p}_j}\\ \le \frac{\left|S_1\cap S_1^{\mathrm{<mo>\; *\; </mo>}}\right|+\left|S_1\backslash S_1^{\mathrm{<mo>\; *\; </mo>}}\right|r}{\left|S_1\cap S_1^{\mathrm{<mo>\; *\; </mo>}}\right|+\left|S_1^{\mathrm{<mo>\; *\; </mo>}}\backslash S_1\right|}\\ \le \frac{\left|S_1\cap S_1^{\mathrm{<mo>\; *\; </mo>}}\right|+\left(\left|S_1\right|-\left|S_1\cap S_1^{\mathrm{<mo>\; *\; </mo>}}\right|\right)r}{2k+1}\\ \le \frac{kr+k+1}{2k+1}\le \frac{r+1}{2}\mathrm{.}\end{array}$

If $\left|S_1^{\mathrm{<mo>\; *\; </mo>}}\cap S_1\right|\le k$ , then $\left|S_1^{\mathrm{<mo>\; *\; </mo>}}\cap S_2\right|\ge k+1$ . By

$L_1-L_2=p_1+{\displaystyle \underset{j=1}{\overset{k}{\sum }}}\left(p_{4j}+p_{4j+1}-p_{4j-2}-p_{4j-3}\right)\le p_1$

we get $L_1\le L_2+p_1$ . Therefore

$\begin{array}{c}\frac{C_{\max }^S\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{L_2+p_1}{C_{\max }^{OPT}\left(L\right)}\le \frac{{\displaystyle \underset{j\in S_2}{\sum }}{p}_j}{{\displaystyle \underset{j\in S_1^{*}}{\sum }}{p}_j}\le \frac{{\displaystyle \underset{j\in S_2\cap S_1^{*}}{\sum }}{p}_j+{\displaystyle \underset{j\in S_2\backslash S_1^{*}}{\sum }}{p}_j+p_1}{{\displaystyle \underset{j\in S_2\cap S_1^{*}}{\sum }}{p}_j+{\displaystyle \underset{j\in S_1^{*}\backslash S_2}{\sum }}{p}_j}\\ \le \frac{\left|S_2\cap S_1^{*}\right|+\left|S_2\backslash S_1^{*}\right|r+r}{\left|S_2\cap S_1^{*}\right|+\left|S_1^{*}\backslash S_2\right|}\\ \le \frac{\left|S_2\cap S_1^{*}\right|+\left(\left|S_2\right|-\left|S_2\cap S_1^{*}\right|\right)r+r}{2k+1}\\ \le \frac{kr+k+1}{2k+1}\le \frac{r+1}{2}.\end{array}$

For the case of $n=4k+2$ , we have $\left|S_1\right|=2k+1$ , $\left|S_2\right|=2k+1$ , $\max \left\{\left|S_1^{*}\right|,\left|S_2^{*}\right|\right\}\ge 2k+1$ . Without loss of generality, suppose $\left|S_1^{\mathrm{<mo>\; *\; </mo>}}\right|\ge 2k+1$ . Therefore there exists $i\in \left\{\mathrm{1,2}\right\}$ satisfying $\left|S_1^{\mathrm{<mo>\; *\; </mo>}}\cap S_i\right|\ge k+1$ . In the following we consider this case according to the two subcases of $L_1\ge L_2$ and $L_1<L_2$ .

In this case of $L_1\ge L_2$ , if $\left|S_1^{\mathrm{<mo>\; *\; </mo>}}\cap S_1\right|\ge k+1$ holds, then the following is true:

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

If $\left|S_1^{\mathrm{<mo>\; *\; </mo>}}\cap S_1\right|\le k$ holds, we consider the following two subcases of $\left|S_1^{*}\right|=2k+1$ and $\left|S_1^{\mathrm{<mo>\; *\; </mo>}}\right|\ge 2k+2$ .

For the case of $\left|S_1^{*}\right|=2k+1$ , $\left|S_2^{*}\right|=2k+1$ holds by $n=4k+2$ . By $\left|S_1\right|=2k+1$ and $\left|S_1^{\mathrm{<mo>\; *\; </mo>}}\cap S_1\right|\le k$ we get $\left|S_2^{\mathrm{<mo>\; *\; </mo>}}\cap S_1\right|\ge k+1$ . Therefore

$\begin{array}{c}\frac{C_{\max }^S\left(L\right)}{C_{\max }^{OPT}\left(L\right)}=\frac{L_1}{C_{\max }^{OPT}\left(L\right)}\le \frac{{\displaystyle \underset{j\in S_1}{\sum }}{p}_j}{{\displaystyle \underset{j\in S_2^{*}}{\sum }}{p}_j}\le \frac{{\displaystyle \underset{j\in S_1\cap S_2^{*}}{\sum }}{p}_j+{\displaystyle \underset{j\in S_1\backslash S_2^{*}}{\sum }}{p}_j}{{\displaystyle \underset{j\in S_1\cap S_2^{*}}{\sum }}{p}_j+{\displaystyle \underset{j\in S_2^{*}\backslash S_1}{\sum }}{p}_j}\\ \le \frac{\left|S_1\cap S_2^{*}\right|+\left|S_1\backslash S_2^{*}\right|r}{\left|S_1\cap S_2^{*}\right|+\left|S_2^{*}\backslash S_1\right|}\\ \le \frac{\left|S_1\cap S_2^{*}\right|+\left(\left|S_1\right|-\left|S_1\cap S_2^{*}\right|\right)r}{2k+1}\\ \le \frac{kr+k+1}{2k+1}\le \frac{r+1}{2}.\end{array}$

For the case of $\left|S_1^{\mathrm{<mo>\; *\; </mo>}}\right|\ge 2k+2$ , by $\left|S_1^{\mathrm{<mo>\; *\; </mo>}}\cap S_1\right|\le k$ we get $\left|S_1^{\mathrm{<mo>\; *\; </mo>}}\cap S_2\right|\ge k+2$ . By rules of S algorithm, we have

$L_1-L_2=p_1+{\displaystyle \underset{j=1}{\overset{k}{\sum }}}\left(p_{4j}+p_{4j+1}-p_{4j-2}-p_{4j-1}\right)-p_{4k+2}\le p_1-p_{4k+2}.$

That means $L_1\le L_2+p_1-p_{4k+2}$ . Therefore

$\begin{array}{l}\frac{C_{\max }^S\left(L\right)}{C_{\max }^{OPT}\left(L\right)}=\frac{L_1}{C_{\max }^{OPT}\left(L\right)}\le \frac{L_2+p_1-p_{4k+2}}{C_{\max }^{OPT}\left(L\right)}\\ \le \frac{{\displaystyle \underset{j\in S_2\cap S_1^{*}}{\sum }}{p}_j+{\displaystyle \underset{j\in S_2\backslash S_1^{*}}{\sum }}{p}_j+p_1-p_{4k+2}}{{\displaystyle \underset{j\in S_2\cap S_1^{*}}{\sum }}{p}_j+{\displaystyle \underset{j\in S_1^{*}\backslash S_2}{\sum }}{p}_j}\le \frac{\left|S_2\cap S_1^{*}\right|+\left|S_2\backslash S_1^{*}\right|r+r-1}{\left|S_2\cap S_1^{*}\right|+\left|S_1^{*}\backslash S_2\right|}\\ \le \frac{\left|S_2\cap S_1^{*}\right|+\left(\left|S_2\right|-\left|S_2\cap S_1^{*}\right|\right)r+r-1}{2k+2}\le \frac{kr+k+1}{2k+2}\le \frac{kr+k+1}{2k+1}\le \frac{r+1}{2}.\end{array}$

Similarly we can prove the case of $L_1<L_2$ .

By the same way used above, we can also show that (1) is true for the case of $n=4k+3$ and $n=4k+4$ for $1\le r\le \frac{4}{3}$ . Now we show the tightness of the bound.

For $\frac{3}{2}<r\le 2$ , Let $L^{\left(1\right)}=\left\{J_1,J_2,J_3,J_4,J_5\right\}$ with $p_1=r,p_i=1,i=2,\cdots ,5$ . By

the rules of S algorithm, we have $L_1=r+2,L_2=2$ , i.e., $C_{\max }^S\left(L^{\left(1\right)}\right)=r+2$ . It is easy to see that $C_{\max }^{OPT}\left(L^{\left(1\right)}\right)=3$ . Hence

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

It is easy to show the tightness for $\frac{4}{3}\le r\le \frac{3}{2}$ by job list $L^{\left(2\right)}=\left\{J_1,J_2,J_3,J_4,J_5,J_6,J_7\right\}$ with $p_1=p_2=p_3=\frac{4}{3}$ , $p_4=p_5=p_6=p_7=1$ and for $1\le r\le \frac{4}{3}$ by job list with $p_1=p_2=p_3=r$ , $p_4=p_5=p_6=p_7=1$ .

4. Concluding Remarks

In this paper, we consider ordinal on-line scheduling for jobs with known sizes in $\left[\mathrm{1,}r\right]\left(r\ge 1\right)$ and non-decreasing processing times on two parallel machines system. Firstly it is proved that the worst case performance ratio of the existing algorithm P₂ can not be improved even if the job processing times are known in $\left[\mathrm{1,}r\right]$ for any $r\ge 1$ . Secondly, an algorithm named S is proposed and its worst case performance ratio is given as follow:

$R\left(2,S\right)=(\begin{array}{l}\frac{2+r}{3},\frac{3}{2}<r\le 2\\ \frac{7}{6},\frac{4}{3}\le r\le \frac{3}{2}\\ \frac{r+1}{2},1\le r<\frac{4}{3}\end{array}$

which is better than algorithm P₂. Just two machines are considered here. It is an interesting problem to consider general m machines system to design better algorithm.

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.

Cite this paper

Wang, L.M., Li, R.H. and Zhou, Y.X. (2019) Better Algorithm of Ordinal Online Schedule for Jobs with Similar Sizes on Two Machines. American Journal of Operations Research, 9, 235-243. https://doi.org/10.4236/ajor.2019.95015

References