256 运筹与管理 2016 年第 25 卷 [2] 快速获得关键链 Menders 等使用随机数编码, 设计了一种基于优先级的遗传算法来识别关键链 Bouleimen 和 Lecocq [3] 使用模拟退火算法解决了多种项目模型的关键链识别问题田文迪和崔南 [4] 方提出了基于动态规划思想的启发

Size: px

Start display at page:

Download "256 运筹与管理 2016 年第 25 卷 [2] 快速获得关键链 Menders 等使用随机数编码, 设计了一种基于优先级的遗传算法来识别关键链 Bouleimen 和 Lecocq [3] 使用模拟退火算法解决了多种项目模型的关键链识别问题田文迪和崔南 [4] 方提出了基于动态规划思想的启发"

蛙姜
7 years ago
Views:

1 第 25 卷第 3 期运筹与管理 Vol.25,No 年 6 月 OPERATIONSRESEARCH ANDMANAGEMENTSCIENCE Jun.2016 关键链断裂情况下的缓冲设置方法比较研究崔南方 1, 赵雁 2, 胡雪君 1 3, 田文迪 (1. 华中科技大学管理学院, 湖北武汉 ;2. 中南财经政法大学工商管理学院, 湖北武汉 ;3. 武汉纺织大学管理学院, 湖北武汉 ) 摘要 : 应用关键链项目管理方法时, 由于项目的复杂性, 在确定关键链和非关键链后, 进一步插入汇入缓冲时, 常常会出现资源再次冲突, 需要对计划进行重排, 重排后又出现关键链断裂汇入缓冲起不到保护作用等问题针对这些问题, 本文采用分散缓冲法制定项目调度计划, 并用项目实例证明了方法的可行性和通用性, 且设计仿真实验将分散缓冲计划与重排后的关键链调度计划进行比较, 结果发现当项目活动时间的变化性较小时, 应用分散缓冲法还可以获得较好的项目绩效关键词 : 项目管理 ; 关键链 ; 分散缓冲 ; 集中缓冲中图分类号 :F224 文章标识码 :A 文章编号 : (2016) doi:12005/orms ComparativeResearchonBuferManagementforCriticalChainGaps CUINan fang 1,ZHAOYan 2,HUXue jun 1,TIANWen di 3 (1.SchoolofManagement,HuazhongUniversityofScienceandTechnology,Wuhan430074,China;3.Schoolof Management,WuhanTextileUniversity,Wuhan430073,China;2.SchoolofBusinesAaministration,Zhongnan UniversityofEconomicsandLaw,Wuhan430073,China) Abstract:Intheapplicationofcriticalchainbufermanagement,whenthecriticalchainandnon criticalchains areidentified,someresourceconflictionsemergeagainbecauseofthecomplexityofproject,whichistobe solvedbyrescheduling.afterreschedulingsomenewproblemsemerge,gapsmaybecreatedinthecriticalchain andsomefeedingbufersappearunavailableforprotection.thispaperaimstosetupaprojectplanbythescat teredbufersmethodtoavoidthoseproblems.andprojectexamplesareusedtoprovethefeasibilityanduniver salityofthismethod.furthermore,simulationexperimentsaredesignedtocomparethescateredbuferedplan withrescheduledcriticalchainplan.theresultsoftheexperimentsshowthatscateredbuferedplansperform beterintheprojectswithsmalactivitydurationvariability. Keywords:projectmanagement;criticalchain;scateredbufer;centralizedbufer 0 引言 Goldrat [1] 于 1997 年将约束理论应用到项目管理中形成了关键链项目管理法 (CriticalChain ProjectManagement,CCPM), 该方法在项目管理实践中得到了成功应用 CCPM 的主要应用步骤包括识别关键链设置缓冲进行缓冲管理等国内外已有许多关于关键链的学术研究成果, 这些文献的研究内容主要集中在关键链识别方法和缓冲计算方法两方面 Goldrat 定义的关键链是 : 同时考虑活动的紧前关系和资源约束, 构建网络图, 将最长的路径作为关键链, 其它路径即为非关键链关键链决定了项目工期的长短当项目规模大工序间依赖关系复杂资源紧缺程度高时, 需使用有效的算法才能收稿日期 : 基金项目 : 国家自然科学基金资助项目 ( , ); 中央高校基本科研业务青年教师资助项目 ( ) 作者简介 : 崔南方 (1963 ), 男, 江西宁都人, 教授, 博士生导师, 研究方向 : 项目调度, 供应链管理 ; 赵雁 (1984 ), 女, 山东烟台人, 通讯作者讲师, 研究方向 : 项目管理, 鲁棒性项目调度 ; 胡雪君 (1989 ), 女, 湖北襄阳人, 博士, 研究方向 : 项目调度, 关键链项目管理 ; 田文迪 (1984 ), 女, 湖北罗田人, 讲师, 博士, 研究方向 : 项目调度, 项目管理

2 256 运筹与管理 2016 年第 25 卷 [2] 快速获得关键链 Menders 等使用随机数编码, 设计了一种基于优先级的遗传算法来识别关键链 Bouleimen 和 Lecocq [3] 使用模拟退火算法解决了多种项目模型的关键链识别问题田文迪和崔南 [4] 方提出了基于动态规划思想的启发式算法, 使用 PSPLIB 库中算例验证了算法的有效性程序和 [5] 吴澄提出了带有预约时间窗口约束的项目调度模型, 将分支定界法和启发式算法结合来识别该类项目模型的关键链按照 CCPM 方法, 识别关键链后, 要在项目网络的适当位置集中设置缓冲, 来应对项目的不确定性即在关键链的末端插入项目缓冲 (Project Bufer), 在非关键链与关键链的交汇处插入汇入缓冲 (FeedingBufer), 以保护整个项目如期完工人们提出了各种确定缓冲大小的方法 [1,6~8] 但以往文献较少关注非关键链汇入缓冲的位置和插入后的相关问题实际上, 由于项目网络的复杂性, 插入汇入缓冲后可能会出现资源的再次冲突, 或者非关键链溢出, 需要对计划进行重排重排后又可能出现关键链断裂缓冲所在位置起不到保护作用等, 目前对这些问题的研究并不多 Heroelen 和 Leus [9] 认为, 插入输入缓冲后, 可能在原有基准计划的某些地方产生资源冲突, 这样会使得缓冲失去预警保护作用, 因此, 插入缓冲后必须对原有基准计划进行调整, 但他们并没有就如何调整进行研 [10] 究彭武良和王成恩在提出一种基于优先权的关键链项目计划生成方法的基础上, 将缓冲作为虚 [11] 拟活动进行二次调度 Cui 等使用分支定界法进行关键链重排, 并提出了局部重排和全局重排两种策略, 最后使用大量的数据实验证明方法有效但这两种重排方法只解决了插入缓冲后的资源冲突, 重排后非关键链的溢出和关键链断裂等问题仍然存在本文针对插入汇入缓冲后出现关键链断裂和非关键链溢出的问题, 从缓冲设置方式的视角进行研究, 提出解决问题的方法下面先以一个具体的项目为例, 阐述关键链断裂问题 ; 然后用分散缓冲方法替代集中缓冲, 并以实验数据证实其在完工和计划鲁棒性方面的优势 ; 最后通过项目管理数据库 (PSPLIB) 中大量实例的验证, 证明该方法的普遍适用性 1 关键链断裂问题插入汇入缓冲所遇到的问题 [12] 该项目一共有 10 个活动, 只有一种可更新资源, 资源可用量为 10 个单位网络图中圆圈内的数字表示活动代号,1 和 10 为虚拟活动圆圈上括号内的两个数字, 分别代表该活动的时间和资源需求量该项目的基础排程如图 2 所示, 最短工期为 11 图 1 项目网络图图 2 项目基础排程图以图 2 所示的排程结果为基础, 可以找到多条关键链, 选择其中的为关键链, 则有三条非关键链, 即和 1 2 按照 CCPM 的思想, 要在 3 条非关键链与关键链的汇合处插入汇入缓冲采用 Goldrat 提出的剪切法 (thecutand PasteMethod,C&PM) 来计算缓冲大小, 即将非关键链长度的 1/2 作为汇入缓冲的大小插入汇入缓冲后的关键链调度计划如图 3 所示可以看到, 插入汇入缓冲后的调度计划存在多处资源冲突, 如时间段 2 5 和 6 8 处, 还引起非关键链的溢出, 即活动 3 的开始时间早于关键链活动 4 的开始时间因此, 需要对计划进行重排有二种重排方案 : 方案 1 为重排时保持关键链不变, 得到重排后的关键链调度计划 I, 如图 4 所示 ; 方案 2 为重排时允许关键链变化, 得到重排后的关键链调度计划 I, 如图 5 所示以图 1 中的项目为例, 来说明应用 CCPM 时,

3 第 3 期崔南方, 等 : 关键链断裂情况下的缓冲设置方法比较研究 257 图 3 重排前的关键链调度计划图 4 重排后的关键链调度计划 I 图 5 重排后的关键链调度计划 I 从图 4 和图 5 可以看出, 采用方案 1 重排后, 非关键链 1 2 和溢出过多, 造成项目工期过长, 而且汇入缓冲没有起到相应的作用采用方案 2 重排后, 解决了非关键链溢出问题, 项目完工时间也较短所以, 相对来说, 方案 2 较优, 但出现了关键链断裂, 即在活动 7 与 8 之间 8 与 9 之间存在间隙, 相当于在它们之间插入了缓冲, 这不符合 CCPM 的思想, 而且活动 5 后面的汇入缓冲不起作用鉴于插入汇入缓冲后可能重新引起资源冲突, 并在计划重排后出现关键链断裂, 本文拟采用分散缓冲替代集中缓冲, 即在项目基础排程的基础上, 采用分散缓冲法生成项目调度计划, 并与采用方案 2 重排后形成的关键链调度计划进行比较, 以验证分散缓冲法的效果 2 基于 STC 分散缓冲法的调度计划分散缓冲法是在项目的某些活动中插入时间缓冲, 生成项目调度计划在资源约束较大的情况下, 它不仅可以获得较短的项目工期, 还能增强计划的鲁棒性 Leus [13] [14] 和 VandeVonder 等都对分散缓冲进行了研究, 提出了各种分散缓冲设置方法 STC(StartingTimeCriticality) 法被证明是一种比较好的保证计划鲁棒性的分散缓冲设置方法 [14], 其主要思想是在项目活动之间插入时间缓冲, 来应对不确定性因素对项目按计划执行的影响该方法定义了各个活动的开始时间关键度 stc, 来表示各活动实际开始时间超过其计划开始时间的危险程度, 其计算公式为 : stc(j)=p(s(j)>s(j)) w j =r j w j (1) 其中,r j =P(S j ) 表示活动 j 延迟开工的可能性, 具体公式为 : r j = (i,j) T(A R) P(d i -LPL(i,j)) 公式 (1) 和 (2) 的相关符号说明如下 : (2) S j : 活动 j 的实际开始时间 ;s j : 活动 j 的计划开始时间 ;s i : 活动 i 的计划开始时间 ;d i : 活动 i 的工期 A: 原始项目网络中活动之间的先后关系原始项目网络 G=(N,A),N 为结点集合, 表示项目活动 ;A 为箭线集合, 代表活动之间的先后关系 R: 项目资源流网络活动之间的前后关系资源流网络 G =(N,R),R 为箭线集合, 代表活动间的资源流向 T: 项目原始网络与资源网络中 (G G ), 所有活动直接与间接前后关系合集 A R w j : 活动 j 偏离其计划开始时间时, 每单位偏离时间所引起的成本, 也被称为惩罚因子 LPL(i,j): 项目网络中活动 i 到 j 的最长路径时间, 该网络包括原始项目网络和资源流网络 G G 公式 (2) 中 (i,j) T(A R) 表示活动 i 是 j 的前序活动因此, 要计算活动 j 偏离计划开工的概率 r j, 首先要计算每个在总项目网络中与 j 有直接或间接紧前关系的活动对其开始时间影响的概率 P(d i -LPL(i,j)) stc(j) 值总的计算步骤为 : (1) 由项目网络 G 和各活动工期 d 可生成基准调度计划, 得到各活动的开始时间 s (2) 查找该计划中的资源流网络 G, 将该网络的并入原始项目网络 G G

4 258 运筹与管理 2016 年第 25 卷 (3) 根据新网络, 查找活动 j 的所有前序活动 i, 并可计算两两之间的最长距离 LPL(i,j) (4) 确定项目中活动的概率分布, 概率分布以活动原始时间 d 为期望值 (5) 由 s i,s j,lpl(i,j) 以及 d i 的概率分布, 可得概率值 P(d i -LPL(i,j)) (6) 由上述步骤计算在总项目网络中与 j 有直接或间接紧前关系的活动 i 对其开始时间影响的概率, 最后相加得公式 (2) 的 rj, 再由公式 (1) 最终得到各活动的 stc(j) STC 法建立项目计划的原理就是计算各活动的 stc 值, 优先在延迟开工风险 (stc) 高的活动前插入缓冲, 且通过反复迭代来确定缓冲插入的位置其算法步骤为 : (1) 以尽可能短的项目工期为目标, 生成一个项目基准调度计划 (BaselineScheduling,BS), 并据此确定项目工期 δn (2) 计算所有活动的 stc(j), 并将活动按 stc (j) 的大小降序排列 (3) 在 stc(j) 最大的活动前插入一单位时间缓冲, 同时将该活动 j 推迟一单位时间, 所有在 G G 中与 j 有直接或间接关系的后续活动的开始时间都推迟一单位时间, 得到一更新计划 (4) 计算该更新计划的完工期 Sn 和鲁棒性成本 stc(j) j N (5) 如果该更新计划的工期不超过项目完工期限 δn, 即 Sn δn, 并且鲁棒性成本较原计划更低时, 那么该更新计划可行, 并将之作为下一次迭代的初始计划, 转步骤 (2) 否则, 转步骤 (6) (6) 去掉在活动 j 前插入的一单位时间缓冲, 更新活动 j 及其后续活动的开始时间 (7) 在序列中选 stc(j) 次大的活动, 若 stc(j)=0, 算法终止, 输出一个鲁棒性调度计划否则, 在该活动前插入一单位时间缓冲, 更新该活动及其后续活动的开始时间, 得到一更新计划转步骤 (4) 该方法涉及到了项目中项目的完工期限活动权重各活动时间分布, 因此在用该方法前首先要确认这些相关参数由于重排后的关键链调度计划 I( 图 5) 所获得的工期为 14( 不包括项目缓冲 ), 为便于与关键链调度计划对比, 本文设置分散缓冲时, 也设定计划完工期限 Sn 为 14 其它相关参数设置如下 : 各活动的权重 w 都为 1, 设每个活动的时间都服从对数正态分布, 期望值分别为网络中给出的活动时间, 所对应的正态分布标准差都为 0.3 使用 STC 法, 所生成的基于分散缓冲的项目调度计划如图 6 所示图 6 基于 STC 分散缓冲法的项目调度计划 3 实验分析在插入汇入缓冲引起新的资源冲突, 并出现非关键链溢出时, 需要对关键链计划进行重排采用上述方案 2 进行重排, 所形成的关键链调度计划相对较好, 但它出现了关键链断裂, 类似于在关键链上分散插入了缓冲因此, 本文拟通过仿真实验, 对基于 STC 法的项目调度计划与重排后的关键链调度计划 I 进行比较, 来分析二种方法的效果 3.1 实验参数设定实验分析的内容是二种计划的完工鲁棒性和计划鲁棒性, 仿真实验的有关参数即项目执行策略设计如下 (1) 活动时间概率分布及模拟为表示活动时间的不确定性, 设项目活动的时间都服从对数正态分布 [7], 期望值为图 1 中给出的活动时间, 在每次模拟项目执行时都按这种概率分布给活动随机分配时间, 项目模拟执行 1000 次设活动 i 的时间为 d i, 即对数正态分布的期望值, 所对应的正态分布标准差为 σ, 则所对应的正态分布时间期望值为 :u(i)=ln(d i )-σ 2 /2, 用 MATLAB 模拟活动 i 的时间为 :lognrnd(u(i),σ) σ 设定为 0.3, 表示活动时间的变化性较小 (2) 项目执行策略项目执行时总体采用并行调度方法, 从前到后为每一时刻点作出每个活动是否运行的决策项目执行时, 采用二种执行策略 [15] : 执行基于 STC 的调度计划时, 采用时刻表 (Railway) 法, 所有活动的开始执行时间不得早于计划开始时间 ; 执行关键链调度计划 I 时, 采用接力赛 (Roadrunner) 策略, 除了每条链的初始活动 (Gating task) 外, 其他活动尽早开始, 关键链活动具有优先执行权

5 第 3 期崔南方, 等 : 关键链断裂情况下的缓冲设置方法比较研究 259 (3) 绩效评价指标以项目的按时完工率 (Timely ProjectCompletionProbability,TPCP) 作为完工鲁棒性评价指标 ; 以鲁棒性惩罚成本 (StabilityCost,SC) 作为计划鲁棒性评价指标, 其大小定义为 [15] : SC = w i S i (3) 其中 s i 和 S i 分别表示项目活动的计划开始时刻与实际开始时刻,w i 是惩罚因子 SC 反映了整个项目执行过程中, 因活动实际开始时刻偏离计划开始时刻所额外增加的成本, 因而称之为惩罚成本 3.2 单项目比较对图 5 和图 6 所示的调度计划进行比较, 实验结果如表 1 所示计划方案绩效指标平均按时完工率平均鲁棒性惩恶罚成本 (SC) 表 1 两种计划的仿真结果关键链调度计划 Ⅱ 基于 STC 法的调度计划可以看出, 在平均按时完工率方面, 两种计划差别不大, 关键链计划 I 略优于基于 STC 法的计划 ; 而在计划鲁棒性方面, 基于 STC 法的计划明显活动变化性 σ 平均鲁棒性惩罚成本 (SC) STC 法优于关键链计划, 能较好地解决项目执行过程中的资源冲突, 应对突发情况, 保持计划的稳定性 3.3 多项目比较表 2 两种计划方法的平均绩效对比结果 CCPM 为进一步验证 STC 分散缓冲替代集中缓冲的方案的有效性和通用性, 本文用项目管理数据库 (PSPLIB) 中的帕特森 110 个项目实例, 分别试用 CCPM 的集中缓冲法和基于 STC 的分散缓冲法建立项目调度计划实验发现, 采用 CCPM 建立计划时, 110 个项目经重排后有 107 个项目出现非关键链溢出和关键链断裂, 再试用 STC 分散方法为这些项目建立计划时, 发现都可有效地避免这些问题, 说明了方法的通用性再通过仿真实验模拟这 107 个项目的两种缓冲计划的运行, 得到平均鲁棒性指标, 以对比两种计划的绩效且为了验证项目活动时间不确定性大小对两种计划的影响, 在仿真实验时, 设置低中高三种活动时间不确定性大小, 即将活动对应的正态标准差 σ 分别设为经过实验, 得到 107 个项目的两种缓冲计划的平均绩效指标如表 2 所示 STC 法平均按时完工率 CCPM STC 法完工率较高的项目数从表 2 可以看出, 在鲁棒性惩罚成本方面, STC 法始终优于 CCPM 当活动变化性较低时( 为 0.3),STC 法在鲁棒性惩罚成本和按时完工率方面都优于 CCPM, 大部分项目 STC 计划的完工率都比 CCPM 计划较高随着活动变动性变大, 即当为 0. 6 和 0.9 时,SC 变大, 但两种计划的 SC 差距逐渐变小 ;STC 计划的完工率占优的项目逐渐减少, 且 CCPM 平均完工率高于的 STC 平均完工率说明随着项目活动的不确定性增大,STC 分散缓冲法逐渐失去了完工鲁棒性方面的优势, 且在计划鲁棒性的优势也逐渐变小 4 结论鉴于使用 CCPM 方法生成项目调度计划时, 因插入汇入缓冲可能引起非关键链溢出, 重排后又会出现关键链断裂本文针对这种情况, 采用分散缓冲替代集中缓冲来避免这些问题, 并增强项目计划的鲁棒性经过单个项目和大量项目的仿真实验分析, 得到以下结论 : (1) 当活动时间的不确定性程度较小时, 即在一个较稳定的项目环境中,STC 在按时完工率和计划鲁棒性方面都优于 CCPM 所以, 可以采用分散缓冲法制定项目调度计划, 不仅可以避免非关键链溢出和关键链断裂, 而且可以取得较好的项目绩效 (2) 在不确定性较大的项目执行环境中, 即活动时间的变化性较大时, 如果追求更高的项目按时完工率, 则可以采用插入汇入缓冲后的关键链重排算法制订项目调度计划, 尽管可能出现关键链断裂, 但仍然可以获得较高的项目按时完工率 (3) 当项目活动开始时间发生偏离所引起的成本较高时, 应更多地考虑分散缓冲法, 以保证各活动按计划时间开工, 因为它所产生的项目调度计划有较好的计划鲁棒性, 也可避免非关键链溢出和关键链断裂问题

6 260 运筹与管理 2016 年第 25 卷参考文献 : [1] GoldratEM.CriticalChain[M].NewYork:TheNorth RiverPress,1997. [2] MendesJJM,Gon alvesjf,resendem G C.A ran dom keybasedgeneticalgorithm fortheresourcecon strainedprojectschedulingproblem[j]. Computers& OperationsResearch,2009,36(1): [3] BouleimenK,LecocqH.A neweficientsimulatedan nealing algorithm for the resource constrained project schedulingproblem anditsmultiplemodeversion[j]. EuropeanJournalofOperationalResearch,2003,149 (2): [4] 田文迪, 崔南方. 关键链项目管理中关键链和非关键链的识别 [J]. 工业工程与管理,2009,14(2): [5] 程序, 吴澄. 一种复杂项目调度问题的混合智能算法 [J]. 计算机集成制造系统,2006,12(4): [6] NewboldR C.Projectmanagementinthefastlane applyingthetheoryofconstraints[m]. TheSt.Lucie Press,BocaRaton,1998. [7] TukelOI,Rom W O,EksiogluSD.Aninvestigationof bufersizingtechniquesincriticalchainscheduling[j]. EuropeanJournalofOperationalResearch,2006,172 (2): [8] 别黎, 崔南方. 关键链多项目管理中能力约束缓冲大小研究 [J]. 计算机集成制造系统,2011,17(7): [9] HeroelenW,LeusR.Onthemeritsandpitfalsofcriti calchainscheduling[j].journalofoperationsmanage ment,2001,19(5): [10] 彭武良, 王成恩. 关键链项目调度模型及遗传算法求解 [J]. 系统工程学报,2010,25(1): [11] CuiN,TianW,BieL.Reschedulingafterinsertingthe buferinthecriticalchainscheduling[c]//logistics SystemsandInteligentManagement,2010International Conferenceon.IEEE,2010,2: [12] HeroelenW.Projectandproductionscheduling[M]. Leuven:Acco,2007. [13] LeusR.Thegenerationofstableprojectplans[D]. Departmentofappliedeconomics,KatholiekeUniversiteit Leuven,Belgium,2003. [14] VandeVonderS,DemeulemeesterE,HeroelenW. Proactiveheuristicproceduresforrobustprojectschedu ling:anexperimentalanalysis[j].europeanjournalof OperationalResearch,2008,189(3): [15] VandeVonderS,DemeulemeesterE,HeroelenW,etal. Theuseofbufersinprojectmanagement:thetrade of betweenstabilityandmakespan[j].internationaljournal ofproductioneconomics,2005,97(2):

<4D F736F F F696E74202D20B5DA39BDB25FB9D8BCFCC1B4CFEEC4BFB9DCC0ED2E707074>

<4D F736F F F696E74202D20B5DA39BDB25FB9D8BCFCC1B4CFEEC4BFB9DCC0ED2E707074> 第 9 讲关键链项目管理 Critical Chain Project Management 项目管理概述关键链缓冲与计划调度基于 TOC 的项目调度方法相关的研究问题项目管理概述工程项目 : 在规定时间内, 由专门组织起来的人员共同完成的有明确目标的一次性工作从生产管理的角度看, 工程项目属于单件生产项目管理 : 对工程项目进行计划组织和控制工程项目建设往往需要多学科多部门