论文部分内容阅读
本文研究了两种现代排序模型,相同的族安装时间的最小化最大延迟的单机成组分批排序问题,工件的加工时间和它们的尺寸成正比的最小化最大完工时间的单机排序和工件运输问题。
本文证明了当工件的加工时间和它们的尺寸成正比时，这个问题仍然是强NP-困难的，并且Chang和Lee提出的启发式算法对我们研究的问题有更好的执行比53/35，我们也提供了一种新的启发式算法，它的最差执行比是3/2，并且这个界是最好的。