基于动态规划的项目工期优化

1、基于动态规划的项目工期优化摘要：工期是工程项目的一个重要指标，如何在有限的资源下进行工期控制、工期优化也是工程管理人员面临的一个难题。现在最常用的计划管理方法如cpm，可以通过计算得出项目的关键路径来控制工程进度，但是当项目的关键路径长度大于项目预计工期时，就需要对项目的工期进行优化，而现在并没有一种方便通用的工期优化算法。基于这一背景，结合运筹学动态规划的相关理论，本文给出一种基于动态规划的项目工期优化算法。关键字：cpm；关键路径；工期优化；优化算法method of project period optimization based on dynamic programmingabstr

2、act: period is an important indicator of a project, how to control and optimize the period of a project with limited resources is also a problem faced by project managers. now the most commonly used project management methods such as cpm(critical path method), can control the period by calculating t

3、he critical path project. when the project critical path length is longer than the expected time of the project, project period optimization is needed, but now we dont have a convenient and general method to optimize the period of a project. based on this background., combined with the theory of dyn

4、amic programming in operations research, a method of project period optimization based on dynamic programming is presented in this paper.key words: cpm; critical path; project optimization; optimize algorithm1.绪论1.1问题的提出在项目网路计划中, 综合考虑任务之间的次序约束条件, 时间约束条件等得到的项目最长任务序列, 称为项目的关键路径1 。项目的关键路径是制约项目工期的最长路经。当

5、项目的关键路径长度大于项目预计时就需要对项目的工期进行优化, 工期优化的主要思想就是对关键路径上的任务进行工期压缩, 因为对非关键路径上的任务压缩不能达到缩短项目工期的目的2 。一般来讲任务的工期压缩量跟压缩代价是成正比的, 而且所有关键路径任务上的时间压缩总量的限度为不改变原有关键路径的构成, 项目的工期压缩往往都是一个反复迭代的过程。在简单的情况下, 任务网络中只存在一条关键路径, 如图1(a)所示; 在复杂的情况下, 任务网络中会存在多条关键路径, 如图1(b)所示。本文首先给出简单情况下的项目工期优化方法, 然后在此算法基础上给出复杂情况下的项目工期优化策略。1.2研究背景对于施工进度

6、计划系统，不论设计新系统或者改进原有系统，都需要提出许多方案，甚至列出所有可行方案，再经过反复论证和比较，选出最佳方案。一般来说，原始施工进度计划只是为人们作出进度安排提供了一个基础模型。它还可能潜在着一些尚未解决的矛盾和缺点：如在时间方面，可能超过了上级规定的期限；在资源方面可能出现供不应求的矛盾；或者说在时间与资源方面的潜力还远没有得到最佳的发挥。因此对于任何一项施工任务还要运用最优化原理，去调整和改善原始施工进度计划，以作出最理想的进度安排。当编制的施工网络计划计算工期大于合同工期时，在人力、材料、设备等资源有充足保证的前提下，通过压缩关键线路中工作的持续时间，以满足工期的要求。在施工措

7、施上，选择压缩时间后对质量影响不大、有充足备用资源、且缩短工作持续工作时间而增加费用最少的关键工作，并通过增加资源数量，增加工作班次，改进施工工艺等途经缩短关键工作的时间。在优化方法上，一般最常用的是图上计算的方法，即根据网络计划的关键路线和关键工作，在网络图的关键线路上一天天的压缩活动时间，直至计算工期达到合同工期为至。该方法的优点是计算简单,缺点是在优化过程中可能出现某些非关键工作转变为关键工作，造成增加费用过大。而且计算量大、优化速度慢。面对原有方法的缺陷，本文通过运筹学的动态规划有关知识，利用动态规划实现对工期的优化，同时实现在matlab上的动态规划程序作业法，从而使优化过程更加简便

8、准确，节省了大量的计算量，同时节省了大量的人力、物力和时间。1.3研究意义和目的1.3.1研究意义通过本文提出的工期优化算法，可以克服原有方法的缺陷，得到问题的最佳解决方案，并可以建立数学模型，编制程序代码，实现在matlab上的操作，为解决此类问题提供了快捷、高效的方法。为以后此类问题的研究者提供一定的参考，并且在一定程度上提高了工期优化人员的工作效率，做到了合理的时间分配和有效地资源配置。1.3.2研究目的1.结合工程管理专业背景及运筹学知识，学会运用运筹学理论知识解决实际问题,提高理论知识解决实际问题的能力。2.将动态规划方法用于网络计划优化,建立了工期优化的动态规划数学模型，利用动态规

9、划的递推方法，寻求工期优化的最优目标。3.掌握matlab的基本操作方法及编制程序代码的过程。1.4研究内容通过对网络计划的研究，运用动态规划法对其进行有效的优化，调整和改善原始施工进度计划，以作出最理想的进度安排和资源配置。本次研究针对工程项目中存在的以下的问题进行优化：1） 图上作业工期优化过程中可能出现某些非关键工作转变为关键工作，造成增加费用过大。2） 图上作业工期优化计算量大、优化速度慢。3）图上作业工期优化迭代过程繁琐，易优化出错。1.5研究方法与思路本次研究运用运筹学动态规划方法解决网络计划的工期优化问题，通过matlab编程进行求解，并通过一个事例来验证算法。本文研究思路如图2

10、所示：提出问题在matlab中建立d-opt工期优化算法总结建立基于动态规划的理论基础案例验算图2 本文研究思路2.理论基础2.1形式化定义当项目任务网络中只有一条关键路径时, 假设关键路径上面任务集合为c - setw - set, 因此,可知 c - set的任务不存在时间上的重叠。设项目需要压缩时间的总量为t, 对于wic-set, 其可压缩的最大时间量表示为 lim (wi), 一般来讲任务 wi 的压缩代价取决于任务压缩的工期量和任务的自身因素, 比如任务的关键度、风险度等。因此, 任务 w i的压缩代价可以用代价函数 g (w i, x )来表示, x 表示压缩的时间量。因此, 定

11、义任务 w i 的压缩代价函数如下: (1)其中, k 是常量, (w i )是调整因子, 调整因子取决于任务的自身因素, 如果只考虑任务的关键度, 风险度，对应的权值分别为 c1和c2, 则调整因子可以简单的描述为（wi）=c1* (w i ) + c2 * (w i )。如果假设 | c - set | = k, 则关键路径任务的工期压缩代价矩阵如下所示: （2）算法求解子集s-setc-set 以及序对集合s(s-set), s(s-set)中的每个元素都是一个序对（wi,xi），其中wis-set, ,s-set中的每一个任务唯一映射到s（s-set）的一个序列，且满足约束p: （3）

12、2.2优化算法根据以上描述，下面给出基于动态规划的单关键路径网络的工期优化算法。参数s用来存放最优选择序列，函数返回最小压缩代价值。优化算法描述如下：function d-opt(s,c-set-wi,t)beginif | c - set |=1beginwic-set中的任务；将选择元组（w,t）加入列表s；return g(wi,t);endwic-set中的第一个任务；/*不选择第一个关键路径任务的处理*/max= d-opt(s,c-set-wi,t);/*当选择第一个关键路径的处理*/tuple；s1；/*初始化列表s1为空*/for j=1 to tbegins2；/*初始化列表

13、s2为空/tempg(wi,j)+ d-opt(s2,c-set,t-j)；if maxtempbeginmaxtemptuple(wi,j)；s1s2；endendif tuple将元组tuple加入s1,将s1中的所有元组加入s；return max；end该算法实质是把问题划分成子问题, 然后再递归求解, 最终把最优的压缩序对存放在列表s中。在此算法基础上, 本节给出多关键路径网络的工期压缩策略。当项目任务网络中存在多条关键路径时, 不能直接利用d - opt优化算法进行求解。因为此时网络中存在着并行的关键路径, 如图1 ( b )所示。根据关键路径的概念可知, 压缩并行关键路径一个分支

14、上的任务工期并不能达到压缩项目工期的目的, 因此要想在并行关键路径上试图压缩工期, 必须对并行关键路径上的每一个条分支都压缩相同的量, 才能达到压缩项目工期的目的。此外, 并行关键路径可以是嵌套存在的, 就是说把并行关键路径的一条分支看成是一个网络计划的话, 那么这个子网中也存在并行关键路径, 图 1 ( b )中就是存在嵌套的并行关键路径的一个例子。根据上述分析, 下面给出多关键路径网络的工期优化策略, 该策略是以单关键路径网络的工期优化方法为基础。先考虑无嵌套并行关键路径的情况, 即并行关键路径的每个分支都是其所在分支网络的唯一的关键路径, 并行关键路径的每个分支肯定有共同的源点和汇点。继

15、续假设项目关键路径集合为 c - set, 此时 c - se t中的任务可能存在时间重叠。假设一个无嵌套的并行关键路径有 c 条分支, 分支路径集合表示为 p - setp1, p 2, pc, 其中对php - set, 有phc - se t, 并且对于px, py p - set, 且x y, 都有 px py = 。由于并行关键路径的每个分支都是在时间上重叠的, 因此在进行工期压缩时, 当且仅当各个分支路径同步压缩, 才能得到有效的项目工期压缩。因此可以把p - set中的各个分支路径看成是一个整体, 作为一个特殊的任务w来看待, 如果要对w压缩工期量为x, 则可以把每个路径分支看成

16、是一个子网络的关键路径, 按照优化算法 d - opt 求得最小压缩代价, 即表示为: （4）根据以上假设后对并行关键路径处理, 接着可以应用单关键路径网络的工期优化算法来解决多关键路径网络的工期压缩问题。如果考虑存在嵌套的并行关键路径, 本文的思想是从最内层的并行关键路径出发, 把它看成是一 个整体性任务 w, 然后利用公式 ( 4 )求解 w 的压缩 代价, 按照此种方法从内层向外层计算, 直到所有的 并行关键路径都处理完为止, 处理完的网络可以看 成是一个单关键路径网络, 因而可以按照单关键路 径网络的工期压缩方法进行求解。3.程序编写根据前章所述算法，在matlab中编写程序代码如下：

17、function max,s = dopt(s,cset,t,g )%untitled summary of this function goes here% detailed explanation goes here if length(cset) = 1 max = g(cset(1),t); s = s;cset(1),t; return; end w = cset(1); max,s = dopt(s,cset(2:end),t,g); tuple = ; s1 = ; for j = 1:t s2 = ; if t = j maxtmp,s2 = dopt(s2,cset(2:en

18、d),t - j,g); temp = g(w,j) + maxtmp; else temp = g(w,j); end if max temp max = temp; tuple = w,j; s1 = s2; end end if isempty(tuple) else s = s1;tuple; end return; end执行语句为：max,tmp=dopt(s,cset,t,g)4.案例验证该算法的实验验证如下:假设一个项目进行w bs任务分解后的任务集合为: w - se t = w 1, w 2, w 3, w 4, w 5, w 6, w 7, w8, w 9, w 10,

19、w 11, w 12, w 13 , 基于wbs任务进行项目计划编制后, 各wbs任务的主要参数如表1所示。表1 任务计划时间参数表任务原定工期（天）w12w28w310w415w512w623w76w86w916w1014w1118w1212项目的wbs任务上的强制性时间限制条件如表2所示, 假设任务上强制性时间限制条件的添加都经过了计划编排过程中的强制限制冲突处理, 每个任务上可以定义多个强制性时间限制条件。表2 强制性时间限制表任务强制性时间限制类型强制限制时间w4强制开工限制2011-01-07w8开工不晚于限制2011-02-25w8开工不早于限制2011-01-28w10完工不晚于

20、限制2011-03-10该项目任务次序依赖关系已经在计划编制过程中确定, 并在编制过程中排除掉所有的异常情况。并假设跨企业项目中的任务依赖关系都是完成-开始 ( fs )类型的依赖, 因此可以假设项目任务的单代号网络图如图3所示。图3 项目原始网络计划假设该项目的开始时间为2011 - 1- 5, 计算任务的准确参数如表3所示。表3 进度计算后的任务时间参数表任务工期最早开始最晚开始最早结束最晚结束关键路径w122011-01-052011-01-072011-01-072011-01-07是w282011-01-072011-01-202011-01-152011-01-28否w310201

21、1-01-072011-01-182011-01-172011-01-28否w4152011-01-072011-01-072011-01-222011-01-22是w5122011-01-152011-02-132011-01-272011-02-25否w6232011-01-282011-01-282011-02-202011-02-20是w762011-01-222011-01-222011-01-282011-01-28是w862011-01-282011-02-252011-02-032011-03-03否w9162011-02-202011-02-202011-03-082011-

22、03-08是w10142011-01-282011-02-242011-02-112011-03-10否w11182011-03-082011-03-082011-03-262011-03-26是w12122011-03-082011-03-142011-03-202011-03-26否w1352011-03-262011-03-262011-03-312011-03-31是其中关键路径集合为 c-set= w1, w4, w6 , w7 ,w9,w11,w13 , 如果项目的预定工期为2011-3-25, 则可知项目的工期超过预定工期6天。通过本文提出的工期优化算法对该项目进行工期优化, 根据图3判断本项目为单关键路径工期优化, 假设关键路径任务的工期压缩代价矩阵如表4所示。表4 关键线路任务工期压缩代价表w t 123456w1w4w60.30.40.50.6w70.20.4w90.40.50.71.01.2w110.10.30.4w130.61.0运行程