基于资源约束的网络计划工期优化的新研究方法郭志宽

基于资源约束的网络计划工期优化的新研究方法郭志宽

郭志宽

(内蒙古电力集团有限责任公司呼和浩特供电局内蒙古呼和浩特010010)

摘要：如何优化网络计划的工期是当前工程项目管理中的一个关键性问题。传统研究着重于以最小的成本增加量来实现期望的优化工期，没有资源、成本约束等限制。本文在考虑网络计划资源一定的前提下，通过转移关键与非关键路径上活动的资源进行重新优化配置；将问题转化为运筹学中的运输问题进行求解，以此达到工期优化的目的。这一新方法的提出，对于实际工程的工期优化具有积极意义。

关键字：工期优化；资源约束；运输问题；关键路径

1引言

网络计划的优化问题一直以来都备受各国学者的重视。最为令人熟知的是时间-费用交换问题（Time-CostTrade-offProblem，以下简称TCTP）主要研究工期的压缩，即假定资源成本没有限制，可以通过增加费用在一定范围内压缩活动的工期，即以费用换时间，求解的是以最少增加费用满足项目进度计划的要求[1]。这种方法的基本思想是要求必须从外界投入新的资源到项目中。然而，在实际项目的应用中，经常是缺乏资源，成本也不可能无限制增加的，所以TCTP方法只适合在资金充裕的少数情况下作为赶工的一种特殊手段。目前，对于网络计划优化的研究，主要分为两个方向。一个是“资源有限，工期最优”，另一个则是“工期固定，资源均衡”。本文研究的是在资源固定的条件下，通过优化配置，使得网络计划的工期达到最优。

2算法思想

现代的工程项目都是应用基于CPM和PERT的网络计划技术作为计划、分配、控制的重要手段和工具。因此，本文是选取单代号网络图作为网络计划的承载体。在网络图中，根据计算，我们可以得到一条或多条工期最长的路径，称为关键路径，在关键路径上的所有的活动称为关键工序，其余的为非关键工序。本文提出的基于资源约束的网络计划工期优化的新研究方法的基本思想是：利用非关键工序的时差，将非关键工序上的既有资源部分转移到关键工序上，以缩短关键工序的总工期，达到工期优化的目的[2]。这种方法的结果是使得网络计划中出现尽可能多的关键路径，或者最长工期与次长工期的差值最小，此时可以认为工期优化过程结束。

利用非关键工序既有资源的转移配置来优化工期时，首先必须确定存在可以被压缩工期的关键工序，存在非关键工序的资源是关键工序压缩时需要的资源，而且可以分割转移。尽管非关键路径因为资源的转移延长工期，关键路径则相反，但是转移后最大工期小于原工期即可。同时，工序上资源的输入量、输出量以及压缩时间都是受到约束的。

此时，固定资源约束下的工期优化问题就转换成了把资源从非关键工序向关键工序转移的规划问题。因此本文将其转换成为运输问题进行问题的求解。

3算法模型

3.1前提假设

项目资源是指在项目实施过程中必须的一切具有使用价值，可以为项目接受和利用，且属于项目发展过程所需求的客观存在。一般情况下，各种资源都是可以转化为费用进行衡量的，所以为了简化研究，本文假设网络计划中有且只有一种可以分割转移并影响工期的资源。

对于非关键工序来讲，具有总时差和自由时差这两种时差，如果选择总时差，虽然对整体工期没影响，但是会影响紧后工序的最早开始时间，导致问题不确定性和复杂性。所以，本文仅选取具有自有时差的非关键工序作为资源输出点。另外，假设在满足约束的前提下，各工序工期变化量与资源变化量成线性关系。

3.2算法分析与建模

本文引用文献[3]的算例与数据作为工期优化的对象，网络计划图如下所示，字母后面的数字表示原来的工期。由图1可以知道，该网络计划图的关键路径为A-C-F-I-K-O。

由表1可知，工序E、H、J、L、M具有可以输出的资源，C、F、I、K这四个关键工序可以通过增加资源的方式来压缩工期。因此，资源约束下工期优化问题就转换成由E、H、J、L、M工序向C、F、I、K工序转移资源的规划问题。那么根据运筹学中的运输问题，将E、H、J、L、M这5个工序等价于5个资源仓库，设m=5，I={1，2，…，m}；同理，C、F、I、K工序为资源需求地，令n=4，J={1，2，…，n}。表示从第i个工序输出点向第j个输入点转移的资源数量，对资源输出点工期的影响为增加天，输入点工期减少天。通过表2将问题以运输问题更直观地列示。最大供应量和最大需求量表明每个工序所能转移或者新增资源的极限，工序代号旁的数字，如E右侧格子内的0.8与C下方格子中的0.43，即上述提出的。中间格子中的数字表明从某一资源仓库向某一需求地调配资源时，对两者的共同作用。

（四）判断目标函数

首先，由表4与式（2）可以知道该初始解是满足前三个约束条件。其次根据式（1）计算6条线路的优化后工期。

Time=max{9+2.14*5.6，21-0.43*7-0.25*8-0.14*7-0.1*10，17-0.43*7+0.75*5.3-0.1*10，11+0.8*7.5+0.75*5.3-0.1*10，7+1.38*10.1,9+1.79*3.5}=max{20.984，14.01，16.965，19.975，20.938，15.265}=20.984。

由此可知，第一次资源转移调配后的工期为20.984，小于计划工期21，优于计划。

（五）解的改进

资源-工期运输问题与平常运输最大的区别是：需求量和供应量均可以不满足，而且资源的调配数量可以不是整数，即运输方法是无穷多的。所以用单纯的表上作业法已经无法解决该问题，而且随着网络计划复杂性的增加，通过LINGO等软件进行求解也会陷入“NP求解”困境。所以，本文认为在后续的求解中，应该采用启发式算法中的人工智能算法，如蚁群、遗传和粒子群算法等[5-7]。

4结论

本文针对实际工程项目中，基于网络计划资源一定的情况下，通过转移非关键工序资源、增加关键工序资源的资源重新优化配置，达到整体工期缩短的目的。另外从运筹学角度出发，提出了一种的新思路：即把资源转移问题转化为产销不平衡的运输问题，建立包含目标函数和约束方程的模型，以西北角法确定初始基可行解。又因为传统方法不适合该问题无穷多种可能性的非整数求解问题，提出后续解的改进应该采取人工智能算法进行求解。整体思路对于资源固定的工期优化问题是有实际借鉴意义的。

参考文献:

[1]PhillipsSJ,DessoukyMI.Solvingthetime/costtrade-offproblemusingtheminimalcutconcept[J].ManagementScience,1977,24:393-400.

[2]白思俊.现代项目管理(中)[M].北京:机械工业出版社,2003.

[3]陆绍凯,武振业.固定资源约束下的网络计划进度优化方法研究[J].重庆建筑大学学报,2005,04:88-92.

[4]《运筹学》教材编写组编.运筹学（第三版）.清华大学出版社，2007年.

[5]周康,同小军,许进.资源优化模型及遗传算法[J].华中科技大学学报(自然科学版),2005,10:59-62.

[6]张凯,赵国荣.粒子群优化算法在网络计划资源优化中的应用[J].海军航空工程学院学报,2008,01:75-78.

[7]郭云涛,白思俊,徐济超,张静文.基于粒子群算法的资源均衡[J].系统工程,2008,04:99-103.