可中断的多任务平行机排序问题

A preemptive multiprocessor order parallel machine scheduling problem

Leung等(Preemptive multiprocessor order scheduling to minimize total weighted flowtime[J].European Journal fo Operational Research,2008,190:40-51)研究了如下问题:有n个订单,其中每个订单i含有ni个不同的工件.所有的订单在零时刻已经到达,并且工件的加工是可中断的.每个订单i有一个权重ωi,定义订单i的完工时间Ci为订单i最后一个完工工件的完工时间.目标是找到一个可行排序使得加权总完工时间∑ni=1ωiCi最小.Leung等证明了这个问题是NP-难的,给出了一个近似算法,并且分析了该算法的最坏情况界.但是定理2的证明存在一些错误.证明了尽管定理2的证明过程存在错误,但是其结论仍然正确.另外,对上述模型的一种特殊情形给出了更好的近似算法.

Leung等（Preemptive multiprocessor order scheduling to minimize total weighted flowtime [J]. European Journal of Operational Research, 2008, 190： 40-51） study the following problem： there are n orders each of which requests various quantities of the different product types. All the orders are available for processing at time t = 0, and preemption is allowed. Order i has a weight wi and its completion time is the time when its last requested product type is completed. The goal is to find a preemptive schedule such that the total weighted completion time ∑^ni=1ωiGi is minimized. They show that this problem is NP-hard and propose a heuristic with worst-case ratio analysis. When reading the proof of Theorem 2 in this paper, we find that some statements are not correct. In this paper, we show that although the proof of Theorem 2 is not valid, the conclusion is still right. Furthermore, we propose an improved approximation algorithm for a special case.