论文部分内容阅读
对带有“扩充链”优先约束的分批排序问题进行了研究，其目标函数为最大完工时间．优先约束为：在一个“扩充链”上包含有n个工件，另外有m个孤立点工件（即工件之间无任何优先约束）．讨论了B=2时问题的最优算法，把这一问题多项式转化成了组合最优化中求解非二部图赋权匹配问题，并相应地给出了一个运算次数为O（n^4）的多项式算法．