基于Dijkstra算法的单工序对其平行工序数量敏感性分析

在CPM网络计划中，一个工序开始和结束时间的变化可能不光会对它的顺序工序产生影响，也会对它的平行工序产生影响，当该工序的结束时间从最早结束时间开始推迟不同的量时，或者当它的开始时间从最迟开始时间开始提前不同的量时，它的平行工序中自由时差、安全时差或总时差增大的工序数量也可能不同。针对该单个工序对其平行工序数量敏感性问题，利用工序自由时差、安全时差和总时差的概念及功能对其进行分析，建立了某工序最早结束时间的推迟量或最迟开始时间的提前量与它的平行工序中受影响工序数之间的函数关系模型。最后，通过算例，进行了具体阐述。     

基于CPM原理和Dijkstra算法的SPM网络计划模型及性质

CPM(关键路线法)网络计划适用于分析工序间存在严格紧前关系(任意工序只能在它的所有紧前工序都结束时才能开始)的进度计划.针对工序间不存在严格紧前关系(任意工序只要其紧前工序中的一个结束它就可以开始)的进度计划,以CPM原理和Dijkstra算法为基础,提出SPM(最短路线法)网络计划以及拟机动时间概念,根据不同的建模原理,建立了两个SPM网络计划模型,并给出了其建立方法以及各模型拟机动时间的求法,分析了每个模型的性质,最后通过算例对其中的一类模型进行了验证.     

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

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

求解GPRs条件下的项目最小费用问题

在项目管理中,最低成本是主要目标之一,也是求解诸如时间-费用权衡等相关问题时必备的起始点,通常只需令各工序选用费用最低的工期即可.但是当工序之间存在一般优先关系(简称GPRs)时,各工序选用费用最低的工期往往无法满足时间约束,使得项目不可行,因此需要考虑其它费用较高的工期.针对如何在满足GPRs条件下使项目成本最低,首先,通过分析GPRs网络的特点,建立了GPRs网络的最小费用模型;其次,对模型进行对偶变换,等效转化为最小费用流模型,其特点是,除了与起点或终点连接的弧,其余均没有容量限制.当前已有的算法能够有效求解该模型,并跟据其最优解可求得原问题的最优解.     

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

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

CPM网络计划中工序机动时间守恒性探究

借助CPM网络计划进行工序机动时间特性研究是对项目进度进行科学管理的基础.针对项目进度中,若某工序的结束时间从最早结束时间开始一直推迟,其后继工序的机动时间是否会一直受其影响的问题,利用工序机动时间已有的概念和性质,提出路线机动时间和路线自由时差的概念,并借助这两个概念进行工序机动时间守恒性分析,得出某工序的后继工序的机动时间会在该工序的结束时间推迟到一定值后达到恒定值,不再随该工序结束时间的推迟而变化的结论,进而给出工序机动时间守恒性的充分条件,以及计算工序机动时间恒定值的方法.最后,通过应用举例进行具体分析和阐述.     

基于标准规范法的四元行偶优化决策问题探究

把2n个平行工序调整为n个顺序工序对是一类典型的资源限制项目排序问题,到目前为止,没有简便有效的解决方法.为了给该类问题的解决提供理论和方法,针对八个平行工序调整为四个顺序工序对的优化决策问题,在重心定理、行偶亏值定理和最佳行偶定理的基础上,提出了标准规范法,并对其进行了理论上的证明.最后,通过算例对该算法的简单可行性进行阐释.     

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

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