论文部分内容阅读
首次研究了机器带准备时间的平行机上的分批排序问题，这里的目标函数为极小化工件的最大完工时间，这类问题是NP-难的．我们根据FBLPT算法、Multifit算法和LPT算法，分别对机器是同型机和同类机的两种情形设计出两个近似算法，并证明它们的最差性能比分别不超过（2-1/B）[9/7＋（1/2）^k]和5/3（2-1/B）