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