匹配算法在带链优先约束的分批排序中的应用

摘要

本文首次就带有链优先序的分批排序问题进行了讨论.优先约束是:包含有n个工件的一条链,另外有m个孤立点工件(即工件之间无任何优先约束).根据B与m的大小关系,分别讨论了它们的最优算法.优先约束为:工件之间有m条链T1,…,Tm,并且每条链是满足一致的.则对于B=2的情形,我们把这一问题多项式转化成了组合最优化中求解非二部图赋权匹配问题,并相应地提出了一个运算次数为O(n4)的多项式算法.