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