2.5　问题1｜ r _j ，pmtn｜∑w _j C _j

这一节我们讨论工件加工可中断排序问题 1｜r _j ，pmtn｜∑w _j C _j ，事实上前一节给出的线性规划（LP 2.9）与（LP 2.10）也是排序问题 1｜r _j ，pmtn｜∑w _j C _j 的线性规划松弛，应用这两种线性规划松弛也可设计求解排序问题 1｜r _j ，pmtn｜∑w _j C _j 的随机化算法（Goemans et al.，2000）。类似于前一节讨论排序问题 1｜r _j ｜∑w _j C _j 的方法，可得下列引理。

引理2.12 由随机化算法构造一工件加工可中断排序，设 是工件 j 的完工时间，若对所有正则集 S 成立

则

其中， 是线性规划（LP 2.10）的最优值。

算法2.6

步骤1：给定 α（0＜α≤1） ，将所有工件按在LP序中 α -点的值从小到大标号 1，2，…，n。

步骤2：按照下列法则构造新的工件可中断排序 ：在可加工的工件中总是安排加工工件标号小的工件。

显然，LP序中机器被占用时间与排序 中机器被占用时间是一致的，我们将排序 中工件 j 的完工时间记为 ，则下列引理中的不等式成立。

引理2.13 给定一正则集 S ，对于工件 k S ，设 α _k 表示在LP序中工件 k 在时间 r _min （S） 之前加工的比例，将 S 中的工件重新编号， S 中所有工件在排序 中第一个完成加工的记为1，第二个完成加工的记为2，第 k 个完成加工的记为 k（k＝1，…，｜S｜）。 则对于工件 j∈S ，成立

证明 注意在排序 中，从时间 r _min （S） 开始，可能有一段时间加工的工件其在LP序中的 α -点在 r _min （S） 之前，然而在排序 中这一段时间的完成不超过

因此，对于 p（S） 单位的时间，排序 仅加工 S 中的工件，考虑第一个工件1，这一工件一定也是在 S 中按 α -点确定的次序的第一个工件，这样，这一工件在LP序中的 α -点在 r _min （S） 与 r _min （S）＋αp（S） 之间，从而得到这一工件开始加工的时间不迟于 r _min （S）＋αp（S）－αp ₁ ，也就是在排序 中，这一工件的完工时间不超过 r _min （S）＋ （1－α _k ）p _k ＋αp（S）＋（1－α）p ₁ ，因此得到

类似地，工件2开始加工不迟于 r _min （S）＋αp（S）－（1－α）p ₁ －αp ₂ ，得到

类似的理由，引理得证。

引理2.14 给定一正则集 S ，对于工件 k S ，设 α _k 表示在LP序中工件 k 在时间 r _min （S） 之前加工的比例，则

证明 不妨假设 S ＝｛1，2，…，｜ S ｜｝，其中， j 表示在 S 中第 j 个完工的工件，设 j∈S ，由引理2.13得

下面我们给出排序问题 1｜r _j ，pmtn｜∑w _j C _j 的随机化算法，设区间[0，1]上的密度函数

0其中， β∈（0，1）。

定理2.16 根据密度函数 h（α） 随机选取 α ，则对任意正则集 S 成立

证明 根据引理2.14成立

首先计算 E ［ α ]：

再计算 ：

因为 α _k 表示在LP序中工件 k 在时间 r _min （S） 之前加工的比例，因此 ≤ r _min （ S ），所以

所以

取 β≈0.682 ，得到

所以由引理2.12得到求解排序问题 1｜r _j ，pmtn｜∑w _j C _j 的随机1.47-近似算法。 FIXr6BsA3N9go39A49EE2gSlP8kuDxkZM1FimEErA/4+vgILHWHgd6R+4ypjvwo+