基于亏值研究的三元序链优化新方法

摘要

CPM网络中的工序排序问题是世界公认的NP-hard问题，是目前项目管理研究的难点之一。三个平行工序顺序优化问题是工序排序问题的子问题，该问题的研究将为工序排序问题的解决提供了新的思路和方法。鉴于此，本文从CPM网络图本身的规律出发，在已有定义和定理基础上，给出了中心对称，前隔断重心以及后隔断重心定理等，进而给出了理论上的证明。在以上定理基础上，进一步研究了三个平行工序调整成一个顺序链使得总工期推迟最少的问题优化算法。算例表明，与传统方法进行比较，该算法简单易行，便于应用，能达到最优结果。