基于网络计划的施工项目调度优化问题研究

柯 玲

(宁夏大学新华学院，宁夏 银川 750000)

0 引言

工程项目进度管理最重要的是设计一个合理的进度计划，进度计划需要按照项目施工的目的设计目标函数。目前国内外对项目调度问题的理论模型、算法设计以及实验验证等方面都取得了很大的进展。在国内研究文献中，张立辉研究了资源受限条件下的重复性项目调度问题，考虑到重复性项目中的工序存在工作连续性约束，对串行进度生成方案进行了改进，在此基础上设计了一种求解模型的遗传算法[1]；熊鹰提出了资源受限施工项目净现值最大化问题。设计了一种求解模型的蚁群算法[2]。

工程活动的完成需要考虑各种类型资源如何利用，工期的优化，利润的最大。如何利用有限的资源进行资源优化和工程调度，这是在具体施工中普遍关心的问题。本文主要围绕以下两方面问题进行研究与分析。

1 资源受限工程调度问题的分类

近年来，关于资源受限工程调度问题的分类的方法有很多分类模型。本文根据项目调度的目标函数不同，可以分为：（1）项目工期最小化；（2）资源均衡问题；（3）最大化项目净现值。

1.1 项目工期最小化

在一般项目施工之前都会制定合理的施工网络计划，部分施工项目在施工过程目的是在最短的工期内完成项目施工。缩短工期可能会带给项目很多压力，消耗更多的资源。这就需要确定合理的施工方案，使得施工项目的工期时间与成本的支出达到最优化。这类问题的模型如下：

问题描述：整个项目包含j(j=1,2,…，J)个子项目，每个项目施工结束需要的资源为k种，每种资源的需求量为qjk，每个子项目的施工时间为dj，第k种资源的需求量为Qk(k=1,2,…，K)，子项目j的施工开始时间为STj，At为这件在（t-1，t）这个时间段内要施工的项目集合。i∈pj,i=1,2,…,J，其中i为子项目j的准备活动。

目标函数为：

s.t.子项目的间的关系

有些项目工期问题还需要考虑其他方面的因此，比如费用，网络计划中的关键施工路线等。

1.2 资源均衡问题

施工的资源均衡问题也是网络计划中的重要组成部分。部分施工项目对资源利用有要求,在施工过程中希望资源利用可以保持平衡。这类问题的数学模型如下：

问题描述：假设施工项目由M个子项目（a1,a2,…,aM）组成，子项目aj，j=1,2,…,M需要施工时间为为非负整数；施工项目需要的总资源数为K，子项目aj需要的施工资源k(k=1,2,…,K)的总量为rrk(aj)。

目标函数的建立：这类问题的目标是资源需求量最小，根据时间的施工时间及资源需求量I最小建立数学模型。

目标函数：

注：ck是第k中资源的价格，rrk(t)是在t时间资源k的需求量，计算公式如下：

注：rrkt(aj)是t时间段子项目aj对资源k的需求量，子项目开工时间的约束条件如下。

1.3 最大化项目净现值

利润最大化，就是在资金总量不变的情况下，通过统筹安排，对各种项目方案所需的资金进行合理分配，以期达到投资的最大收益[3]。这类问题强调的是利益最大化，对工期最小化和资源均衡问题都没有最优化的要求。这这类问题的模型如下：

问题描述：假设施工项目的总预算A，总预算A的投资分为I种资源，投资时间段分为n期，每期投入量为bi1,…,bij(i=1,…,n,j=1,…,m)每年施工项目的投资总额为a1,…,am投资手段为B1,…,Bm每年获得效益为C1,…,Cm，考虑时间对资金的影响，假设收益率为q其中，x1,x2,…,xn为各子项目的资金分配值，则目标函数使净现值NPV最大。

对于约束方程，假设每期的投资是固定的，则有约束方程为：

2 资源受限工程调度问题的求解

2.1 最优化方法

根据上述对资源受限工程调度问题的分类，在资源受限工程调度问题如果分别是以工程工期，资源消耗最小，净现值最大为目标函数的最优化方法中，分支界定法由于计算效果和效率上的特点被人们广泛采用。分支界定法是数学模型中对于整数线性规划的一种求解方法。分支定界算法是资源受限工程调度问题最优化的方法。在这类问题的求解过程需要建立枚举树。对于线性规划问题的求解方法有以下几种方法：

（1）分支界定法—可求纯或混合整数线性规划。

（2）割平面法—可求纯或混个整数线性规划。

（3）隐枚举法—求解“0-1”整数规划。

①过滤隐枚举法；

②分支隐枚举法。

（4）匈牙利法—解决指派问题。

（5）蒙特卡洛法—求解各种类型规划。

用最优化方法解决实际的工程调度问题一般的步骤是：一、分析问题、整理数据、二、建立模型、列出目标函数，以及对目标函数的约束条件。三、解出问题，检验最优解。四、应用最优解。

最优化的核心内容是数学模型的建立，下面介绍一下数学模型建立的一般过程。

设变量：在工程项目施工的网络计划中，不管施工项目的目标函数是什么，都需要假设出建立目标函数需要的各种数学变量。

给出约束条件：不管是目标函数是最小工期，资源均衡的优化还是净现值最大化都是有约束条件的，比如资源均衡问题要考虑施工项目的开始时间和结束时间的约束，工期最小优化考虑资源总需求量的约束。

建立目标函数：用最优化方法求解问题核心的部分就是建立合适的目标函数，目标函数最基本的类型就是最大和最小的目标函数。

2.2 现代算法

现代优化算法是20世纪80年代初兴起的启发式算法。这些算法包括禁忌搜索（Ta-bu Search）、模拟退火（Simulated Annealing）、遗传算法（Genetic Algorthms）、人工神经网络（Neural Networks）。他们主要用于解决大量的实际问题。目前这些算法理论和实际应用方面得到了较大的发展。无论这些算法是怎样产生的，它们都有一个共同的目标—就NP-hard组合优化问题的全局最优解。虽然有这些目标，但是NP-hard理论限制它们只能以启发式的算法去求解实际问题。

启发式算法包括的算法很多，例如求解复杂优化问题的蚁群算法（Ant Colony Algo-rithms）。有些启发式算法是根据实际问题而产生的；另外一些算法是集成算法，这些算法是诸多启发式算法的合成。

用算法求解资源受限项目调度问题一般包括五个过程：

选取编码程序与方式，这一过程主要是要确定解码规则。

确定算法的初始化方式。

确定算法的迭代方法。

确定整个算法带入数据的适应区间。

确定整个算法的终止条件。

近年来，随着科技的发展，对于各类施工项目问题的智能优化算法不断发展和成熟，目前各种资料都有关于智能优化算法求解施工项目调度优化问题。比如郭研等学者给出了资源均衡问题的微粒群算法。

3 结语

本文对网络计划的施工项目调度优化问题的研究主要是围绕两个方面：一是对资源受限工程调度问题按照目标函数不同分类并建立相应的数学模型，二是对求解项目调度优化问题方法的总结梳理。施工项目调度优化问题是一类比较复杂的优化问题，在今后的工作中就是对求解的算法做进一步的研究。