求解CPM网络计划的最大网络时差

CPM网络计划的网络时差表示项目中各工序实际可使用的机动时间的总和(绝非理论上机动时间的简单加总),即CPM网络计划的总机动时间,它决定着在总工期不变的前提下,所有工序实际可以达到的最大工期的总和,与项目的成本管理和时间管理密切相关。网络时差是变量,取决于各工序的时间进度安排,说明可以通过调整工序的时间进度来决定该时差的取值,特别是其最大值,进而实现成本和时间优化。本文首先从新的角度分析了网络时差的含义;然后,在此基础上设计了求解最大网络时差的算法,其思路为,通过建立和分析最大网络时差模型,将其转化为特殊的"时间-费用权衡问题",进而可运用Fulkerson算法等经典算法求解;最后,通过应用举例对该算法进行了演示。

等效化简带有广义优先关系的时间-费用权衡问题

对于经典的时间-费用权衡问题,工序之间只存在单一时间约束,可用CPM网络表示。但是对于工序之间存在多种时间约束的时间-费用权衡问题,包括最大和最小时间约束(称为广义优先关系,简称GPRs),则只能用GPRs网络表示,比CPM网络复杂许多。首先,论述了带有GPRs的时间-费用权衡问题与经典问题的巨大差别:在GPRs中,(1)缩短某些关键工序的工期能使总工期缩短,但缩短另一些关键工序的工期反而能使总工期延长;(2)缩短或延长工序的工期可能会破坏项目自身的可行性;等。其次,研究了GPRs网络的特性,推导出该网络的路长定理。第三,根据该定理,设计出等效化简带有GPRs的大型时间-费用权衡问题的简单方法,从而大幅减小求解该问题的难度和计算量。最后,通过算例演示了该方法。

用最少的虚工序构建等效多阶段工序网络

运用网络计划可以直观地表示项目管理中的诸多疑难问题,便于分析和求解.但是它也存在明显的缺点,如,(1)工序网络的有向无回路性表明很多时候适合运用动态规划法,但它在通常情况下的无阶段性使得该方法无法直接应用;(2)任意构建的工序网络容易表现得错综复杂,不利于研究;(3)用最少的虚工序表示双代号网络是NP-难问题,因此对一个工序系统可能构建出多个差别迥异的工序网络,有碍于进度计划管理研究,等等.如果能将工序网络构建成等效的多阶段网络,各工序分别表示在相应的阶段中,无疑有助于上述问题的解决.构建等效多阶段工序网络需要添加虚工序.通过添加最少的虚工序将工序网络构建成等效多阶段网络,从而有助于建立更合理的工序网络表示法.

搭接网络中的路长悖论及其特性研究

本文发现在搭接网络中存在"工序间加入不同表现形式的同一时间约束,可能会产生不同的最大路长"这个悖论。通过研究此悖论形成原因从而提出搭接网络的一种新表示方法。该方法不但与经典的CPM网络在表示形式上完全统一,而且在求解时间参数及关键路线的方法上也保持一致。该新表示法使得CPM网络中许多基础理论可以推广到搭接网络中来,例如工序的总时差Tij等于关键路长μ-#与过该工序(ij)的最大路长μ-#ij之差(μ-#-μ-#ij);任意一条路线μ上自由时差的和都等于关键路长μ-与该条路的路长之差(μ-#-μ-)等。利用这些定理与规律,本文解决了搭接网络中如何正确求解时间参数问题,提出在搭接网络中评估关键路长与次关键路长之差的简便方法以及求解搭接网络次关键路线的一系列精确算法,并通过算例表明这些方法在搭接网络应用中的具有有效性与简便性。

搭接网络的新表示方法与奇异现象研究

针对搭接网络,设计了新的表示方法,将工序之间的所有搭接关系(时距)都等效地用经典的关键路线法(critical path method,CPM)双代号网络表示,并且能直接运用CPM法计算搭接网络的各类时间参数,使搭接网络具有和CPM双代号网络一样的直观性和便利性,更使建工行业规定的计算程序大为简化.另外,利用搭接网络的新表示方法,发现了搭接网络中的奇异现象,例如,某些关键工序的工期缩短,总工期反而延长,而某些非关键工序的工期无论如何变动,其机动时间总保持不变,等等,为项目调度等问题的解决提出新的挑战,开拓了搭接网络在研究和应用上的新领域.