关于最小化总误时单机排序问题的若干注记

SEVERAL NOTES ON ONE-MACHINE SEQUENCING PROBLEM FOR MINIMIZING TOTAL TARDINESS

最小化总误时的单机排序问题是一个著名的复杂性迄今未知的问题,人们曾作了大量的研究.本文在前人工作的基础上,对一种特殊情况(诸工件的工时与工期有同序关系的情况)给出了一个简单解法.对一般情况改进了最优解的必要条件和已有的消去规则.

One-machine sequencing problem for minimizing total tardiness is a famous project which complexity is still unknown. Many researches have been made on this problem. In this paper, a simple solution is given for some special case (i.e.,the work-time and the work-cycle of all the components are identical sequencial).For general case, the necessary condition for optimal solution and the existing elimination rules are improved.