下载掌阅APP，畅读海量书库
立即打开
在这一节里我们讨论的排序模型是工件加工可中断的，即一个工件的加工可以在其没有完工前的某一时刻被停止加工，称为工件加工被中断，并在后面的某个时刻再继续加工该工件，工件的加工可以多次被中断。对于工件加工可中断的排序问题1｜ r j ，prec，pmtn｜ ∑w j C j 的可行序，其工件的完工时间｛ C j ｜ j ＝1，2，…， n ｝显然也是线性规划（LP 2.7）与线性规划（LP 2.8）的可行解，因此，线性规划（LP 2.7）与线性规划（LP 2.8）也都是工件加工可中断排序问题1｜ r j ，prec，pmtn｜ ∑w j C j 的线性规划松弛。故算法2.2也是工件加工可中断排序问题1｜ r j ，prec，pmtn｜ ∑w j C j 的3-近似算法，虽然算法2.2所得到的排序其所有工件的加工是不中断的。
下面我们将给出一个基于线性规划（LP 2.8）的求解工件加工可中断排序问题1｜
r
j
，prec，pmtn｜
∑w
j
C
j
的2-近似算法（Hall et al.，1997）。对于排序问题1｜
r
j
，prec，pmtn｜
∑w
j
C
j
的一个实例，若工件
j
与
k
具有前后约束关系
j
k
，这意味着工件
k
必须在工件
j
完工之后才能加工，因此，工件
k
一定是在时间
r
j
＋p
j
后才能加工。所以，若
r
j
＋p
j
＞r
k
，那么，可以将工件
k
的就绪时间
r
k
增加到
r
j
＋p
j
而得到一个新实例，显然原实例的可行序也一定是新实例的可行序。这样可以用这种方法对排序问题1｜
r
j
，prec，pmtn｜
∑w
j
C
j
的实例相关数据进行预处理，使所有具有前后约束关系
j
k
的工件
j
与
k
成立
r
k
≥r
j
＋p
j
。
算法2.3（Preemptively-Schedule-by-
算法）
步骤1：求解线性规划（LP 2.8）得到其最优解｛
｜
j
＝1，2，…，
n
｝。
步骤2：按｛
｜
j
＝1，2，…，
n
｝的非降序考虑工件
j
，在已构造的部分序中确定工件
j
可以加工的最早时间。这一时间点就是工件
j
的就绪时间
r
j
与工件
j
的所有前续工件加工都完成的时间这两者中大的一个，从这一时间点起，在部分序中的任意空闲时间里安排加工工件
j
，直到工件
j
加工完成。
由线性规划（LP 2.8）的约束条件
C
k
≥C
j
＋p
k
（若
j
k
）保证了｛
｜
j
＝1，2，…，
n
｝的非降序与工件之间的前后约束关系是一致的，所以由算法2.3所得到的排序是排序问题1｜
r
j
，prec，pmtn｜
∑w
j
C
j
的可行序。
定理2.5
设｛
｜
j
＝1，2，…，
n
｝是线性规划（LP 2.8）的最优解，不妨假设
是由算法2.3所得到的排序问题1｜
r
j
，prec，pmtn｜
∑w
j
C
j
可行排序的工件完工时间，则
成立，即算法2.3是求解排序问题1｜ r j ，prec，pmtn｜ ∑w j C j 的2-近似算法。
证明
对于工件
j
，由算法2.3构造的排序其完工时间为
。考虑对于工件｛1，2，…，
j
｝由算法2.3构造的部分序，设
t
表示在
之前机器空闲的最大时间，如果
之前机器没有空闲时间，则定义
t
＝0，显然，区间［
t
，
］不包括机器空闲时间。
在区间［
t
，
］中加工（或部分加工）的工件集合记为
S
，我们可以证明
S
中没有工件的就绪时间小于
t
。如果在
S
中存在就绪时间小于
t
的工件，则根据前面提到的数据预处理，若
j
k
则
r
k
≥r
j
＋p
j
成立。设工件
m
是
S
中就绪时间最小的工件，这样工件
m
就会被安排在
t
之前的某段空闲时间内加工，这是不可能的，与
t
的定义矛盾，所以
t＝r
min
（S）。
由于区间
［t，
］
不包括空闲时间，所以
根据部分序的构造，显然对所有
k∈S
，成立
，再结合线性规划（LP 2.8）中的约束条件
得
即
所以
显然，算法2.3在执行过程中仅仅可能在工件的就绪时间这一时间点产生工件加工中断，即当一个工件可以开始加工时可能中断正在加工的工件，所以总的中断次数不超过 n。 因此，算法2.3是多项式时间算法。
由于假设工件的所有参数都是整数，因此，算法2.3所产生的工件加工中断一定发生在整数点，所以算法2.3也可求解排序问题 1｜r j ，prec， p j ＝1｜∑w j C j ，显然也是2-近似算法。