工件具有相似加工时长时两台机上LPT算法的性能分析

Performance Analysis of LPT Algorithm for Jobs with Similar Sizes on Two Machines

摘要: 本文研究了工件具有相似加工时长时2台同类型平行机上LPT算法的最坏性能比。目标函数是使所有机器的最大完工时间达到最小。若工件序列L={J₁,J₂,...,J_n}中的工件满足p_j∈[1,r](r≥1)，证明了LPT算法的最坏性能比为r的分段线性函数，此结论改进了已有的最好结论，并且是不能再改进的最好结论。

Abstract: In this paper, LPT algorithm is considered for the scheduling problem in which the processing times of jobs are similar on two 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 if job list L={J₁,J₂,...,J_n} satisfies p_j∈[1,r](r≥1). Our result improves the best existing result. Furthermore, the ratio given here is the best. That means our result cannot be improved any more.

1. 引言

排序问题是组合优化的重要分支之一，在生产管理、计算机信息技术处理等方面具有广泛的应用背景。自从Graham [1] 在1969年首次提出排序问题以来，这个问题一直是最活跃的研究领域之一。经典排序问题是将n个独立工件 $J_1,J_2,\cdots ,J_n$ 分配到m台具有同样性能的机器 $M_1,M_2,\cdots ,M_m$ 上加工，每一个工件只需在其中一台机器上加工一次就能完工，每台机器每次只能加工一个工件。工件 $J_1,J_2,\cdots ,J_n$ 之间没有先后的依存关系，且 $J_i$ 的加工时间为 $p_i$ ，目标是使所有工件在最早时间内完成全部加工，也就是使得所有机器中最大完工时间达到最小。由于排序问题是NP-困难问题，我们目前只能研究多项式时间近似算法。LPT (Largest Processing time)算法是Graham [2] 提出的著名近似算法。该算法首先将工件排序使其满足 $p_1\ge p_2\ge \cdots \ge p_n$ ，然后依次安排每个工件，每次总是把尚未投入加工的工件中编号最小者(即加工时

长最大的)送到最早空闲的机器上进行加工。LPT算法的最坏性能比是 $\frac{4}{3}-\frac{1}{3m}$ 。

在经典排序问题的算法性能比分析中是假设工件的加工时长是任意的，但实际情况中，工件的加工时长不会太小，也不会太大。为了更符合实际，也为了改进算法的性能比，促使研究工作者对工件加工时长做出适当假设。工件加工时长具有相似加工长度(即假设工件加工时长在区间[1, r]内，其中 $r\ge 1$ )是常用假设之一 [3] - [8] ，也有假设工件最大时长已知的 [9] 及假设所有工件加工时长总和是已知的 [6] 。

H. Kellerer [10] 给出了在m台同类型平行机上当工件具有相似的加工时长时LPT算法的性能比的上界为

$R\left(m,LPT,\mu \right)\le \{\begin{array}{l}\frac{m\left(2k-2\right)-\mu \left(k-2\right)}{km}\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}\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}$

其中 $k\ge 3$ ，k为整数， $\frac{p_1}{p_n}=2-\frac{\mu }{m},\left(1\le \mu <m,\mu \in R\right)$ ，m表示机器数。当 $\mu \le \frac{m+3}{4}\left(k=3\right)$ 时， $\frac{4m-\mu }{3m}$ 是紧的，其它区间不是紧界。

本文考虑两台机情形，即 $m=2$ ，证明了LPT算法的最坏性能比为

$R\left(2,LPT,r\right)=\{\begin{array}{l}\frac{7}{6},r\ge \frac{3}{2},\\ \frac{kr+k+1}{2k+1},1+\frac{1}{2k}-\frac{2}{2k\left(2k+3\right)}\le r<1+\frac{1}{2k},\\ \frac{4k+7}{4k+6},1+\frac{1}{2k+2}\le r<1+\frac{1}{2k}-\frac{2}{2k\left(2k+3\right)},\\ 1r=1.\end{array}$

其中 $k\ge 1$ ，k为整数。

当 $\frac{11}{8}\le r\le \frac{3}{2}$ 时(相当于 [10] 里的 $\mu \in \left[1,\frac{5}{4}\right]$ ，我们得到的性能比和 [10] 一样。当 $r<\frac{11}{8}$ 时，我们得到的

最坏性能比比 [10] 的更小。

2. 定义符号

在本文中我们引入下面记号：

1) $L=\left\{J_1,J_2,\cdots ,J_n\right\}$ 为一个工件序列，其中每个工件J_j的加工长度为 $p_j,j=1,2,\cdots ,n$ ；

2) $p_{i\left(j\right)}$ 表示第i台机器上的第j个工件的加工时长；

3) $L_i\left(i=1,2,\cdots ,m\right)$ 表示在LPT算法下最后一个工件J_n被安排之前机器M_i上所安排的所有工件加工时长的总和。并且我们将机器重新编号，使之满足 $L_1\le L_2\le \cdots \le L_m$ ；

4) 设A是任一算法， $C_{\max }^A\left(L\right)$ 表示工件集L在算法A下所有机器的最大完工时间；

5) OPT表示最优算法。

定义1：算法A是一个近似算法， $C_{\max }^A\left(L\right)$ 和 $C_{\max }^{OPT}\left(L\right)$ 分别表示在A算法和最优算法下该工件序列的

最大完工时间。定义

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

并称其为算法A的最坏性能比，其中 $L=\left\{J_1,J_2,\cdots ,J_n\right\}$ 为任一符合条件的工件序列。

下面我们分析LPT算法在两台机上的最坏性能比。

3. 定理及其证明

对于任意工件序列 $L=\left\{J_1,J_2,\cdots ,J_n\right\}$ ，易知

$C_{\max }^{OPT}\left(L\right)\ge \frac{{\displaystyle {\sum }_{j=1}^n{p}_j}}{m}$ (1)

其中m为机器台数。

在没有特别说明的情形下，下面我们总是假设工件序列 $L=\left\{J_1,J_2,\cdots ,J_n\right\}$ 满足， $p_i\in \left[1,r\right],p_1\ge p_2\ge \cdots \ge p_n$ ，并且总是假设 $m=2$ 。

定理1. 当 $m=2$ 时，LPT算法的最坏性能比为：

$R\left(2,LPT,r\right)=\{\begin{array}{ll}\frac{7}{6},\hfill & r\ge \frac{3}{2},\hfill \\ \frac{kr+k+1}{2k+1},\hfill & 1+\frac{1}{2k}-\frac{2}{2k\left(2k+3\right)}\le r<1+\frac{1}{2k},\hfill \\ \frac{4k+7}{4k+6},\hfill & 1+\frac{1}{2k+2}\le r\le 1+\frac{1}{2k}-\frac{2}{2k\left(2k+3\right)},\hfill \\ 1\hfill & r=1.\hfill \end{array}$

其中 $k\ge 1$ ，k为整数。

证明： $r\ge \frac{3}{2}$ 时的结论即是Graham [2] 给出的 $R\left(2,LPT\right)=\frac{4}{3}-\frac{1}{3m}$ 当 $m=2$ 时的情形。当 $r=1$ 时，所有工件的加工时长都一样，显然LPT算法也是最优算法，所以结论显然成立。下面讨论 $\frac{2k+3}{2k+2}\le r<\frac{2k+1}{2k}$

的情形。我们首先证明对任意满足条件的工件序列L，下面不等式成立：

$\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \{\begin{array}{ll}\frac{kr+k+1}{2k+1}\hfill & 1+\frac{2k+1}{2k\left(2k+3\right)}\le r<\frac{2k+1}{2k},\hfill \\ \frac{4k+7}{4k+6}\hfill & \frac{2k+3}{2k+2}\le r<1+\frac{2k+1}{2k\left(2k+3\right)}.\hfill \end{array}$ (2)

如果(2)不成立，设 $L=\left\{J_1,J_2,\cdots ,J_n\right\}$ 是使(2)不成立且工件个数n最小的工件序列，这样的工件序列我们称之为最小反例。对于最小反例，易知最后一个工件J_n是最后完工的工件，即 $C_{\max }^{LPT}\left(L\right)=L_1+p_n$ 。

所以当 $1+\frac{2k+1}{2k\left(2k+3\right)}\le r<\frac{2k+1}{2k}$ 时，我们有

$\begin{array}{c}\frac{kr+k+1}{2k+1}<\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}=\frac{2\left(L_1+p_n\right)}{2C_{\max }^{OPT}\left(L\right)}\\ \le \frac{L_1+L_2+2p_n}{2C_{\max }^{OPT}\left(L\right)}=\frac{{\displaystyle {\sum }_{j=1}^n{p}_j+p_n}}{2C_{\max }^{OPT}\left(L\right)}\\ \le 1+\frac{p_n}{2C_{\max }^{OPT}(L)}\end{array}$

最后不等式由(1)得。即

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

当 $\frac{2k+3}{2k+2}\le r<1+\frac{2k+1}{2k\left(2k+3\right)}$ 时，我们同样可得(3)。因此，对于最小反例L，其总工件个数 $n\le 4k+\text{4}$ 。

下面我们令

$S_i=\left\{j|J_j在LPT算法下安排在M_i上并且j\ne n\right\},i=1,2$ ； $S_i{}^{*}=\left\{j|J_j在OPT算法下安排在M_i上\right\},i=1,2$ 。

易知 $\left|S_1\cup S_2\right|=n-1,\left|S_1^{*}\cup S_2^{*}\right|=n$ 。

为了完成定理1的证明，我们首先给出下面的几个引理。

引理2. 对最小反例L，在LPT算法下， $J_{2i-1}$ 和 $J_{\text{2}i}$ 安排在不同机器上 $\left(i=1,2,\cdots ,2k,2k+1\right)$ 。

证明：假设不然，设 $i_0$ 是使 $J_{2i-1}$ 和 $J_{\text{2}i}$ 为第一对被LPT算法安排在同一台机器上的两个工件，不失一般性，假设都安排在 $M_2$ 上，那么在 $J_{2i_0-1}$ 和 $J_{\text{2}{i}_0}$ 安排之前， $M_1,M_2$ 上的工件集 ${S^{\prime }}_1,{S^{\prime }}_2$ 满足 $\left|{S^{\prime }}_1\right|=\left|{S^{\prime }}_2\right|=i_0-1$ ，

则由LPT算法规则下面不等式必然成立：

$\left(i_0-1\right)r\ge {\displaystyle \underset{j\in {S^{\prime }}_1}{\sum }{p}_j\ge {\displaystyle \underset{j\in {S^{\prime }}_2}{\sum }{p}_j}+p_{2i_0-1}}\ge i_0$

所以有 $r\ge \frac{i_0}{i_0-1}\ge 1+\frac{1}{2k}$ 。这显然与 $r<1+\frac{1}{2k}$ 矛盾，即引理得证。

由引理2可以得出，在LPT算法下未安排工件 $J_{4k+4}$ 时，两台机器上的工件个数相差不会超过1。

引理3. 对最小反例L，若 $\left|S_1^{*}\right|\ge \left|S_2^{*}\right|$ ，则 $\left|S_1\cap S_1^{*}\right|\ge \left|S_1\cap S_2^{*}\right|$ 和 $\left|S_2\cap S_1^{*}\right|\ge \left|S_2\cap S_2^{*}\right|$ 至少有一个成立。

证明：若 $\left|S_i\cap S_1^{*}\right|<\left|S_i\cap S_2^{*}\right|\left(i=1,2\right)$ 成立，则 $\left|\left(S_1\cup S_2\right)\cap S_1^{*}\right|\le \left|\left(S_1\cup S_2\right)\cap S_2^{*}\right|+2$ 成立。由定义我们有

$\left|\left(S_1\cup S_2\right)\cap S_i^{*}\right|=\{\begin{array}{ll}\left|S_i^{*}\right|\hfill & n\notin S_i^{*}\hfill \\ \left|S_i^{*}\right|-1\hfill & n\in S_i^{*}\hfill \end{array}$

这样我们有 $\left|S_1^{*}\right|-1\le \left|S_2^{*}\right|+2\left(n\in S_1^{*}\right)$ 或者 $\left|S_1^{*}\right|\le \left|S_2^{*}\right|+1\left(n\in S_2^{*}\right)$ ，此时都与假设 $\left|S_1^{*}\right|\ge \left|S_2^{*}\right|$ 矛盾。

引理4. 设 $p,q\in \left\{1,2\right\}$ ，令 $\bar{q}=q\mathrm{mod}2+1$ ，即 $q=1$ 时 $\bar{q}=2$ ，而 $q=2$ 时 $\bar{q}=1$ 。若 $\left|S_p\right|\le k_0$ ， $\left|S_q^{*}\right|\ge k_0+1$ ， $\left|S_p\cap S_q^{*}\right|\ge \left|S_p\cap S_{\bar{q}}^{*}\right|$ 且 $k_0\le 2k$ ，则有

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

证明：由 $C_{\max }^{LPT}\left(L\right)\le {\displaystyle {\sum }_{j\in S_p}{p}_j}+p_n$ 和 $C_{\max }^{OPT}\left(L\right)\ge {\displaystyle {\sum }_{j\in S_q^{*}}{p}_j}$ 得

$\begin{array}{c}\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{{\displaystyle {\sum }_{j\in S_p}{p}_j}+p_n}{{\displaystyle {\sum }_{j\in S_q^{*}}{p}_j}}=\frac{{\displaystyle {\sum }_{j\in S_p\cap S_{\bar{q}}^{*}}{p}_j}+{\displaystyle {\sum }_{j\in S_p\cap S_q^{*}}{p}_j}+p_n}{{\displaystyle {\sum }_{j\in S_q^{*}\backslash S_p}{p}_j}+{\displaystyle {\sum }_{j\in S_p\cap S_q^{*}}{p}_j}}\\ \le \frac{{\displaystyle {\sum }_{j\in S_p\cap S_{\bar{q}}^{*}}{p}_j}+\left|S_p\cap S_q^{*}\right|+1}{{\displaystyle {\sum }_{j\in S_q^{*}\backslash S_p}{p}_j}+\left|S_p\cap S_q^{*}\right|}\le \frac{\left|S_p\cap S_{\bar{q}}^{*}\right|r+\left|S_p\cap S_q^{*}\right|+1}{\left|S_p\cap S_q^{*}\right|+\left|S_q^{*}\backslash S_p\right|}\\ =\frac{\left|S_p\cap S_{\bar{q}}^{*}\right|r+\left|S_p\cap S_q^{*}\right|+\left|S_p\cap S_{\bar{q}}^{*}\right|r+\left|S_p\cap S_q^{*}\right|+2}{2\left|S_q^{*}\right|}\\ \le \frac{\left|S_p\cap S_q^{*}\right|r+\left|S_p\cap S_{\bar{q}}^{*}\right|+\left|S_p\cap S_{\bar{q}}^{*}\right|r+\left|S_p\cap S_q^{*}\right|+2}{2\left|S_q^{*}\right|}\\ \le \frac{\left|S_p\right|r+\left|S_p\right|+2}{2\left|S_q^{*}\right|}=\frac{k_{0}r+k_0+2}{2k_0+2}\le \frac{kr+k+1}{2k+1}\end{array}$

上面第二个不等式是因为 $p_n\ge 1$ 和函数 $f\left(x\right)=\frac{a+x}{b+x}\left(a\ge b>0\right)$ 在 $x\ge 0$ 里是x的减函数，第四个不等式由引理3得，最后一个不等式是因为 $k_0\le 2k$ 和函数 $g\left(x,y\right)=\frac{\left(r+1\right)x+2}{2x+2}$ 是 $x\ge 0$ 的增函数。

引理5. 设 $p,q\in \left\{1,2\right\}$ ，令 $\bar{q}=q\mathrm{mod}2+1$ 。若 $\left|S_P\right|\le 2k_0+1$ ， $\left|S_q^{*}\right|\ge 2k_0+2$ 且 $k_0\le k$ ，则有(4)。

证明：与引理4的证明类似可得

$\begin{array}{c}\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \frac{{\displaystyle {\sum }_{j\in S_p\cap S_{\bar{q}}^{*}}{p}_j}+{\displaystyle {\sum }_{j\in S_p\cap S_q^{*}}{p}_j}+p_n}{{\displaystyle {\sum }_{j\in S_q^{*}\backslash S_p}{p}_j}+{\displaystyle {\sum }_{j\in S_p\cap S_q^{*}}{p}_j}}\\ \le \frac{\left|S_p\cap S_{\bar{q}}^{*}\right|r+\left|S_p\cap S_q^{*}\right|+1}{\left|S_p\cap S_q^{*}\right|+\left|S_q^{*}\backslash S_p\right|}\\ =\frac{\left|S_p\cap S_{\bar{q}}^{*}\right|\left(r-1\right)+\left|S_p\right|+1}{\left|S_q^{*}\right|}\\ \le \frac{k_{0}r+k_0+2}{2k_0+2}\le \frac{kr+k+1}{2k+1}\end{array}$

上面最后一个不等式是因为函数 $g\left(x,y\right)=\frac{\left(r+1\right)x+y}{2x+y}$ 是 $x\ge 0$ 的增函数，是 $y\ge 0$ 的减函数。

由(3)，我们下面分 $n=2k^{\prime }+1,2k^{\prime }+2\left(k^{\prime }\le 2k\right)$ 和 $n=4k+3,4k+4$ 这4种情况证明(4)成立。

情况1. $n=2k^{\prime }+1,k^{\prime }\le 2k$ 。

由 $\left|S_1^{*}\right|+\left|S_2^{*}\right|=2k^{\prime }+1$ 不妨设 $\left|S_1^{*}\right|\ge k^{\prime }+1$ 。由引理2得 $\left|S_1\right|=\left|S_2\right|=k^{\prime }$ ，由引理3知， $\left|S_1\cap S_1^{*}\right|\ge \left|S_1\cap S_2^{*}\right|$ 和 $\left|S_{\text{2}}\cap S_1^{*}\right|\ge \left|S_{\text{2}}\cap S_2^{*}\right|$ 至少有一个成立。若 $\left|S_1\cap S_1^{*}\right|\ge \left|S_1\cap S_2^{*}\right|$ 成立。则令 $p=1,q=1,k_0=k^{\prime }$ ，由引理4得(4)成立。若 $\left|S_{\text{2}}\cap S_1^{*}\right|\ge \left|S_{\text{2}}\cap S_2^{*}\right|$ 成立。则令 $p=2,q=1,k_0=k^{\prime }$ ，由引理4也得(4)成立。

情况2. $n=2k^{\prime }+2,k^{\prime }\le 2k$ 。

由引理2不妨设有 $\left|S_1\right|=k^{\prime },\left|S_2\right|=k^{\prime }+1,\left|S_1^{*}\right|\ge k^{\prime }+1$ 。若 $\left|S_1\cap S_1^{*}\right|\ge \left|S_1\cap S_2^{*}\right|$ ，则令

$p=1,q=1,k_0=k^{\prime }$ ，由引理4得(4)成立。

若 $\left|S_1\cap S_1^{*}\right|\ge \left|S_1\cap S_2^{*}\right|$ 不成立，此时若有 $\left|S_2^{*}\right|\ge k^{\prime }+1$ ，令 $p=1,q=2,k_0=k^{\prime }$ ，由引理4得(4)成立。否则有 $\left|S_2^{*}\right|\le k^{\prime }$ ，因而 $\left|S_1^{*}\right|\ge k^{\prime }+2$ 。则由引理3知 $\left|S_2\cap S_1^{*}\right|\ge \left|S_2\cap S_2^{*}\right|$ 成立，这时令 $p=2,q=1,k_0=k^{\prime }+1$ ，由引理4知当 $k^{\prime }<2k$ 时(4)成立。

若 $\left|S_1\cap S_1^{*}\right|\ge \left|S_1\cap S_2^{*}\right|$ 不成立，且 $\left|S_2^{*}\right|\le k^{\prime }$ 和 $k^{\prime }=2k$ 成立，令 $p=1,q=2,k_0=k^{\prime }$ ，由引理5知(4)成立，因为由 $\left|S_1\cap S_1^{*}\right|\le \left|S_1\cap S_2^{*}\right|$ 可得 $\left|S_1\cap S_1^{*}\right|\le k$ 。

情况3. $n=4k+3$ 。

不妨设 $\left|S_1^{*}\right|>\left|S_2^{*}\right|$ 。由引理2及(3)知 $\left|S_1^{*}\right|=2k+2$ 且 $\left|S_1\right|=\left|S_2\right|=2k+1$ 。由引理3知 $\left|S_1\cap S_1^{*}\right|\ge \left|S_1\cap S_2^{*}\right|$ 和 $\left|S_2\cap S_1^{*}\right|\ge \left|S_2\cap S_2^{*}\right|$ 中至少有一个成立。若 $\left|S_1\cap S_1^{*}\right|\ge \left|S_1\cap S_2^{*}\right|$ 成立，则有 $\left|S_1\cap S_1^{*}\right|\ge k+1$ ， $\left|S_1\cap S_2^{*}\right|\le k$ 。令 $p=1,q=1,k_0=k$ ，则由引理5即得(4)成立。

若 $\left|S_1\cap S_1^{*}\right|\ge \left|S_1\cap S_2^{*}\right|$ 不成立，则必有 $\left|S_2\cap S_1^{*}\right|\ge \left|S_2\cap S_2^{*}\right|$ 成立，所以有 $\left|S_2\cap S_1^{*}\right|\ge k+1$ ， $\left|S_2\cap S_2^{*}\right|\le k$ $p=\text{2},q=1,k_0=k$ 则由引理5即得(4)成立。

情况4. $n=4k+\text{4}$ 。

由(3)得 $\left|S_1^{*}\right|=\left|S_2^{*}\right|=2k+2$ 。由引理2可不妨设 $\left|S_1\right|=2k+1,\left|S_2\right|=2k+2$ 。

若 $\left|S_1\cap S_1^{*}\right|\ge k+1$ 成立，则有 $\left|S_1\cap S_2^{*}\right|\le k$ 这时令 $p=1,q=1,k_0=k$ ，则由引理5即得(4)成立。由于 $\left|S_1\cap \left(S_1^{*}\cup S_2^{*}\right)\right|=2k+1$ ，若 $\left|S_1\cap S_1^{*}\right|\ge k+1$ 不成立，则 $\left|S_1\cap S_2^{*}\right|\ge k+1$ 成立，因而有 $\left|S_1\cap S_1^{*}\right|\le k$ ，这时令 $p=1,q=\text{2},k_0=k$ ，则由引理5也得(4)成立。

由上所述可知

$\begin{array}{c}\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}\le \max \left\{\frac{kr+k+1}{2k+1},\frac{4k+7}{4k+6}\right\}\\ =\{\begin{array}{ll}\frac{kr+k+1}{2k+1},\hfill & 1+\frac{2k+1}{2k\left(2k+3\right)}\le r<\frac{2k+1}{2k}\hfill \\ \frac{4k+7}{4k+6},\hfill & \frac{2k+3}{2k+2}\le r<1+\frac{2k+1}{2k\left(2k+3\right)}\hfill \end{array}\end{array}$

下面我们分别给出上面不等式等号成立的实例：

当 $\text{1}+\frac{\text{2}k+1}{2k\left(2k+3\right)}\le r\le \frac{2k+1}{2k}$ 时，我们令 $L=\left\{J_1,J_2\text{,}\cdots ,J_{4k+1}\right\}$ ，其相应的加工时长为 $\left\{r,r,\cdots ,r,1,1,\cdots ,1\right\}$ ，其中时长为r和1的工件分别有2k和 $\text{2}k+\text{1}$ 个。在LPT算法下， $M_1$ 上安排时长为r和1的工件各 $k,k+1$ 个， $M_{\text{2}}$ 上安排时长为r和1的工件各k个，故 $C_{\max }^{\text{L}PT}\left(L\right)=kr+k+1$ 。

在OPT算法下， $M_1$ 上安排时长为r的工件2k个， $M_{\text{2}}$ 上安排时长为1的工件 $\text{2}k+\text{1}$ 个，故 $C_{\max }^{OPT}\left(L\right)=\text{2}k+1$ ，即

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

当 $\frac{\text{2}k+\text{3}}{2k+\text{2}}\le r<\text{1}+\frac{2k+1}{2k\left(2k+3\right)}$ 时，我们分别给出k为奇数和偶数时紧界的实例：

当k为奇数时，令 $L=\left\{J_1,J_2\text{,}\cdots ,J_{4k+\text{5}}\right\}$ ，其相应加工时长为 $\left\{r,r,\cdots ,r,r^{\prime },r^{\prime },\cdots ,r^{\prime },1,1,\cdots ,1\right\}$

时长为r和 $r^{\prime }$ 的各有 $k+\text{1}$ 个，时长为1的有 $\text{2}k+\text{3}$ 个，并且满足

$1<r^{\prime }<r,r+r^{\prime }=\frac{2k+3}{k+1}$

在LPT算法下， $M_1$ 上安排时长为r和 $r^{\prime }$ 的工件各有 $\frac{k+1}{\text{2}}$ 个，安排 $k+\text{2}$ 个时长为1的工件。 $M_{\text{2}}$ 上安排时长分别为r和 $r^{\prime }$ 的工件各 $\frac{k+1}{\text{2}}$ 个，时长为1的工件 $k+\text{1}$ 个。则

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

在OPT算法下， $M_1$ 上安排时长为r和 $r^{\prime }$ 的工件各 $k+\text{1}$ 个， $M_{\text{2}}$ 上安排 $\text{2}k+\text{3}$ 个时长为1的工件，

则 $C_{\max }^{OPT}\left(L\right)=2k+3$ ，故

$\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}=\frac{\text{4}k+\text{7}}{\text{4}k+\text{6}}$

当k为偶数时，令 $L=\left\{J_1,J_2\text{,}\cdots ,J_{4k+\text{5}}\right\}$ ，其相应加工时长为 $\left\{r,r,\cdots ,r,r^{\prime },r^{\prime },\cdots ,r^{\prime },r^{″},r^{″},1,1,\cdots ,1\right\}$ 长分别为r和 $r^{\prime }$ 的各有k个，时长为 $r^{″}$ 的工件有2个，时长为1的有 $2k+\text{3}$ 个，并且满足

$1<r^{″}<r^{\prime }<r,k\left(r+r^{\prime }\right)+2r^{″}=2k+3$

在LPT算法下， $M_1$ 上安排时长为r和 $r^{\prime }$ 的工件各 $\frac{k}{2}$ 个，安排1个时长为 $r^{″}$ 的工件和 $k+\text{2}$ 个时长为1的工件。 $M_{\text{2}}$ 上安排时长分别为r和 $r^{\prime }$ 的工件各 $\frac{k}{2}$ 个和1个时长为 $r^{\text{'}\text{'}}$ 的工件以及 $k+1$ 个时长为1的工件。则

$C_{\max }^{LPT}\left(L\right)=\frac{k\left(r+r^{\prime }\right)}{2}+r^{″}+k+2$

在OPT算法下， $M_1$ 上安排时长为r和 $r^{\prime }$ 的工件各k个，以及2个 $r^{″}$ ，在 $M_{\text{2}}$ 上安排 $2k+\text{3}$ 个时长为1的工件，则 $C_{\max }^{OPT}\left(L\right)=2k+3$ 故：

$\frac{C_{\max }^{LPT}\left(L\right)}{C_{\max }^{OPT}\left(L\right)}=\frac{\text{4}k+\text{7}}{\text{4}k+\text{6}}$

综上可知，定理1得证。

4. 小结

本文主要研究了工件具有相似加工时长时，LPT算法在同型平行机上的最坏性能比。证明了当 $m=2$ 时对于任意的工件序列L，LPT算法的最坏性能比为

$R\left(2,LPT,r\right)=\{\begin{array}{ll}\frac{7}{6},\hfill & r\ge \frac{3}{2},\hfill \\ \frac{kr+k+1}{2k+1},\hfill & 1+\frac{1}{2k}-\frac{2}{2k\left(2k+3\right)}\le r<1+\frac{1}{2k},\hfill \\ \frac{4k+7}{4k+6},\hfill & 1+\frac{1}{2k+2}\le r\le 1+\frac{1}{2k}-\frac{2}{2k\left(2k+3\right)},\hfill \\ 1\hfill & r=1.\hfill \end{array}$

其中 $k\ge 1$ ，k为整数。

本文成果改进了已有的最好结果，并且这是不能改进的最好结果。本文的分析比较复杂，更有趣的问题是能否改进一般性m台机时的最坏性能比。

基金项目

本文得到国家自然科学基金(编号11471110)和湖南省教育厅重点课题(编号16A126)资助。

NOTES

^*通讯作者。