摘要
本文讨论了具有调整时间的多类工件单机排序问题I|MCS|∑Ci|尽.管该问题是强NP—完全的,但本文证明了一个最优解的必要条件,由此给出了一个复杂性为O(M^2(n/M+1)~M)的动态规划算法.这是一个相当满意的结果.本文还对表现测度为加权完工时间和的情况做了一些讨论,在权为类权时得到了与上述同样的结果.
This paper discussed a scheduling model:single machine scheduling problem with multiple job classes.Althrough it is NP—complete,the author present a dynamic programming algorithm with computational complexity O(M^2(n/M+1)~M).Further,some result with weighted completion time are givea.
出处
《郧阳师范高等专科学校学报》
1997年第2期26-29,13,共5页
Journal of Yunyang Teachers College
