研究了工件有不同的到达时间和平行链约束(也就是每一个工件至多有一个前驱和一个后继)的情形.考虑有m条链,其中一条链上包含n个工件,其余的m-1条链上的工件数总和为常数,给出了一个多项式算法.同时指出,对于其他正则单目标函数也是多项式可解的.
滨州学院学报
2007年6期