（计算机应用技术专业论文）基于约束的关键路径动态优化算法的研究及实现.pdf

摘要 基于约束的关键路径动态优化算法的研究及实现 摘要 进度管理是项目管理的重要组成部分，进度管理系统通过分解项 目，排定网络计划以及优化资源和成本项目来生成项目的计划。合理 的项目进度管理是项目执行、跟踪与控制的基础，是项目成败的关键。 现代项目日趋复杂，要求周期更短、准时完工率更高、成本更低。因 此，要求项目进度管理具有更高的可行性、确定性以及越来越高的稳 定性。这些新要求的提出，使得传统项目进度管理方法在指导项目的 实施过程中难以胜任。 本文系统的分析了传统项目进度管理的缺陷，以及使用关键链进 行项目进度管理中的优点和难点，提出采用约束转换的方法解决在进 度管理安排上出现的问题。关键链项目管理的构想及内容和传统的项 目进度管理理论有所差异。它着眼于项目的存在的约束关系，考虑项 目进度中的资源约束和项目人员的心理因素，并利用缓冲对项目进度 进行监控。但由于实际的项目进度管理过程中存在着信息获取和评估 人员的知识体系不同的问题，本文单独从时间资源的角度来分析整个 进度管理过程，在统一考虑全部资源的同时，将其它资源的约束转化 为对任务的时间约束，同时引入蒙特卡罗方法模拟工期的不确定性， 从而方便的进度计划的时间管理。 本文利用计算机进行了项目进度管理系统的设计与实现，并引用 中石化对伊朗石化公司的改造项目数据，以项目计划工期的可行性和 l 稳定性作为评价标准，对本文提出算法的有效性进行了分析。通过建 立p e r t c p m 项目进度计划和基于约束的关键路径进度计划的仿真 模型，在实现了的项目进度管理系统下进行仿真，获得了项目完成时 间的频率统计图和相关统计量。与传统方法进的对比、分析表明，本 文提出的基于的约束进度管理方法较传统项目进度管理方法在提高 项目计划工期的可行性和稳定性方面有很大的优势。 关键词：网络计划，约束，项目进度管理，蒙特卡罗，关键路径 摘要 r e s e a r c ha n di m p l e m e n to fd y n a m i cc p mo p t i m a l a l g o r i t h mb a s e do nc o n s t r a i n t s a b s t a c t s c h e d u l em a n a g e m e n ti st h em o s ti m p o r t a n t p a r t o fp r o je c t m a n a g e m e n t i tg e n e r a t e st h ep r o j e c tp l a nt h r o u g hb r e a k i n gd o w na n d m a k i n gt h en e t w o r kp l a n n i n g ，b a l a n c ea n do p t i m i z et h e r e s o u r c ea n d c o s t so f p r o j e c t s r e a s o n a b l ep r o j e c ts c h e d u l em a n a g e m e n ti st h eb a s e so f p r o j e c t s p e r f o r mt r a c k i n ga n dc o n t r 0 1 m o d e mp r o j e c t sb e c o m em o r e c o m p l e x s h o r t e rp e r i o d s ，l e s sc o s ta n dm u s tb ef i n i s h e do nt i m ea r e r e q u i r e d s om o d e mp r o j e c t s c h e d u l em a n a g e m e n ts h o u l db em o r e f e a s i b l e ，m o r ed o u b t l e s sa n dm o r es t a b l e ，h o w e v e r , t h et r a d i t i o n a lp r o je c t s c h e d u l em a n a g e m e n tm e t h o d sc a n n o tf u l f i l lt h e s ed e m a n d s t h et h e s i sa n a l y z e st h ed i s a d v a n t a g e so ft r a d i t i o n a lp r o j e c ts c h e d u l e m a n a g e m e n ts y s t e m a t i c a l l y , a n da d v a n t a g e sa n dp r o b l e m so fa p p l y i n g c r i t i c a lc h a i nt od op r o je c ts c h e d u l em a n a g e m e n t a sar e s u l t ，an e w m e t h o do fu s i n gt i m ec o n s t r a i n tt r a n s f o r m e df r o mo t h e rc o n s t r a i n t si s p r o p o s e dt os o l v et h ep r o b l e m s c r i t i c a lc h a i nt a k e sr e s o u r c ec o n s t r a i n s a n dp s y c h o l o g yf a c t o r si n t oc o n s i d e r a t i o n ，a n dm a k e su s eo fb u f f e r i n gt o c o n t r o lt h ep r o j e c ts c h e d u l i n g a sc o l l e c t i n gi n f o r m a t i o ni sh a r da n d p r o j e c tm a n a g e r sa r ef a m i l i a rw i t hd i f f e r e n ta s p e c t so fk n o w l e d g e ，t h i s 北京化工大学硕士学位论文 a r t i c l ep r e s e n t sh o wt oe x e c u t et h ep r o j e c ts c h e d u l em a n a g e m e n to n l y c o n s i d e r i n gf r o mt h et i m ea s p e c t ，w h i l eo t h e rr e s o u r c ec o n s t r a i n t s a r e t r a n s f o r mi n t ot i m ec o n s t r a i n s i na d d i t i o n ，m o n t ec a r l om e t h o di s i m p o r t e dt os o l v et h ep r o b l e m so f i n s t a b l eo ft a s k sd u r a t i o n an e ws y s t e mo fp r o je c ts c h e d u l em a n a g e m e n ts y s t e ms o f t w a r ei s d e s i g n e da n dc o d e d ，a n da l i s to fs c h e d u l ed a t af r o mt h ep r o j e c to f s i n o p e ci su s e dt oc h e c kt h ev a l i d i t yo ft h ep r o p o s e dm e t h o dw h i l es e t p r o j e c tp e r i o da sc r i t e r i o n t h r o u g he s t a b l i s h i n gt h es i m u l a t i o nm o d e lo f t h ep r o p o s e dp l a n n i n ga n dt r a d i t i o n a ls c h e d u l ep l a n n i n g ，a r t i c l ec o m p a r e s t h en e wp e r i o dd i s t r i b u t i o na n ds t a t i s t i c so ft h ep r o p o s e dp l a n n i n gw i t h t r a d i t i o n a lm e t h o d sd i s t r i b u t i o na n ds t a t i s t i c sb ym a k i n gu s eo ft h en e w p r o j e c tm a n a g e m e n ts y s t e ms o f t w a r e ，w ef i n do u tt h a tt h en e ws c h e d u l i n g m e t h o dm a k e sg r e a ti m p r o v e m e n ta n dt h ep r o p o s e dm e t h o dp l a n n i n gi s p r o v e d t ob eam o r es t a b l ea n dm o r ef e a s i b l e p r o j e c t s c h e d u l e m a n a g e m e n tm e t h o d k e y w o r d s ：s c h e d u l i n gn e t w o r kp l a n ，c o n s t r a i n t ，p r o j e c ts c h e d u l e m a n a g e m e n t ，m o n t ec a r l o ，c r i t i c a lp a t h 北京化工大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 作者签名：毋虹日期：j 2 掣一一 关于论文使用授权的说明 学位论文作者完全了解北京化工大学有关保留和使用学位论文 的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北 京化工大学。学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编 学位论文。 保密论文注释：本学位论文属于保密范围，在土年解密后适用 本授权书。非保密论文注释：本学位论文不属于保密范围，适用本授 权书。 作者签名：。啦日期：坦2 鱼：! 导师签名：訇兰刍塑日期：兰= 翌型一一 第一章绪论 1 1 研究背景与动机 第一章绪论 进度计划是项目管理的核心，进度计划系统通过对项目的分解，网络计划的 排定以及资源与成本的平衡优化来生成项目的计划安排。合理的项目进度计划使 项目执行、跟踪与控制的基础，是项目成败的关键。现代的工程项目进度受到诸 多因素的影响，要求工程项目的管理人员在事先对影响进度的各种因素进行全面 调查研究、预测、评估这些因素对工程建设进度产生的影响，并编制可行的进度 计划。然而在执行进度计划的过程中，不可避免的会出现影响进度按计划执行的 其他因素，使工程项目进度难以按预定计划执行。在工程项目实施过程中，当通 过实际进度与计划进度的比较，发现有进度偏差时，需要分析该偏差对后续工作 及总工期的影响，从而采取相应的调整措施对原先进度计划进行调整，以保证工 期目标的顺利实现【。 项目进度控制管理的内容包项目的工程建设过程中实施经过审核的通过的 工程进度计划，并采用适当的方法跟踪、检查工程实际进度状况，与计划进度对 照、比较找出两者之间的偏差，并对产生偏差的各种因素及影响工程目标的程度 进行分析与评估，并组织、指导、协调、监督监理单位、承包商及相关单位及时 采取有效措施调整工程进度计划。在工程进度计划的执行中不断循环往复，直至 按设定的工期目标如期完成，或在保证工程质量和不增加工程造价的条件下提前 完成。项目进度目标按期实现的前提是要有一个合理的科学的进度计划；这就需 要项目管理者在执行进度计划中，运用动态规划的控制原理，不断进行检查，将 实际情况和进度计划进行对比，找出计划产生偏差的原因，特别是找出主要原因 后，采取纠偏措施【2 , 3 , 4 】。 项目进度控制管理是项目建设中与质量和投资并列的三大管理目标之一，其 三者之间的关系是相互影响和相互制约的【5 ，6 7 】。在一般情况下，加快进度、缩短 工期需要增加投资。但提前竣工为开发商提前获取预期收益创造了可能性。项目 进度的加快有可能影响项目质量，而对质量标准的严格控制极有可能影响项目进 度。如有严谨、周密的质量保证措施，虽严格控制而不致返工，又会保证项目进 度，从而也保证了质量标准及投资费用的有效控制。 安排计划的目的是为了控制和节约时间，而项目的主要特点之一，就是有严 格的时间期限要求，由此决定了进度计划在项目管理中的重要性。项目进度计划 的核心技术是网络计划技术，网络计划技术为现代生产提供了科学的管理方法。 它主要用于制定规划、计划和实时控制，在缩短建设周期、提高工效、降低造价 】 北京化工人学顾二卜学位论文 以及提高企业管理水平方面都能取得显著的效果。进度计划要说明哪些工作必须 于何时完成和完成每一任务所需要的时间，但最好同时也能表示出每项活动所需 要的人数。制定进度计划的常用方法有以下几种： ( 1 ) 关键日期表：这是最简单的一种进度计划表，它只列出一些关键活动和进 行的日期。 ( 2 ) 甘特图：也叫做线条图或横道图，是以横线来表示每项活动的起止时间。 它的优点是简单、明了、直观、易于编制，因此到目前为止仍然是小型项目中常 用的工具。即使在大型工程项目中，它也是高级管理层了解全局、基层安排进度 时有用的工具。通过甘特图，可以看出各项活动的开始和终了时间。在绘制各项 活动的起止时间时，也考虑它们的先后顺序。但各项活动之间的关系却没有充分 表示出来，同时也没有指出影响项目寿命周期的关键所在。因此，对于复杂的项 目来说，甘特图就显得不合适。 ( 3 ) 关键路线法( c r i t i c a lp a t hm e t h o d ，简称c p m ) 。关键路径算法是通过分析 项目过程中哪个活动序列进度安排的总时差最少来预测项目工期的网络分析方 法。关键路径上的任何一个活动都是关键活动，其中任何一个活动的延迟都会导 致整个项目的完工时间的延迟。因此，缩短关键路径的总耗时，会缩短工期；反 之，则会延长整个项目的总工期。而缩短非关键路径上的各个活动所需要的时间， 则不会影响工程的完工时间。 ( 4 ) 计划评审技术( p r o g r a me v a l u a t i o na n dr e v i e wt e c h n i q u e ，简称p e r t ) 。 p e r t 可以在没有经验数据可循环时，使用三点时间估计来确定工序时间，然后 通过工序时间来估计整个项目在规定时间完成的概率。简言之，估计的活动时间 是一个加权平均值，其中，赋予员可能时间以最大权重。而赋予最长完成时间和 最短完成时间以较小的权重，通常其比例确定为4 ：1 ：1 。网络的估计完成时间用 基本统计方法计算，该方法假设事件序列的标准差是每一事件方差之和的平方根 z 。因此，只要在概率表上查出相应标准差的z 值，就可得到完成时间的概率【8 ，9 1 。 此外，人们考虑到过程的随机性，把概率论引入到p e r t 中，产生了图示评审技 术g e r t ( g r a p h i c a le v a l u a t i o na n dr e v i e wt e c h n i q u e ) t 1 0 , 1 1 , 1 2 】；将风险决策理论引 入g e r t 后又产生了风险评审技术v e r t ( v e n t u r ee v a l u a t i o na n dr e v i e w t e c h n i q u e ) 巾l 引。目前，人们在三个方面展开：首先是“时间费用 优化问题上 利用现行规划理论对该问题进行了系统的研究。其次是基于资源约束的规划闯题， 此类问题：一是数学规划算法【1 4 , 1 5 , 1 6 】。1 9 6 4 年w i e s t ，1 9 7 3d a v i s ，1 9 9 1 年g a r i s h 和p i r k u l 等就分别利用线性规划和动态规划的方法对问题进行了系统的研究和 求解；二是启发式算法。2 0 0 0 年l e e 和k i m 对启发式算法的搜索方法进行了改 进研究，把模拟退火、t a b us e a r c h 和遗传算法引入到项目计划优化中，取得了 2 第一章绪论 一定的效果。最后是工作时间的估计问题，蒙特卡罗模拟方法【1 7 , 1 8 】、遗传算法的 引入、模糊数法 1 蛆4 】等等都对解决该问题做出了贡献。 ( 5 ) 近年来，随着项目的日趋复杂，要求工期更短、准时完工率更高、成本更 低，尤其对于越来越多的企业，一个项目的拖期会导致整个供应链上相关项目计 划的变化，因此，现代项目管理要求项目进度管理具有更高的可行性、确定性以 及越来越高的稳定性，这些新的要求的提出，使得许多项目在传统项目进度管理 的指导下出现以下问题【2 5 j ： ( a ) 进度超期、预算超支现象严重； ( b ) 项目范围变大； ( c ) 某些关键资源和信息在需要时常常不存在； ( d ) 各项目之间争夺资源的现象时有发生。 为解决这些问题，人们将约束理论【2 6 】引入到项目管理中，逐渐形成关键链技 术【27 1 。然而在运算过程中，关键链方法往往要求项目提供相当多的信息，并要 求资源在分配过程中避免多任务分配，因此在面对多资源重复分配，多任务分配 的问题时，这使得关键链方法在应用上存在了相当的局限性。很多学者在应用关 键链上更多关注如何避免任务出现单资源多任务分配的情况，因而放弃了对这一 问题的解决。 1 2 研究目的与内容 为分析、评估项目实施过程所涉及各种不确定因素对项目进度评价结果的影 响，同时利用项目经验的指导效果，在实施的过程动态的汲取和分析信息中，提 高项目进度评价的科学性、准确性，本文将在蒙特卡洛模拟方法下进行项目进度 的约束研究，并旨在发现一种能够集中反映时间对工程进度影响方法。在项目进 度计划中，通过分析不确定性因素对项目进度情况的影响，将不确定性因素视为 随机变量并据此建立模拟模型，将获取的大量随机变量观测值带入模型中进行多 次模拟实验从而得出目标变量的可能结果，通过研究目标变量的各种统计特征， 为投资决策提供更加全面、科学的依据。 ( 1 ) 在对蒙特卡洛方法的实际应用中，通过深入研究e x c e l 对蒙特卡洛的统 计使用功能【2 8 】以及m a t l a b 的统计功能模块如何与蒙特卡洛模拟分析及项目进度 计划进行紧密结合，探讨了如何利用自编的程序来来实现蒙特卡洛模拟分析 2 9 , 3 0 】。 ( 2 ) 由于现代化项目进度管理的需求，也为能够引入最新的约束理论和关键 链方法解决因使用传统的项目进度管理方法而出现的相关问题。本文在分析关键 链运用的案例基础上，将重点放在对项目时间的管理和分析上，采用转化资源约 3 北京化工大学硕士学位论文 束为时间约束的方法，来解决实施过程中资源出现的多任务分配的情况。 1 3 技术路线及研究流程 本文首先通过对国内外相关文献资料的收集和整理，明确研究的对象和主要 内容：通过撰写论文综述，进一步研究了蒙特卡洛模拟法和约束关键链理论的相 关理论知识，分析得出蒙特卡洛模拟法结合约束方法应用于项目进度计划的重要 性。 在对e x c e l 软件各项功能的深入研究分析，并利用水晶球模拟进行蒙特卡洛 模拟分析的基础上，研究蒙特卡洛应用的理论及应用问题，了解使用蒙特卡洛方 法的基本步骤以及在应用实践中的几个重要问题，从而为进一步将蒙特卡洛模拟 方法应用于进度计划奠定了理论基础。通过对约束理论和关键链技术和技术的学 习，了解约束理论和关键链技术的适用范围及其存在的缺陷，为进一步研究提供 良好的前提条件和理论基础。 本文将理论与工程实例相结合，利用蒙特卡洛方法对具体工程项目进行模拟， 分析项目执行过程中存在的约束，在对大量实际案例以及与相关专业人员进行互 动探讨的基础上，分析得出进度计划评价指标的计算模型以及模型的变量构成； 同时利用研究得出的理论方法与实际相结合研究不确定性因素的概率分布，以及 各种资源约束对工期产生的影响，最终利用自编的项目进度管理软件以基于约束 的关键路径动态算法，对项目进度计划进度影响效果进行模拟，获得较为全面的 决策信息。研究流程如图1 1 所示。 4 第一章绪论 1 4 文献综述 1 4 1 模拟理论研究 图1 - 1 本文研究的技术路线图 f i g 1 - 1t e c h n ol e d g er o a d m a p 何谓模拟，美国学者j a m e sre v a n s 和d a v i dlo l s o n 在i n t r o d u c t i o nt o s i m u l a t i o na n dr i s ka n a l y s i s 一书中是这样定义的：模拟是建立系统或决策问题 的数学或逻辑模型，并以该模型进行试验，以获得对性行为的认识或帮助解决问 题的过程。简单的说模拟式用模型进行试验并分析其结果，当问题表现出不确定 性是，模拟方法特别有用【3 。 对于模拟的类型，j a m e sre v a n s 在其著作中指出，在实际运用中，最常用 的两种模拟类型是蒙特卡洛模拟( m o n t ec a r l os i m u l a t i o n ) 和系统模拟( s y s t e m s i m u l a t i o n ) 前者常被用于影响决策变动所涉及的风险的评估，后者常被用于处 理各种设计时间推移和事件出现顺序如库存、排队、制造等方面的问题。 5 北京化丁大学硕：l 学位论文 何谓蒙特卡洛呢，p a u lg l a s s c r m a n 所著商业统计学精要以及王兴德所著 电子化商务决策分析等文献中均有描述。综合来看，蒙特卡洛模拟，也可称 为随机模拟( r a n d o ms i m u l a t i o n ) 、统计模拟( s t a t i s t i c a ls i m u l a t i o n ) ，他是一种描 述性的研究，它的基本思想就是建立一个概率模型或过程的观察和抽样试验来计 算所求参数的分布及特征，最后给出所求解的近似值，其本质就是从概率中重复 抽样以建立输出变量的分布。 1 4 2 进度管理理论研究 ( 1 ) 关键路径 在美国，对4 0 0 家最大建筑企业调查表明，应用c p m 方法者，1 9 5 6 年为百 分之四十七，1 9 7 0 年达百分之八十。在苏联，从1 9 6 4 年开始颁布了一系列有关 制定和应用网络计划指示、基本条例等法令性文件，规定所有的重大建筑工程都 必须采用c p m p e r t 方法，其广面不断扩大。在英国、法国、日本等国家，网 络计划法也得到了广泛的推广应用。 ( 2 ) 关键链 约束理论( t h e o r yo fc o n s t r m n t s ，t o c ) 是以色列物理学家戈德拉特于2 0 世纪 8 0 年代中期在他的最优生产技术基础上创立和发展起来的。最优化生产技术是 由一组管理理念和规则组成的理论体系，最初被理解为“对制造企业进行管理， 解决瓶颈的方法”。后几经改进发展成为“产销率、库存、运行”为基础的指标 体系，逐渐形成了一种面向增加产销率而不是传统的面向减少成本的管理理论工 具，并且最终到企业管理的所有职能方面。 关键链技术植根于约束理论。关键链认为在项目实施过程中，资源的利用率 是不可能保持平衡的。但是项目进度只是受到一部分资源的影响，面不是受到所 有资源的影响。前者称为瓶颈资源( 或者叫关键资源) ，后者称为非瓶颈资源( 或 者非关键资源) 。瓶颈资源上的任务称为瓶颈任务( 关键任务) ，非瓶颈资源上的 任务称为非瓶颈任务( 非关键任务) 。瓶颈资源的利用率越高，项目进度就越快； 如果瓶颈任务延误一天，将导致整个项目延误一天。要加快项目进度，就必须提 高瓶颈的利用率，防止由于非瓶颈任务延误导致瓶颈资源处于等等状态，造成整 个项目。 通过对上述内容的研究，本课题试图取得以下两个方面的突破与创新： a ) 在前人对关键链应用于进度管理的基础上，进一步单一化进度管理的处 理环节，将分析主要集中于时间上，通过转换约束的方式实现进度评价的专一性。 b ) 采用蒙特卡罗方法，结合关键路径方法，实现基于约束的关键路径运算 方法，真正的实现进度管理的模拟简化。 6 第一章绪论 论文根据上述内容对文章的章节进行安排，全文共分七章。各章内容如下： 第一章：绪论 介绍本文研究背景、意义、国内外研究现状，提出论文的技术路线、研究内 容及章节安排。 第二章：关键路径技术及关键链理论 介绍关键路径技术、约束理论以及关键链理论的产生与发展，并进一步阐述 关键路径和关键链技术的融合特性，从而推出在关键链技术下，关键路径仍然有 研究的必要性，以及从关键链的角度考虑关键路径方法的可行性和发展方向。 第三章：蒙特卡罗理论 介绍蒙特卡洛模拟法的产生、发展和基本过程，并从蒙特卡洛理论基础阐述 将蒙特卡洛运用在解决工期不确定性问题上的有效性和可行性。 第四章：基于约束的关键路径动态优化算法 通过描述关键链中存在的资源约束和关系，描述了时间和资源约束之间存在 的相互关系，从而将资源约束分离出来。介绍了时间约束是如何应用到关键路径 中并结合蒙特卡洛算法动态的实现模拟运算的。 第五章：项目进度管理系统的开发与应用 介绍了一个招投标管理系统中进度管理系统的设计与实现方法。通过中国石 化集团公司在伊朗石化改造项目中的进度数据验证了在约束理论和蒙特卡罗理 论的指导下，采用基于约束的c p m 动态优化算法的优越性。 第六章：结论和展望 通过本文内容的研究，为动态环境下进行项目的进度管理提供了可借鉴的方 法。对开发进度管理软件时设计流程时提供了可行的研究成果。但同时也提出了 不足之处，关于本文提出的方法是否可以在应用到其他问题领域并进一步简化关 键链将会是未来一个研究方向。 7 第二章网络计划技术与关键链理论 第二章网络计划技术及关键链理论 2 1 项目管理的概念 项目是指完成某些特定指标的一次性任务。所有项目都是一项有待完成的专门任 务，是在一定的组织机构内，在限定的资源条件下，在计划的时间里，按满足一定性 能质量与数量的要求去完成的一次性任务。项目具有惟一性、一次性、整体性、多目 标性和寿命周期性。 项目管理是以项目为对象，由项目组织对项目进行高效率的计划、组织、领导、 控制和协调，以实现项目目标的过程。项目管理的主要内容有范围管理、进度管理、 费用管理、质量管理、人力资源管理、风险管理、沟通管理、采购管理和综合管理等。 其中项目进度管理是为了确保项目按时完成对所需的各个过程活动进行管理。进度管 理的过程和内容【l 】主要有： 工作界定为完成各种项目的交付成果，确定必须进行的各项具体活动； 工作安排一识别项目工作清单中各项活动的相互关联与依赖关系，并据此对各 项工作的先后顺序进行安排； 工作持续时间的估算对项目确定的各项工作的时间长短进行估算； 编制进度计划根据项目工作顺序、工作时间和所需资源编制项目进度计划； 进度计划控制对项目进度计划实施与项目进度计划变更所进行的管理控制工 作。 2 2 网络计划技术 在企业日常的生产和经营活动中，常常会发生各个生产、经营环节的不协调，从 而影响到整个生产、经营活动的正常进行。为此，我们在生产经营的组织和安排上， 必须进行综合平衡，统筹安排，按照客观经济规律办事，明确主次。妥善安排各项工 作或生产任务，以避免不必要的失误。网络计划技术正是解决这方面问题的一种科学 管理方法【2 1 。 在计划工作中，人们曾广泛采用横道图计划，如图2 1 。这种横道图计划，对提高 管理工作水平和促进生产的发展起到过重要作用。但是，随着生产的迅猛发展，工程 规模越来越大，各个生产环节之间，各项工作之间的关系错综复杂，影响生产技术过 程和各项工作的因素也日益增多。在这种情况下，横道图计划越来越难以反应这些复 杂关系，更难以统筹安排众多的工程项目以及年、季、月计划。所有这些，都需要有 9 北京化工大学硕- i ：学位论文 一种新型 的编制计划的方法和计划表达方式，因而引起了计划理论与方法中的变革。网络计划 法就是在这种历史条件下产生的。许多工业发达国家，为了适应现代化生产发展，为 了组织生产和科学研究的需要，进行了大量的调查研究工作，先后发明并采用了一些 新的科学管理方法，其中网络计划技术得到了很快的发展。网络计划技术有许多种具 体方法，关键路径法( c r i t i c a lp a t hm e t h o d 简称c p m ) 和计划评审技术( p r o g r a m e v a l u a t i o na n dr e v i e wt e c h n i q u e 简称p e r t ) ，则是其中应用最广和最有代表性的两种 方法。 2 2 1 网络计划技术的优点 图2 - 1 甘特图 f i g 2 - 1d i a g r a mo fg a n n t 关键路径法( c p m ) 主要是为解决项目中出现的成本超支和进度拖延问题，提出了 统筹协调和优化的思想。与关键路径法同时被提出的计划评审技术p e r t ，是专门针 对研究开发一类项目不确定性和风险较大的特点，采用三点时间估计法( 乐观、悲观和 最可能估计) 取代了c p m 法中单一时间估算，并在各项目活动的风险相互独立并遵从 b e t a 概率分布的假定下，给出一个对项目的总体工期风险。国内对网络计划技术研究 内容的提法是：向“关键路线要时间”，向“非关键路线要资源”。 由于过去缺少计算机这种手段，完全依靠人力编排，不能充分发挥网络计划技术 的优点，所以效果不够显著。近年来，有关研究所、大专院校、大型厂矿企业等均先 后研制了一些有关计算机程序，很多工作可以借助计算机来完成，因此，使这项新的 科学管理技术在各行各业中得到迅速的推广。计算机可以用数学定量分析方法，通过 1 0 第二章网络计划技术与关键链理论 时间参数的计算，做好工程安排，以最少的人力、物力和时间完成总目标，并达到最 好的经济效果。网络计划技术存在着一下的优点： ( 1 ) 能够把方案规划中的工序，组成一个有机的整体，因而可以全面准确地表达 各工序，尤其是紧邻工序之间的逻辑关系。 ( 2 ) 能够计算出各项工序的时间参数，从而可以提高管理的计划性与预见性。 ( 3 ) 标明关键工序与关键路线，了解关键路线，对施工计划有若非常重要的意义。 指挥人员可以凭此“向关键路线要工期，向非关键路线要资源”。 ( 4 ) 计划的实施过程中，因某种因素使一些工序无法如期完成时，应用网络计划 法，通过对每项工序的时差计算，可为决策提供可靠依据。 ( 5 ) 工序提前或推迟时，网络计划法能够充分描绘出对其紧后工序以及总工期的 影响程度。 ( 6 ) 能够为优化提供形象而简洁的数学模型，并可以从许多可行的方案中选出最 优案，因而可以缩短工期，降低成本，提高经济效益。 ( 7 ) 可以利用计算机进行计算，为项目管理、全面计划管理提供必要的前提。 综上所述，网络计划技术，既是方案、规划、计划的科学表达方法，又是一种有 效实施方案、规划、计划的控制和管理方法。编制和修订网络计划的过程，也就是利 用网计划对工程进行模拟的过程，是进行动态的仿真与预演的过程。 真是由于网络计划存在这以上的优点，在过去的几十年里，网络计划无论在国外 还是国内都得到了迅猛的发展。国内是在世纪六十年代中期时，由华罗庚教授将网络 计划方法引入我国，并进行了大力宣传和推广，近半个世纪以来，曾在我国的许多工 程项目和企业中应用，取得了巨大的成果【3 2 ，3 3 1 。 2 2 2 网络计划技术的基本概念 ( 1 ) c p m p e r t 的基本概念 a 工序：工序即一项工程中的一道工艺过程或局部工作，它既消耗时间也消耗资 源。一般用大写字母a ，b ，c 表示，或用工序首尾相连的两个节点表示或用节点表 示。 紧后工序指的是某工序结束之后紧接着要进行的后继工序，紧前工序指的是与某 工序箭尾直接相连的工序，其紧前工序结束之后，该工序可以紧接着开始。两工序之 间无其它工序称它们为紧前紧后关系，否则称为前继后继关系。因此，般工序既是 它紧后工序的紧前工序，同时又是它紧前工序的紧后工序。 b 节点：节点即网络图中的圆圈，它代表某工序可能的开始时间或可能的结束时 间。节点只是表示某事件的开始时间或结束时间，它只代表着某一个瞬间，因此它既 不消耗时间也不消耗资源。 】 北京化i # 啦学位论文 开始节点是指代表某工序开始时间的节点；代表某工序结束时间的节点叫做该工 序的结束节点。同一个节点，对不同的工序而言，它既可以是开始节点，又可以是结 束节点。两节点间无第三个节点称其为紧前紧后的关系，否则，称为前继后继关系。总 丌始的节点叫源点，总结束的节点叫汇点。 c 工序的工期：工序消耗的时间称为该工序的工期，用字母t 表示。工期一般情 况下写在箭线的下方。 d 虚工序：网络图中的虚箭线。它既不消耗时间也不消耗资源。它代表虚工序的 紧前工序结束之后，虚工序的紧后工序才能开始。 e 路线、关键路线、关键工序 由源点开始顺着箭线方向一直到达汇点的条通道，叫做一条路线。每条路线都 要有很多工序组成。 路线上所有各工序的工期之和叫做该路线的路长，路长最长的路线叫做关键路线。 关键路线有时一条，有时有好几条，无论有几条部叫做关键路线，在网络图中一般都 用红色表示如图2 - 2 。 专一囝! ：、 “ l 卜9 掬喜玉 囝却谭黟簿蚤囝 是。jl ； i 图2 - 2 项目关键路径图 f i g2 2c r i t i c a lp a t hd i a g r mo f ap r o j e c t 关键路线上的所有工序都叫做关键工序，关键工序是工程的主要矛盾。如果关键 工序的工期推迟一天，则整个工程的总工期必定推迟一天：如果关键工期提前一天，则 整个工程的总工期可能提前一天。 总工期：总工期等于关键路线的长。 r 2 ) c p m p e r t 的时间参数 网络计划技术是系统工程的方法，它研究问题是从全局出发，从局部与周围环境 的联系中去把握事物。时间参数，正是一个局部的工序与周围的环境以及联系的一种 具体描述，因此，研究时间参数就是研究局部与整体的关系。网络技术的优越之处皆 从时间参数而来。 最早时间参数：主要反映一个工序与前继工序的关系。它有三个时间参数：工序的 最早开始时卣j ，工序的最早结束时间，节点的最早开始时间。 工序的最早开始时间：在网络计划中，工序最早可能的开始时间，记为e s 或e s 1 2 第二章网络计划技术与关键链理论 工序的最早结束时间：在网络计划中，工序最早可能的结束时间，记为e f “或e f a 。 工序最早开始时间加上该工序工期就得到该工序的最早结束时间，用如下公式表示： e f a = e s a + t a ( 2 1 ) t a 代表工序的工期，是网络图给出的，可当作已知的。因此只要工序的最早开始 时间知道，就可立即推知工序的最早结束时间。工序的最早开始时间是紧前工序最早 结束时间的最大值，即： e s 0 - - - m a x e s k l i ，e s k 2 i ，e s k n i ) ( 2 - 2 ) 因i j 与i r 有相同的紧前工序，所以e f i r - - - m a x e f k l i ，e f ) a i ，e f 】( 1 1 i ) 。即e s 0 = e s i ， 也就是说，共开始节点的工序最早开始时间相等。 节点的最早开始时间：某节点的任一紧后工序的最早开始时间，称为该节点的( 最 早) 开始时间，记为e s i 。显然，e s i = e s i j 。节点的最早开始时间等于其紧前工序最早 结束时间的最大值。 最早开始时间的特点是同一节点的所有紧后工序的最早开始时间都相同，或者说 共开始节点的工序的最早开始时间相同。 最迟时间参数：主要反映工序与其后继工序之间的相互关系。它也有三个时间参 数：工序的最迟结束时间，工序的最迟开始时间，节点的( 最迟) 结束时间。 工序的最迟结束时间：在不影响总工期的前提下，工序最迟可能的结束时间，记 为u 认或l f ，j 。如果工序实际结束时间比最迟结束时间推迟多少天，则总工期也会 被推迟多少天。 工序的最迟开始时间：在不影响总工期的前提下，工序最迟可能的开始时间，记 为或l s a 或l s ，j 。工序的最迟结束时间减去工期就等于工序最迟开始时间，用公式 表示如下： l s = l f a - t a ( 2 3 ) 工序的最迟结束时间应当等于其紧后工序最迟开始时间的最小值，用公式表示： l f i i - - m i n l s i k j ，l s j l a ，l s j k a ) ( 2 4 ) 因i j 与r j 有相同的紧后工序，所以l f i j = l f i j 即共结束节点的工序，最迟结束时间相等。很显然，实际开始时间比最迟开始时 间推迟n 天，则总工期就会因此而推迟n 天。 节点的最迟结束时间：节点的任一紧前工序的最迟结束时间称为该节点的( 最迟) 结束时间。 i p ：l f j = l f i j ，节点的最迟结束时间等于紧后工序最迟开始时间的最小值。 最迟结束时间的特点是同一节点的所有紧前工序的最迟结束时间都相等，或者说 共结束节点的工序的最迟结束时间都相等。 机动时间参数：机动时间参数反映了工序与其它工序联系的总和，它反映了该工序 在整体中地位，因此它是一个综合性的指标。 北京化工大学硕士学位论文 工序的总时差：在总工期不推迟的前提下，工序完工期可以延迟的最长时间，叫 做工序的总差或最大机动时间，工序a 的总时差记为t f ；。总时差等于工序的最迟结 束时间最早结束时间的差或等于最迟丌始时间与最早开始时间的差。 节点的时差：节点的时差等于该节点的最迟结束时间与节点的最早开始时间之差。 2 2 3c p i p e r t 的应用 在应用网络方法编制计划时，是通过网络图来表示一项工程、组成工程的各道工 序及其相互关系。网络图( n e t w o r kg r a p h ) 是由圆圈和箭线组成的代表一项工程计划 的图形。按网络的结构不同，可以把网络计划分为双代号网络和单代号网络。而双代 号网络可以分为双代号时间坐标网络和非时间坐标网络；单代号网络又可分为普通单 代号网络和搭接网络。主要是为了反映工作之间执行过程的逻辑关系而引入的一种网 络计划表达形式。 c p m p e r t 中的逻辑关系有【蚓： ( 1 ) 紧前工作( f r o n tc l o s e l ya c t i v i t y ) ：紧排在本工作之前的工作； ( 2 ) 紧后工作( b a c kc l o s e l ya c t i v i t y ) ：紧排在本工作之后的工作； ( 3 ) 平行工作( c o n c u r r e n ta c t i v i t y ) ：可与本工作同时进行的工作： ( 4 ) 先行工作( p r e c e d i n ga c t i v i t i e s ) ：自起点节点至本工作之前各条线路上的所有 工作； ( 5 ) 后续工作( s u c c e e d i n ga c t i v i t i e s ) ：本工作之后至终点节点各条线路上的所有工 作； ( 6 ) 虚工作：即是虚拟的，实际并不存在的工作，它不占用时间、也不消耗资源， 是双代号网络图中为了正确表示各工作间逻辑关系的需要而人为设置的，以虚箭线表 示： ( 7 ) 完成到开始关系f s ( f i n i s ht os t a r t ) = 后工作才开始的顺序关系； ( 8 ) 开始到开始关系s s ( s t a r tt os t a r t ) ： 开始的顺序关系； 某一工作完成后或完成一定时间后，其紧 某一工作开始一定时间后，其紧后工作才 ( 9 ) 完成到完成关系f f ( f i n i s ht of i n i s h ) ：某一工作完成一定时间后， 完成的顺序关系； ( 1 0 ) 开始到完成关系s f ( s t a r tt of i n i s h ) ：某一工作开始一定时间后， 完成的顺序关系。 其紧后工作才 其紧后工作才 c p m p e r t 的基本原理是，依据项目活动的各种逻辑关系( 硬逻辑、优先逻辑等) ， 将它们排成一个项目任务的网络图，在这个网络图中，各项项目任务从项目的开始日 期起按照“尽早开始”( a s s o o n - a s p o s s i b l e ，a s a p ) 进行排程，计算得出项目的总工 1 4 第二章网络计划技术与关键链理论 期，并形成一条或多条项目的关键路径。所谓项目的关键路径就是在那些由项目的并 行任务形成的多条实施路线当中对项目总工期起着决定作用的那些耗时最长的路线。 绘制中应遵循如下原则：a 按照前后工作的逻辑关系，从开始到结束，从左至右， 依次排列；b 突出关