论文部分内容阅读
本文研究了两种排序模型,工件具有位置约束的限位排序问题和工件先加工后运送到顾客的单机排序问题。
本文通过考虑此问题的特殊情形，给出了一些多项式可解的例子，接着考虑了一个关于平行机排序问题；研究了工件先分批加工后运送到顾客的单机排序问题，证明了这个问题1→D，k=2|v=1，c=z|Cmax是强NP-困难的，同时提供了一个启发式算法，它的最劣性能比为2，在2T1≥T3限制下，我们提供了一个最劣性能比为27/14的改进算法。