1 引言
我们研究的问题可简记为$1|d_{j}=d|\Sigma w_{j}T_{j}$, 这是一个经典的排序模型.最小化加权总误工问题在实际中经常遇到, 然而有关的结果却并不是很多, 由于对工期为任意值的问题的研究相当困难, 因此近来对特殊工期的模型的研究比较多.已知问题$1\|\Sigma
w_{j}T_{j}$是强NP-困难的[1, 2], Potts和Van Wassenhove[3]给出了该问题的分支定界算法, Schrage和Baker[4]利用动态规划的方法得到了$O(2^n)$时间的算法, Cheng等人[5]给出了此问题的$O(n^2)$时间的近似算法.对于特殊工期的模型研究集中在具有相同工期$d=d_{j}$, 工期等量松弛$(SLK)$ $d_{j}=p_{j}+q$, 其中$q$为给定的常数, 以及更一般情形工时加等待工期$(PPW)$ $d_{j}=\alpha p_{j}+q$, 其中$\alpha$、$q$都为给定的常数.除了研究特殊工期模型, 还有一些学者则关注了在其他参数上进行特殊限制的情形.如问题$1|w_{j}=1|\Sigma w_{j}T_{j}$,
$1|w_{j}=kp_{j}|\Sigma w_{j}T_{j}$, $1|p_{j}=p|\Sigma w_{j}T_{j}$在文献[1, 2, 6, 7]中都有所研究.对于我们研究的问题$1|d_{j}=d|\Sigma
w_{j}T_{j}$, 已知有下面的引理:
引理1.1[8] 问题$1|d_{j}=d|\Sigma
w_{j}T_{j}$是一般意义下的NP-困难问题.
Lawler和Moore[9]已经对该问题给出了一个拟多项式时间算法, 我们将给出该问题的FPTAS算法, 方法类似于Cheng等人在文[5]中对问题$1|d_{j}=p_{j}+q|\Sigma w_{j}T_{j}$给出的算法, 即将问题$1\| \Sigma w_{j}T_{j}$的近似算法得到的目标值作为问题$1|d_{j}=d|\Sigma
w_{j}T_{j}$的一个上界, 从而得到我们的结果.
下面首先介绍一下Cheng等对问题$1\| \Sigma
w_{j}T_{j}$设计的近似算法“Modified Lawler's Algorithm”.它可以描述如下:有$n$个工件, 设每个工件$J_{j}$的加工时间为$p_{j}$, 工期为$d_{j}$, 权重为$w_{j}$, $1\leq j \leq
n$.对每个工件, 将工期修改为$d'_{j}=\max\{p_{j}, d_{j}\}$, 这样得到一个排序$\pi^{*}$使得目标函数$g(\pi)=\max\limits_{1\leq
j\leq n}w_{j}T'_{j}(\pi)$最小, 其中
| $
T'_{j}(\pi)=\max\{0, C_{j}(\pi)-d'_{j}\},
$ |
则$\pi^{*}$为原问题的一个近似解.下面是该算法的具体步骤:
Modified Lawler's算法:
第一步 修改工期为$d'_{j}=\max\{p_{j}, d_{j}\}$, $1\leq j \leq n$;
第二步 令$k:=n$, $\mathcal {J}:=\{J_{1}, J_{2}, \cdots, J_{n}\}$,
$P:=\sum\limits_{j=1}^{n}p_{j}$;
第三步 对所有的$J_{j}\in \mathcal {J}$, 选择使$w_{j}\times
\max\{0, P-d'_{j}\}$最小的工件$J_{i}$, 然后令$\pi^{*}(k)=i$;
第四步 令$k:=k-1$, $\mathcal {J}:=\mathcal {J}\backslash
\{J_{i}\}$且$P:=P-p_{i}$;
第五步 如果$k=0$, 则停止; 否则, 转回第三步.
引理1.2[9] 对于问题$1\| \Sigma w_{j}T_{j}$, Modified Lawler's算法是一个$(n-1)-$近似算法, 时间复杂性为$O(n^2)$.
2 动态规划算法
下面我们将要研究问题$1|d_{j}=d|\Sigma w_{j}T_{j}$的有效算法:
引理2.1 对问题$1|d_{j}=d|\Sigma
w_{j}T_{j}$的任意给定的排序$\pi$, 如果$J_{k}(\pi)$是误工工件, 则$J_{i}(\pi) (k\leq i\leq n)$也为误工工件, 且有
| $
T_{i}(\pi)=T_{k}(\pi)+\sum\limits_{j=k+1}^{i}p_{i}(\pi).
$ |
证 注意到$C_{k}(\pi)=T_{k}(\pi)+d_{k}(\pi)=T_{k}(\pi)+d$, 因此, 对$k\leq i\leq n$有
| $
C_{i}(\pi)=C_{k}(\pi)+\sum\limits_{j=k+1}^{i}p_{j}(\pi)=T_{k}(\pi)+\sum\limits_{j=k+1}^{i}p_{i}(\pi)+d,
$ |
即
| $
T_{i}(\pi)=T_{k}(\pi)+\sum\limits_{j=k+1}^{i}p_{j}(\pi).
$ |
引理2.2 对问题$1|d_{j}=d|\Sigma w_{j}T_{j}$, 设$J_{k}(\pi)$是最优排序$\pi$下第一个误工工件, 则以下结论成立:
(1) $\frac{w_{k}(\pi)}{p_{k}(\pi)}\geq\frac{w_{k+1}(\pi)}{p_{k+1}(\pi)}\geq\cdots\geq\frac{w_{n}(\pi)}{p_{n}(\pi)}$;
(2) 如果存在两个工件$J_{i}(\pi)$和$J_{t}(\pi)$满足$i, t\geq k$且$\frac{w_{i}(\pi)}{p_{i}(\pi)}= \frac{w_{t}(\pi)}{p_{t}(\pi)}$, 则交换$i$和$t$的位置得到的仍为最优排序;
(3) 前$k-1$个不误工工件按任意顺序排列都不影响最优排序.
证 (1) 令$\pi$是一个最优排序, 但不满足$\frac{w_{k}(\pi)}{p_{k}(\pi)}\geq\frac{w_{k+1}(\pi)}{p_{k+1}(\pi)}\geq\cdots\geq\frac{w_{n}(\pi)}{p_{n}(\pi)}$.则在$\pi$中一定至少存在两个相邻的工件假设$J_{l}$和$J_{m}$, 满足$k\leq l<m$且$\frac{w_{l}(\pi)}{p_{l}(\pi)}<\frac{w_{m}(\pi)}{p_{m}(\pi)}$.设工件$J_{l}$的开始时间为$S_{l}(\pi)$, 我们可以交换工件$J_{l}$和$J_{m}$的位置得到一个新的排序$\pi'$.则有
| $
\begin{array}{l}
{C_l}(\pi ) = {S_l}(\pi ) + {p_l}(\pi ),{C_m}(\pi ) = {S_l}(\pi ) + {p_l}(\pi ) + {p_m}(\pi ),\\
{C_m}(\pi ') = {S_l}(\pi ) + {p_m}(\pi ),{C_l}(\pi ') = {S_l}(\pi ) + {p_m}(\pi ) + {p_l}(\pi ).
\end{array}
$ |
因为设$J_{k}(\pi)$是$\pi$下第一个误工工件, 则由引理2.1, 目标值可以写为
| $
f(\pi)=\sum\limits_{j=k}^{n}w_{j}(\pi)C_{j}(\pi)-\sum\limits_{j=k}^{n}w_{j}(\pi)d.
$ |
那么
| $
\begin{eqnarray*}f(\pi)-f(\pi')=&(w_{l}(\pi)C_{l}(\pi)+w_{m}(\pi)C_{m}(\pi))-(w_{l}(\pi')C_{l}(\pi')+w_{m}(\pi')C_{m}(\pi'))\\
=&w_{m}(\pi)p_{l}(\pi)-w_{l}(\pi)p_{m}(\pi)=w_{l}(\pi)w_{m}(\pi)(\frac{p_{l}(\pi)}{w_{l}(\pi)}-\frac{p_{m}(\pi)}{w_{m}(\pi)})>0,
\end{eqnarray*}
$ |
与$\pi$的最优性矛盾.故结论(1) 成立.
(2) 类似于(1) 的证明由二交换法可证得.
(3) 由于$J_{1}(\pi), \cdots, J_{k-1}(\pi)$是不误工工件, 则$C_{j}(\pi)\leq d \ (j=1, \cdots, k-1)$, 因此有$\sum\limits_{j=1}^{k-1}p_{j}(\pi)\leq d$, 故前$k-1$个不误工工件按任意顺序排列都能保证它们不误工.
我们将满足以上三条的排序$\pi$称为一个正规排序, 以下我们只考虑正规排序.下面是算法的思想:假设先将工件按WLPT序排好, 即$\frac{w_{1}}{p_{1}}\leq\frac{w_{2}}{p_{2}}\leq\cdots\leq\frac{w_{n}}{p_{n}}$.令
| $
\begin{array}{l}
P = {p_1} + {p_2} + \cdots + {p_n},\\
{\mathcal {J}_j} = \{ {J_1},{J_2} \cdots ,{J_j}\} ,\\
P(j) = {p_1} + {p_2} + \cdots + {p_j}\;(1 \le j \le n).
\end{array}
$ |
对每一个$j$, 我们构造一个包含三元组$(X, t, c)$的所有可能性的集合$M_{j}$, 使得下面三条成立:
1. $X\subseteq \mathcal {J}_{j}$为正规排序$\pi$下最后$|X|$个误工工件的集合, 则$\mathcal {J}_{j}\backslash X$为$\pi$下不误工工件的集合.
2. $t=P-\sum\limits_{J_{i}\in X}p_{i}$是$\pi$下$X$中第一个误工工件的开始时间.
3. $c$为$\pi$下$X$中所有工件的加权误工时间总和.
实际中, 一些无用的三元组将会从$M_{j}$中删除掉.我们用$SL=(X, c)$表示存在一个正规排序, 其中集合$X$包含所有的误工工件, $c$为加权误工时间和.
一开始, 令$M_{0}=\{(\emptyset, P, 0)\}$, 且$SL=(\emptyset, +\infty)$.由于$\frac{w_{1}}{p_{1}}$是$\frac{w_{i}}{p_{i}}
(1\leq i\leq n)$中最小的, 由引理4知或者存在一最优排序$\pi$使得$J_{1}$是$\pi$下最后一个误工工件, 或者存在一个最优排序$\pi'$使得$J_{1}$是$\pi'$下的不误工工件.对第一种情形, 则$M_{1}$应包含三元组$(\{J_{1}\}, P-p_{1}, w_{1}(P-d)|P>d)$; 对第二种情形, 则$M_{1}$应包含三元组$(\emptyset, P, 0)$, 故
| $
M_{1}=\{(\emptyset, P, 0)\}\cup\{(\{J_{1}\}, P-p_{1}, w_{1}(P-d)|P>d)\}.
$ |
一般地, 假设$M_{j-1}$已确定, 对每个$(X, t, c)\in M_{j-1}$, 存在一族正规排序$\{\sigma\}$, 使得在$\sigma$下$X$中最后$|X|$个误工工件按WSPT序排列, 且$\sigma$下$\mathcal {J}_{j}\backslash
X$中的为不误工工件, 由$\sigma$的正规性, $J_{j}$或者是$\sigma$下的不误工工件, 或者是$\sigma$下工件集$\{J_{j}, J_{j+1}, \cdots, J_{n}\}$中的最后一个误工工件.
如果$J_{j}$是不误工的, 则为确保$\mathcal {J}_{j}\backslash X$中工件按时完工, 我们必须有$P(j)-(P-t)\leq
d$.也即是这种情况下存在一族正规排序$\{\sigma'\}\subseteq\{\sigma\}$使得$\sigma'$下$X$中最后$|X|$个误工工件以WSPT序排列, $\mathcal{J}_{j}\backslash X$中的工件为$\sigma'$下的不误工工件,
$\sigma'$下$X$中工件的开始时间为$t$, 且$\sigma'$下$X$中工件的加权误工时间和为$c$.结构见图 1.
如果工件$J_{j}$为误工工件, 我们须有$t>d$.也就是说这种情况下, 存在一族正规排序$\{\sigma''\}\subseteq\{\sigma\}$使得$\sigma''$下最后$|X|+1$个误工工件是$X\cup\{J_{j}\}$中工件按WSPT序排列, 且工件$J_{j}$是工件集$X\cup\{J_{j}\}$中的第一个误工工件,
$\mathcal {J}_{j}\backslash(X\cup \{J_{j}\})=\mathcal
{J}_{j-1}\backslash X$是$\sigma''$下的不误工工件,
$\sigma''$下$X\cup\{J_{j}\}$中工件的开始时间为$t-p_{j}$,
$\sigma''$下$X\cup\{J_{j}\}$中工件的加权误工时间总和为$c+w_{j}(t-d)$.结构见图 2.
因此, 我们令
| $
\begin{array}{l}
{M_j}\;\; = \;\;\{ (X,t,c)|(X,t,c) \in {M_{j - 1}},P(j) - (P - t) \le d\} \\
\;\;\;\;\;\;\;\;\;\;\;\; \cup \{ (X \cup \{ {J_j}\} ,t - {p_j},c + {w_j}(t - d))|(X,t,c) \in {M_{j - 1}},t > d\} .
\end{array}
$ |
为了减少计算量, 假如在$M_{j}$中有两个不同的元素$(X_{1}, t_{1}, c_{1})$和$(X_{2}, t_{2}, c_{2})$且$t_{1}\leq t_{2}, c_{1}\leq c_{2}$, 则元素$(X_{2}, t_{2}, c_{2})$可以删去不再考虑.证明见本节附录1.我们在下面的算法$G$中令$t$相同, 比较$c$, 进而删减元素.
另外, 如果$(X, t, c)$是$M_{j}$中的元素满足$t\leq d$且$c$是最小的, 则存在一个正规排序$\pi$满足误工工件集为$X$且$c$为加权误工时间和.证明见本节附录2.因此, 如果$c<b$ (其中$b$是$SL$的第二部分), 我们将改写$SL$为$SL:=(X, c)$, 然后从$M_{j}$中删除所有满足$c'\geq
c$的元素$(X', t', c')$.根据以上讨论可以得到下面的算法:
算法 A
输入: $n$个工件$J_{1}, J_{2}, \cdots, J_{n}$, 加工时间和权重分别为$p_{j}$和$w_{j} (j=1, 2, \cdots, n)$, 工期为$d$.不失一般性, 我们可以假设工件已经按WLPT序排好, 即$\frac{w_{1}}{p_{1}}\leq\frac{w_{2}}{p_{2}}\leq\cdots\leq\frac{w_{n}}{p_{n}}$, 否则, 我们可以在$O\left( {n\log n} \right)$时间内得到按WLPT序排好的工件.
第一步 计算$P=p_{1}+p_{2}+\cdots+p_{n}$和$P(j)=p_{1}+p_{2}+\cdots+p_{j} (1\leq j\leq n)$;
第二步 令$M_{0}=\{(\emptyset, P, 0)\}$, $SL=(\emptyset, +\infty)$;
第三步 对$j=1, 2, \cdots, n$, 作下面的循环:
(a)令$M_{j}=\emptyset$;
(b)对$M_{j-1}$的每个元素$(X, t, c)$, 如果$P(j)-(P-t)\leq d$, 则$M_{j}=M_{j-1}$; 如果$t>d$且$c+w_{j}(t-d)<b$
(其中$b$是$SL$的第二部分), 则添加元素$(X\cup\{J_{j}\}, t-p_{j}, c+w_{j}(t-d))$于$M_{j}$中;
(c)如果$M_{j}$中存在第二部分相同的元素$(X_{1}, t, c_{1})$和$(X_{2}, t, c_{2})$满足$c_{1}\leq$
$c_{2}$, 则删除$(X_{2}, t, c_{2})$, 否则删除$(X_{1}, t, c_{1})$;
(d)令$(X, t, c)$ (可以是多个)为$M_{j}$中满足$t\leq d$且$c$最小的元素, 如果$c<b$ (其中$b$是$SL$的第二部分), 则令$SL:=(X, c)$, 然后从$M_{j}$中删除所有满足$c'\geq c$的元素$(X', t', c')$;
第四步 得到最终的排序$SL=(X, c)$.
输出:一个将误工工件按WSPT序排列, 按时完工的工件按WLPT序排列的最优排序$\pi$.
定理 2.3 算法$A$在$O(nP)$时间内解决了问题$1|d_{j}=d|\Sigma w_{j}T_{j}$, 其中$P=\Sigma
p_{j}$.
证 正确性可由前面的分析看出.下面分析时间界:注意到由于每个$M_{j}$中第二部分$t$不会有相同的情形, 故每个$M_{j}$所含元素个数不会超过$P$.而对$M_{j}$中的每个元素执行循环步骤$3(b)$需要时间$O(n)$, 步骤$3(c)$、$3(d)$的执行和步骤$3(b)$的执行是同时进行的, 因此需要的时间也为$O(n)$, 故总的时间界为$O(nP)$.
为了方便下面的讨论, 我们考虑接下来的一个改进的算法.
改进算法$A'$
令$U$是目标值的上界, 我们将上面算法的初始值设为$SL=(\emptyset, U)$, 然后将第三步$(c)$改写为下面的形式(可以由附录1的证明中得到):
第三步(c)找到$M_{j}$中的第三部分相同的元素$(X_{1}, t_{1}, c)$和$(X_{2}, t_{2}, c)$, 如果$t_{1}\geq t_{2}$, 则删除$(X_{1}, t_{1}, c)$, 否则删除$(X_{2}, t_{2}, c)$;
类似于定理2.3的证明, 我们容易得到下面的定理.
定理 2.4 改进的算法$A'$在$O(nU)$时间内解决了问题$1|d_{j}=d|\Sigma w_{j}T_{j}$, 其中$U(\leq \sum\limits_{1\leq i\leq j\leq
n}w_{j}p_{i})$是目标值的上界.
注 $U$值由式子$U=f(\pi^{*})$确定, 其中$\pi^{*}$是指由Modified Lawler's算法得到的排序, 因此是最优值的$n-1$倍.假设$U>0$, 我们得到原问题的一个FPTAS算法:
算法 B
输入:一个任意的$\varepsilon>0$, $n$个工件$J_{1}, J_{2}, \cdots, J_{n}$, 加工时间和权重分别为$p_{j}$和$w_{j} (j=1, 2, \cdots, n)$, 工期为$d$, 且使得$\frac{w_{1}}{p_{1}}\leq\frac{w_{2}}{p_{2}}\leq\cdots\leq\frac{w_{n}}{p_{n}}$.令$U$是由Modified Lawler's算法得到排序$\pi^{*}$的目标值.
第一步 计算$K=\lceil\frac{\varepsilon
U}{n^2}\rceil, P=p_{1}+p_{2}+\cdots+p_{n}$和$P(j)=p_{1}+p_{2}+\cdots+p_{j} (1\leq j\leq n)$;
第二步 令$M_{0}=\{(\emptyset, P, 0)\}$, $SL=(\emptyset, U)$;
第三步 对$j=1, 2, \cdots, n$, 作下面的循环:
(a)令$M_{j}=\emptyset$;
(b)对$M_{j-1}$的每个元素$(X, t, c)$, 如果$P(j)-(P-t)\leq d$, 则$M_{j}=M_{j-1}$; 如果$t>d$且$c+K\lfloor w_{j}(t-d)/K\rfloor<b$
(其中$b$是$SL$的第二部分), 则添加元素$(X\cup\{J_{j}\}, t-p_{j}, c+K\lfloor
w_{j}(t-d)/K\rfloor)$于$M_{j}$中; 找到$M_{j}$中的第三部分相同的元素$(X_{1}, t_{1}, c)$和$(X_{2}, t_{2}, c)$, 如果$t_{1}\geq$ $t_{2}$, 则删除$(X_{1}, t_{1}, c)$, 否则删除$(X_{2}, t_{2}, c)$; $(X, t, c)$ (可以是多个)为$M_{j}$中满足$t\leq d$且$c$是最小的元素, 如果$c<b$ (其中$b$是$SL$的第二部分), 则令$SL:=(X, c)$, 然后从$M_{j}$中删除所有满足$c'\geq c$的元素$(X', t', c')$;
第四步 得到最终的排序$SL=(\bar{X}, \bar{c})$.
该算法与前面算法的重要区别是每个$M_{j}$最多有$O(U/K)$个元素.并且每个工件$J_{j}$的加权误工时间被统一成$K\lfloor
w_{j}T_{j}/K\rfloor$.下面的定理说明算法$B$是一个FPTAS.
定理 2.5 对任给的$\varepsilon>0$, 算法$H$对问题$1|d_{j}=d|\Sigma w_{j}T_{j}$是一个$(1+\varepsilon)-$近似算法, 时间复杂性为$O(n^3/\varepsilon)$.
证 令$c$是原问题$1|d_{j}=d|\Sigma
w_{j}T_{j}$的最优的目标值,
$(\bar{X}, \bar{c})$为算法$H$得到的最终的$SL$的值且$\sigma$为对应的排序.由于$\bar{c}$实际上是问题$1|d_{j}=d, \pi$是正规排序$|\Sigma K\lfloor
w_{j}T_{j}/K\rfloor$的最优的目标值, 因此我们有$c\geq
\bar{c}$.进一步, 令$c^{*}$是算法$H$得到的原问题的近似值, 即排序$\sigma$下的加权误工时间总和.由$c$的最优性, 我们有$c^{*}\geq c$且$U\leq
(n-1)c<nc$.我们记$c^{*}=f(\sigma)=\Sigma w_{j}T_{j}$, 则$\bar{c}=\Sigma K\lfloor w_{j}T_{j}/K\rfloor$.由于
| $
w_{j}T_{j}-K\lfloor w_{j}T_{j}/K\rfloor\leq
K-1\leq\varepsilon U/n^2\leq\varepsilon c/n,
$ |
我们有
| $
c^{*}-c\leq
c^{*}-\bar{c}=\Sigma(w_{j}T_{j}-K\lfloor
w_{j}T_{j}/K\rfloor)\leq\varepsilon c.
$ |
这就意味着$c^{*}\leq(1+\varepsilon)c$, 故得到的是原问题的一个FPTAS算法.又由于每个$M_{j}$最多有$O(U/K)$个元素, 因此最多需要$(nU/K)=O(n^3/\varepsilon)$时间.
2015, Vol. 35 
PDF