论文部分内容阅读
本文讨论了极小化加权完工时间和的Flowshop问题.我们给出了一个最坏情况误差界为m的启发式算法,对于m=2的情况,如果工件具有一致权因子,即pi＜pj意味着wi≥wj,(i,j=1,2,…,n).最坏情况误差界为2β/α+β,其中α和β分别是全部工序加工时间的最小值和最大值.此外,分析了m＝2的两种特殊情况,给出了多项式算法.