固定资源约束下的网络计划进度优化方法研究.doc

固定资源约束下的网络计划进度优化方法研究 如何制定进度计划一直是各种行业中非常重要的问题。制定进度计划的主要目的是在一定的资源约束下使工期最短，或者是在工期一定的约束条件下使资源（费用）消耗最小。由此自20世纪60年代以来随着运筹学的发展产生了很多相关的研究成果，近期的研究主要围绕固定资源约束下的进度计划制定而展开。Bouleiman和Lecocq提出了一类模拟退火算法以有效得对工作节点进行排序1, Rolf等学者运用拉格朗日松弛提出了一种基于最早开始时间的整数规划方法对进度计划进行优化2.然而相关的大多数研究是从传统的“机器排序”问题演变而来，并不很适用于解决工程项目中的进度问题。工程项目的进度计划与传统的“机器排序”问题有着较大差异：一是工作节点有着明确的先后作业顺序并且一般不能改变，例如房屋的修建必须是从基础开始。二是工作节点的作业时间有着较大的不确定性，由于气候、设计等因素造成的工期变化极为常见。三是由于工程项目进度计划的时间窗单位比较大，所以最初的进度计划制定没有像一般的制造加工业那样要求精确。因此工程项目中的进度优化集中于研究对资源如何进行分配，而不是各工序之间的作业次序调整。现代的工程项目都是应用基于CPM和PERT的网络计划技术作为计划、分配、控制的重要手段和工具。最常见的网络计划进度优化方法是强制缩短法，即采取措施使网络计划中的某些关键工作的持续时间尽可能缩短3.目前关于工期进度优化方法的研究思路也集中于不断改进强制缩短法，力求在优化项目工期的同时，使所增加的额外成本最小。吴育华等学者提出了割集平行路线差额法解决工期优化的算法4，刘津明运用“最大流最小截”理论研究了工期一成本非线性变化时工期优化的算法思路5.随着现代信息技术的日益成熟，使用Management scientist等软件可以非常迅捷的求出基于上述强制压缩法进行进度优化的最优结果6.强制压缩法要求必须从外界投入新的资源到关键线路的工作节点中，然而在现实工程项目建设中经常缺乏多余资源，这就要求利用网络计划中非关键工作的既有资源进行工期优化，解决所谓的赶工问题。基于上述思想，本文对单代号网络计划中固定资源约束下的工期优化算法进行探讨。利用非关键工作的既有资源进行工期优化，就是利用非关键工作的时差，抽调其中的部分资源用于加强关键工作，以缩短关键工作的持续时间，使工期缩短3.利用关键线路的转移进行工期优化的最终结果，是使网络计划中出现尽可能多的关键线路，或者是关键线路的工期与次关键线路的工期差值最小。即当原关键线路的工期经过优化达到设定缩短的工期目标时，就认为工期优化已达到期望。利用关键线路的转移优化工期，必须先明确关键线路上有可以压缩的关键工作，非关键工作节点有关键线路上可压缩工作节点压缩所需的资源，并且这种资源可以分割转移。非关键工作节点上的资源转移会延长其自身的工期，而关键线路上的工作节点接受了转移的所需资源后会缩短计划工期，从而缩短项目的整体工期。根据资源输出和输入节点的位置，原网络计划中的所有线路工期有可能出现不同程度的延长或缩短，但压缩后的原关键线路工期不能小于次关键线路工期。同时，工作节点上资源的输出或输入量也受到最小资源需求用量和最大压缩时间的约束。因此，将非关键工作中的资源转移到关键线路上的工作中进行工期优化，要解决如下问题：如何选择进行资源输出的非关键工作节点，各非关键工作节点输出多少资源，以及如何选择关键线路中的资源输入节点，各压缩节点输入多少资源。3.1 前提假设为简化研究，进一步假设网络计划的所有节点中只有一种可以分割转移并且影响工期的资源。以往的大部分工期优化研究都是基于成本费用和工期之间的关系，通常项目所需的各种资源也能转化为费用进行衡量，因此我们的假设不失一般性。调整非关键工作节点的总时差会影响其后工作节点的最早开始时间，加大项目的不确定性，因此这里仅选择具有自由时差的非关键工作节点作为资源输出对象。同时，假设工期优化前的网络计划中只有一条关键线路，在满足约束前提下，各工作节点的资源变化量与工期变化量成线性关系。3. 2 变量假设设网络计划由m个工作节点和二条线路组成分别记为J1,2, ,m和I=1,2二.特别地，将关键线路表示为cp , cp I ，关键线路上的p个工作节点表示为cpk, cpk J, kP, P =1 , 2, , p .以xj表示工作节点 j 资源的输入或输出量，qj为工作节点j的计划资源用量。qj表示工作节点j资源需求量的极值，对于关键线路上的节点，qj表示工期经过最大压缩后，完成工作所需的资源量，对于非关键线路上的节点，qj表示充分利用自由时差后完成工作需要的资源量，因此有xj |qj qj|.由前所述，在网络计划只做一次性工期优化的前提下，同一工作节点的资源只能单方向转移（输入输出）或者不发生变化。设tj为工作节点j的计划工期，以tj表示工作节点j工期变动的最大范围。对于非关键工作节点，tj表示可以利用的自由时差，对于关键线路上的工作节点，tj表示极限压缩时间。设aj为工作节点j上资源与工期时间的相关系数，aj表示约束条件下单位资源量对工期的影响程度，由资源变化量与工期变化量成线性关系的假设，有进而工作节点j因为资源量变化而引起的工期时间变化量为ajxj.设Tcp, Ti （icp）分别表示关键线路和非关键线路的计划工期，aij表示工作节点j的资源变化对线路i工期的影响系数。3.3算法分析令Ajqjtj, BjAj.Aj表示节点j上包含有工期和资源用量的计划安排，Bj表示关于节点j所有可行计划安排的集合。根据是否是关键节点，有：基于关键线路的转移而提出的工期优化算法，是寻找能最大压缩工期的集合B,B=Bj, j J .以Fmax表示关键线路节点输入资源后所能压缩的最大工期，固定资源约束下的工期优化问题可以转化为解决如下嵌套模型：式（2）表示对于非关键工作节点在工作量恒定的前提下输出资源会导致其工期延长但工期延长量不能超过可利用的自由时差。同理式（3）表示对于关键线路上的工作节点输入资源会使工期缩短工期的缩短量不能超过极限压缩时间。（4）式表示工期优化后的关键线路工期不小于网络计划中的其它线路的工期。（5）式表示节点资源改变对工作线路工期的影响。式（6）和式（7）分别表示非关键工作节点中输出的资源全部输入到关键线路的工作节点中，各节点资源量改变的绝对值非负。在实际工期优化时，非关键工作节点的自由时差和充分利用时差后完成工作所需的最小资源量，关键线路上工作节点的极限压缩时间和对应的需求资源量是已知的，由可以求出各节点的资源时间相关系数从而把上述模型转化为线性规划问题求解。下面以一个算例说明固定资源约束下运用转移关键线路法进行工期优化的解决过程。我们引用文献7l的算例作为工期优化对象随机给出了关键线路上工作节点的最大压缩工期并以（tj+tj） （qj-qj）=qjtj 给出各节点工期极值下的资源需求量。图1显示了单代号网络图中各工作节点的计划工期和资源消耗量。各工作节点上的资源一时间参数如表1所示。网络计划各工作线路的计划工期以及其上可进行资源转移的节点如表2所示。对此算例进行工期优化，实质上就是从H, J, E,L,M节点向C, F, 1, K节点输入资源，这里用lindo程序运算求解，主要结果如图2所示。图2中的结果表明在不从外界投入资源的情况下，可以利用网络计划中的既有资源，使工期最大缩短4个时间单位。在实际的工程建设中，很多都是以季度作为制订网络计划的时间单位，因此上述算法对于工程实践中的工期优化有着明显的意义。图3为算例经过工期优化后的网络计划图（数据取整），优化后的网络计划中出现了3条关键线路：A一B一H一O,A一C一F一I一K一O, A一M一O.本文提出了运用关键线路的转移进行工期优化的一类算法。在网络计划的既定资源约束下，利用非关键工作的自由时差将其上的资源转移到关键线路的可压缩工作上，从而缩短了整个网络计划的工期。为简化模型，本文只利用有自由时差的非关键工作作为资源输出对象，但也可以将具有时差的工作节点一并考虑，从而可能获得更大的优化效果。此外，节点的工期一资源并非一定成线性关系，已有学者利用灰色预测方法对这一问题进行了深入研究8.在实际的工程项目中，工期优化还必须考虑资源均衡等诸多现实问题。因此一般情况下仅需将原关键线路的工期进行一次性优化到达工期优化的期望值即可，实际上如果在优化后新的关键线路上仍然有可以继续压缩的工作节点，并且非关键节点上也有相应的时差资源，就可以再次利用上述算法进一步进行优化。但如果完全利用非关键节点的时差资源后仍不能满足工期优化期望，则必须重新利用强制压缩法从外部投入新的资源。在明确资源和工期的相关系数后，本文提出的算法转化为了很多商业软件都能求解的规划问题，对算法在实际工程行业中的推广有着积极作用。：1K. Houleiman. H.Lecocq. A new efficient simulated annealing algorithm for the resource一constrained project scheduling problem and its multiple mode version J. European Journal of0perational Research. 2003（149）：268一281.2Rolf H.Solving project scheduling problem、by minimum cut computations J. Management Science, 2003, 49（3）：330-350.3白思俊。现代项目管理（中）M.北京：机械工业出版社，2003.4吴育华，李崇斌，吴灵慧。割集平行路线差额法一种确定网络计划最佳工期的有效算法J.管理工程学报，1996,10（2）：67一71.5刘津明。工程项目进度计划优化方法的研究J.天津大学学报，2003,36（5）：610一613.6David R. Anderson, Dennisn J. Sweeney, Thomas A. Williams. An Introduction to Management Science Quantitative Approaches to Decision Making M.Thom son Learning, 2003： 340.7Son一Sen Len