（计算机应用技术专业论文）电力工程中网络计划优化的研究.pdf

华北电力大学硕士学位论文摘要 摘要 网络计划技术是一门兼有技术性和工程性的新兴学科。随着网络计划技术的不 断推广，其理论的不断成熟，越来越多的优化算法应用于工程项目的网络计划范畴 中来。本文分析和比较了网络计划中的优化算法，特别讨论了粒子群算法，并对其 改进形成了基于速度松弛策略的模拟退火粒子群算法( r s a p s o ) 。对资源，工期， 费用，质量等多方面进行研究后，建立了资源均衡模型和多目标优化模型，并引入 改进后的粒子群算法进行求解。实验证明，r s a p s o 算法和多目标优化的数学模型在 电力工程的网络计划中有很大的应用价值。 关键词：网络计划技术，粒子群算法，资源均衡，多目标优化 a b s t r a ct t h en e t w o r kp l a n n i i l g 妣h n o l o g yi sat e c i l l l i c a la n dm ep 删e c t 锄e r g i l l gd i s c i p l i i l e w i mm e d e v e l o p m e l l to ft h en e 铆o r kp l 锄i n gt e c h e i l o l o g ya i l dm em 跳j r i t yo ft l l et h e o m o r ea i l d m o r ea l g o r i t h m sh a v eb e e i la p p l i e di l ln e 咐o r kp l a n n i n g 矗e l do fp r o j e c tm 锄a g e m e n t t l l i s p 印e ra n a l y s e s 趾dc o m p a r e sa 1 9 0 r i t l l l n sa p p l i e di nn e t 、o r kp l 砒u l i n 岛m o s t l yd i s c 惦s e sm e p a r t i c l es w 锄o p t i m i z a t i o na l g o r i m m ，a n dm a d et h ei i i l p r o v e m 髓tt om ep s oa i g o r i t b mt 0f o m r s a p s o ( p 枷c l es w a mo p t i i n 也a t i o n 觚ds i i l l u l a t e da 妯e a l i n gb 硒e do nm es 似e g yo f r e l a ) 【a t i o n - v c l o c i 妒u p d a t e b a u s e do nm es ”t h e t i cs t u d yo fc o s t i l l g ，q u a l i 坝 s u i t a b l e r e s o u r c ea r r 锄g e i l l 朗t 锄dc o n s 觚l c t i o np 嘶o d ，h a se s t a b l i s h e dn l eu i l l i i i l i t e d1 e v e l i n g0 p t 沛a l a i l dt l l em u l t i o b j e c t i v eo p t i m a lm a d l e m a t i c a lm o d e l ，i n 仃0 d u ci i i l p r o v e dp s oa 1 9 0 r i t t 0s o l v e a b o v em a l e m a l i c a lm o d e l 1 t 圮e x p e r i m 即tp r 0 v e dt h a t ，也er s a p s oa l g 硪m m 觚da b 0 州n 饥t i o n e d m a m 锄a t i c a lm o d e l sh a v ev e r y b i ga p p l i c a t i 砌u ei nt h ee l e c t r i cp o w e 叩r o j e c tn e 咐o r kp l 锄 d o n gn a ( c o m p u t e ra p p l i e dt e c h n o l o g y ) d i r e c t e db yp r o f m e n gj i a n l i a n g k e yw o r d s ：n e t w o r k p l a n n i n g ，p a r t i c l es w a r mo p t i i n i z a t i o na l g o r i t h i i l u n u n i i t e d l e v e l i l i g m u l 昏o b j e c 廿v eo p t i m a l 华北电力大学硕士学位论文摘要 摘要 网络计划技术是一门兼有技术性和工程性的新兴学科。随着网络计划技术的不 断推广，其理论的不断成熟，越来越多的优化算法应用于工程项目的网络计划范畴 中来。本文分析和比较了网络计划中的优化算法，特别讨论了粒子群算法，并对其 改进形成了基于速度松弛策略的模拟退火粒子群算法( r s a p s o ) 。对资源，工期， 费用，质量等多方面进行研究后，建立了资源均衡模型和多目标优化模型，并引入 改进后的粒子群算法进行求解。实验证明，r s a p s o 算法和多目标优化的数学模型在 电力工程的网络计划中有很大的应用价值。 关键词：网络计划技术，粒子群算法，资源均衡，多目标优化 a b s t r a ct n en e 柳o r kp l a i l n i i l g 溉1 1 l l o l o g yi sat e c t l l l i c a l 锄dm ep r o j e c t 既唧l gd i s c i p l i i 蟛w i mm e d e v e l o p m e i l to ft h en e 铆o r kp l a i l n i n gt e c h e l l o l o g ) ，a i l dt h em a t u r i t yo ft l l et h e o m o r ea i l d m o r ea l g o r i t h m sh a v eb e e i la p p l i e di l ln e 咐o r kp l a i l n i n g 矗e l do f p r o j e c tm 柚a g e m e n t t h j s p 印e ra n a l y s e s 趾dc o m p a r e sa l g o r i t l l l n sa p p l i e di nn e 卸o r kp l 锄l l i n 岛m o s t l yd i s c 吣s e sm e p 椭c l es w a n no p t i m i z a t i o na l g o r i n ，a n dm a d et h ei m p r o v 锄e n tt ot h ep s oa l g o r i t h mt of o m r s a p s o ( p a n i c l es w a mo p t i i n 娩a t i o na i l ds i i i l u l a t e da n n e a l i n gb 硒e do nt l l es 廿a t e g yo f r e l a ) 【a t i o n - v c l o c i 妒u p d a t e b a u s e d o nm es ”t h e t i c s t u d yo fc o s 曲g ，q u a l i 吼 s u i t a b l e r e s o u 】沁e 龇啪g 锄饥ta i l dc o n s t m c t i o np 击o d ， h 弱e s ta ：b l i s h i 。dt l l eu 】 d i m i t e dl e v e l i n go p t h a l a n d 1 em u l t i o b j e ( ：t i v eo p t i m a lm a d l e n l a t i c a lm o d d ，i n 仃o m l ci l n p r o v e dp s oa l g o 打廿1 mt 0s o l v e a b 0 v em a l e m 撕c a lm o d e l 1 ke x p e r i m 即tp r o v e dt h a t ，也er s a p s oa l g 砸t l 吼锄dd b o v c - i n 饥t i 伽e d m a m e m a t i c a lm o d e l sh a 、，e 、 e r yb i ga p p l i c a t i o n 砌u ei nt h ee l e c t r i cp o w a p r o j e c tn e t w o r ：kp l a n d o n gn a ( c o m p u t e ra p p l i e dt e c h n o l o g y ) d i r e c t e db yp r o f m e n gj i a n l i a n g k e yw o r d s ：n e t w o r kp l a n n i n g ，p a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h i l l u n l i m i t e d i e v e l i l i g m u l 昏o b j e c 廿v eo p t i m a l 声明尸明 本人郑重声明：此处所提交的硕士学位论文电力工程中网络计划优化的研究， 是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研究工作和取得的研究 成果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得华北电力大学或其他教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示了谢意。 学位论文作者签名： 耋望f 日期： 加锣； 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权 保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或 其它复制手段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校 可以学术交流为目的，复制赠送和交换学位论文；同意学校可以用不同方式在不 同媒体上发表、传播学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名： 翩签名础 日 期： 矽胡弓 华北电力大学硕士学位论文 1 1 课题背景 第一章引言 网络计划技术作为一门技术性的、工程性的新兴学科，广泛应用于基建、制造、 修配等各行各业中，国家经委、原电力部更是把它列为四大现代化管理方法之一， 它已经在许多领域发挥了重要作用。网络计划技术是现代电力建设中土建工程使用 得最为广泛的管理技术之一，它以图形的形式将工程进度计划安排的各方面内容直 观地展现在工程技术人员面前，使工程管理者方便且高效地兼顾了工程项目建设的 质量、工期与成本三大目标。网络计划技术的应用价值己远远超过了它诞生时对其 价值的认识，而网络计划技术价值的提高，则必须依赖计算机在其全过程中的应用 【l 】 o 随着网络技术的不断推广，其理论的不断成熟以及计算机技术的不断普及，人 们迫切希望有一些更为有效的理论、知识和方法，能够迅速准确地帮助人们从这些 繁杂的劳动中解放出来，由此相继有许多优化算法应用到网络计划领域中来。但随 着工程项目的复杂化和多元化，它们都或多或少地存在一些不完善的方面和需要改 进的地方；鉴于这种情况，改进和优化网络计划技术算法势在必行。一种现代化管 理方法从产生到全面推广应用要经过各方面的努力，除了其它因素外，它还迫切需 要与计算机技术很好的结合，只有把改进的理论应用于计算机领域，才能更好地应 用计算机技术为项目管理服务，这也正是我们改进算法的基本出发点。 1 2 电力工程管理的现状 电力工业作为基础产业对整个国民经济长期、持续、健康发展起着重要作用。 自建国以来，中国十分重视电力基本建设，在计划经济体制下，国家对基本建设进 行有计划的统筹安排，一般大中型基本建设项目均需由国家计划委员会批准，小型 基本建设项目由国家计委拨给一定的费用，由各部或省、市、自治区政府的计划委 员会批准，即使自筹资金进行基本建设也需由各级计委按规定权限审批。 经济体制改革以来，电力工程建设已由政府拨款改为银行贷款，并在国内外多 方筹集资金，审批项目权限也有所放宽。经济体制的变革，必将导致电力企业经营 思想的改变，从而也会引起电力基建工程管理制度的变革。 电力工业是资金密集型的基础工业，电力基本建设投资规模很大。目前，中国 每年用于电力基本建设的投资达数百亿元，如何筹集、分配和使用好这笔资金，发： 挥其最大的经济效益，是电力基本建设中的重要任务。 1 华北电力大学硕士学位论文 在电力系统各企业体制改革的同时，电力工程的管理也逐步向国际工程管理的 模式靠拢。实行了项目业主责任制、工程招标投标制、工程建设监理制。但是在长 期计划体制的影响下，在企业体制改革还未深入的情况下，电力工程的管理还存在 相当多的问题n 1 。 网络计划技术引入我国已经有几十年的历史了，并且在某些领域中发挥了不可 替代的重要作用。我国在6 0 年代初，首先在航天工程中试用该项技术，并在著名 的数学家华罗庚教授的推动下，把从网络计划技术延伸出的统筹法、优选法应用到 各行各业，取得了明显的经济效果。 在电力工程建设中，主要的生产要素是：人、资金、材料、设备、能源以及相 应的管理方法，只有有效地利用这些生产要素，处理好它们之间错综复杂的关系， 才能加快建设速度，才能带来经济效益；在检修、施工工程过程中，对各个环节合 理调节和控制，进行科学计划的依据，掌握工程建设的主动权，这正是我们引入网 络计划技术，完善网络计划算法来提高电力工程管理水平的目的所在。 1 3 电力工程管理中运用网络计划技术的必要性和现实性 1 3 1 必要性 虽然网络计划技术在我国并没有获得其应有的发展和发挥应有的作用。但随着 社会主义市场经济的深入和企业效益观念的增强，必然会给网络计划技术带来广阔 的发展空间，深入研究网络技术也越来越重要： 1 企业管理水平低仍然是制约企业发展的瓶颈。我国企业管理水平低是勿庸 置疑的共识，科技水平发展越快，这一点就越突出。因此，改变认识上的误区，把 科技和管理放在平等的地位上来对待，向管理要效益已经被越来越多的的企业界人 士所认可。因此，适时重新把网络技术献给企业，改变过去管理粗放，甚至经验管 理的情况有重要意义。 2 资源配置不合理的现象仍然很严重。资源配置优化是每个企业所期望的， 网络计划技术具备这方面的功能，是企业寻求优化资源配置的有效工具。 3 企业系统的开放型增强，需要企业高层领导者能够系统、整体、快速的作 出决策，这可以借助网络计划技术实现。 1 3 2 现实性 社会的进步和经济的发展无时无刻都在为网络技术的发展准备和创造着条件。 一方面，随着改革开发的深入，社会主义市场经济的发展，打破了传统体制的束缚。 2 华北电力人学硕士学位论文 企业呼唤更多的管理技术为其服务。同时，国有企业改革进入攻坚阶段，三年脱困 的压力也促使企业要努力去寻找一些管理技术来解决企业内部存在的问题。另一方 面，随着计算机软硬件技术的发展。网络技术操作复杂的缺陷已经不存在，便捷的 分析工具使网络计划技术向方便、精确、便捷的方向发展，并将深入到越来越广泛 的领域。 1 4 电力工程中引入网络计划的研究目的 随着中国加入w t 0 ，国际间的交流合作日益增多。国际间的合作与交流往往都是 通过具体项目实现的。根据美国项目管理协会( p m i ) 定义，项目是通过一次性的努力， 得到独特的产品或服务。项目受到时间、成本和绩效的约束，项目必须通过积极有 效的管理来实现预定目标。项目管理即是在项目活动中运用知识、技能、工具和技 术来实现项目要求。工程项目的最大特点是“一次性”，工程项目不能重复，不能失 败了重新再来。成功的项目管理者，不管是负责内部项目还是负责客户要求，都必须 运用有效计划技术，为完成一个目标而进行系统的任务安排，从系统的观点来看，计 划管理即有效利用资源。没有有效的计划，任何项目的失败几率将大增。 正因为如此，电力工程项目的管理更具有较强的挑战性，在项目建设的工期、资 源、费用、质量的统筹安排方面，内外沟通协调方面需要一些独特的知识和技能。 目前国际上流行的网络计划技术是一种科学的计划管理方法，它在工程项目计划管 理中的使用价值己得到了各国的认可。网络计划技术以缩短工期、提高生产力、降 低消耗为目标。它可以为项目管理提供许多信息，有利于加强项目管理。它既是一 种编制计划的方法，又是一种科学的管理方法。它有助于管理人员全面了解、重点 掌握、灵活安排、合理组织，经济有效完成项目目标n 6 1 1 5 本文的主要工作 本文在研究电力工程的基础上，将网络计划技术引入到电力工程的管理中来， 构造资源均衡模型和工期一收益一质量多目标优化数学模型，对粒子群算法进行了研 究和改进，提出了基于速度松弛策略的模拟退火粒子群算法，并将其应用到电力工 程中。其主要工作如下： 分析和研究网络计划技术，对网络计划优化的各种算法进行对比分析。 对粒子群算法进行研究，并把它引入到电力工程中的网络计划优化中来。 结合电力工程的实际情况提出改进粒子群算法的需求和需要改进的方向，使其 适用于电力工程。 ： 对网络计划中的数学模型进行改进，形成资源均衡模型，并对标准粒子群算法 3 华北电力大学硕士学位论文 进行改进，引入其对该模型进行求解。 分析并构造多目标优化的数学模型，并将改进后的基于速度松弛策略的模拟退 火粒子群算法引入其中进行寻优。 对改进后的基于速度松弛策略的模拟退火粒子群算法、网络计划资源均衡模型 和多目标优化的模型进行实例验证，验证其正确性和先进性。 4 华北电力大学硕士学位论文 2 1 概述 第二章网络计划技术概述 2 1 1 网络计划技术的内容 国内对网络计划技术研究内容的提法是：向“关键路线要时间 ，向“非关键路 线要资源 。 关键路线决定着整个工程和计划的进度，在关键路线上的作业的迟缓和提前， 就决定整个工作的迟缓和提前。要想缩短某一工程或某一计划任务的生产周期，就 必须要千方百计缩短关键路线上的工序时间。工业企业管理人员要保证任务如期完 成，首先要促使关键路线上的各个工序的作业如期完成，并且要即使全面地检查关 键路线上的各个工序是否存在机动时间，如有机动时间，应立即设法加以利用，以 缩短生产周期。 向非关键路线要资源( 人力、物力等) ，是应用网络计划技术达到最优化的主要 办法。企业管理人员除了抓关键路线上的各个工序，保证完成任务外，还必须抓非 关键路线上各工序的机动力量，向非关键路线要资源。人们可以从非关键工序调出 一部分人力来支援关键路线以保证任务的如期或提前完成。 由于过去缺少计算机这种手段，完全依靠人力编排，不能充分发挥网络计划技 术的优点，所以推广进展工作还不够理想，效果不够显著。近年来，有关研究所、 大专院校、大型厂矿企业等均先后研制了一些有关计算机程序，很多工作可以借助 计算机来完成，因此，使这项新的科学管理技术在各行各业中得到迅速的推广。 2 1 2 网络计划技术的产生 网络计划技术于1 9 5 8 年产生于美国。网络计划技术是为适应生产的需要而应 运而生的，网络计划技术有两个起源： 一个是“关键线路法 是由美国的杜邦化学工业公司发明的。早在1 9 5 2 年， 杜邦公司即注意到数学家在网络分析计算上的成就，认为可以在工程规划方面加以 应用；1 9 5 5 年，杜邦公司设想将每一工作规定起讫时间并按工作顺序绘制成网状图 形以指导生产。1 9 5 6 年，他们设计了电子计算机程序，用计算机编制出了生产网络 计划。1 9 5 7 年，他们将此法应用于新工厂建设的研究工作，形成了“关键线路法”。 1 9 5 8 年初，他们将关键线路法应用于价值1 0 0 0 万美元的建厂工作计划安排，接着 又将此法应用于一个2 0 0 万美元的施工计划的编制。由于认识到了关键线路法的潜 5 华北电力大学硕十学位论文 力，便把此法应用于设备检修工程，使设备应检修而停产的时间从过去的1 2 5 小时 缩短到7 4 小时，仅一年时间就用此法节约了1 0 0 万美元。 另一个是“计划评审技术”简称p e r t 法。p e r t 首次应用于1 9 5 8 年，当时美国 海军特种计划局制定了北极星导弹计划，这个工程由八家总承包公司，2 5 0 家分公 司承担，涉及到1 万多个企业，工作任务十分繁重复杂。采用p e r t 后，提高了工 作效率，使整个工期比预定计划提前约两年完成，成本控制方而也取得了显著的效 果。不过它注重于对各项任务安排的评价和审查，所以把这种方法称为计划评审方 法，即p e r t 。1 9 7 9 年，又使用p e r t 组织“阿波罗”载入登月计划，获得了圆满 成功。从此以后，网络计划技术成为一种盛行的科学管理方法。 关键线路法和计划评审技术大同小异，都是用网络图表达计划，故统称为网络 计划技术n 。 2 1 3 网络计划技术的发展 网络计划技术产生后j 以惊人的速度进行传播，也以超常的速度得到发展，几 乎每两三年就出现一些新的模式，使网络计划技术发展成为一个模式繁多的“大家 族”。国外的网络计划技术有几十种，可以归纳为三大类：第一类是非肯定型网络 计划，是时间或线路或两者都不肯定的计划。包括( 1 ) 计划评审技术( p e r t ) ；( 2 ) 图示评审技术( g e r t ) ；( 3 ) 随机网络计划技术( q e r t ) ；( 4 ) 风险型随机网络计划技 术( v e r t ) ；第二类是肯定型网络计划技术，即图形和时间都确定，包括：( 1 ) 关键 路径法( c p m ) ；( 2 ) 决策关键线路法( d c p m ) ；( 3 ) 决策树型网络等；第三类是搭 接网络，包括：( 1 ) 前导网络计划( m p m ) ；( 2 ) 组合网络计划h m n 等。在我国还有流 水网络计划，是将流水作业技术和网络计划技术结合在一起的一种网络计划模型， 在许多项目中应用取得了良好效果。 美国是网络计划技术的发源地，应用网络计划技术取得成功后，对于它的扩大 应用和发展给予高度重视。美国政府1 9 6 2 年规定，凡与政府签订工程合同的企业， 都必须采用网络计划技术，以保证工程的进度和质量。根据对美国4 0 0 家大型建筑 企业的调查，1 9 7 0 年网络计划技术的使用者达到8 0 。1 9 7 4 年麻省理工学院调查指 出：绝大部分美国建筑公司采用网络计划技术编制施工计划，在大学里，凡是学土木 建筑的，都学网络计划技术课。美国已经用网络计划技术实现了计划工作和项目管 理计算机化。 日本1 9 6 1 年便从美国引进了网络计划技术；1 9 6 3 年确认了网络计划技术的实 用价值；1 9 6 8 年1 0 月，日本建筑学会发表了网络施工进度计划和管理指南， 并在建筑业推广应用。日本的许多超高层建筑都采用网络计划技术组织施工。 6 华北电力大学硕十学位论文 原苏联从1 9 6 4 年开始颁布了一系列有关制定和应用网络计划技术的指示条例 等法令性文件，规定所有大的建筑工程都必须采用网络计划技术，乌克兰建设部早 在6 0 年代中期便应用网络计划技术对全国4 0 0 多个重点工程进行计划管理。原苏 联统计1 9 7 5 年采用网络计划技术完成的建筑安装工作量与1 9 6 7 年比为l ：8 4 9 ，其 发展速度快得惊人。他们通过大量实践后得出结论：应用网络计划技术可以缩短工 期2 0 ，降低成本1 0 ，而且几乎没有必要做新的投入。因此原苏联长期把网络 计划技术作为一项必须推广应用的新技术且正式列入了国民经济发展计划中。 德国从1 9 6 0 年开始应用网络计划技术，并广泛使用单代号搭接网络；主要应 用于工程项目管理，进行工期和费用的系统控制，有国家统一的网络规范，并大量 使用标准网络。 英国普遍推广使用网络计划技术于施工、设计、规划等领域2 7 1 网络计划技术引入我国已经有几十年的历史了，并且在某些领域中发挥了不可 替代的重要作用。我国在6 0 年代初，首先在航天工程中试用该项技术，并在著名 的数学家华罗庚教授的推动下，把从网络计划技术延伸出的统筹法、优选法应用到 各行各业，取得了明显的经济效果。 2 1 4 网络计划法的功能与优点 网络计划法的功能和优点如下： ( 1 ) 能够把方案规划中的工序，组成一个有机的整体，因而可以全面准确地表 达各自工序，尤其是紧邻工序之间的逻辑关系。 ( 2 ) 能够计算出各项工序的时间参数，从而可以提高管理的计划性与预见性。 ( 3 ) 标明关键工序与关键路线。了解关键路线，对施工计划有着非常重要的意 义。指挥人员可以凭此“向关键路线要工期，向非关键路线要资源。 ( 4 ) 计划的实施过程中，因某种因素使一些工序无法如期完成时，应用网络计 划法，通过对每项工序的时差计算，可为决策提供可靠依据。 ( 5 ) 工序提前或推迟时，网络计划法能够充分描绘出对其紧后工序以及总工期 的影响程度。 ( 6 ) 能够为优化提供形象而简洁的数学模型，并可以从许多可行的方案中选出 最优方案。因而可以缩短工期，降低成本，提高经济效益。 ( 7 ) 可以利用计算机进行计算，为项目管理、全面计划管理提供必要的前提。 7 华北电力大学硕士学位论文 综上所述，网络计划技术既是方案、规划、计划的科学表达方法，又是一种有 效地实施方案、规划、计划的控制和管理方法。编制和修订网络计划的过程，也就 是利用网络计划对工程进行模拟的过程，是进行动态的仿真与预演的过程。 2 2 网络计划技术的理论基础 2 2 1c m p 的基本概念 2 2 1 1 网络计划图 在应用网络方法编制计划时，是通过网络图来表示一项工程、组成工程的各道 工序及其相互关系的。网络图( n e t w o r kg r a p h ) 是由圆圈和箭线组成的代表一项 工程计划的图形。 2 2 1 2 网络图( c m p ) 的绘制规则 网络图中不允许出现回路。这是为了避免出现逻辑上的矛盾。一个有效的解决 方法是：在给节点编号时，让个工序的开始节点的号码总是小于结束节点的号码。 节点编号时一般采取：先左后右，由上而下的顺序来编号。 ( 1 ) 紧前工序全部结束后，紧后工序才能开始。 ( 2 ) 箭线与工序一一对应。 ( 3 ) 相邻两节点间只允许有一道工序。 ( 4 ) 源点与汇点唯一。 2 2 1 3c m p 的基本概念 ( 1 ) 工程：一项施工任务、科研试制项目、生产以及较复杂的工作任务，统称 为工程。 ( 2 ) 工序：工序即网络图中箭线，它代表一项工程中的一道工艺过程或局部工 作，它既消耗时间也消耗资源。一般用大写字母a 、b 、c 表示，或用工序首尾相连 的两个节点表示。 紧后工序指的是某工序结束之后紧接着要进行的后继工序。紧前工序指的是与 某工序箭尾直接相连的工序，其紧前工序结束之后，该工序可以紧接着开始。两工 序之间无其它工序称它们为紧前紧后关系，否则称为前继后继关系。因此，一般工 序既是它紧后工序的紧前工序，同时又是它紧前工序的紧后工序。 ( 3 ) 节点：节点即网络图中的圆圈，它代表某工序可能的开始时间或可能的结 束时间，一般用表示。节点只是表示某事件的开始时间或结束时间，它只代表着 8 华北电力大学硕士学位论文 某一个瞬间，因此它既不消耗时间也不消耗资源。 开始节点是指代表某工序开始时间的节点；代表某工序结束时间的节点叫做该 工序的结束节点。同一个节点，对不同的工序而言，它既可以是开始节点，又可以 是结束节点。 两节点间无第三个节点称其为紧前紧后的关系；否则，称为前继后继的关系。 总开始的节点叫源点，总结束的节点叫汇点。 ( 4 ) 工序的工期：工序消耗的时间称为该工序的工期，用字母t 表示。工期 一般情况下写在箭线的下方。 ( 5 ) 虚工序：网络图中的虚箭线。它既不消耗时间也不消耗资源。它代表虚 工序的紧前工序结束之后，虚工序的紧后工序才能开始。路线、关键路线、关键工 序：由源点开始顺着箭线方向一直到达汇点的一条通道，叫做一条路线。每条路线 都要有很多工序组成。 ( 6 ) 路线上所有各工序的工期之和叫做该路线的路长，记为u 。路长最长的 路线叫做关键路线。关键路线有时一条，有时有好几条，无论有几条都叫做关键路 线。在网络图中一般都用红色表示。 关键路线上的所有工序都叫做关键工序。关键工序是工程的主要矛盾环节，如 果关键工序的工期推迟一天，则整个工程的总工期必定推迟一天，如果关键工序的 工期提前一天，则整个工程的总工期可能提前一天。 ( 7 ) 总工期：总工期等于关键路线的长。 2 2 1 4c p m 的时间参数 网络计划技术是系统工程的方法，它研究问题是从全局出发，从局部与周围环 境的联系中去把握事物。时间参数，正是一个局部的工序与周围的环境以及与全局 联系的一种具体描述，因此，研究时间参数就是研究局部与整体的关系。网络计划 技术的优越之处皆从时间参数而来。因此，研究网络的时间参数是网络的中心任务 之一。 1 最早时间参数 主要反映一个工序与前继工序的关系。它有三个时间参数：工序的最早开始时 间，工序的最早结束时间，节点的( 最早) 开始时间。 ( 1 ) 工序的最早开始时间：在网络计划中，工序最早可能的开始时间，记为e s 。j 或e s a 。 ( 2 ) 工序的最早结束时间：在网络计划中，工序最早可能的结束时间，记为e f ” 9 华北电力大学硕士学位论文 或e f a 。 工序最早开始时间加上该工序工期就得到该工序的最早结束时间，用公式表示 如下：e f a = e s a + t a t a 代表a 工序的工期，是作网络图时给出的，可当作已知的。因此只要知道工 序的最早开始时间，可立即推知工序的最早结束时间。工序的最早开始时间等于其 紧前工序最早结束时间的最大值，即： e s i j = m a x ( e s k 。i ，e s k 2 i ， ，e s k 。i ) 且共开始节点的工序最早开始时间相等。 ( 3 ) 节点的最早开始时间：某节点的任一紧后工序的最早开始时间，称为该 节点的( 最早) 开始时间，记为e s 。显然，e s 。= e s m 节点的最早开始时间等于其 紧前工序最早结束时间的最大值。 ( 4 ) 最早开始时间的特点：同一节点的所有紧后工序的最早开始时间都相同， 或者说共开始节点的工序其最早开始时间相同。 2 最迟时间参数 最迟时间参数主要反映工序与其后继工序之间的相互关系。它也有三个时间参 数：工序的最迟结束时间，工序的最迟开始时间，节点的( 最迟) 结束时间。 ( 1 ) 工序的最迟结束时间：在不影响总工期的前提下，工序最迟可能的结束， 时间，记为l f a 或l f 如果工序实际结束时间比最迟结束时间推迟多少天，则总 工期也会被推迟多少天。 ( 2 ) 工序的最迟开始时间：在不影响总工期的前提下，工序最迟可能的开始 时间，记为l s a 或l s 。，。工序的最迟结束时间减去工期就等于工序最迟开始时间， 用公式表示如下： l s a = l f a t a 工序的最迟结束时间应当等于其紧后工序最迟开始时间的最小值，用公式表 示：l f 。j = m i n ( l s j t 。，l s j k 。，l s j 。) 且共结束节点的工序，最迟结束时间相等。很显然，实际开始时间比最迟开始 时间推迟n 天，则总工期就会因此而推迟n 天。 ( 3 ) 节点的最迟结束时间：节点的任一紧前工序的最迟结束时间称为该节点 的( 最迟) 结束时间。即 l f j = l f i j 节点的最迟结束时间等于紧后工序最迟开始时间的最小值。 1 0 华北电力大学硕士学位论文 ( 4 ) 最迟结束时间的特点： 同一节点的所有紧前工序最迟结束时间都相等，或者说共结束节点的工序最迟 结束时间都相等。 3 机动时间参数 机动时间参数反映了工序与其它工序联系的总和，它反映了该工序在整体中的 地位，因此它是一个综合性的指标。目前国际上通用的有三种机动时间参数：总时 差，单时差，共用时差。因本文只涉及到总时差和节点的时差这两个参数，因此只 介绍它们两个。 ( 1 ) 工序的总时差：在总工期不推迟的前提下，工序完工期可以延迟的最长 时间，叫做工序的总时差或最大机动时间，工序a 的总时差记为t f a 。总时差等于 工序的最迟结束时间与最早结束时间的差或等于最迟开始时间与最早开始时间的 j z o ( 2 ) 节点的时差：节点的时差等于该节点的最迟结束时间与节点的最早开始 时间之差2 6 1 。 2 3 网络计划技术与优化算法的结合 网络计划技术是现代化的科学的管理方法，网络计划技术的不断发展为各种优 化算法提供了肥沃的土壤，相继有许多优化算法应用到网络计划领域中来，有遗传 算法，差异演化算法，粒子群算法等等。这些智能仿生类算法具有良好的并行性、 随机性、自适应性、鲁棒性，并且在非线性复杂问题的求解方面表现出了独特的优 势，尤其是求解组合优化等n p 困难问题更是取得了巨大的成功。本文中我们要研 究的粒子群算法在网络计划技术领域方面的应用就非常具有代表性，本文中我们把 优化算法在网络计划技术方面的应用统称为网络计划优化算法。 2 4 本章小结 本章介绍了网络计划技术的基本内容，产生和发展过程，详细介绍了网络计划 技术的一些基本理论基础，并将优化算法融合到网络计划技术中来。 华北电力大学硕士学位论文 第三章粒子群优化算法的改进 3 1 基本粒子群算法 3 1 1 基本原理 粒子群优化算法来自于对鸟群的捕食行为的模拟。设想这样一个场景：一群鸟 在随机搜索食物，在这个区域里只有一块食物，所有的鸟都不知道食物在那里，但 是它们知道当前的位置离食物还有多远，那么找到食物的最优策略是什么呢? 最简 单有效的就是搜寻目前离食物最近的鸟的周围区域。p s o 从这种模型中得到启示并 用于解决优化问题。 在p s o 模型中，每个优化问题的解都是搜索空间中一个“粒子的状态。每个 粒子都有一个由被优化函数决定的适应值( f i t n e s sv a l u e ) ，同时还有一个速度决 定它们的飞行的方向和距离。粒子根据自身及同伴的飞行经验进行动态调整，也可 以说是通过跟踪两个位置来更新自身。一个是粒子本身所找到的最优解p b e s t ，即 个体最好位置；另一个是整个种群当前找到的最优解g b e s t ，即全局最好位置。p s o 算法运行过程中，随机产生一个初始种群并赋予每个粒子一个随机速度，并根据公 式( 3 一1 ) 和公式( 3 2 ) 来更新粒子的速度和位置。 喵1 = w 宰屹+ c l + 1 宰( 砌一艺) + c j 吒木( 以d 一) 1 = 屹+ 竹1 公式( 3 1 ) 公式( 3 2 ) 其中，w 是惯性权重因子，学习因子c l 和岛是非负常数，和是两个独立的介 于 0 ，1 之间的随机数；t 表示进化代数；d = 1 ，2 ，口，d 。公式( 3 1 ) 中的第l 部分是粒子的惯性速度，它体现了粒子的记忆行为；第2 部分通过粒子f 当前位置 与自己最好位置之间的距离来体现“认知 部分，即表示了粒子的动作来源于自 己经验的部分；第3 部分通过粒子f 当前位置与群体最佳位置之间的距离来体现“社 会部分，即表示粒子的动作来源于群体中其他粒子的经验部分，表现为知识的共 享和合作吲h 1 ，它引导粒子飞向粒子群的最佳位置。这三个部分之间的相互平衡和 制约决定了算法的主要性能。惯性因子w 即是粒子上一次的速度对本次飞行速度的 影响因子，它主要用于平衡粒子群的全局搜索能力和局部搜索能力。有研究表明， w 对优化性能的影响很大。较大的w 值有利于跳出局部极小点，而较小的w 值有利 于算法收敛阻1 。p s 0 算法的这些观点某种程度上可以通过心理学加以解释：在寻求 一致的认知过程中，个体往往记住它们的信念，同时考虑同伴们的信念；当个体察 觉同伴的信念较好时：，它将根据同伴的信念进行适应性地调整“们。 1 2 华北电力大学硕士学位论文 3 1 2 算法流程 p s o 算法运行时首先初始化一群粒子( 种群规模为p ) ，包括随机位置和速度； 并根据适应函数计算每个粒子的适应度；接着，将每个粒子的适应值与自身经历过 的最好位置p b e s t 作比较，如果较好，则将当前位置作为自身最好位置p b e s t ；将 每个粒子的适应值与种群所经历的最好位置g b e s t 作比较，如果较好，则作为种群 最好位置曲e s t ；最后根据公式( 3 1 ) 和公式( 3 2 ) 更新粒子的速度和位置，并继续 计算下一个粒子。 3 1 3 参数设置 基本p s o 算法包含以下参数：种群规模p ，粒子维度d ，粒子活动范围x ，惯性 因子w ，学习因子c l 和c 2 ，最大速度v ，最大迭代次数m a x i t e r a t i o n 。 ( 1 ) p ：种群中的粒子总数，通常设为1 0 4 0 间的一个值。 ( 2 ) d ：由具体优化问题决定，就是问题解空间的维度。 ( 3 ) x ：粒子的活动范围，由优化问题决定，每一维可是设定不同的范围。 ( 4 ) v ：最大速度，决定粒子在一个循环中最大的移动距离，通常设定为粒子活 动范围的宽度，例如，对于粒子( x 。，x ：，x 。) ，x 。属于 一1 0 ，1 0 ，那么v 的大小就是 2 0 。如果v 。太高，粒子可能会飞过较好解，从而丧失局部搜索能力；如果v 太小， 粒子不能在局部区间之外进行足够的探索，导致陷入局部极值。 ( 5 ) 权重因子w ：使粒子保持运动惯性，使其有扩展搜索空间的趋势，有能力探 索新的区域。w 一般取小于或等于1 4 的定值，也可设计为在迭代中随时间线性减 少。 ( 6 ) 学习因子：c l 和c 2 代表将每个粒子推向p b e s t 和g b e s t 位置的统计加速项的 权重。较低值允许粒子在被拉回之前可以在目标区域外徘徊，而较高值则导致粒子 突然的冲向或越过目标区域。一般取c l 等于c 2 ，并且范围在o 和4 之间。 ( 7 ) 最大迭代次数：算法的终止条件，该值由具体的问题确定。 3 2 全局模式与邻域模式 k e n n e d y 等人在观察鸟群觅食的过程中注意到，通常飞鸟并不一定看到鸟群中 其他所有飞鸟的位置和动向，往往只是看到相邻的飞鸟的位置和动向。因此他在研 究粒子群算法时，同时开发了两种模式：全局模式( g b e s t ) 和邻域模式( 1 b e s t ) 。在 全局模式中，每个粒子的轨迹受粒子群中所有粒子的所有的经验和意识的影响；而 在局部模式中，粒子的轨迹只受自身的认知和邻近的粒子状态的影响，而不是被所 1 3 华北电力大学硕十学位论文 有粒子的状态影响。全局模式提供了较快的收敛速率，但付出了不够鲁棒的代价。 邻域模式本身存在着两种不同的方式。一种方式是由两个粒子空间位置决定 “邻居”，它们的远近用粒子间距离来度量；邻域的另一种方式是编号方法，粒子 群中的粒子在搜索之前就被编以不同的号码，例如1 号与最后一个粒子和2 号相邻， 2 号粒子则与1 号、3 号相邻；形成环状拓扑社会结构u 。根据社会学家的研究， 这两种邻域的概念都是有社会背景的。对于第一种方式，在每次迭代之后都需要计 算每个粒子与其他粒子间的距离来确定邻居中包括哪些粒子，这导致算法的复杂度 增强，算法运行效率降低，而第二种方式由于事先对粒子进行了编号，因而在迭代 中粒子的邻域不会改变。这导致在搜索过程中，当前粒子与指定的“邻居粒子迅 速聚集，而整个粒子群就被分成几个小块，表面上看似乎是增大了搜索的范围，实 际上则大大降低了收敛速度。 实验发现在邻域模式中邻居的数目不同对算法的性能也会产生的影响。图3 1 给出了在不同的邻居数下对多模态g r i e w a n k 函数的优化性能曲线。从图中可以看 出，全局模式收敛速度快，但容易陷入局部极值；邻域模式收敛速度较慢，但却具 有较强的全局搜索能力。可见在全局模式和邻域模式两者间存在着一种平衡，也就 是局部搜索速度与全局搜索能力的平衡。两者虽然不可兼得，但却可以针对不同问 题选择不同的模式。例如，对于较简单的单模态优化问题，可以使用全局模式提高 算法的收敛速度。 图3 1g r i e w a n k 函数最小值优化问题在不同邻域下的性能比较 3 3 粒子群算法的各种改进方法 目前，世界各国学者对标准粒子群算法进行了多种方法的改进。总的来说有以 1 4 华北电力大学硕士学位论文 下三种方法：提高收敛速度、提高种群多样性、算法离散化。 3 3 1 提高收敛速度 提高收敛速度的己知方法主要在于修改p s o 算法的速度更新方程，而不是去修 改算法的结构。这些方法通常会得到较好的局部优化结果，然而对于一些多模态优 化问题则会导致性能下降。 惯性因子的大小决定着粒子保持原来运动速度的程度，也可以说是粒子对自身 运动状态的信任。早期的试验将w ，c 。和c 2 固定，因此v 成为唯一需要调节的参数。 接着引入了惯性因子，通过某种途径来调节惯性因子w 也是早期使用最多的提高收 敛速度的办法。最原始的p s o 没有惯性因子，也可以看作w = l 。s h i 和e b e r h a r t 通过研究发现w 取值在 o 8 ，1 2 具有较高的收敛速度，如果w 过大( 例如w 1 2 ) 则会导致算法很难收敛n 羽。一些学者还对惯性因子和v 。间的交互关系进行了研究。 这样，当v 增加时，可通过减小w 来达到平衡搜索，而w 的减小可使得所需的迭 代次数变小。从这个意义上看，可以将v 。，固定为粒子每维的变化范围，只对w 进 行调节。通过实验进一步发现，线形变化的惯性因子有助于