论文部分内容阅读
对一类工件加工时间成比例的两阶段自由作业排序问题进行了研究．工件需要分别在包含m1和m2台平行机的两阶段中进行加工，工件在阶段闻的加工满足自由作业环境要求，且相同工件在两阶段的加工时间相同，目标是极小化时间表长，即最后完工工件的完工时间．证明了当min{m1，m2）≥2时该问题是NP-难的，给出了该问题的一个近似算法，并证明了该算法的最坏情况界不大于3/2-3/2（2min{m1,m2}＋1,得到了当min{m1，m2）=1时，该算法为问题的最优算法．