（道路与铁道工程专业论文）公路施工项目网络计划优化问题研究.pdf

摘要 公路建设项目管理问题是当前管理经济学和建筑经济学领域的一个研究热点和重点， 项目进度管理问题是其中的一个重要方面。网络计划技术是现代管理科学总结出的一种科 学的计划管理方法，是项目进度管理的一种有效工具。本文针对国内外研究现状与存在的 问题，从经济学原理、施工组织原理和系统分析方法等视角和层次，研究了公路施工项目 进度计划中有关工作持续时间的估算、网络计划工期及成本、资源优化等问题，主要研究 工作和研究成果如下： 1 通过对现行工作作业持续时间计算方法的分析，应用经济学中的“边际收益递减规 律 理论，研究工作投入资源量与其产量之间的非线性关系，对确定性工作的持续时间计 算模型进行了修正；通过实例对新模型的可操作性和实用性进行了验证，结果表明：应用 本文给出的计算模型进行工作持续时间分析，是可取的简便方法。 2 工作的费用率是网络计划工期成本优化的关键因素，本文在分析工作资源投入量与 其费用之间关系的基础上，建立了工作正常持续时间及正常费用、临界持续时间及临界费 用的计算模型，给出了工作费用率的确定方法，使工期一成本优化理论更加完善。 3 对带资源约束的工程进度安排问题，通过“优先系数法”和“资源调配法( r s m ) 的应用分析，提出加入“工作最早完成时间”参数，对优先系数计算公式进行了修正，提 高了优化模型的适应性；应用流水作业方法中对项目进行最优排序的“约翰逊贝尔曼 法 则，对新参数的合理性作了进一步的论证。 4 对资源均衡问题中的“缩方差”法优化机理进行了较为深入地分析，针对其繁杂的 处理过程，修正了资源均衡收敛条件；研究实例表明：应用修正后的优化模型，可使资源 均衡优化过程的作图及计算工作量大大减少，提高了寻找最优方案的速度。 5 为了能在有限的计算时间内获得大型网络计划资源均衡优化问题的最优解，尝试减 少网络计划中大量非关键工作的许多可能开工时间所形成的组合，分析了利用“非关键工 作组 进行资源均衡优化的可行性，并给出了优化方法，它可使大型工程网络计划的资源 均衡优化工作变得简便而可行。 6 为了更加合理地解决网络计划的综合优化问题，以系统综合评价方法为基础，重点 对网络计划综合优化指标设置问题进行了研究。通过对工期、成本、质量三者之间关系的 分析，提出了在网络计划综合优化中，应按质量优先的原则，将质量指标作为约束条件， 把综合优化指标确定为工期、成本和资源；为了使综合优化方法更具实用性、可操作性和 易接受性，本文认为应以单目标优化方法为基础研究提出简便、易行的综合优化方法。 关键词：网络计划，工作，工作持续时间，费用率，工期，成本，资源，资源需要量， 质量，优化 a b s t r a c t 、t h em a n a g e m e n to fh i g h w a yp r o j e c t si sah o ta n dav i t a li s s u e i nt h ed i s c i p l m e so f m a n a g e r i a le c o n o m i c sa n da r c h i t e c t u r a le c o n o m i c s ，t h ep r o j e c ts c h e d u l em a n a g e m e n tb e l n g a n i m p o r t a n ta s p e c t a sas c i e n t i f i ca p p r o a c h o fp l a n n i n gm a n a g e m e n td e r i v e df r o mm o d e m m a n a g e m e n t ，n e t w o r kp l a n n i n gt e c h n o l o g y s e r v e sa sa ne f f e c t i v et o o li nt h ep r o j e c ts c h e d u l e m a n a g e m e n t i nl i g h to f t h ep r e s e n tr e s e a r c hh o m ea n da b r o a da n dt h ee x i s t i n gp r o b l e m s ，t h l s p a p e rs t u d i e ss u c hi s s u e sa st h ec a l c u l a t i n gm e t h o do f d u r a t i o ni nt h ep l a no fh i g h w a yp r o j e c t s ， n e t w o r kp l a n n i n gp r o j e c td u r a t i o n c o s ta n dr e s o u r c eo p t i m i z a t i o nf r o mt h ep e r s p e c t i v e so f e c o n o m i cp r i n c i p i e ，p e r f o r m a n c eo r g a n i z i n gp r i n c i p l ea n ds y s t e m i ca n a l y z i n g m e t h o d t h ep a p e r c o v e r ss u c hr e s e a r c h e sa n da c h i e v e m e n t sa sf o l l o w s ： 1 t h r o u g ha n a l y z i n gt h ee x i s t i n gc a l c u l a t i n gm e t h o d o fd u r a t i o n ，b ya p p l y i n gt h et h e o r yo f m a r 画n a lu t i l i t yp r o g r e s s i v ed e c r e a s er u l e ，t h ea u t h o rs t u d i e st h en o n l i n e a rr e l a t i o nb e t w e e nt h e i n v e s t e dq u a n t i t yo fr e s o u r c e sa n do u t p u ta n dr e c t i f i e st h ec a l c u l a t i n gm a t r i xo f d u r a t i o no ft h e a s s u r e da c t i v i t v ac a s es t u d yi so f f e r e dt ot e s t i f yt h eo p e r a t i b i l i t ya n dp r a c t i b i l i t yo f t h en e w m a t r i x ，w h i c hs h o w st h a tt h em a t r i xi sa ne a s ym e t h o di na n a l y z i n g d u r m i o n 2 c o s ts l o p ei st h ek e yf a c t o ri no p t i m i z i n go f t h ep r o j e c td u r a t i o n c o s to f n e t w o r kp l a n n i n g o nt h eb a s i so ft h ea n a l y s i so ft h er e l a t i o nb e t w e e ni n v e s t e dq u a n t i t yo f r e s o u r c e sa n dc o s t ，t h i s p a p e re s t a b l i s h e st h ec a l c u l a t i n gm a t r i xo fn o r m a ld u r a t i o n & n o r m a lc o s t ，c r i t i c a l d u r a t i o n & c r i t i c a lc o s t a n dp o s i t st h em e t h o do fc o s ts l o p e ，t h u sp e r f e c t i n gt h eo p t i m a lt h e o r yo fp r o j e c t d u r a t i o n - c o s t 3 b yc o n t r a s t i n gp r i o r i t yc o e f f i c i e n tm e t h o da n dr s m , t h i sp a p e r r e c t i f i e st h ec a l c u l a t i n g m a t r i xo fp r i o r i t yc o e f f i c i e n t ，i m p r o v i n gt h ea d a p t a b i l i t y o ft h eo p t i m a lm a t r i x ；b ya p p j y i n g j o l u l s o n - b e l l m a nr u l eo ft h ec o n v e y o rs y s t e m ，t h er a t i o n a l i t yo ft h en e wp a r a m e t e r 1 sf u n h e r d e m o n s t r a t e d 4 t h i sp a p e ra n a l y s e sp r o f o u n d l yt h eo p t i m a lm e c h a n i s m o ft h er e d u c e dv a r i a n c em e t h o do t t h er e s o u r c ee q u i l i b r i u m ，r e v i s e st h ec o n s t f i n g e n c yc o n d i t i o n so ft h er e s o u r c ee q u i l i b r i u m t h e c a s es t u d yg i v e ns h o w st h er e v i s e do p t i m a lm a t r i xc a nd i m i n i s hg r e a t l yt h ec h a r t i n ga n d c a l c u l a t i n ga m o u n ti nt h ep r o c e s so fr e s o u r c eb a l a n c i n ga n do p t i m i z i n ga n d a c c e l e r a t et h es p e e d o ff i n d i n gt h eo p t i m a ls c h e m e 5 1 no r d e rt ob a l a n c ea n do p t i m i z et h er e s o u r c e so fl a r g e s c a l en e t w o r kp l a n n i n g 1 1 1t h e l i m i t e ds p a no ft i m ea n dd e c r e a s et h ei n t e g r a t i o no fv a r i e d s t a r tt i m eo fl o t so fn o n - c r i t i c a l a c t i v i t ys t e p si nn e t w o r kp l a n n i n g ，t h i sp a p e ra n a l y s e st h ef e a s i b i l i t yo f b a l a n c i n ga n do p t i m i z i n g r e s o u r c e sb yu t i l i z i n g “n o n c r i t i c a la c t i v i t yu n i t ”a n do f f e r s t h ea p p r o a c h e so fo p t i m i z a t i o n , m a k i n gt h ee q u i l i b r i u ma n do p t i m i z a t i o no f r e s o u r c e si nl a r g e - s c a l en e t w o r k p l a n n i n gs i m p l ea n d f e a s i b l e 6 f o rt h ep u r p o s eo fs o l v i n gt h ei s s u eo fs y n t h e s i z e do p t i m i z a t i o no fn e t w o r kp l a n n i n g ，t h i s p a p e rs t u d i e st h ed e s i g n a t i o no fo p t i m i z a t i o ni n d e xo fn e t w o r kp l a n n i n go nt h eb a s i so ft h e m e t h o d o l o g yo fs y s t e m a t i ca p p r a i s e m e n t t h i sp a p e ra n a l y s e st h er e l a t i o n s h i pa m o n gp r o j e c t d u r a t i o n ，c o s ta n dq u a l i t y , p u t sf o r w a r dt h ep r i n c i p l eo f “q u a l i t yf i r s t i nt h en e t w o r kp l a n n i n g o p t i m i z a t i o n , a n dp r e s c r i b e st h es y n t h e s i z e do p t i m i z a t i o ni n d e x - - p r o j e c td u r a t i o n ，c o s t r e s o u r c e s i na na t t e m p tt om a k et h es y n t h e s i z e do p t i m i z a t i o na p p r o a c hp r a g m a t i c ，m a n e u v e r a b l e a n df l e x i b l e ，t h ea u t h o rh o l d st h a ti ts h a l lb es i m p l ea n df e a s i b l eo nt h eg r o u n do ft h ep r i m a r y s t u d yo fs i n g l e - g o a lo p t i m i z a t i o nm e t h o d k e yw o r d s ：n e t w o r kp l a n n i n g ，a c t i v i t y , d u r a t i o n ，c o s ts l o p e ，p r o j e c td u r a t i o n ，c o s t ，r e s o u r c e ， r e s o u r c er e q u i r e m e n t ，q u a l i t y , o p t i m i z a t i o n 论文独创性声明 本人声明：本人所呈交的学位论文是在导师的指导下，独立进行研 究工作所取得的成果。除论文中已经注明引用的内容外，对论文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本论文 中不包含任何未加明确注明的其他个人或集体已经公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：炳己晚啊年午月f ) 日 论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属学校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请 专利等权利。本人离校后发表或使用学位论文或与该论文直接相关的 学术论文或成果时，署名单位仍然为长安大学。 ( 保密的论文在解密后应遵守此规定) 论文作者签名 导师签名： 词年午月，日 年月 日 长安大学博士学位论文 第一章绪论 1 1 研究目的及意义 任何项目管理都是从制订项目计划开始。项目计划是有效协调项目工作、推动项目 工作顺利进行的最重要的工具。 项目计划是项目组织根据项目目标的规定，对项目实施工作进行的各项活动作出周 密安排。项目计划围绕项目目标的完成系统地确定项目的任务、安排任务进度、编制完 成任务所需的资源预算等，从而保证项目能够在合理的工期内，用尽可能低的成本和尽 可能高的质量完成。 网络计划技术是现代管理科学总结出的一种科学的计划管理方法，是项目管理的一 种有效工具。它可用来解决工程技术和管理工作中的许多问题，已被广泛地应用于编制 各种计划。在项目管理中主要用来编制工程施工进度计划，其方法主要有关键线路法( 简 称c p m ) 和计划评审法( 简称p e r t ) i2 。后来还陆续提出了一些新的网络技术，如图示 评审技术( 简称g e r t ) ，风险评审技术( 简称v e l 玎) 等。总体思路是以缩短工期、 提高效率、节省劳力、降低成本消耗为最终目标，通过较为形象的网络图来表达项目中 各项工作的进度和它们之间的相互关系，并在此基础上进行网络分析，计算网络中各项 时间参数，确定关键工作和关键线路，利用时差不断地调整与优化网络，以求得最短工 期。然后，还可将成本与资源等问题考虑进去，以求得综合优化的项目计划方案。 网络计划技术是上世纪5 0 年代后期出现的计划方法。随着科学技术和生产的迅速 发展，出现了许多庞大而复杂的科研和工程项目，它们工序繁多，协作面广，常常需要 动用大量人力、物力和财力。因此，如何合理而有效地把它们组织起来，使之相互协调， 在有限资源下，以最短的时间和最低费用，最好地完成整个项目，就成为一个突出的问 题。网络计划技术就是在这种背景下出现的，最初是作为大规模开发研究项目的计划、 管理方法而被开发出来，但由于网络计划方法具有广泛的适用性，特别对复杂的大型项 目更显示出它的优越性。因此，它是现代项目管理中被人们普遍采用的计划方法。在公 路工程项目施工计划的编制与优化过程中，网络计划技术也得到了广泛的应用。 网络计划的实施，需要各种条件的支持。一个工期符合要求、资源需求均衡、费用 合理的计划方案，是在对网络计划进行优化后实现的。所谓优化，就是通过利用时差不 断改善和调整网络计划的初始方案，在满足规定条件的情况下，按某一衡量标准求解最 优方案的问题。根据所寻求的目标不同，有着各种各样的优化理论、方法和途径。此外， 第一章绪论 优化的理论和方法也在不断发展，寻找一种简捷、可靠的优化技术是十分必要的，是众 多学者的研究目标。 由网络计划技术的进化和发展可以看出，随着各种方法的提出，计算的结果越来越 精确了，但是方法的复杂性也增加了，这似乎是一对不可调和的矛盾。这种研究进展也 多亏计算技术和计算机工具( 软、硬件) 的发展，使得计算的速度和精度大大提高。虽然 较高精确度的算法，可靠性也较高，但是从理论上和数值计算的观点看，复杂性却大大 增加了。因此，文献中的许多复杂方法并不适合支持基于不确定信息项目计划的频繁的 动态变更和控制，因而在实际中很少被采用。k i d d 作了一份对于网络计划方法 ( c p m ，p e r t ，v e r t 和g e r t ) 使用方便性的调查。报告指出，虽然人们对v e r t 和g e r t 方法 已经研究了许多年，但是目前的项目管理网络计划方法仍然用方便快捷的c p m 和p e r t 算法。而v e r t 和g e r t 则由于计算量大、计算繁杂、耗时长而没有被使用i l o a l l 。 关键线路法( c p m ) 以进度计划技术为主，历经半个世纪的发展，己经形成一套较 完整的进度管理方法。近期其发展集中于在原来的思想观念内对计划技术和算法的丰 富，国内外学者做了大量研究工作，提出了各种项目进度管理方法，但在理论和数值计 算方面，方法复杂性大大增加，可操作性和易接受性不够。由于计算量大、计算繁杂、 耗时长而导致计算成本较高；同时方法过于复杂，在现实企业的管理层中很难理解和操 作，难以得到应用。 因此，本文将结合生产理论、流水作业法、系统分析方法等，重点对以c p m 为基础 的项目网络计划方法进行研究，试图寻找一套简捷、可靠的计划编制及优化方法。 1 2 国内外研究现状及发展动态 近年来，国内外有关网络计划的研究主要分为两类：一是有关工作持续时间的估算 方法；二是网络计划最优方案的评价。 工作活动持续时间的确定是一个复杂、涉及面十分广泛的问题。影响持续时间的最 基本因素是工程量、资源投入和劳动生产率等。项目在实施过程中，还经常会遇到各种 突发事件，导致各项工作的作业持续时间的不确定性，因此，如何更真实地反应作业活 动时间、消除不确定因素的影响成为最近研究的热点。 一个计划方案，是由工期、成本、资源消耗、质量等多种经济技术指标构成的。 实现各指标的综合优化，从理论上分析可以采用数学规划的方法建立模型并求解。而在 实际工作中，在工程项目较大或资源种类较多时，由于出现了它们难以逾越的“维数障 碍”，而较多地采用近似的，逐次逼近的方法，即对一些较大规模的网络采用搜索性程 2 长安大学博士学位论文 序来解决诸如缩短工期、均衡资源、降低成本等优化问题。在公路施工网络计划优化中， 一般来说可以把问题分为三类：工期一成本优化，资源有限一工期最短优化以及工期固定一 资源均衡优化。 工期成本优化，即在工程工期和工程成本之间寻求一种均衡，使得在一定工期下 的成本最低，或者在成本最低的情况下使得工期最短，从而使两者之间达到最优的组合。 工期一资源优化，是在工期和资源之间寻求相互协调和相互适应。针对没有资源 限制的项目，是在工期一定的条件下寻求资源消耗的均衡；然而现实中经常会发生项目 之间或项目内部相互影响、争夺资源等现象，因此在资源有限的情况下，如何协调各个 项目所需的资源，成为目前热衷研究的问题。 到目前为止，国内外学者进行了大量的研究和探索，采用各种不同的方法和手段来 解决上述问题。 1 2 1 工期一成本优化问题研究进展 在工程管理领域，工期一成本优化问题的研究始终是一项重要课题。通常，解决该 问题的方法主要是数学规划方法和启发式算法。 数学规划方法包括线性规划方法和动态规划方法1 1 4 - 1 7 l 。但该方法在实际应用中计算 工作量大，仅适合工序不多的中小型网络计划1 1 8 l 。 启发式算法1 1 9 2 0 1 只能提供较好解，并不保证求出最优解，但应用启发式方法求解的 大量问题却都得出了最优解。由于网络的线路数目随着网络工作数目的增加急剧增加， 因此对大型网络利用这种方法是不现实的1 1 2 l 。 工期成本的优化，是人们比较感兴趣的，它的经济效益也是显而易见的。目前的另 一个问题是基础资料的取得，即在上述各种优化模型中，对于工作费用率的确定，均没 有明确具体的计算模型。 我们知道，不同工程( 即使是同一标准设计) 的施工，由于自然条件和社会经济条 件的变化，施工单位的技术与管理水平，施工力量的不同投入，施工方法与施工机械选 用的差异，供应条件的影响等等，同一工作的施工持续时间和费用率是不会完全相同的。 这样，就不得不针对不同工程分别计算它们的每项工作的费用率( 很难找到一套通用数 据) 。这是一项极为繁重的工作，而且这项工作还只能靠手工进行，各种项目管理软件 尽管可以迅速地完成整个优化过程，但对此却是无能为力的。这就从根本上妨碍了工期 一成本优化的实际应用i 们。 针对这一情况，文献 2 1 凭经验将工作的持续时间与直接费用关系假定成二次函数 3 第一章绪论 模型，然后应用机器学习的方法并结合大量已有的相似工程的实例归纳出具体的曲线参 数，再利用遗传算法对该问题进行求解。文献 1 3 也假定工作的持续时间与直接费用关 系呈二次函数，即：c j = a i t ；+ b i t i + k i ，因而确定该函数的关键是确定系数a j 、b i 和k i 的大小，其确定系数数值的方法是：对同一工作选取大量的相似工程实例作为样本数据， 然后应用二次回归方法对这些数据进行处理，回归出具体的系数值，作为工作持续时间 和直接费用真实关系的反映。但这种方法假定工作的持续时间与直接费用呈二次函数关 系，没有理论和实际依据，且回归出的系数值的可靠性受所取实例的影响较大。 为此，本文将根据经济学中的生产理论研究工作持续时间与其直接费用之间的关 系。 1 2 2 工期一资源优化问题研究进展 网络计划资源优化是项目管理理论发展的重要内容，是项目管理的核心问题之一， 是工程项目进度管理的重要组成部分。计划和控制好资源的使用情况，是保证工程建设 如期顺利完成的重要手段，也是项目管理成败的关键之一。对资源进行优化配置是保证 资源合理使用的重要手段，在工程建设过程中显得尤其重要。 项目管理的一个重要特征是在限定的资源( 人力、物力、财力) 条件下，尽可能确 保按期完工。一般来说，由于资源供应的限制，往往使某些工作不可能同时进行，其中 有的工作要推迟进行。当某一工作的开始时间向后推迟时，如果超过该工作总时差的范 围，则会使整个项目延期，因此在进行资源合理安排时，应分析究竟推迟哪项工作才能 不拖延或少拖延工期，且尽量使项目实施各阶段的资源需要量均衡，这就是工期与资源 平衡问题。 一、“资源有限一工期最短问题 很多项目在实施的过程中，都会受到资源约束条件的制约，通常出现的情况就是某 时间段内能提供的最大资源供应量要低于该时间段内各个展开工作所需要的资源量的 总和。这样就必须通过推迟展开一些工作，使得资源的使用情况得到满足，直接导致的 结果就是总工期可能受到延误。“资源有限，工期最短 问题也称为“带资源约束的工 程进度安排问题 ( 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 g ) ，是项目工作受到资源约 束，而每项工作只有一种完成方法，且工作开始后就不能中断。优化的目标是，合理地 安排被推迟的工作顺序，使得总工期受到延误的程度最小。 资源有限网络计划优化问题是目前讨论得比较多的一个热点问题，从理论上说它是 一种组合优化问题，最优可行解的多解性是组合优化的特点之一，即所提供的可行解集 4 长安大学博j ：学位论文 极其浩大。解决此类问题主要有两个派系，一是以经验加理性判断为主的启发式方法( 或 称为探索法) ，另一是以数学模型为主的解析方法( 或称为最优化方法) 1 2 7 l 。 在当前的实际应用中，启发式搜索方法被广泛应用，这种方法容易理解和应用， 在计算编程上也很方便，对处理实际的工程实例很有效。同时，在当前的关于这个优化 问题的软件大部分是基于启发式搜索来进行开发的。 1 解析方法 以线性规划、0 - 1 规划1 2 8 , 2 9 1 和整数规划1 3 0 3 1 i 等为代表的最优化解析方法的应用起始 于上世纪6 0 年代末。虽然解析方法可以求得问题的最优解，但在工程项目大、资源种 类多时，就出现了它们难以逾越的“维数障碍”1 2 7 1 。因此这些解析方法在该类问题的求 解空间相当小，只能求解小型问题。 2 启发式方法 由于在理论上和实践中，用解析法来求解这类问题非常复杂，人们提出了大量的启 发式优化方法，它以c p m 为基础，运用各种准则、经验、技巧，对工作按一定的规则 进行处理，其着眼点不在数学意义上的最优解，而是在一定范围内满足时间需要的满意 解。一般可求得任何规模的工程项目的虽非最优但却可行的进度安排方案。该方法在求 解有资源约束的大型网络计划问题时，显示出了巨大的优越性，它的最大特点是计算简 单、可操作性强。目前己有数种启发式准则和相应算法，按其求解问题的计算顺序和优 先准则，可以划分为两大类：并行法( p a r a l l e l ) 和序列法( s e r i a l ) 。并行法根据时间 区段来安排工作。将某一时间段内的所有工作按照一定的规则排序，形成一个工作序列， 以资源可用量为前提安排，分配不上资源的工作被推迟到下一个时间段；当序列中的所 有工作已被考虑后，时间将推进到下一个时间区段。序列法首先将所有工作按优先顺序 排队，然后按给定序列制订计划；如因缺乏资源不能安排某一工作时，那就必须等到其 它工作完成后再进行安排；当所有工作被列入计划后，计算结束。 以上两类启发式方法的关键问题是如何选择排队准则。通常这些准则是基于网络时 间的分析值，如最小时差准则、最小最迟开始时间准则、最小最早完成时间准则、最小 最迟完成时间准则、最小持续时间准则、最大持续时间准则、最大资源需求准则等1 2 7 2 9 i 。 显然，以时间为主导的准则把注意力仅仅放在时间上，忽略了资源需求量及网络复杂程 度可能对工期的影响；而以资源为主要考虑对象的准则却淡化了关键工作、网络构成参 数等对工期的作用。可以想象得到，有许多研究者在探讨如何选择“好 的准则。文献 1 2 7 、1 3 4 l 、【3 8 1 、1 3 9 1 、【4 0 l 、1 4 l j 、1 4 2 l 、1 4 3 1 分别综合考虑了各项工作的持续时间、 5 第一章绪论 资源需要量、总时差、工作的紧后工作数、不考虑资源约束时工作的紧后线路的最大长 度以及网络计划未考虑资源约束时的总工期、计划中某种资源的单位时间供应量、网络 中工作的总数目等因素，给出了确定各项工作先后顺序的“优先安排准则”及计算“优 先系数”的数学模型，比较全面地反映了网络参数和资源对工程工期的影响。但“资源 有限，工期最短”问题涉及因素众多，这些准则及其计算模型不是对所有问题都能表现 良好。 本文将结合解决这类问题的另一较好方法一资源调配法( r s m ) ，给出一个修正的 优先系数模型，以便更合理地确定各项工作的先后顺序。 二、“工期固定一资源均衡”问题 “工期固定，资源均衡 问题是指在工期一定的情况下，使项目完成过程所需的资 源水平趋于均匀。所要达到的目标就是工程施工过程中资源的利用能够尽量保持均衡， 避免出现频繁、严重的高峰或低谷现象，从而减少现场各种临时设施的规模，最大限度 地节约施工费用等。优化的原理就是在活动总时差范围内，调整非关键活动的实际开始 时间，达到资源分配动态曲线的高峰尽可能降低，资源的使用情况尽可能的趋于均衡的 目的。和“资源有限，工期最短”问题一样，该类问题从产生发展至今，也经历了由解 析法到启发式算法的过程。这类问题是目前讨论得比较多的一个热点问题，提出的解决 方法也很多。 1 解析方法 资源均衡的方法很多，但各个方法的使用和影响范围各不相同。该问题在最初阶段， 主要是借鉴统筹规划的原理，结合网络计划技术和数学规划，针对不同的问题建立精确 的数学模型，然后采用合适的优化方法进行求解。采用得比较多的有整数规划、枚举法、 分支定界等数学解析方法1 4 4 - 4 7 i 。 “工期固定，资源均衡”问题在理论上也是属于组合优化问题，具有计算复杂度随 着计算规模呈指数增长的特点。解析方法侧重于从理论上阐明问题，通过严密的数学方 法和推理建立切合实际的数学模型，然后用数学方法进行求解，因此该方法比较容易出 现无解的情况。并且由于网络计划本身的复杂性，对于各种不同类型的问题，无法建立 一个完全公认统一的数学模型，因此解析方法的可移植性和通用性比较差。 2 启发式方法 鉴于解析法的局限性，人们开始着眼于启发式算法的研究。其思想就是在保持工期 不变的前提下，尽量减小资源柱状图绕坐标轴的力矩，哪些非关键工作在时差允许的范 6 长安人学博：仁学位论文 围内使力矩减小的最大，哪些工作最先移动。其实现的方法是根据经验预先设计好探索 准则，设定一定的判定方法，迅速有效地接近最优目标。该方法还编制了专门的软件。 目前运用比较多的启发式算法有削高峰法、缩方差法等。缩方差法是利用时差来调整非 关键工作的开始与结束时间以缩小资源需要量的方差，从而使资源的需要量趋向均衡。 在优化过程中，按照现行的优化收敛条件计算公式进行，过程十分繁琐。另外，它是基 于单一非关键工作的逐步调整，其优化的依据是所有非关键工作能够在它们的最早和最 迟开工时间之间的任何时间开始，这样由于各非关键工作的不同开始时间，构成网络计 划的各工作的许多组合，优化的过程就是检查全部组合，找出资源需要量方差值最小的 那个组合为较优解。但对大型工程项目来说，网络计划的工作将会很多，为了得到资源 均衡问题的较优解，必须研究大量的非关键工作不同开工时间的组合，要在有限的计算 时间内获得大型网络计划的资源均衡动态图，即使利用计算机也变得不可行。 本文将对资源均衡收敛条件进行修正，同时利用非关键工作组的概念，提高寻找最 优方案的速度。 三、智能仿生类算法在资源优化方面的研究现状 近代科学技术发展的显著特点之一就是生命科学与工程科学的相互交叉，相互渗透 和相互促进。以遗传算法、人工神经网络、d n a 分子算法、蚂蚁算法、鸟群算法( 微粒 群算法) 、鱼群算法为代表的智能仿生类算法主要是模拟生物进化和生物群体的智能化 方法，它们的蓬勃发展和广泛的应用正体现了科学发展的这一特征和趋势。智能仿生类 算法具有良好的并行性、随机性、自适应性、鲁棒性，并且在非线性复杂问题的求解方 面表现出了独特的优势，尤其是求解组合优化等问题更是取得了成功。借鉴智能仿生类 算法在其它领域的成功经验，将它们引入到网络资源优化问题中来，对于网络资源优化 问题来说具有极其重要的意义m j 。 1 遗传算法 遗传算法是智能仿生类算法的最早代表，是继启发式算法之后又一类求解组合优 化u 口- j 题的新方法。对于“资源有限，工期最短 优化问题，文献 4 8 1 提出了一个模拟模 型，作为评价函数，把计划的启发式准则线性地组合在一起，并使用模拟模型来评价它 们的组合效果，然后用遗传算法更好地选择下一个较好的启发式准则的线性组合；文献 【4 9 1 通过构造拟交叉和突变基因的线性组合，设计了改进过的遗传算法，成功地运用到 资源有限的优化中：文献l s o l 提出了另一种改进的遗传算法，把活动分为不同的执行模 式，对活动实施不同的资源配置方式，从而产生不同的工期，用启发式方法结合遗传算 7 第一章绪论 法搜索符合条件的最优工期；文献1 5 1 1 提出了资源限制条件下一种自适应遗传算法，在 算法的基因编码中，保留一位基因变量来判断是选择序列启发式还是选择平行启发式， 具有一定的智能性。 对于“工期固定，资源均衡”优化问题，文献1 5 4 1 首先将基于二进制编码的遗传算 法运用到网络资源优化的资源均衡问题中；文献 5 5 1 设计了带修复算子的遗传算法，结 合一个具有4 3 项工作的资源均衡问题算例，取得了良好的效果；文献1 5 6 1 针对二进制 编码过长的问题，提出了基于实数编码的遗传算法，运用到单一资源的均衡问题中；文 献 5 7 1 对遗传算法的评价函数做出改进，采用凝聚函数作为资源均衡问题的评价函数， 并且提出从“资源占用峰值区”往两侧强制修复操作数的优化方法；文献 5 8 1 将多种资 源的消耗数量进行数字化，以获得多种资源数字的合成分布，在此基础上结合遗传算法， 研究了网络资源优化中多资源的均衡问题；文献 2 2 1 提出多种群划分与聚类的资源均衡 优化过程，提高了算法的全局寻优能力。 2 蚁群算法 蚁群算法( a n tc o l o n yo p t i m i z a t i o n ) 诞生于2 0 世纪9 0 年代初期，是由意大利学者 m d o r i g o 最早提出的一种新的模拟进化算法。对于“资源有限，工期最短 问题，文 献1 5 5 1 采用蚁群算法对该问题做了详细的论述；文献 6 5 1 等提出了一种改进的蚁群算法 用于求解基于一般优先关系的工期最短问题，文中提出了一种具有回溯功能的蚂蚁，并 且在方法中加入了一些启发式的信息，取得了不错的效果。对于资源优化中的均衡问题， 文献1 6 6 1 采用了遗传算法和蚂蚁算法混合的方法，求解了一个4 3 项工作的算例，取得 了比较好的结果和收敛效率。由于目前蚂蚁算法仍处在理论研究中，关于它应用方面的 文章还比较少。 通常来说，智能仿生类算法的寻优过程就是不断保留历史最佳适应值的过程，尽管 在理论上已经证明了算法可以全局收敛，但是在现行的计算能力和条件下需要花费相当 长的时间，这也是目前各种智能仿生类算法急需解决的问题之一，目前许多研究者通过 各种改进方法来改善算法的进化速度和收敛时间。在实际运用中，通常采取另外种策 略，就是保存当前最优个体值，这样在规定的进化代数下，就能够以概率1 找到全局最 优解，这是目前众多智能仿生算法所采用的近似收敛策略。具体做法是在程序运行前， 设置一个最大进化代数g ，使得程序运行g 代后自动终止，把当前找到的最优解作为 全局最优解i 3 6 i 。 8 长安人学博士学位论文 1 2 3 网络计划的综合优化 工程网络计划综合优化，就是使计划方案的工期、成本、资源等多个目标同时达到 最优，即寻找工期最佳、成本最低、资源配置最合理的方案。为此，众多学者在优化目 标的选择、优化模型的建立和求解等方面作了大量的研究工作。文献【9 1 ，9 2 】是考虑工 期、成本、质量目标的优化模型，其中对质量目标，是假定工作的完成质量与工作持续 时间成线性关系，用工作的正常时间和临界时间对质量指标进行量化处理，其中文献 9 2 1 用模糊决策方法求解找出最优方案；文献1 9 3 1 是考虑工期、质量、成本、资源目标的优 化模型，对质量目标用工作持续时间进行量化，先进行工期成本优化，再进行资源均衡 优化；文献【8 l ，9 4 ，9 5 】是考虑工期、成本、资源目标的优化模型，优化分两个阶段进 行：阶段一是考虑工期成本优化和资源的限制，阶段二在阶段一的基础上进行资源均衡 优化，其中文献1 8 1 1 用协调度模型求解最优方案，文献 9 5 1 是用遗传算法进行求解。 从对以往综合优化方法研究成果的分析中可知，对质量目标的量化采用工作时间 质量线性模型的理论依据不充分。本文将对网络计划综合优化指标设置问题进行研究。 1 3 主要研究内容与方法 网络计划以网络图为分析基础，网络图最本质的优点是能直观地反映工作项目之间 的相互关系，使一项计划构成一个系统的整体，从而为实现对计划的定量分析奠定基础。 本文的主要研究内容与方法如下： 1 总结前人在网络计划理论及应用方面的研究成果，提出主要研究目标：对以c p m 为基础的项目网络计划方法进行研究，寻找一套简捷、可操作和易接受的计划编制及优 化方法。 2 通过对现行工作持续时间计算方法的分析，应用经济学中的边际收益递减规律， 研究工作投入资源量与其产量之间的非线性关系；对确定型工作的持续时间计算模型进 行修正：并通过实例对新模型的可操作性和实用性进行分析验证。 3 通过对工程工期一成本优化原理的分析，针对现行优化模型中，工作费用率没有 明确具体的计算公式的情况，分析工作资源投入量与工作直接费之间的关系，建立工作 正常作业时间及正常费用、临界作业时间及临界费用的计算模型，给出网络计划工期成 本优化中的关键因素- - i 作费用率的确定方法。 4 对资源有限一工期最短优化问题，通过研究示例，对“优先系数法 和“资源调 配法( r s m ) 进行对比分析，尝试将流水作业法中对项目进行最优排序的“约翰逊- 贝 尔曼 法则，应用于发生资源冲突的工作的排序问题中，对优先系数计算公式进行改进， 9 第一章绪论 以提高优化模型的适应性。 5 对工期固定资源均衡优化问题，重点对“缩方差”法优化过程机理进行深入分 析，针对其繁杂的处理过程，提出简单明了的优化方法，对资源均衡收敛条件( 即工作 右移判断公式) 进行修正，并通过研究示例对修正公式的可行性进行验证。 6 在现行的资源均衡优化模型中，优化过程均是检查各非关键工作的不同开始时间 构成的全部组合，找出资源需要量方差值最小的组合为较优解，但是，要在有限的计算 时间内获得大型网络计划的资源均衡动态图，即使利用计算机也变得不可行。因此，尝 试减少网络计划中大量非关键工作的许多可能开工时间所形成的组合，将变得十分必 要。本文将分析利用“非关键工作组 进行优化的可行性，对网络计划资源均衡优化问 题作进一步的研究，以便使大型工程网络计划的资源均衡优化工作变得简便可行。 7 为了更合理地解决网络计划的综合优化问题，以系统综合评价方法为基础，重点 对网络计划综合优化指标设置问题进行研究；考虑到各个工程项目的控制重点不同，例 如，在有些情况下，为了控制工程成本的超支，工程成本最小化是工程项目的主要任务； 而在有些情况下可能是重点解决在质量和成本约束下的工期优化问题。为了使综合优化 方法更具实用性、可操作性和易接受性，本文将以单目标优化方法为基础来研究简便、 易行的综合优化方法。 1 0 长安大学博：l ：学位论文 第二章工作持续时间计算方法研究 本章将通过对现行工作持续时间计算方法的分析，根据经济学中的边际收益递减规 律，研究工作投入资源量与产量之间的非线性关系，对确定型工作的持续时间计算模型 进行修正。 2 1现行工作持续时间计算方法分析 工作是指计划任务按需要粗细程度划分而成的、消耗时间和( 或) 资源的一个子项 目或子任务。即它既可以是一项简单的工序操作，也可以是一个复杂的施工过程或一个 工程项目。 工作持续时间是一项工作从施工开始到完成所需的作业时间，也就