（系统工程专业论文）基于关键链的项目调度模型与算法.pdf

东北大学硕士学位论文 摘要 基于关键链的项目调度模型与算法 摘要 资源受限项目调度问题是一类典型的运筹学难题。随着经济全球化导致市 场竞争的日趋激烈，现代项目日趋复杂，要求周期更短、准时完工率更高、成 本更低。传统的项目计划与调度方法已经无法完全满足现代项目管理的实际需 求。关键链作为一种全新的项目管理方法，已经在多个欧美企业获得成功应用， 并在北美和欧洲发达国家受到了相当的重视和研究。关键链项目管理方法在许 多方面具有显著优点，能有效缩短工期，有效管理项目执行过程中的不确定性， 提高项目管理效率。 关键链是项目的制约因素，加强对关键链的管理意义重大，然而关键链的 识别却十分困难。本文在吸收前人研究成果的基础上，提出了一种关键链识别 方法，试验证明，此方法行之有效。该方法与其他优化算法相结合，可以解决 关键链的最优性问题，但目标仅限于工期最短。 在项目执行的过程中存在许多不确定性，这些不确定性对项e t 的完成会造 成一定影响。为了消除或减少不确定性对项目造成的影响，关键链方法采用设 置缓冲区的办法。本文将汇入缓冲区的设置分为汇入点的确定、非关键链的确 定和汇入缓冲区大小的确定三个步骤，提出了汇入点的确定方法和非关键链的 确定方法，改进了汇入缓冲区大小的确定方法，使汇入缓冲区的设置方法更加 系统化，更具可操作性。通过在不同执行环境中进行模拟试验，与现有汇入缓 冲区设置方法在执行效果上进行比较，试验结果表明，本文提出的方法优于现 有方法。 关键词：项目管理项目调度约束集理论关键链缓冲区关键路线法 计划评审技术 东北大学硕士学位论文 a b s t r a c t c r i t i c a lc h a i nb a s e dm o d e l sa n da l g o r i t h m s f o rp r o je c ts c h e d u l i n g a bs t r a c t r e s o u r c e - c o n s t r a i n e d p r o j e c ts c h e d u l i n gp r o b l e m s ( r c p s p s ) a r et y p i c a l d i f f i c u l tp r o b l e m so fo p e r a f i o n a ir e s e a r c h 。b e c a u s eo fs e v e r em a r k e tc o m p e t i t i o n d u et ot h ed e v e l o p m e n to fe c o n o m i cg l o b a l i z a t i o n ，c u r r e n tp r o j e c t sb e c o m em o r e a n dm o r ec o m p l e xa n dr e q u i r es h o r t e rp r o j e c td u r a t i o n s ，h i g h e rj u s t - i n t i m e c o m p l e t i o nr a t e s ，a n dl e s sc o s t c o n v e n t i o n a lm e t h o d sf o rp r o j e c tp l a n n i n ga n d s c h e d u l i n gc a n n o tm e e tt h ep r a c t i c a ln e e d so fm o d e mp r o j e c tm a n a g e m e n t a sa n e wm e t h o do fp r o j e c tm a n a g e m e n t ，c r i t i c a lc h a i nm e t h o d ，w h i c hh a sb e e n s u c c e s s f u l l yu s e di ns o m ea m e r i c a na n de u r o p e a ne n t e r p r i s e s ，h a sb e e nr e c o g n i z e d a n dr e s e a r c h e di nd e v e l o p e dc o u n t r i e si nn o r t ha m e r i c aa n de u r o p e c r i t i c a lc h a i n p r o j e c tm a n a g e m e n t ( c c p m ) i sa d v a n c e di nm a n ya s p e c t s ，p u r s u i n gs h o r t e rp r o j e c t d u r a t i o n ，m o r ee f f i c i e n tm a n a g e m e n to f u n c e r t a i n t i e st h a tw i l le m e r g ei nt h ep r o c e s s o f t h ep r o j e c te x e c u t i o n s ，a n dh i g h e rm a n a g i n ge f f i c i e n c y t h ec r i t i c a lc h a i ni st h ec o n s t r a i n e df a c t o ro fap r o j e c t i ti ss i g n i f i c a n tt o e n h a n c et h em a n a g e m e n to ft h ec r i t i c a lc h a i no fap r o j e c t b u ti d e n t i l y i n gt h e c r i t i c a lc h a i no fap r o j e c ti saq u i t ed i f f i c u l tt h i n g i nt h i st h e s i sam e t h o dt oi d e n t i f y t h ec r i t i c a lc h a i no fap r o j e c t ，w h i c hi sb a s e du p o nt h er e s e a r c h e so ft h ep i o n e e r s ，i s p r o p o s e d t e s t sh a v ep r o v e dt h ev a l i d i t yo ft h em e t h o dp r o p o s e d w i t ht h e c o o p e r a t i o n w i t ha n o t h e r o p t i m i z a t i o na l g o r i t h m s ，t h i s m e t h o dc a nr e s o l v e o p t i m a l i t yp r o b l e mo fc r i t i c a lc h a i n ，b u tt h eo b j e c t i v ef u n c t i o ni sl i m i t e dt o m i n i m i z i n gt h ep r o j e c td u r a t i o n t h e r ee x i s tm a n yu n c e r t a i n t i e s ，w h i c hw i l ld oh a r mt ot h ec o m p l e t i o no ft h e p r o j e c t ，i nt h ep r o c e s so ft h ee x e c u t i o no fap r o j e c t i no r d e rt oe l i m i n a t eo rw e a k e n t h i sk i n do fd i s a d v a n t a g e o u si n f l u e n c e ，t h em e a n so fc r i t i c a lc h a i nm e t h o di st os e t b u f f e r s i nt h i st h e s i s ，t h et a s ko fs e t t i n gf e e d i n gb u f f e r si sb r o k e nd o w ni n t ot h r e e s t e p s i d e n t i l y i n g t h ef e e d i n gp o i n t s ，i d e n t i l y i n gt h en o n - c r i t i c a lc h a i n sa n d c a l c u l a t i n gt h es i z e so ft h ef e e d i n gb u f f e r s t h em e t h o d st oi d e n t i f yt h ef e e d i n g 东北大学硕士学位论文a b s t r a c t p o i n t sa n dt oi d e n t i f yt h en o n c r i t i c a lc h a i n sa l ea l s op r o p o s e d ，a n dt h em e t h o dt o c a l c u l a t e 也es i z e so ft h ef e e d i n gb u f f e r si sr e v i s e di nt h i st h e s i s t o o t h e s e s y s t e m a t i z et h em e t h o do fs e t t i n gf e e d i n gb u f f e r s ，a n dm a k et h em e t h o dm o r e p r a c t i c a l s i m u l a t i o nt e s t si nd i f f e r e n te x e c u t i n ge n v i r o n m e n t st h a tw i l li n v e s t i g a t e t h ee x e c u t i n ge f f i c i e n c yh a v ep r o v e dt h a t t h er e v i s e dm e t h o di sb e t t e rt h a nt h e c u r r e n t k e yw o r d s ：p r o j e c tm a n a g e m e n t ，p r o j e c ts c h e d u l i n g ，t h e o r yo fc o n s t r a i n t s ， c r i t i c a lc h a i n , b u f f e r , c p m ，p e r t 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究 成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果， 也不包括本人为获得其他学位两使用过的材料。与我一同工作的同态对本研究 所做的任何贡献均己在论文中作了明确的说明并表示谢意。 第巨聋 学位论文作者签名：奠巨华 日 期：2 0 0 5 年2 月 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位 论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人授权东北大学可以将学位论文 的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不同意。) 学位论文作者签名：莫巨华 导师签名： 签字日期： 签字日期 东北大学硕士学位论文 第一章绪论 第一章绪论 1 1 研究背景与意义 项目，也叫工程或工程项目，本文统称为项目，是指由一组有起止时间、 相互协调的受控活动所组成的特定过程【l 】，该过程要达到符合规定要求的目标， 包括时间、费用和质量等。作为现代管理科学研究的重要分支，项目管理理论 与方法的研究己成为当今世界各国十分关注的科学课题【2 】。 国家和地方各省市每年都会有很多“重点工程”，这些重点工程所涉及的金 额十分巨大，关系国计民生与社会发展，意义非常重大。随着经济全球化的发 展，市场竞争程度越来越激烈，本来在管理上处于劣势的中国企业要想在激烈 的市场竞争中立于不败之地，就必须加强管理，而项目管理正是其中的重要内 容。项目管理不仅在经济建设中有重要应用，在科学研究、国防建设与社会事 务中也有重要应用，例如“阿波罗登月计划”、四年一度的奥运会等。由此可见， 现代社会对项目管理的需求是十分旺盛的。 起源于2 0 世纪5 0 年代的传统项目管理理论至今己走过半个世纪的历程， 其研究已取得巨大进展，其应用已取得巨大成功，为全世界的科技进步、经济 和社会发展做出了不可磨灭的贡献。但是，随着信息时代的来临和高新技术产 业的飞速发展，资本、服务、技术、信息、劳务( 人才) 在全球范围内流动空 前加快，项目的特点发生了显著变化，项目本身和执行环境的不确定性及复杂 性不断增多和增强，各行各业对项目管理的要求越来越高。目前项目管理中仍 旧存在非常突出的问题【3 】，主要表现在：( 1 ) 项目拖期完成；( 2 ) 项目成本超 支；( 3 ) 为了控制成本或工期，不得不牺牲项目的规模或设计内容。这些问题 表明，目前的项目管理理论还不能满足项目管理的实际需要，还需要进步加 强研究，提出更新、更有效的管理方法。 目前国际上有两大项目管理研究组织：欧洲的国际项目管理协会 ( i n t e r n a t i o n a lp r o j e c tm a n a g e m e n t a s s o c i a t i o n ，简称i p m a ) 和美国的( 美国) 项目管理协会( p r o j e c tm a n a g e m e n ti n s t i t u t e ，简称p m i ) 。几十年来，两大组织 在项目管理理论与方法的研究和推广应用中做了许多卓有成效的工作，为推动 项目管理现代化做出了杰出的贡献。在欧美发达国家，项目管理已经普遍应用 于各行各业，成为各行各业经营管理的中心模式。而我国无论在项目管理理论 1 东北大学硕士学位论文 第一章绪论 的研究上，还是在项目管理理论的应用上都明显落后于欧美发达国家，还没有 形成自己的理论体系和学科体系，极其缺乏高水平、专业的项目管理人才。这 对我国的经济发展和现代化建设极为不利，因此，需要加强对项目管理理论的 研究。 关键链项目管理( c r i t i c a lc h a i np r o j e c tm a n a g e m e n t ，简称c c p m ) 是2 0 世纪9 0 年代末出现的全新的项目管理理论与方法，它与传统的项目管理理论相 比在多方面具有较大优越性1 4 ，能够有效缩短工期，减少w i p ( w o r k i n p r o c e s s ) ， 提高项目的执行效率和效益。国际上已有不少组织和学者对c c p m 进行研究， 高德拉特学会、p m i 和i p m a 就是其中的几个较有影响的组织。c c p m 在一些 欧美发达国家已有非常的成功应用【5 ，但在我国，从作者掌握的资料来看，只 有少数学者在研究c c p m ，c c p m 的应用在我国则是空白。因此，研究c c p m 对提升我国的项目管理水平具有重大的理论意义和实践意义。 1 2 项目调度理论的发展历程 最早用于项目调度的方法是1 9 1 7 年由h e n r r yl g a n t t 提出的甘特图7 删 ( g a n t tc h a r t ) 法。甘特图法形象直观，简单易懂，绘图简单，便于检查和计 算资源需求量。因此，甘特图法也是在项目调度中使用最广泛的方法之一。但 甘特图法有着明显的缺陷：( 一) 不能显示工作间的相互依赖关系；( 二) 不能 显示工作早开始或晚开始所带来的后果；( 三) 只能用于解决小规模问题。 2 0 世纪5 0 年代在美国出现了关键路线法( c r i t i c a lp a t hm e t h o d ，简称c p m ) 和计划评审技术1 7 。1 3 1 ( p e r f o r m a n c ee v a l u a t i o nr e v i c wt e c h n i q u e ，简称p e r t ) 。 c p m 和p e r t 在制定调度计划时，不考虑资源的约束，即认为项目所用的所有 资源随时随地都是能得到满足的。这两种方法所用的概念基本相同，差别只在 项目中各个工作的执行时间的估计方法上。c p m 用的是一点估计法，即直接根 据历史数据和经验给出各个工作的执行时间估值。这种方法比较简单，忽略项 目执行过程中可能出现的不确定性因素，适用于各个工作的执行时间较固定的 领域，例如建筑领域。p e r t 采用三点估计法，其出发点是假设各工作服从b a t a 分布，且相互独立，给出三个时间估值，即：乐观时间a ，最可能时间r t l ，悲 观时间b ，利用近似均值 d ：a + 4 m 一+ b ( 1 1 ) b 作工作持续时间估值，用近似方差 2 东北大学硕士学位论文 第一章绪论 2r 6 一口、2 矿2 l 了j ( 1 2 ) 来描述各个工作的变动。c p m 和p e r t 与随机过程、排队论、决策论、系统仿 真技术、可靠性理论相结合，形成了许多c p m 和p e r t 的扩展理论一，l l j ，如： 图示评审技术( g e r t ) 、随机网络计划技术( q g e r t ) 、风险评审技术( v e r t ) 、 决策关键路线法( d c p m ) 、搭接网络计划技术( o l n ) 、流水网络计划技术等。 c p m 和p e r t 及其相关技术可用来解决大规模问题。c p m 和p e r t 的缺点是忽 视资源约束，这使得制定出的调度计划在实施过程中需要做较大的调整。 资源受限项目调度【1 4 ，l5 j ( r e s o u r c e c o n s t r a i n e dp r o j e c ts c h e d u l i n gp r o b l e m s ， 简称r c p s p s ) 理论从资源受限的前提出发研究项目调度问题，从诞生之日起， 一直受到全世界众多学者和实践者的研究和关注，可谓硕果累累。r c p s p s 在 4 0 多年的发展过程中模型不断得到丰富，可进一步分为单执行模式资源受限项 目调度问题( s r c p s p ) 、多执行模式资源受限项目调度问题( m i 配p s p ) 、离散 时间成本权衡项目调度问题( d t c t p ) 、单执行模式资源水平问题( s r l p ) 、 多执行模式资源水平问题( m r l p ) 、带最 b 最大时间滞后的资源受限项目调度 问题( r c p s p m a x ) 、以最大净现值为目标的资源受限项目调度问题( n p v ) 等。 随着模拟退火【1 6 】( s i m u l a t e d a n n e a l i n g ，s a ) 、禁忌搜索【1 6 1 ( t a b us e a r c h ，t s ) 和遗传算法 1 5 - 1 9 ( g e n e t i c a l g o r i t h m ，g a ) 等现代优化方法的出现，大型资源 受限项目调度问题得到了更加有效的求解。但调度计划是在确定环境中进行的， 在项目执行的动态环境中存在着许多不确定性，这些不确定性往往会导致项目 无法按计划完成，资源受限项目调度理论对这个问题没能给出有效地处理方法。 针对这一问题，约束集理论 2 0 , 2 1 1 ( t h e o r yo fc o n s t r a i n t s ，简称t o c ) 的创 始人高德拉特( e l i y a h um o o l d r a t t ) 博士在1 9 9 7 年出版了一本管理小说关 键链( c r i t i c a lc h a i n ) ) ) 2 2 1 , 将t o c 理论应用于项目管理领域，建立了关键链 项目管理理论。关键链项目管理理论在世界上已有成功应用 5 , 6 1 ，但对关键链理 论研究时间并不长，在该理论和应用中还有许多地方需要进一步深究和完善 【3 4 ，- ，2 4 2 5 。 1 3 国内外对c c p m 的研究现状 关键链项目管理理论在1 9 9 7 才被提出，至今公开发表的文献不多。b a r b e r 等【5 】叙述了一个应用关键链项目管理的实例，并且对关键链方法进行了评价。 t a y l o r 2 3 1 提出了一种用蒙特卡罗模拟技术确定项目缓冲区大小的方法，并认为 3 * 3 l a 学硕士学位论文 第一章绪论 ( 爿 ( 1 2 ) 来描述各个工作的变动。c p m 和p e r t 与随机过程、排队论、决策论、系统仿 真技术、可靠性理论相结合，形成了许多c p m 和p e r t 的扩展理论p 川，如： 图示评审技术( g e r t ) 、随机网络计划技术( q g e r t ) 、风险评审技术( v e r t ) 、 决策关键路线法( d c p m ) 、搭接网络计划技术( o l n ) 、流水网络计划技术等。 c p m 和p e r t 及其相关技术可用来解决大规模问题。c p m 和p e r t 的缺点是忽 视资源约束，这使得制定出的调度计划在实施过程中需要做较大的调整。 资源受限项目调度i i t ”1 ( r e s o u r c e - c o n s t r a i n e dp r o j e c ts c h e d u l i n gp r o b l e m s ， 简称k c p s p s ) 理论从资源受限的前提出发研究项目调度问题，从诞生之日起， 一直受到全世界众多学者和实践者的研究和关注，可谓硕果累累。r c p s p s 在 4 0 多年的发展过程中模型不断得到丰富，可进一步分为单执行模式资源受限项 目调度问题( s r c p s p ) 、多执行模式资源受限项目调度问题( m r c p s p ) 、离散 时间成本权衡项目调度问题( d t c t p ) 、单执行模式资源水平问题( s r l p ) 、 多执行模式资源水平问题( m r l p ) 、带最小，最大时间滞后的资源受限项目调度 问题( r c p s p m a x ) 、以培大净现值为目标的资源受限项目调度问题( n p v ) 等。 随着模拟退火【”1 ( s i m u l a t e d a n n e a l i n g ，s a ) 、禁忌搜索【1 6 ( t a b us e a r c h ，t s ) 和遗传算法 1 “”1 ( g e n e t i c a l g o r i t h m ，g a ) 等现代优化方法的出现，大型资源 受限项目调度问题得到了更加有效的求解。但调度计划是在确定环境中进行的， 在项目执行的动态环境中存在着许多不确定性，这些不确定性往往会导致项目 无法按计划完成，资源受限项目调度理论对这个问题没能给出有效地处理方法。 针对这问题，约束集理论1 2 雌”( t h e o r yo fc o n s t r a i m s ，简称t o c ) 的创 始人高德拉特( e l i y a h um g o l d r a t t ) 博士在1 9 9 7 年出版了一本管理小说关 键链( c r i t i c a lc h a i n ) ”，将t o c 理论应用于项目管理领域，建立了关键链 项目管理理论。关键链项目管理理论在世界上已有成功应用1 5 , 6 ，但对关键链理 论研究时间并不长，在该理论和应用中还有许多地方需要进一步深究和完善 【3 4 ，2 4 ，2 5 1 。 1 3 国内外对c c p m 的研究现状 关键链项目管理理论在1 9 9 7 才被提出，至今公开发表的文献不多。b a r b e r 等1 5 1 叙述了一个应用关键链项目管理的实例并且对关键链方法进行了评价。 t a y l o r l 2 3 1 提出了一种用蒙特卡罗模拟技术确定项目缓冲区大小的方法，并认为 t a y l o r l 2 3 1 提出了一种用蒙特卡罗模拟技术确定项目缓冲区大小的方法，并认为 - 3 - 东北大学硕士学位论文第一章绪论 自由时差可充当汇入缓冲区的角色。r a n d 【6 l 对t o c 理论与关键链项目管理理论 进行了简单介绍，但未进行深入分析。h e r r o e l e n 和l e u s 2 4 对关键链项目管理 的优缺点进行了深入分析，并通过仿真试验将关键链方法的调度计划与分支定 界算法产生的调度计划进行了对比分析。s t e y n 在文献 2 5 1 回顾了t o c 理论 在项目管理中的应用情况，并且考察了关键链项目管理的假设和机理，最后还 提出了一些未来研究方向。s t e y n 在文献【2 6 】中指出了t o c 理论最早被应用于 项目进度管理的原因，并提出了将t o c 理论应用于多项目管理、项目成本管理 和项目风险管理的思想和方法。w e i 等【2 7 】提出了一种改进的关键链项目调度方 法，并与传统项目管理、关键链项目管理进行了比较，指出了各自的优缺点。 y e o 和n i n g ( 2 8 结合供应链管理和关键链管理概念，针对项目管理的全过程提出 了一种新的管理框架，体现了文化、过程和技术的内涵。刘士新等【3 】对关键链 项目管理理论进行了系统的介绍，并讨论了关键链项目管理的优点和不足，指 明了进一步的研究方向。蔡晨和万伟1 7 】在p e r t c p m 的基础上，引人t o c 的 核心思想，提出了一种基于三点估计的关键链管理方法。万伟等t 2 9 1 提出了一种 在单资源约束下进行关键链项目管理的方法。 虽然有关关键链项目管理理论的文献较少，但关键链项目管理理论在制定调 度计划时考虑资源约束，这一点与资源受限项目调度理论相同，因此，资源受 限项目调度理论为关键链项目管理理论提供了很好的理论基础。 w i e s t 3 0 j 提出了与关键链类似的概念“关键序列( c r i t i c a ls e q u e n c e ) ”， 并提出了一种识别关键序列的方法，这种关键序列识别方法为关键链的识别提 供了参考。此外，w o o d w o r t h 和s a n a h a n 3 l 】也提出了一种关键序列识别方法。 b o w e r s 3 2 1 、r a z 和m a r s h a l l ( 3 3 1 提出的时差计算方法都值得借鉴。 1 4 本文主要工作 本文主要工作包括两部分：( 1 ) 研究关键链项目管理理论中的难题关 键链识别方法；( 2 ) 研究缓冲区设置的方法。论文组织结构如下：第一章的主 要内容是关键链项目管理理论的研究背景与研究价值，以及项目调度理论与关 键链项目管理理论的研究现状：第二章对关键链项目管理基础理论进行了详细 介绍；第三章提出了一种关键链识别方法，并指出了识别最优关键链的思路； 第四章对已有缓冲区设置方法进行完善和改进，并利用计算机模拟技术比较改 进后的方法与已有方法在执行效果上的优劣；第五章是结论和未来研究方向。 4 东北大学硕士学位论文 第二章关键链管理理论基础 第二章关键链管理理论基础 2 1c c p m 的基本思想 c c p m 是t o c 理论是在项目管理领域中的应用和发展。t o c 是由g o l d r a t t 博士在二十世纪七十年代末期基于o p t 2 1 , 3 4 ( o p t i m i z e dp r o d u c t i o nt e c h n o l o g y ) 系统发展起柬的，认为系统的制约因素决定系统的有效产出，因此，应把管理 重点放在系统的制约因素( 瓶颈) 上，通过改进制约因素达到最大的有效产出。 t o c 主要有以下5 个核心步骤： ( 1 ) 找出系统的制约因素； ( 2 ) 充分挖掘制约因素的潜能； ( 3 ) 非制约因素服从制约因素； ( 4 ) 提升制约因素能力； ( 5 ) 假如产生了新的制约因素，转步骤( 1 ) 。 制约因素是指妨碍实现系统目标的主要因素，可以分为两类【3 】：( 1 ) 实物 类制约因素，特点是产能不足以应付需求；( 2 ) 政策或制度约束，不合理的政 策同样会制约企业的有效产出。挖掘制约因素的潜能就是对实物类或政策约束 提出解决办法，从而实现有效产出的增加。 步骤( 3 ) 目的是实现系统中其他因素与制约因素同步，从而充分利用制 约因素的生产能力。步骤( 4 ) 是步骤( 2 ) 的延伸，指通过增加投入的方法提 升制约因素的生产能力，例如：加班、购买新机器等。这一步骤有可能使系统 的制约因素发生转移，因此，需要步骤( 5 ) ，开始新的循环。 t o c 在生产管理领域取得了巨大的成功。然而，在项目管理领域，现有的 项目管理方法不能很好地满足目前项目管理的实际需要。c c p m 正是基于t o c 思想，针对项目管理而设计的一种全新方法，目前已经在少数先进的欧美企业 获得了成功应用，一些著名的软件公司已经开始将关键链管理方法嵌入到其项 目管理软件中，例如p s g 。 关键链项目管理理论将资源约束提升到与工艺约束同等重要的位置，认为 项目的制约因素是由各个工作的持续时间、工艺约束和资源约束共同决定的“关 键链”，而不是p e r t c p m 中的关键路径。关键链与关键路径的主要区别在于 关键链不仅考虑了工作的持续时间和工作间工艺约束，而且考虑了工作间的资 5 查i ! 垄兰堡主兰堡堡圭苎三主墨竺竺量墨墨! 鱼：墅! ! 源约束和冲突，而关键路径不考虑资源约束，是制约整个项目周期的一个工作 序列。关键链方法通过加强对关键链上各个工作的管理，并通过项目缓冲、汇 入缓冲和资源缓冲机制来消除项目中不确定因素对项目计划执行的影响，保证 在确定环境下编制的项目计划在动态环境下的顺利执行。 2 2c c p m 项目调度的数学模型 关键链项目管理方法考虑了项目执行过程中的资源约束，因此，关键链管 理理论中的数学模型可以参考资源受限项目调度理论中的数学模型建立，根据 优化目标也可分为单执行模式资源受限项目调度问题( s r c p s p ) 模型、多执 行模式资源受限项目调度问题( m r c p s p ) 模型、离散时间一成本权衡项目调 度问题( d t c t p ) 模型、单执行模式资源水平问题( s r l p ) 模型、多执行模 式资源水平问题( m r l p ) 模型、带最小最大时间滞后的资源受限项目调度问 题( r c p s p m a x ) 模型、以最大净现值为目标的资源受限项目调度问题( n p v ) 模型等。目前c c p m 的研究主要以工期最短为目标 3 , 2 4 1 ，本节只列出最简单的 单执行模式资源受限项目调度问题的数学模型 ”】： m i n 踢( 2 1 ) s t s r , - - s t j d ， ，只，i = 1 ，2 ，j( 2 2 ) r ：r ：r = o m ，蹋，k = 1 ，2 ，k ( 2 3 ) j a 其中，( 2 1 ) 式为目标函数，代表项目工期最短；( 2 2 ) 式代表工艺约束( 紧前关 系约束) ；( 2 3 ) 式代表资源约束。各符号的含义如表2 1 所示。 工作1 和工作j 是虚工作，其执行时间为0 ，分别表示项目的开始和项目的 结束。可更新资源是指这种资源的获得和消耗是以每一阶段为基础的，例如： 劳动力和机器设备，它们在每一阶段的获得是有限的，但消耗之后在下一阶段 可更新；有关概念可参考文献【1 5 。 6 查些垄堂壁主兰堡垒查 苎三主墨坚篁堡型奎壁 表2 1c c p m 数学模型中各参数的定义 t a b l e2 1d e f i n i t i o n so f t h ep a r a m e t e r so f c c p mm a t h e m a t i cm o d e l 参数定义 1 工作号 嘭工作，的执行时间 蹈 工作f 的开始时间 工作i 的紧前工作集 4 t 时间段正在执行的工作的集合 咏 工作，对可更新资源k 的需求量 群 可更新资源k 的可用量 2 3 关键链和缓冲区 关键链是指项目中考虑资源约束情况下持续时间总和最长的工作序列。关 键链是针对特定的调度计划而言的，一个项目可以制定不同的调度计划，不同 的调度计划会对应不同的关键链( 请参考第三章) 。关键链的长度代表了整个项 目的持续时间，因此，关键链是整个项目时间管理的核心，整个项目的时间管 理都应围绕关键链进行。除了关键链上的工作，其余所有工作组成的链路，都 称为非关键链。对非关键链的管理要服从对关键链的管理。 缓冲区分为项目缓冲区( p r o j e c tb u f f e r ，简称p b ) 、汇入缓冲区( f e e d i n g b u f f e r ，简称f b ) 和资源缓冲区( r e s o u r c eb u f f e r ，简称r b ) 三种。p b 是为 了克服整个项目完成时间上的不确定性而设置的一段预留时间。f b 是为了防止 非关键链“碰撞”关键链而设置一段预留时间；所谓的“碰撞”是指非关键链 上的工作因为延误而影响其紧后的关键链上工作的正常开始，从而造成整个项 目的延误。l i b 是关键链上工作所需资源到位的提前时间，保证关键链上工作 所需资源能及时获得。 如图2 1 所示，工作序列1 4 7 9 就是关键链，工作序列2 5 6 8 和3 ( 2 1 2 作3 独自成为一条链) 都是非关键链。p b 设置在整个项目最后一个工 作的后面，f b l 设置在非关键链2 5 6 8 汇入关键链上的工作9 之前处， f b 2 设置在非关键链3 汇入关键链上的工作7 之前处。各缓冲区的大小属于缓 冲区设置的问题，将在第四章进行阐述。r b 在图2 1 中未标示出来，r b 是针 对关键链上所有工作所需的各种资源的，是在关键链上第一个使用这些资源的 - 7 东北大学硕士学位论文 第二章关键链管理理论基础 工作的开始时间前设置r b 。例如在图2 i 中，关键链1 - - 4 - - 7 - - 9 上所有工作 所需的资源共有3 种：r 1 、r 4 和r 6 ，假设三种资源的缓冲时间分别为r b l 、 r b 4 和r b 6 ，则这三个缓冲区分别应设在工作1 、工作4 和工作9 的开始时间 之前，意思是资源r 1 、r 4 和r 6 必须分别在s 乃一r b 、s 乃一衄4 和s 乃盘b 6 时间在工作1 、工作4 和工作9 的工作地点等候。r b 的大小根据项目执行环境 确定。资源缓冲机制可能会产生某些资源的空闲时间，但可以保证关键工作的 顺利进行，从而确保项目在较短的时间内完成。 0 1 l _ 0 著j - 3 0 j 一4 0 。5 0 。6 0 弓_ j 8 0 9 l _ 9 1 l _ 0 0 古1 。2 0 j - 1 3 0 时同) 7 0l l o( 时叫j 图2 1 关键链项目网络 f i g 2 1c r i t i c a lc h a i ni np r o j e c tn e t w o r k 本文只讨论项目缓冲区和汇入缓冲区的设置。项目缓冲区和汇入缓冲区的 设置有利于缩短项目总周期，这主要体现在两个方面： ( 1 ) 缩短了安全时间 一系列工作组成一条工作链，假设链长为d ，每个工作的持续期都包含一 定的安全时间，如图2 2 中的工作链1 ，又假设工作链l 上所有工作在d 这么 长的时间内完成的概率是p 。其中阴影矩形的长度代表工作 工作链l ： = 二二i 至 二二! 二二i 二要二工= 二j 二二二 二玉 工作链2 ： 二! 二二 二二! 二= 工二二三二二丁二二二二互亘受二= 卜l_一d一1 工作链3 ： 二工二 二二二二二二 二二 二二 二二二二 卜 _ 一d 一一1 图2 2 缓冲区缩短工期实例 f i g 2 2c u t t i n gs a f et i m eb ys e t t i n gb u f f e r 持续时间的期望值，空白矩形的长度表示安全时间的大小，s 1 、s 2 、s 3 分别表 示工作1 、2 、3 的安全时间，s 为缓冲区长度，设置方法参见第四章。 如果把每个工作的安全时间都分离出来，全部置于工作链之后，形成“聚 8 东北大学硕士学位论文第二章关键链管理理论基础 合的”安全时间，这个“聚合的”安全时间等于工作链上每个工作的安全时问 的总和。此时的链长仍为d ，如图2 2 中的工作链2 ，但由风险聚合( a g g r e g a t i o n o fr i s k ) 原理【9 ，2 5 1 知，工作链2 上所有工作在d 这么长的时间内完成的概率将 大于p ，也就是说，如果把所有工作的安全时间都置于工作链之后，链上所有 工作的安全时间“聚合”起来，可以以更少的安全时间达到相同的保护效果， 如图2 2 中的工作链3 ，工作l 、2 、3 在d 内完成的概率与工作链l 上工作l 、 2 、3 在d 内完成的概率相同。这就是设置项目缓冲区和汇入缓冲区的出发点之 q ( 2 ) 汇入缓冲区的设置提高了项目按期完工的概率 要明白为什么汇入缓冲区的设置会提高项目按期完工的概率，有必要考察 一下汇入点的完工概率。如图2 3 所示，工作l 、2 、3 都汇入工作4 ，假设工 作l 、2 、3 按时完成的概率均为8 0 ，那么，工作4 能按时开始的概率 图2 3 汇入点完工概率的计算 f i g 2 。3p r o b a b i l i t yc a l c u l a t i o no ff e e d i n gp o i n t 是多大呢? 在工作l 、2 、3 中，只要有一个工作未按时完成，工作4 都不能按 时开始，因此，工作4 能按时开始的条件是工作1 、2 、3 都按时完成，概率为 0 8 3 = o 5 1 2 。如果将工作1 和工作2 按时完成的概率提高，那么，工作4 按时 开始的概率将大大提高。如果认为工作l 是非关键链i ，雨认为工作2 是非关 键链i i ，工作3 和工作4 构成一条关键链，在非关键链i 和非关键链i i 之后都 设置汇入缓冲区f b ，也就是使非关键链i 和菲关键链u 以较旱的时间开始，从 而提高非关键链i 和非关键链按时完成的概率，那么就能减少非关键链i 和 非关键链对关键链上工作4 的干扰，从而达到提高整个项目完工概率的目的。 这就是设置汇入缓冲区的另一个出发点。 2 4c c p m 的调度过程 c c p m 的调度过程可分为6 步。 ( i ) 估计各工作的执行时间 c c p m 以有5 0 完成概率的时闽( 或取各个工作持续时间的均值) 作为各 o 东北大学硕士学位论文 第二章关键链管理理论基础 工作持续时间的估计值。以图2 1 所示的项目为例，各工作执行时间估计值如 表2 2 所示。 表2 2 各工作的执行时间估值 t a b b l e 2 2e s t i m a t i o no f t h ed u r a t i o no f e a c hi o b 工作号 12 3 45 6 78 9 执行时间估值 1 01 03 03 02 01 01 51 01 5 ( 2 ) 确定一个可行调度计划 定义2 1 ：设踞表示工作，的开始执行时间，则称，元组s = ( s 乃，s 乃， s 乃) 为一个调度计划。既满足工艺约束又满足资源约束的调度计划称为可行调 度计划。 确定一个可行调度计划的方法有很多，可参考文献【1 5 1 。一个可行调度计划 可由一张类似于图2 4 的图形表示。 f 弋弓亩# 、 靠， 图2 4 可行调度计划 f i g 2 4f e a s i b l es c h e d u l e ( 3 ) 找出关键链 虽然关键链管理方法没有给出关键链的识别方法，但现有的资源受限项目 调度理论已经提出了几种在资源受限条件下计算各个工作的时差的方法 3 0 3 3 1 ， 这些方法可以应用于关键链的识别中。本文在第三章提出了一种关键链识别方 法，也可以完成识别关键链任务。在图2 4 中，关键链是卜一4 7 9 。 ( 4 ) 各工作以最晚开始时间开始 如图2 5 所示，将各工作以最晚开始时间开始，有三个好处：其一，降低 w i p 水平；其二，减少工作反复；其三，使关键链更加容易被识别。 1 0 东北大学硕士学位论文 第二章关键链管理理论基础 01 0 3 0 40,506 07 0 ( 时问) 图2 5 以最晚开始时间开始的可行调度计划 f i g 2 5f e a s i b l es c h e d u l ew i t he v e r yj o bs t a r t i n ga sl a t ea sp o s s i b l e ( 5 ) 设置缓冲区 采用剪切粘贴法( 请参考第四章) 设缓冲区，即得到图2 1 。 ( 6 ) 确定各工作的开始时间 在图2 1 中，各个工作的开始时间如表2 3 所示，这等同于s = ( 2 0 ，0 ，0 ， 3 0 ，1 0 ，3 0 ，6