（计算机应用技术专业论文）cg项目中进度优化算法的研究与实现.pdf

硕士论文 c g 项目中进度优化算法的研究与实现 摘要 近年来，随着计算机图形和图像技术的发展，使用计算机进行图形图像处理和逼真动 画的制作越来越多。三维c g ( c o m p u t e rg r a p h i c s ，电脑图形图像，简称c o ) 动画制作 与开发就是借助当今高速发展的先进的计算机技术来完成电影艺术制作的一个典范。鉴 于现在我国还没有成熟的针对c g 项目的管理软件，开发c g 项目管理软件具有很大的 商业价值，而进度控制、进度优化是项目管理中一个重要组成部分。 本文在对项目管理技术进行深入研究的基础上，完成了以下工作： 1 研究进度控制调整的方法。项目管理者及时收集与跟踪当前项目的实际进度信 息，将计划进度与实际进度进行比较，找出偏差，判断此偏差对项目进度的影响，并根 据其影响对进度计划做相应的调整和优化。 2 在研究了网络计划技术和c g 项目制作特点的基础上j 对网络图的相关计算方 法进行了讨论，根据当前任务的执行情况建立了系统的网络图。 3 对项目进度的优化与调整算法进行了研究。利用网络计划的传统优化算法实现 项目未完成任务的工期一费用优化：在深入研究了工期一资源的平衡优化后，利用免疫 遗传算法和启发式算法实现了工期最短与资源均衡的双重优化，并对这两个算法作出比 较。 4 提出了成本、工期与资源的综合优化模型。 最后将各种优化算法运用到c g 项目中，为决策者提供进度控制的依据。 关键词：网络计划进度优化免疫遗传算法启发式算法c g 项目 a bs t r a c t i nr e c e n ty e a r s ，c o m p u t e r sa r em o r ea n dm o r ef r e q u e n t l yu s e dt od e a lw i t hg r a p h sa n d m a k ev i v i da n i m a t i o n sa sc g ( c o m p u t e rg r a p h i c s ) t e c h n o l o g yd e v e l o p s t h e3 dc g a n i m a t i o ni so n em o d e lo fm o v i ea r tm a k i n g 、析t l lt h ea i do ff a s td e v e l o p i n ga n da d v a n c e d c o m p u t e rt e c h n o l o g y b e c a u s et h e r ei sn om a t u r em a n a g e m e n ts o f t w a r ew h i c hi su s e di nc g p r o j e c t ，d e v e l o p i n gc gp o r j e c tm a n a g e m e n ts o f t w a r eh a sm u c hc o m m e r c i a lv a l u e s c h e d u l e c o n t r o l i n ga n do p t i m i z m i o ni sa ni m p o r t a n tp a r to fp r o j e c tm a n a g e m e n t t h i sp a p e rc o m p l e t e st h ef o l l o w i n gt a s k so nt h ef o u n d a t i o no fad e e p g o i n gr e s e a r c hi n p o r j e c tm a n a g e m e n t ： 1 i ts t u d y st h em e h o do f s c h e d u l ec o n t r o l i n ga n da d j u s t m e n t p o j e c tl e a d e r sc o l l e c ta n d f o l l o wf a c t u a ls c h e d u l ei n f o r m a t i o ni nt i m e ，c o m p a r ef a c t u a ls c h e d u l ew i t l lp l a n e ds c h e d u l e a n dc o m p u t et h ed e v i a t i o n t h e nt h e yj u d g et h ei m p a c to nt h ep r o j e c ts c h e d u l ea n do p t i m i z e t h ep l a n e ds c h e d u l ea c c o r d i n g l y 2 i td i s c u s s e st h ec o m p u t i n gm e t h o da b o u tn e tc h a r ta n dc o n s t r u c t ss y s t e m i cn e tc h a r t a c c o r d i n g t ot h ea c c o m p l i s h e ds t a t eo ft h et a s k sa f t e rs t u d y i n gt h en e tp l a nt e c h n i ca n dc g p o j e c tc h a r a c t e r i s t i c 3 i tr e s e a r c h e st h eo p t i m i z a t i o na l g o r i t h mo fp r o je c ts c h e d u l i n g a tf i r s t ，i tr e a l i z e st h e t i m e c o s to p t i m i z a t i o nb yt h et r a d i t i o n a lo p t i m i z a t i o na l g o r i t h mo fn e tp l a n ；t h e n ，i tu t i l i z e s h e u r i s t i ca l g o r i t h ma n di m m u n eg e n e t i ca l g o r i t h m ( i g a ) t oa c h i e v et h ed o u b l eo p t i m i z e d o b j e c tw h i c ha r et h es h o r t e s tt i m ea n dr e s o u r c ee q u i l i b r i u ma f t e rs t u d y i n gt h et i m e - r e s o u r c e o p t i m i z a t i o na n dc o m p a r e so n ea l g o r i t h mt ot h eo t h e r 4 i tp r o p o s e da i n t e g r a t e dm o d e lw h i c ho p t i m i z e sc o s t ，t i m ea n dr e s o u r c ei nt h es a m e p r o c e s s a tl a s t ，t h i sp a p e ra p p l y sa l lt h eo p t i m i z a t i o na l g o r i t h m st ot h ec g p r o j e c ta n dp r o v i d e s d e c i s i o n m a k e r st h eb a s i so fs c h e d u l ec o n t r o l i n g k e y w o r d s ：n e tp l a n ，s c h e d u l i n go p t i m i z a t i o n ，i g a ，h e u r i s t i ca l g o r i t h m ，c gp o r j e c t 声明严明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：型坠至至堕 幼妇年6 月2 2 网 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容尊对 于保密论文，按保密的有关规定和程序处理。 研究生签名： 浏瞻菌 2 移碣年6 月2 2 日 颈士论文 c g 项秘串迸度优化算法的研究与实现 1 绪论 1 1 课题背景介绍 科学家预言，2 l 世纪最有前途的两个行业，是信息产业和文化产业。动蘧业作为后 起之秀，越来越成为文化产业的生力军。其全球受众和衍生产品消费者，达数十亿之多。 在0 7 年世界十大卖座电影中，怪物史莱克3 、料理鼠王和辛普森一家都是动 藏电影，变形金玛l 剡运用了大量的c g 制作。美国作为全球最大的娱乐产品输出善， 其每年的动诋产品和衍生产品的产值就达5 0 多亿美元。前颢四部卖座电影全都出自美 国。日本则通过动画片、卡通书和电子游戏三者的商业组合，成为全球产量最大的动画 大国，年营业额超过粥亿美元。即使是后起之秀的韩国，发展势头亦咄咄逼入，以全 球3 0 的产量，稳居世界动蘧年产值探花位萋。但反观我国动画产业则处于起步阶段， 与上述国家差距甚大。据统计，现在全国动蕊从业者不足l 万人，仅为韩国的1 3 。国 产动画年产量仅有日本的1 ，日本人均拥有国产动画5 8 分钟，而我国只有区区0 0 0 1 2 秽。所以要打破钤国动痼垄断世界市场的局面，离外国震示我们中国独特的东方文化， 为世界文化添上绚丽的一笔，大力发展动画产业已i 刻不容缓。 一个动厕项目，通常都需要大量的行政人员及开发人员，硬件设备和资源素材；与 此同时，需要大量的资金投入，而且一般项嗣的执行周期也比较长，项目管理复杂。项 舅所需资源之间一般都有潜在的依赖性和限制条件，以及资源的相互替代和排他性，这 些都大大增加管理项目的复杂度。怎样通过一定的方式合理地组织有关人员，并有效地 管理项目中的所有资源( 人员、设备等) 与数据，提出项目计划，对项目进度进行优化，； 怎样在项目实际运行时，根据实际运行情况与计划之闻的差异，对项目重新进行优化， 即在限定的资源消耗，限定的时间要求、限定的成本要求和限定的质量规定内，以最低 的成本、最短的工期和均衡的资源利用为目标对项目中那些未完成的任务进行进度控制 来完成既定项目。这些都是摆在项目经理面前必须克服的难题，同时这些难题很难用个 人经验和直觉来科学地解决。现实和市场需求要求我们及时地开发出适用于现有多媒体 创造与制作的项圈管理软件。 本课题源于上海上影数码公司研发项目“c g 制作环境开发和关键技术研究”，该项 豳的主要目标是针对c g 制作这个特殊的行业开发个软件平台。这个软件不但可以跟 踪整个项譬的工作流程，很好地集成现有的管理软件、3 d 制作软件、多媒体创作和动 漫软件，而且可以移植到各种不同的硬件平台和操作系统环境中使用，帮助管理者对项 目计划进行优化和对公司的人力资源和项目进度进行监控，最终保证项目的顺利完成。 i 绪论 硕士论文 1 2 项目管理研究历史、现状与展望 1 2 1 项目管理研究历史 自从项圈( p r o j e c t ) 这个词诞生以来，项目管理就应运而生。刚开始项目管理者利 用关键日期表来计划项目。关键日期表是最简单的一种进度计划表，它只列出一些关键 活动和进行的日期。尽管它编制时闻短、费用低，但其精度低，不能有效地管理项目。 于是在第一次世界大战期闻美国法兰克福兵工厂的h g a n t t 进行计划管理时，酋先用横道 图来代替关键日期表。横道图简单明了，容易控制，所以至今仍被广泛应用。但同时横 道图的缺点也显现出来了，就是各工序之间的相互关系不能清晰、严格地反应出来。二 战以后，市场竞争和国际军事竞争冒益激烈，促使人们进行计划管理方法上的变革，网 络计划技术在这种形势下应运而生。1 9 5 6 年，美国杜邦与兰德公司合作，开发了 c p m ( c r i t i c a lp a t hm e t h o d ，关键路径法) ，使项目工期缩短，成本大幅度下降。但随着这 项技术的广泛运用，入们发现其只能对各项任务工期是确定值的项目效采显著，而对那 些任务王期不确定，风险大的项冒就不适用了。1 9 5 7 年，美圜海军特种计划局为军备竞 赛和开发宇宙空间的需要，提出了p e r t ( 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 ，计 划评审技术) 。它与c p m 基本原理一致，都是利用网络计划技术来反映整个项目的全貌， 即用网络图来表示项目中各项活动的进度和它们之间的相互关系，并在就基础上，进行 鼹络分析，计算网络中各项经务时间参数，确定关键任务与关键路线，利用时差不断地 调整与优化网络，以求得最短周期。同时，它与c p m 也有所不同：1 它克服了c p m 的缺 陷，采用悲观工期、乐观工期和最可能工期三种情况估算不确定性较大的任务工期。 2 c p m 重点用于费用与成本的控制，p e r t 重点用于时闻的控制。英后，人们陆续提遗了 一系列新的网络计划技术。7 0 年代，人们充分考虑到过程的随机性，把概率论引入到 p e r t 中，提出了g e i 玎【1 1 ( 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 ，图示评审技术) 。 8 0 年代初，人们将风险决策理论弓l 入g e r t ，又提出t v e r t t 2 j ( v e n t u r ee v a l u a t i o na n d r e v i e wt e c h n i q u e ，风险评审技术) 。v e r t 和g e r t 虽然在理论上能够解决生产中的许多 问题，然而它们的缺点也是十分致命的。首先，它们的求解需要大量的相似项目的历史 统计数据和高级的计划管理人员。项目的一次性，这个项目管理的最大特征，使得在实 际操作时没有多少历史资料可以借鉴，因此后两种网络计划技术尽管在理论上可行，但 是并不符合客观实际情况。其次，它们计算量大，耗时长，根本不适合运用到现在的软 件上。 因此，目前制定项目进度计划的常用方法仍然是c p m 与p e r t 。 1 2 2 项目管理研究现状与展望 目前项舀进度管理的研究主要分三个方面展开：首先是时间一费用( 成本) 优化 2 颧士论文c g 项嗣中进度优化算法的研究与蜜现 t 3 ( t i m ec o s tn a d p _ 0 鳓，在工程工期和成本之间寻求种均衡，使得在工期允许的情 况下费用最低，或者在费用允许的情况下使得工期最短，从而使两者之间达到最优的组 合。其次，出予p e r t 和c p m 是针对没有资源限制筋蕈个顼蕊的计划管理，弱现实中一 个企业霹对管理多个项基邑阉空见惯。在这种情况下，经常发生顼墨之闯相互影响、争 夺资源的现象，因此在资源有限的约束下，如何制定每个项目的计划，保证各个项目顺 利完成( 即项目工期与成本符合项目要求) ，并且充分地利用企业的所有资源成为学者 黧翦热衷研究熬闯题。最嚣，顼圈在实麓过程孛，经常会遥捌各种突发事件，导致各个 活动的作业时间的不确定性，丽c p m 要求的作业活动时间是确定的，p e r t 采用经验公 式来计算，不能真实地反映实际的任务工期，因此，如何更准确地估算任务工期、消除 不确定园素的影响成为最近研究的热点。 众所周知，发展韵实现顼嚣进度警理离不舞管理愚想、管翌组织、管理方法和手段 的现代化。随着客户曰益严格的现实需求、先进管理思想的涌现以及计算机技术的发展， 项目进度管理的发展趋势和前景主要体现在两个方面；管理理念和管理方法的提升、先 进应粥方式的提舞。在管理理念弱管理方法的提升上，近霸涌现了些先进鹩管理愿想， 如弼c ( 制约因素理论、约柬管理 、知识管理、柔性管理等等嘲。这些管理思想都是处 在起步阶段，有很大的发展空间。在先进应用方式提升方面，主要表现在将计算机模拟 技术、智能方法、数据库技术、多媒体技术、g i s ( g e o g r a p h i c a li n f o r m a t i o ns y s t e m ，地 理信患系统) 、c a d ( c o m p u t e ra i d e dd e s i g n , 计算机辅助设计) 以及计算枕嚣络技术魅综 含集成，从瘸集成这些方法的优越性，克服它们的局限性，使项嗣管理走向智能化、集 成化、实时化和网络化。 1 3 论文主要工作 本文在对c g 项嚣髂开发流程和项匿进度管理进行深入研究的基蕊上，采用网络计 划技术构建颂譬进度管理摸型，实现多种顼遐进度控剃的优化算法，从而完成了对进度 的调整与控制。 本文的主要工作有： 1 研究进度控制调整静方法。骚基管理者及时收集与跟踪巍蓠顶毒豹实际进度瘩怠， 将计划进度与实际宪成鲶进度进行比较，找懋偏差，判断此镳差对顼星进度麴影响， 并根据其影响对进度计划做相应的调整和再次的优化。 2 根据c g 项嚣管理的特点，确定项目剩余任务( 融开始末完成的任务或未开始的任 务) 的逻辑关系，应用掰络计划技术建立进度计划，为优诧葵法的计算做好准备。 3 。对进度计划的优化算法进行研究。对项遐工期与成本之闻的关系进行分析，用传统 的正期一成本算法找出工期一费用的最优组合。采用免疫遗传算法和启发式算法对 1 绪论 硕士论文 工期一资源进行优化，并对这两种算法进行比较，总结它们的优缺点。最后在此基 础上提出一种工期、成本、资源的综合优化工作模型。 1 4 论文结构 论文章节安排如下： 第一章绪论。介绍本文的课题背景、项目管理研究历史、现状及展望、论文工作 内容和论文各章结构。 第二章项目进度管理的基础理论。简要地介绍关于项目管理的基本概念，重点是 对项目进度管理的基本内容进行阐述，包括进度管理模型和方法，进度控制 世 号宁。 第三章网络计划技术。简述网络计划技术的基本理论，以及介绍怎样为当前正在 执行的项目建立项目网络图的方法。 第四章c g 项目进度的优化与调整。首先利用传统的工期一成本算法找出工期一成 本的最优组合，从而确定各剩余任务的工期；然后采用免疫遗传算法和启发 式算法对进度计划的工期一资源进行优化，并对这两种算法进行比较，总结 它们的优缺点。最后在此基础上提出一种工期、成本、资源的综合优化模型。 第五章进度管理系统实现。 第六章结束语。总结全文，指出不足之处，展望今后的研究方向。 1 5 本章小结 4 本章简要介绍了课题背景，项目管理的研究现状，论文的主要工作和结构。 硕士论文c g 项黼中进度优化算法的研究与实现 2 项目进度管理的基本理论 2 1 项目管理的基本概念 2 1 1 项目定义与特征 项目就是以一套独特而相互联系的任务为前提，有效地利用资源，为实现一个特定 的目标而做的努力。鉴于这个定义，可以总结出项目有如下特点1 5 】： ：盾置任务的结束取决于前置任务的结束，只有前置任务结 束，后委任务才能结柬。 ( 3 ) s t s ( 开始一开始) ：鏖置任务麴开始取决予前置任务的开始，只有翦置任务开 始，后置任务才能开始。 o ) s t f ( 开始一结束) ：后霞任务的结束取决予前置任务的开始，只有前置任务开始， 后萋饪务才笼结束。 3 。2 。2 网络图的绘制 众所周知，在绘制网络图时，必须了解和遵守一些基本原理。按绘制网络图麴形式 不同，可分为两种：箭线表示活动( a c t i v i t yo nt h ea r r o w ，a o a ) 和节点活动( a c t i v i t yo n t h en o d e ，a o n ) 。 1 箭线表示溪动翳络图 箭线表示活动网络图又称为双代号网络图，用一条箭线表示任务，节点表示任务的 开始与结束。它分为兰步绘制：将每项任务由虽仅由个箭头表示，箭尾代表任务的开 始，箭头代表任务熬结束，并将任务戆描述写在篱线上；利霜节点( 又稼事件 表示任 务之阀的逻辑关系；慰这些节点指定唯一的序号，以便霹以利用唯一的紧静和紧随事件 序号来识别任务。其中，紧前事件( p r e d e c e s s o re v e n t ) 是指任务的开始事件，紧随事件 ( s u c c e s s o i e v e n t ) 是指任务的结束事件。如图3 2 1 。从图中，我们可以看到：对于活 动“致”，紧前事件是3 ，紧随事件是5 。 圈3 2 1 箭线袭示活动网终图示例 从图3 2 1 可班看出：这种网络图仅能表示f t s 这种逻辑关系。如果要表示其它的 任务逻辑关系，藏妊须增舅鬟一释特殊酶活动，麓徽纛活动( d u m m ya c t i v i t y ) ，它没有往 务名称，也不消耗时阑和资源，在网络图中用一条虚翁线表示。值褥注意豹是，使用虚 活动还有个作用：有助于很好地识别活动，以便予计算机软件来计算项目进度。但同 时，豳予增加了虚活动，表达变得烦琐，所以渐渐被节点表示活动网络图所替代。 2 。节点表示活动鼹络图 节点表示活动隧络图又称单代号网络图，用节点表示镬务，周节点闻豹箭头连线襄 1 6 硕士论文c g 项飚中进艨优化冀法的研究与鬟现 示任务之阕黧逻辑关系。它分两步来绘制：将每项任务鼹一个畜唯一序号翁框表示，并 把该项任务的描述填入框内；根据任务之间的逻辑关系，用箭头将这些框连起来。这时， 我们将箭尾节点称为前置节点，箭头所指节点称为后置任务。如图3 2 2 。 睡3 。2 2 节焦表豕活动鼹络图示镶 实践证明，这种网络图表达逻辑关系简洁明了，丽且能反映各种逻辑关系。随着网 络计划技术的发展，以及计算机技术在项目篱理上的应用，国内外所有基于网络计划技 术的项器管理软件现在都只采用节点表示活动网络图这种形式，本文亦采用这种形式。 3 2 3 瓣络匿的裰关计算 3 。2 。3 。1 任务逻辑关系的转换 本文3 2 2 节所介绍的节点表示活动网络图可以支持s t s 、s t f 、f t s 、f t f 四种任务 逻辑关系，然而使用网络计划技术计算的逻辑关系一般是f t s ，也就是说前鬣任务完成 后，蒿嚣饪务才可以开始的逻辑关系。这就要求消除f t s 之外的三释关系。 力了消除其余三静关系，我们对节点表示活动网络中的每个繁线定义l t ( i , j ) ；其中， l t ( i j ) 表示一段时间，i 表示前置任务，j 表示膳置任务。l t ( i j ) 在支持不同的任务逻辑关 系的蹿络图含义不闻：在支持f t s 的网络图中，l t ( i j ) 是指往细在任务i 完成t l t ( i j ) 时 阑后才允诲开始；在支持f 程的飚络蚕中，l t ( i j ) 是指饪筠在往务i 完成t l t ( i j ) 辩闻后 才允许完成；在支持s t s 的网络图中，l t ( i j ) 是指任妫在任务i 开始i l t ( i j ) 时间蜃才允 许开始；在支持s t f 的网络圈中，l t ( i j ) 是指任蜘在任务i 开始t l t ( i j ) 时间眉才允许完 成。由此爵以看出：无论哪种逻辑关系类型都可以用任务i 完成与任务j 歼始时间差来统 一所有逻辑关系，从蔼完成其余三种关系i 龟f t s 的转换。 令4 表示任务i 的工期，d ，表示任奶的工期，任务i 与任务i 之间的关系是除f t s 的 其它兰种关系，现在要将它们转为f t s ，重新定义两者之间的l t ( i ，j ) 罄2 】； s t s 转为f t s ：l t ( ；，力= 五r ，j ) - 叠( 3 2 _ 1 ) f t f 转为研s ：l t ( i ，) = l t ( i ，力一d ，( 3 3 2 ) s 耶转为f t s ：l t ( i ，) = 五r ( f ，) 一d i d ，( 3 3 3 ) 3 2 3 2 网络时间参数与网络计算 将除f t s 的其它三种逻辑关系转化为f t s 以焉，项瞬管理者就应利用两络计划技术 计算潮络时阕参数来为计划、控制项髫提供数据支持。 1 7 3 网络计划技术硕士论文 1 网络计算主要时间参数 ( 1 ) e s 。：任务i 的最早开始时间 醪，= m 然( e s ，+ d ，+ l t ( j ，f ) ) ( 3 2 4 ) ，e ，i 。 式( 3 2 4 ) 中，p ( i ) 为任务i 的前置任务集；d ，为任务j 的工期；l t ( j ，i ) 表示任务j 完成 了l r ( j ，i ) 时间后，任务i 才允许开始。 ( 2 ) e f , ：任务j 的最早结束时间 e f , = e s ，+ d f l( 3 2 5 ) 式( 3 2 5 ) 中，e s ，为任务i 的最早开始时间；d i 为任务i 的工期。 ( 3 ) 三e ：任务i 的最晚结束时间 砸2 勰( 乃一d j l t ( i ，脚 ( 3 2 6 ) 式( 3 2 6 ) 中，s ( i ) 为任务i 的后置任务集；d j 为任务j 的工期；l t ( i j ) 表示任务i 完 成了l t ( i , j ) 时间后，任务j 才允许开始。 ( 4 ) l s 。：任务i 的最晚开始时间 三= 互一e + 1( 3 2 7 ) 式( 3 2 7 ) 中，三只为任务i 的最晚结束时间；口为任务i 的工期。 ( 5 ) r s 。：任务i 的总时差( t o t a ls l a c k ) ，是任务i 不影响整个项目完工日期的情况 下可以延迟的时间。 t s ，= 工e e e或t s ，= l s ，一e s 。( 3 2 8 ) 式( 3 2 8 ) 中，e s ，为任务i 的最早开始时间；嬲为任务j 的最早结束时间；三只为 任务i 的最晚结束时间：船，为任务i 的最晚开始时间。由上面的公式可知，这两种计算 方法得出的结果是相等的。这里，需要指出的是：总时差值可正可负；所有总时差为最 小的任务都是关键任务。这些关键任务组成的路径就是关键路径。 ( 6 ) f s ( i ，) ：任务i 对于任务j 的自由时差( f r e es l a c k ) ，是任务i 不影响其后置任 务i 最早开始时间的情况下可以延迟的时间。 f s ( i ，) = t s j m j n 女) (39),(rs 2 nejij j 式( 3 2 8 ) 中，t s i 为任务i 的总浮时，p ( i ) 为任务j 的前置任务集。 ( 7 ) o d 原定工期( o r i g i n a ld u r a t i o n ) ，指完成某项任务的工期估计。 不同的模型对任务的工期估计计算也不相同。这里，介绍一下计划评审技术中的任 务工期估计模型。假设每个任务都有三个估计时间：乐观时间( o p t i m i s t i ct i m e ，f ) 、 最可能时间( m o s tl i k e l yt i m e ，t m ) 和悲观时间( p e s s i m i s t i ct i m e ，t t , ) 。乐观时间是指 在任何事情都进行得很顺利，没有遇到任何困难的情况下，完成某项任务所需的时间； 1 r 硕士论文c g 项目中进度优化算法的研究与实现 最可能时间是指在正常情况下完成某任务最经常出现的时间；悲观时间是指某任务在最 不利的情况下能够完成的时间。 d d ：垒丝坐巳 ( 3 2 1 0 ) 6 。 注意：式( 3 2 1 0 ) 成立的假设是这三个估计时间均服从概率分布。 2 网络计算的方法 根据计算的网络时间参数的不同可以分为两种方法，即正推法( f o r w a r dp a s s ) 和逆推 法( b a c k w a r dp a s s ) 。 正推法是从项目开始沿网络图到项目完成进行计算的方法，被用来计算最早开始时 间和最早结束时间。 逆推法是从项目完成沿网络图到项目的开始进行推算的方法，被用来计算最晚开始 时间和最晚结束时间。与正推法不同的是，反推法必须有项目结束时间已确定为前提。 所以，当项目未确定结束时间时，就将用正推法计算出来的项目最早结束日期( 即所有 任务的最早结束时间的最大值) 作为逆推的时间起点。 3 3 网络计划技术在c g 项目中的应用 项目管理发展到现在，网络计划技术在制订c g 项目计划的应用中已经非常成熟了， 能够根据c g 项目制作流程的特点将其进行工作结构分解，并用分级网络计划技术形成 一个巨大、复杂的网络图。但是，网络计划技术在c g 项目执行后出现变更的应用并没 有详细地研究。本文所指的变更有两种：项目相关信息的变更；由于任务实际执行时出 现严重延迟或超支而导致项目不能按计划完成进而产生的变更，即任务参数( 进度、成 本) 引起的变更。这里，项目相关信息的变更主要指的是各种资源数目的改变、项目最 晚完工日期( p r o j e c td e a d l i n e ) 的改变和项目成本( p r o j e c tc o s t ) 的增加与减少。很明显， 这些变化都是项目宏观的改变，不会影响网络图发生改变，应该直接进入项目优化这个 流程。而任务参数引起的变更多数是由任务实际的开始与完成日期与计划有出入引起 的，会影响网络图。这就需要网络计划技术根据当时的任务执行情况重新绘制网络图。 但不管是哪种变更，都需要一个机制，将变更数据及时汇报，使项目管理者能够及 时处理变更，进而使项目按计划完成。这就是项目控制过程。 3 3 1 项目控制过程 项目控制过程包括定期收集项目完成情况的数据，并将实际完成情况数据与计划进 行比较，一旦发现项目实际进程晚于计划进程，则及时采取补救措施。这个过程在整个 项目工期内必须定期进行。 1 9 3 网络计划技术 硕士论文 图3 3 1 说明了项目控制的步骤。该过程从制定项目( 任务) 范围如何在预算( 资 源、成本) 内按时完成的基准计划开始。 图3 3 1 项目控制过程 从图3 3 1 可以看出，确定一个固定的报告期( r e p o r t i n gp e r i o d ) 是十分重要的。根 据c g 项目具体的复杂程度和完工期限，可以将报告期定为日、周、双周或月。如果项 目只是给电影或电视剧添加动画效果，工作量比较小，预计在一两个月内就能完成，报 告期应该短至一天；如果项目是完成一部动画电影，工作量很大，预计工期为三五年， 那么报告期可以是一个月。当然，报告期相对长的项目，还要建立一种机制，就是一发 现有项目变更，就立即向项目管理者汇报，以保证信息的及时收集和迅速采取有效的补 救措施。 3 3 2 进度的比较与偏差分析 项目管理者收集到任务参数后，就将实际进度与计划进度进行比较，以便监控项目 和在必要时采取补救措施。! 挣值管理法、横道图比较法、s 型曲线比较法、香蕉曲线比 较法、前锋线比较法和列表比较法等是进度分析与比较的常用方法，这些在本文第二章 都有详细描述。在c g 项目中，对于项目的整体我们采用s 型曲线比较法，而对于具体 的任务我们采用列表比较法。 进度偏差主要指项目中的一些任务由于对其困难估计不足或发生突发事件而导致 完成时间的拖延。列表比较法是利用网络计划中的总浮时和自由浮时来判断是否对项目 进度进行补救的技术。图3 3 2 表明了列表比较法的分析步骤【2 3 1 。其中，匕表示进度偏 差，t s 表示总时差，f s 表示自由时差。 列表比较法的分析步骤中有三次重要的判断： 首先，判断出现进度偏差的任务是否为关键任务。如为关键任务，则无论偏差大小， 2 0 硕士论文c g 项目中进度优化算法的研究与实现 都肯定会对后置任务以及项目工期产生影响，必须重新绘制网络图，并采取措施进行补 救，即利用项目剩余任务优化模块对项目正在进行的任务和将要执行的任务组成的网络 图进行优化，并执行其变更后的计划。 其次，判断进度偏差是否大于总浮时。若任务的进度偏差大于该任务的总浮时，则 该任务对后置任务和项目工期肯定都有影响，需要变更计划；若任务的进度偏差小于该 任务的总浮时，则此偏差对项目工期无影响，而对后置任务是否有影响，要进一步比较 自由浮时和进度偏差。 最后，判断进度偏差是否大于自由浮时。若任务的进度偏差大于自由浮时，则对后 置任务会产生影响，只要对后置任务作适当调整；若任务的进度偏差小于或等于自由浮 时，则对后置任务无影响，原进度计划可不作调整。 图3 3 2 列表比较法分析步骤 3 3 3 网络图的生成 1 算法描述 我们知道，项目计划网络图包含的节点比项目剩余任务网络图包含的节点多，因为 项目计划网络图包含所有任务，而项目剩余任务网络图包含部分的正在执行的任务和全 部的将要执行的任务。但如果我们将项目计划网络图的所有任务都看成是将要执行，就 与项目剩余任务网络图的理论相一致了。 图3 3 3 表明将项目计划网络图处理为项目剩余任务网络图的过程。其中，i 表示任 务的序号，r l 表示项目的任务数量。 图3 3 3 中“项目参数修改”主要做的是：将项目计划开始时间定为当前时间；项目 成本定为原来计划的总成本减去已经花去的成本。 众所周知，项目一旦开始执行，项目网络计划图上的任务就分为三个状态：已执行、 正在执行和将要执行。已执行的任务由于不需要优化在项目剩余任务网络图被删除；而 将要执行的任务全部留在了项目剩余任务网络图上。接下来，就剩下对正在执行的任务 2 1 3 网络计划技零 矮士论文 进行处理：根据计算任务还需要执行的工期f ，来决定是否将此任务留在网络图上。 图3 3 3 项嚣剩余任务网络图处理过程 式( 3 3 。1 ) 就是正在执行任务的剩余工期( 即还需要执行的王期) 计算公式。其中f ，表 示任务还需要执行的工期，o d 表示任务计划时所定的工期，f 。表示任务从实际开始时 间到当前时间所执行的时间段。从这个公式可以看出：它是建立在任务一旦开始，就不 会中断的假设之上。 ，一o d - t 。+ l ( 3 3 。1 ) 我们承认，任务会由于某种原因到了应该完成的时阗还没有完成的情况确实存在， 但由于在计划时项目管理者一般充分估计了任务的困难和突发事件的可能性，并给任务 工期留有一定的裕量，所以这种情况出现的概率不丈。实践证明，我们在计算f ，时出现 工期小于零的情况，大多不是因为任务嵩现延迟，丽是因为项譬信息流通受阻，不能及 时将任务完成的信息及时通知管理者。也正是由于这个原因，当出现这种情况时，我们 就假设此任务已经完成，将其从网络图中删除。 图3 3 3 中“修改未删除任务时间参数”主要是确定哪些是网络图的开始任务，即它 们的计划开始墨期为当前时阁。开始任务分为两种：一种是剩余工翘茭正数的正在执行 的任务，另一种是其所有前置任务都已经完成的任务。注意，这里确定任务完成有两种： 一种是实际已完成，即实际结束日期已经录入；另一种是期望完成，即剩余工期非正。 处理过程到此，就生成了项圈剩余任务溺络图的所有任务，郎为节点。 硕士论文c g 项目中进度优化算法的研究与实现 生成网络图的难点是怎样将分散的节点连成复杂、相互关联的大型网络图。但由于 本文主要作的是项目变更后的研究，其前提是在项目执行之前，已经有一个详细的项目 计划。而在做项目计划的时候，首先要绘制项目网络图，即项目中所有任务的逻辑关系 已经明确了。所以，要绘制项目剩余任务网络图就只要在原来项目网络图删除已经完成 的任务节点及其连线，并增加一开始的虚节点( 任务工期为零，消耗资源、成本为零) ， 将它连上所有计划开始日期为当前时间的任务即可。 图3 3 3 中“确定任务的计划时间”是根据各任务工期将网络图上所有任务的时间参 数计算出来，并根据项目的“尽早完成”原则，将所有任务的计划开始时间置为最早开始 时间。 2 生成网络图的基本数据结构 由于本文实现算法所用的是a s p n e t 技术，通常不使用指针，所以数据结构主要 是用数组来实现。虽然数组比邻接表实现方法浪费空间，但它在使用时编程比较方便( 只 要通过下标查询即可) ，也节省时间。这对一个复杂的程序来说，是一个至关重要的优 点，因为它直接关系到技术的可实用性，即运用此技术是否能在较短的时间内得到结果。 ( 1 ) 任务节点数据结构 p u b l i cc l a s st a s k p n 。v a t e 血枷；任务号，用于标识任务 。：，p r i 。v a t ed a t e t i m ee a r l i e s t s t a r t t i m e ；任务最早开始时间 p n v m ed a t e t i m el a t e 删i m e ；任务最晚开始时间 p n v a t ei n tt o t a l f l o a t ；总浮时 p n v a t ei n tf r e e f l o a t ；自由浮时 p r i v a t ed a t e t i m ep l a n e d s t a r t t i m e ；任务计划开始时间 p n v a t ed a t e t i m ep l a n e d f m i s h t i m e ；任务计划结束时间 p n v a t ei n tp l a n e d c o s t ；任务计划所需的成本 p n v a t ei n tp l a n e l e r i o d ；任务计划所需的完成时间 p r i v a t eb o o ld o i n g ；确定任务是否是正在执行任务 ) 注意：为了方便起见，这个任务节点的数据结构省去了任务名与负责人，因为这些 信息对下一章项目优化没有任何用处。 在网络图中，它的所有节点用一个节点数组描述： t a s kt a s k = n e wt a s k m ；m 为节点数量 ( 2 ) 任务节点之间逻辑关系的数据表示 b o o l ，】f o u o w t a s k t a s k = n e wb o o l r n ，m 】；n 为节点数量 3 网络计划技术 硕士论文 f o l l o w t a s k _ t a s k i , j 的布尔值表示任纫是否是任务i 的后置任务；如果为真，则表示 任务j 为任务i 的后置任务，反之则不是。 这里，需要注意的是：本文使用的是网络计划技术，其假设任务是一次完成，不能 重复完成，也就是说网络图中不能有环。所以，按常理，在向f o l l o w t a s k _ t a s k 数组赋值 时，要同时检查它是否符合这个要求。但就像前面说的一样，本文是建立在项目计划已 完成，正在执行的基础之上，项目网络图中是否有环在做项目计划时就已经检查过了， 而且项目剩余任务网络图只是项目网络图的一部分，所以，在项目变更重构项目剩余任 务网络图时就不需要重新检查，直接赋值就行了。 ( 3 ) 项目数据结构 p u b l i cc l a s sp r o 厄c t p n v a t ei n tp r o j i e c t l d ；项目号，标识项目，方便查询 p n v a t ei n tp l a n e d t o t a l c o s t ；项目总成本 p n v a t ed a t e t i m ep l a n e d f m i s h t i m e ；项目计划结束时间 p n v m ed a t e t i m ep l a n e d s t a r t t i m e ；项目计划开始时间 p n v a t ei n tm a x c o s t ；项目最大成本 p n v a t ed a t e t i m ed e a d l i i l e ；顺目允许的最晚完成日期 ) 3 3 4c g 项目进度的计算方法 本文3 3 2 节的进度比较是微观的进度比较，即以实际任务是否按计划完成来比较。 作为一个项目管理者，他同时也需要宏观的进度进行比较，即实际项目完工程度与计划 完工程度的比较。 项目的完工进度就是指项目的完工百分比。这里，本文利用每项任务的实施进展速 度都是均匀的假设来计算项目完工进度。式( 3 3 2 ) 是计算完工进度的公式；其中，d o n e ， 是任务i 己完成的工作量，用任务i 已经执行的工期表示，为以后书写方便起见， 设加：yd o n e 。；1 1 是项目网络图的节点数目；p l a n e 勿e r i o d , 是任务i 的工期。 备 n d o n e j c o m p l e t e d = 下- l 一奉1 0 0 ( 3 3 2 ) 芝lp l a n e d p e r i o d i 面。 b k 式( 3 3 2 ) 可以看出，很明显，p l a n e 和p r i o d ，是一个常量，一旦对各任务的时间 估算确定，此值也确定了；t d 是一个随着项目的执行而变化的数值，也是项目完工进 度计算的难点。 项目完工进度分为计划完工进度和实际完工进度。图3 3 4 的左图是计算计划完工 2 4 硕士论文c g 项目中进度优化算法的研究与实现 进度时获得t d 值的流程，右图是计算实际完工进度时获得t d 值的流程。其中，1 1 是 项目网络图的节点数量；p s t , 是任务i 的计划开始时间( p l a n e ds t a r tt i m e ) ；剧z 是任 务i 的计划结束时间( p l a n e df i