下载掌阅APP，畅读海量书库
立即打开
在这一节里我们所讨论的排序问题是在之前讨论工件具有前后约束关系的基础上同时考虑工件具有就绪时间，即讨论工件具有就绪时间与前后约束关系的排序问题 1｜r j ，prec｜∑w j C j （Hall et al.，1997）。显然，线性规划（LP 2.1）也是排序问题 1｜r j ，prec｜∑w j C j 的线性规划松弛，但由于工件 j（j＝1，2，…，n） 具有就绪时间 r j ，而线性规划（LP 2.1）中没有刻画出工件就绪时间 r j ，因此，根据线性规划（LP 2.1）所计算得到的 C j 与就绪时间 r j 之间无法进行比较。所以，应用线性规划（LP 2.1）这一线性规划松弛不能得到求解排序问题 1｜r j ，prec｜∑w j C j 的近似算法。而事实上，对于排序问题 1｜r j ，prec｜∑w j C j ，其工件 j（j＝1，2，…，n） 的完工时间 C j 一定满足 C j ≥r j ＋p j ，所以，我们可以在线性规划（LP 2.1）中增加约束条件 C j ≥r j ＋p j ，从而得到下列排序问题 1｜r j ，prec｜∑w j C j 的线性规划松弛：
显然，对于排序问题1｜ r j ，prec｜ ∑w j C j 的任意可行序，其工件的完工时间｛ C j ｜ j ＝1，2，…， n ｝是线性规划（LP 2.7）的可行解，因此，线性规划（LP 2.7）的最优值是排序问题1｜ r j ，prec｜ ∑w j C j 的一个下界，这样得到下列求解排序问题1｜ r j ，prec｜ ∑w j C j 的算法。
算法2.2（Schedule-by-
算法）
步骤1：求解线性规划（LP 2.7）得到其最优解｛
｜
j
＝1，2，…，
n
｝。
步骤2：按｛
｜
j
＝1，2，…，
n
｝的非降次序确定工件的加工次序。
显然，如果安排在第 j 个加工的工件其就绪时间大于第 j－1 个加工工件的完工时间，则第 j 个加工工件的开工时间为该工件的就绪时间。
定理2.3
设｛
｜
j
＝1，2，…，
n
｝是线性规划（LP 2.7）的最优解，不妨假设
是由算法2.2所得到的排序问题1｜
r
j
，prec｜
∑w
j
C
j
可行排序的工件完工时间，则
成立，即算法2.2是求解排序问题 1｜r j ，prec｜∑w j C j 的3-近似算法。
证明
显然根据假设
，可得到由算法2.2所得到的工件加工次序为（1，2，…，
n
）。设
S
＝｛1，2，…，
j
｝，
r
max
（
S
）＝max｛
r
k
｜
k∈S
｝，显然
r
max
（
S
）与工件
j
的完工时间
之间没有空闲时间，所以
又由于
，所以
因此
再根据定理2.1的证明，
成立，得
，所以
设工件集合
，不妨假设
S
中工件加工次序为
i
1
，i
2
，…，i
s
。当工件没有就绪时间时，工件
i
j
的完工时间
，而当工件具有就绪时间时，设
r
min
（
S
）＝min｛
r
j
｜
j∈S
｝，则工件
i
j
的完工时间
从而得到一个更强的约束条件。
引理2.2
设工件集
J
＝｛1，2，…，
n
｝，对于排序问题1｜
r
j
，prec｜
∑w
j
C
j
的任何可行排序，
C
j
（
j
＝1，2，…，
n
）是工件
j
的完工时间，则对任意工件集合
，以下公式成立：
证明 不失一般性，不妨假设 S 中工件加工次序为 i 1 ，i 2 ，…，i s ，则
因此，根据上面引理2.2的结果，可得到下列排序问题 1｜r j ，prec｜∑w j C j 的另一个线性规划松弛，其约束条件强于线性规划（LP 2.7）的约束条件：
定理2.4 设 ｛ C j ｜ j ＝1，2，…， n ｝是线性规划（LP 2.8）的可行解，则 ｛ C j ｜ j ＝1，2，…， n ｝也是线性规划（LP 2.7）的可行解。
定理2.4的结论是显然的，因此，我们将算法2.2的步骤1中求解线性规划（LP 2.7）的最优解改为求解线性规划（LP 2.8）的最优解，这样得到的算法也是求解排序问题 1｜r j ，prec｜∑w j C j 的3-近似算法。