固定资源约束下网络计划的最优进度安排方法研究

如何制定进度计划一直是各个行业中至关重要的问题。制定进度计划的主要目标是在既定资源约束下实现最短工期，或在工期约束下实现最小资源消耗。因此，自20世纪60年代以来，随着运筹学的发展，涌现了大量相关研究成果，近期研究主要集中于固定资源约束下的进度计划制定。Bouleiman和Lecocq提出了一种模拟退火算法，以有效地对工作节点进行排序。Rolf等学者运用拉格朗日松弛法，提出了一种基于最早开始时间的整数规划方法来优化进度计划。然而，大多数相关研究源于传统的“机器排序”问题，并不完全适用于解决工程项目中的进度问题。

工程项目的进度计划与传统的“机器排序”问题存在显著差异：一是工作节点具有明确的先后作业顺序，且通常不可更改，例如房屋修建必须从地基开始；二是工作节点的作业时间具有较大的不确定性，受气候、设计等因素影响造成的工期变化极为常见；三是由于工程项目进度计划的时间窗单位较大，因此最初的进度计划制定不像一般制造业那样要求精确。故而，工程项目中的进度优化侧重于研究如何进行资源分配，而非各工序间的作业次序调整。

1、网络计划优化

现代工程项目普遍采用基于CPM（关键路径法）和PERT（计划评审技术）的网络计划技术，作为计划、分配和控制的重要手段与工具。最常见的网络计划进度优化方法是强制压缩法，即采取措施尽可能缩短网络计划中某些关键工作的持续时间。目前，关于工期进度优化方法的研究思路也集中于不断改进强制压缩法，力求在优化项目工期的同时，使新增的额外成本最小化。吴育华等学者提出了割集平行路线差额法来解决工期优化问题。刘津明运用“最大流最小截”理论，研究了工期-成本非线性变化时的工期优化思路。随着现代信息技术的日益成熟，借助Managementscientist等软件，可以快速获得基于上述强制压缩法进行进度优化的最优结果。

强制压缩法要求必须从外部向关键线路的工作节点投入新的资源。然而，在实际工程项目建设中，常常面临缺乏额外资源的情况，这就需要利用网络计划中非关键工作的既有资源来进行工期优化，即解决所谓的赶工问题。基于上述思想，本文将探讨单代号网络计划中固定资源约束下的工期优化算法。

2、算法思想

利用非关键工作的既有资源进行工期优化，即利用非关键工作的时差，抽调部分资源来加强关键工作，以缩短关键工作的持续时间，从而缩短工期。利用关键线路的转移进行工期优化的最终目标，是使网络计划中出现尽可能多的关键线路，或是使关键线路的工期与次关键线路的工期差值最小。也就是说，当原关键线路的工期经过优化达到设定的缩短目标时，即可认为工期优化已达到期望。

利用关键线路的转移优化工期，必须首先明确关键线路存在可压缩的关键工作，且非关键工作节点拥有关键线路可压缩工作节点所需的资源，并且这些资源可以分割转移。非关键工作节点上的资源转移会延长其自身工期，而关键线路上的工作节点接受转移的资源后会缩短计划工期，从而缩短项目的整体工期。根据资源输出和输入节点的位置，原网络计划中的所有线路工期可能出现不同程度的延长或缩短，但压缩后的原关键线路工期不得小于次关键线路的工期。同时，工作节点上的资源输出或输入量也受到最小资源需求量和最大压缩时间的约束。因此，将非关键工作中的资源转移到关键线路上的工作中进行工期优化，需要解决以下问题：如何选择进行资源输出的非关键工作节点？各非关键工作节点输出多少资源？以及如何选择关键线路中的资源输入节点？各压缩节点输入多少资源？

3、算法模型

1 前提假设

为简化研究，进一步假设网络计划的所有节点中只有一种可以分割转移且影响工期的资源。以往的大部分工期优化研究都基于成本费用和工期之间的关系，通常项目所需的各种资源也能转化为费用进行衡量，因此我们的假设不失一般性。
节点，qj’表示工期经过最大压缩后，完成工作所需的资源量；对于非关键线路上的节点，qj’表示充分利用自由时差后完成工作需要的资源量。因此，xj ≤ qj – qj’。在网络计划只进行一次性工期优化的前提下，同一工作节点的资源只能单向转移或不发生变化。设tj为工作节点j的计划工期，△tj表示工作节点j工期变动的最大范围。对于非关键工作节点，△tj表示可利用的自由时差；对于关键线路上的工作节点，△tj表示极限压缩时间。设aj为工作节点j上资源与工期时间的相关系数，表示约束条件下单位资源量对工期的影响程度。由资源变化量与工期变化量成线性关系的假设，有：△tj = ajxj。设Tcp和Ti分别表示关键线路和非关键线路的计划工期，aij表示工作节点j的资源变化对线路i工期的影响系数。

3.3 算法分析

令Aj = qj × tj，Bj = {Aj | xj ≤ qj – qj’}。Aj表示节点j上包含工期和资源用量的计划安排，Bj表示关于节点j所有可行计划安排的集合。基于关键线路的转移而提出的工期优化算法，是寻找能最大压缩工期的集合B，B = {Bj | j∈J}。以Fmax表示关键线路节点输入资源后所能压缩的最大工期，固定资源约束下的工期优化问题可以转化为解决如下嵌套模型：

[模型公式及约束条件] (此处应插入数学公式，表示模型的约束条件，包括对非关键节点资源输出的限制，关键节点资源输入的限制，以及整体工期约束和资源平衡约束。)

式中，模型公式及其约束条件应清晰表达：非关键工作节点输出资源导致工期延长，但延长量不超过可利用的自由时差；关键线路上的工作节点输入资源会缩短工期，但缩短量不超过极限压缩时间；工期优化后的关键线路工期不小于网络计划中的其他线路工期；节点资源改变对工作线路工期的影响；非关键工作节点输出的资源全部输入到关键线路的工作节点中；各节点资源量改变的绝对值非负。

在实际工期优化时，非关键工作节点的自由时差、充分利用时差后完成工作所需的最小资源量，关键线路上工作节点的极限压缩时间和对应的需求资源量是已知的。通过 [计算公式] 可以求出各节点的资源时间相关系数，从而将上述模型转化为线性规划问题求解。下面以一个算例说明固定资源约束下运用转移关键线路法进行工期优化的解决过程。

4. 算例说明

参考文献：

[1] Rolf H. Solving project scheduling problem by minimum cut computations. *Management Science*, 2003, 49(3): 330-350.

[2] 白思俊. 现代项目治理[M]. (此处需补充出版社及出版年份)

[3] 刘津明. 工程项目进度计划优化方法的研究[D]. 天津大学, 2003.

[4] David R. Anderson, Dennis J. Sweeney, Thomas A. Williams. *An Introduction to Management Science: Quantitative Approaches to Decision Making*[M]. Thomson Learning, 2003: 340.

[5] Son-Sen Len, Chung-Huei Yang, Jiun-Ching Huang. Resource leveling in construction by genetical algorithm-based optimization and in decision support system application. *Automation in Construction*, 2000, 27-41.