最小成本加快法中的优化组合方案定理及其计算机程序

摘要

本文提出了最小成本加快法中寻找多关键路线情况下的组合压缩方案的方法,并用图论中有关割集的理论进行了论证,得到了优化组合方案定理。该定理指出:在由网络计划图中的关键路线构成的子图中,如果每项作业都允许压缩或放宽作业时间,则其最小费用率完全割集中的每个正向割弧(作业)压缩单位时间,每个反向割弧(作业)放宽单位时间,则总工期以最低成本压缩单位时间。文中详细介绍了这种算法。