（技术经济及管理专业论文）一种基于CPM的多资源约束项目调度启发式方法研究.pdf

华北电力大学硕士学位论文 摘要 资源约束项目调度问题是项目进度管理中的典型问题。解决这类问题必须同 时处理工序的前后关系约束和资源约束，使得它比一般调度问题更加难以解决，属 于n p - 难问题。文章在回顾了资源约束项目调度问题的发展历程和研究现状的基 础上，结合c p m 和平行工序顺序优化理论，提出了一种多资源约束项目调度的新 的启发式方法基于重心优先规则的启发式方法，给出了算法步骤。最后，文 章构建了多资源约束项目启发式方法评价研究系统，将基于重心优先规则的启发 式方法与现有其他启发式方法比较，证实了该方法的求解效果和执行效率。 关键词：项目进度管理，资源约束项目调度问题，平行工序顺序优化，启发式方 法 a b s t r a c t 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 mi sat y p i c a li s s u ei np r o j e c t s c h e d u l i n gm a n a g e m e n t a sp r e c e d e n c er e l a t i o n sa n dr e s o u r c ec o n s t r a i n t sm u s tb e c o n s i d e r e dc o n c u r r e n t l y , t h i sp r o b l e mi ss od i f f i c u l tt os o l v ec o m p l e t e l yt h a ti t b e l o n g s t on p h a r d a f t e r r e v i e w i n gt h ed e v e l o p m e n th i s t o r y a n dr e s e a r c h i n g a c t u a l i t yo fr c p s p t h i sp a p e rb r i n g sf o r w a r dan e wh e u r i s t i c am i n - qb a s e d h e u r i s t i cf o rm u l t i r e s o u r c ec 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 mc o m b i n i n gw i t h c p ma n ds e r i a t i o no p t i m i z a t i o nt h e o r yo fp a r a l l e la c t i v i t i e s ，t h ea l g o r i t h mf o rt h e m e t h o di sa l s op r o p o s e d f i n a l l y , 8 1 1e v a l u a t i o ns y s t e mf o rh e u r i s t i cm e t h o d sf o r m u l t i - - 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 mi sc o n s t r u c t e da n dt h ea r t i c l e p r o v e s t h es o l u t i o n sa r eo fo p t i m i z a t i o na n de x e c u t i o ne f f i c i e n c y , t h r o u g h c o m p u t a t i o n a lc o m p a r i s o nw i t ht h eg o o dh e u r i s t i c si ne x i s t e n c e g u ox i n z h i ( t e c h n i c a le c o n o m i c sa n dm a n a g e m e n t ) d i r e c t e db yp r o q ij i a n x u n k e yw o r d s ：p r o j e c ts c h e d u l i n gm a n a g e m e n t , r e s o u r c ec o n s t r a i n e dp r o j e e t s c h e d u l i n gp r o b l e m ，s e r i a t i o no p t i m i z a t i o no fp a r a h e la c t i v i t i e s ，h e u r i s f i e i i l 华北电力大学硕士学位论文 主要符号表 符号 说明 a o n 单节点网络图 互 工序i 的工期 号 工序i 的紧前工序的集合 s i 工序，的紧后工序的集合 毯工序i 的最早开始时间 匹 工序珀q 最早完成时间用 l s , 工序，的最迟开始时间 瑾。工序，的最迟完成时间 珥 工序珀9 总时差 ( 力 序偶 【刃序偶亏值 q 工序珀q 重心 ，t 工序，在其工期弓内每天需要个单位的第七种 资源 r项目中每天可提供的第k 种资源容量 嘏在r c p s p 中，工序珀g 时间完成时间 m i n q基于重心优先规则的启发式方法 甲 关键路线 7关键路线的长度 p t + ?同时过工序f 和工序，的最长路线 p i 。：同时过工序f 和工序，的最长路线的长度 p l工序i 的前主链 工序i 的前主链的长度 p i ，。 工序i 的后主链 ，审工序i 的后主链的长度 v i 声明 本人郑重声明：此处所提交的硕士学位论文一种基于c p m 的多资源约束 项目调度启发式方法研究，是本人在华北电力大学攻读硕士学位期间，在导师 指导下进行的研究工作和取得的研究成果。据本人所知，除了文中特别加以标注 和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得华北电力大学或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名：巡日期：- 塑：! ：! ! 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有 权保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩 印或其它复制手段复制并保存学位论文；学校可允许学位论文被查阅或借阅； 学校可以学术交流为目的，复制赠送和交换学位论文；同意学校可以用不同方 式在不同媒体上发表、传播学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：导师签名 日期：坦2 ：! ! ! !日 期：筮盟：! ! 巡 华北电力大学硕士学位论文 1 1 研究的背景和意义 第一章引言 项目管理从人们开始共同合作，进行社会生产与活动之日起就已经开始了， 并在近年来发展成为一个管理学科的新领域。特别是进入上世纪9 0 年代以后， 随着信息系统工程、网络工程、软件工程、大型建设工程以及高科技研究与开发 项目的出现，项目管理在理论和方法等方面不断地发展进步。目前，国际专业人 士对项目管理的重要性及其基本概念已有了初步共识。p m i ( 美国项目管理协会) 的项目管理知识体系指南( 2 0 0 4 ) 【l 】把项目管理划分为九个领域，即：范围管理、 时间管理、成本管理、质量管理、人力资源管理、沟通管理、采购管理、风险管 理和集成管理等。该文件已被世界项目管理界公认为一个全球性标准。 在项目管理的三大目标进度、成本和质量之中，进度管理具有重要的地 位，尤其是在如今快速变化的市场环境中，是否能够按时完成项目对于维持企业 的可持续竞争力有着至关重要的影响，而且项目进度管理的好坏会直接影响到项 目的成本与项目最终的盈利能力【2 】。资源约束的项目调度是项目进度管理中的重 要分支，它是在传统进度管理的基础上考虑了资源的约束。在文献中以及目前的 项目管理实践中，解决资源约束的项目调度问题主要有如下两种方案： 方案一：首先，不考虑资源约束，按照c p m p e r t 的规则计算工序时间参数 和其他特征参数，得到初步的进度计划；然后，考虑资源约束的限制条件，调整 初步进度计划以满足目标要求。例如，在解决项目调度问题时，首先按照c p m 计 算项目初步进度计划，然后通过将平行工序调整为顺序工序解决平行工序问的资 源冲突，并保证项目工期最短【3 】：在解决时间成本均衡问题时，首先按照工序的 正常工期安排项目进度计划，再按照最低成本加快方法压缩工序的工期，以达到 项目工期要求口】【4 1 。方案一强调对项目网络图的内在特征及规律的熟练掌握和深 刻剖析。依据方案一的思想开发的计划管理方法很多已经应用到实际生产中，相 应的软件被开发出来用以指导计划管理的实践【5 1 1 “。 方案- - ：通过c p m p e r t 规则计算得到工序时间参数以后，在考虑资源约束 和前后关系约束的条件下直接优化。例如，在解决项目调度问题时，利用0 一l 规 划、动态规划、分枝定界、智能优化、启发式方法【2 】、关键链管理等方法将资源 和前后关系作为约束条件，以项目工期最短为目标，直接求取每个工序的开始时 间【7 1 1 8 1 1 9 1 ；在解决时间成本均衡问题时，利用线性规划的方法将前后关系作为约 束条件，以项目成本最低为目标，直接求取每个工序的开始时间和工期【1 0 】【l l 】。方 案二中的优化方法大都来自于网络计划技术之外的计算和优化领域。依据方案二 华北电力大学硕士学位论文 的思想开发的计划管理软件更为广泛的应用到项目管理实践中，例如p 。等。 项目管理的实践除了要求进度计划的工期短、成本低，对进度计划算法的求 解效率也有一定的要求f 2 】。这使得启发式方法在所有的项目调度管理方法中脱颖 而出，因为启发式方法操作简单方便，容易被商业软件采用，耗费的计算时间相 对较短，无论对于多大规模多么复杂的项目，都可以在人们可接受的时问内给出 结果。大量的启发式方法被提出来并广泛的应用到生产实践中f 8 j 【1 2 j 【1 3 j 。但是不同 的启发式方法处理项目调度问题的效果和效率差异很大，同一方法用于处理不同 调度问题时也不一定能够取得满意解l l ”。所以，项目调度领域亟需求解效果好执 行效率高的启发式方法出现。 本文结合传统的进度管理手段和r c p s p 现代方法，将平行工序顺序优化理论 中重心的概念引入到解决资源约束项目调度问题的启发式方法中，提出了一个新 的启发式方法基于m i n - q 的启发式方法。通过启发式方法评价研究发现，这 种新方法与现有较好的方法相比求解效果优异且效率很高。本文的工作不但丰富 了r c p s p 的基于优先规则的启发式方法的理论，而且为项目调度管理实践提供了 一个值得推荐的新方法。文章构建的多资源约束项目调度启发式方法评价研究系 统，也为启发式方法评价工作提供了一种新的研究思路和研究平台。 1 2 研究内容和研究框架 本文在总结项目调度方法的基础上，分析了平行工序顺序优化和资源约束项 目调度的异同。在解决资源冲突的共同点上将二者结合起来文章将平行工序顺 序优化理论中两个平行工序问重心比较的思路扩展为任意多个平行工序之间的 比较。扩展了的重心比较的思路，为解决r c p s p 提供了一种新的优先规则。文章 将m i n q 与平行调度生产方案相结合，提出了基于m i n q 的启发式方法，并通过 与现有较好的启发式方法比较，证实了基于m i n q 的启发式方法的实用性和最优 性。文章后面的内容参照以下框架： 第二章简述网络计划技术的理论基础，重点介绍了重心的概念以及重心定理 在两个平行工序顺序优化中的应用。 第三章综述资源约束项目调度问题的概念、分类、模型及发展历程。 第四章提出基于重心优先规则的启发式方法，论述了其在资源约束项目调度 问题中的可行性，并通过实例演算说明了该方法的应用过程。 第五章回顾启发式方法评价研究的发展和现状，构建了多资源约束项目调度 启发式方法评价研究系统，通过计算比较评价了本文所提方法的求解效果和执行 效率。 第六章对全文工作进行总结。 2 华北电力大学硕士学位论文 第二章网络计划技术简述 网络计划技术是2 0 世纪5 0 年代中期发展起来的一门科学的计划管理技术，它 最早出现在美国，最具代表性的是关键路径法( c r i t i c a lp a t hm e t h o d ，简称c p m ) 与计划评审技术( p l a ne 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 ) 。这两种方 法弥补了使用甘特图安排计划的某些不足，其优越性逐渐得到计划部门的重视，并 在各行各业迅速推广应用。 各国逐渐开始重视网络计划技术在生产计划工作的应用。我国于上世纪6 0 年 代引入了网络计划技术。华罗庚院士亲自在全国各地各个行业中推广。上世纪8 0 年代末期，网络计划技术开始在国防、农业、工业，交通、电力等领域的计划管理 工作中得到实际应用。 近年来，随着计算机技术的飞速发展，各学科的互相渗透，边缘学科的兴起， 网络计划技术已经同决策论、排队论、控制论、仿真技术相结合，应用范围不断拓 宽，有关网络计划的理论研究与应用研究不断涌现，相继出现了搭接网络计划技术 ( o l n ) 、决策网络计划技术( d n ) 、图示评审技术( g e r t ) 、风险评审技术( v e r t ) 等一大批现代计划管理方法。 网络计划技术是项目进度管理的核心技术。随着现代项目管理理念的发展，项 目管理不再仅仅应用于工程建设中，已经推广到r r 、咨询、甚至服务性领域。项目 管理的日益推广必定为网络计划技术的发展提供新的契机 2 1c p m 的理论基础 1 9 5 6 年美国杜邦化学公司新化工厂在建设生产设备的维修工作中首次使用 c p m ，使停工时间从原来的1 2 5 小时减少到7 8 小时，从而，一年内节约了1 0 0 多 万美元，它相当于研究开发c p m 所花费用的5 倍多。这种计划方法借助网络表示 各项工作、每项工作所需要的时问和各项工作之间的相互关系，从而找出执行计划 中的关键路线，这种方法就称之为关键路径法，简称c p m 。 2 1 1 基本概念 ( 1 ) 网络计划图：由圆圈和箭线连接而成的有向无环网状图，代表一个项目的 整体信息。网络计划图有双节点网络图( a c t i v i t y - o n a r r o w , 简称a o a ) 和单节点 网络图( a c t i v i t y - o n n o d e ，简称a o n ) 两种。 资源约束项目调度问题多以a o n 为处理对象，本文重点介绍单节点网络图， 图2 - 1 所示的就是一个单节点网络图。 华北电力大学硕士学位论文 5 图2 1a o n 网络图 ( 2 ) 工序：即网络图中的节点，它表示项目中的一个活动。圆圈中的数字表示 工序的编号。在单节点网络图中，始节点和终结点代表虚工序，不耗费工期和资源。 其他工序耗费的工期在工序上方标出，工序耗费的资源在下方标出 ( 3 ) 前后关系；在单节点网络图中，箭线表示工序之间的前后关系网络中的 工序都满足完成一开始关系，即只有当某个工序的所有前继工序完成后，这个工序 才能开始执行。 ( 4 ) 路线：连接始节点和终节点的一条线。路线的长度等于该路线上所有工序 的工期之和，记为。关键路线是路长最长的一条或几条路线，关键路线上的工序 称为关键工序。 ( 5 ) 资源：所有实工序都耗费资源，包括人力、资金、机器、设备、原材料等。 一般，项目中使用的资源分为可更新资源、不可更新资源、双约束资源和部分可更 新资源四种类型。每一类型资源又根据功能的不同进一步细分为不同种类每一种 资源都有一个资源容量值( a v a i l a b i l i t y ) ，表示这种资源的总量约束。 可更新资源是指，项目对这类资源的使用在每一个单位工期( 如，一天，一周、 一月、一年等，下同) 内都受到数量的约束，但在整个项目周期中，使用总量不受 约束。即，在同一单位工期使用这种类型资源的多个工序可能会产生资源的冲突， 但在整个周期中，项目对这类资源的使用不受总量的约束。例如，机器、设备、人 力、原材料等。 不可更新资源，是指项目对这类资源的使用在单位工期内不会受到数量的约 束，但在整个项目周期中，会受到使用总量的约束。即，在同一单位工期使用这种 类型资源的多个工序不会产生资源的冲突，但在整个周期中，项目对这类资源的使 用受到总量的约束。例如，资金 双重约束资源，是指项目对这类资源的使用既在每一单位工期会受到数量的约 束，而且在整个项目周期中也会受到使用总量的约束。例子还是资金。如，某项目 4 华北电力大学硕士学位论文 周期内可用资金总量为1 0 0 0 0 元，且受实际情况的限制，每天可使用的资金最多为 1 0 0 0 元，就是双重约束资源的例子 部分可更新资源，是指项目使用这类资源时，在整个项目周期的某个局部时间 段中受到使用数量的约束。例子是工时。如，预定生命周期为一个月的项目，每一 天对每个员工的可用工时数量不加限制，但是每一周内每个员工的可用工时不超过 4 0 小时 是否考虑资源约束对项目进度计划的影响，是r c p s p 与c p m 在安排进度计划 时的核心区别。项目执行过程中，每个工序可能需要多种资源，每种资源的容量也 不同，且各种不同容量的资源对工序开始时间的影响也不同。所以，在安排项目进 度计划时，有必要把项目使用的资源进行分类处理。 2 1 2 工序的时间参数 网络图除了能够清楚地表达各工序问的工艺要求和前后关系之外，其时间参数 更加详细具体的展现了网络图本身的结构特征，使得这个计划工具成为一门真正的 技术网络计划技术。时间参数作为网络计划的技术基础，尤其是其中的机动时 间，一直是项目进度管理方面的研究热点。 b a t t e r s b y ( 1 9 6 7 ) 和t h o m a s ( 1 9 6 9 ) 最早提出了四种机动时间( 时差) ：总时差 ( t o t 8 l f l o a t ) 、安全时差( s a f e t y n o a t l 、自由时差( f r e e f l o a t ) 和独立时差( i n t e r f e r e n c e f l o a t ) ；e l m a g h r a b y ( 1 9 7 7 和1 9 9 5 ) 【1 6 】【1 7 】对以上的四种时差分别进行了分析和陈述 但是针对网络本身的复杂性，这四个机动时间还不足以反映出工序之间时差的内在 联系，于是乞建勋教授【1 5 l ( 1 9 9 7 ) 又给出了前共用时差和后共用时差的概念，并把 安全时差更名为前单时差，自由时差更名为后单时差自从这两个时差的引入，使 得c p m 网络中，紧前和紧后工序的时差关系变得清楚起来。为了清楚表达工序在 使用机动时间时对其紧前、紧后工序的影响，李星梅 埽1 引入了三个新时差概念：前 共后单时、前单后共时差和双共时差。 2 1 2 1 工序的开始、完成时间参数 ( 1 ) 最早开始时间：工序f 的最早开始时间用e s , 表示， e s , = m a x e f j ，曰 ( 2 - 1 ) 其中，只表示工序i 的紧前工序的集合。 ( 2 ) 最早完成时间：工序珀q 最早完成时间用e f 表示， 明t i e s , + 刀( 2 - 2 ) 其中，z 表示工序i 的工期。 ( 3 ) 最迟完成时间：工序，的最迟完成时间用珥表示， 巧= m i n l s , ，i s ， ( 2 - 3 ) 5 华北电力大学硕士学位论文 其中，邑表示工序，的紧后工序的集合 ( 4 ) 最迟开始时间：工序_ ，的最迟开始时间用墨表示， 三马= 嵋一乃 ( 2 - 4 ) 其中，乃表示工序j 的工期a 2 1 2 2 工序的机动时间参数 ( 1 ) 总时差：工序i 的总时差用硒表示， 晒= l s , 一e s , = 鸠一点：e ( 2 - 5 ) ( 2 ) 后单时差：工序i 的后单时差用明6 表示， 够6 = 哆一奶 ( 2 - 6 ) 其中，工序_ ，是工序f 的紧后工序。 ( 3 ) 后共用时差：工序i 的后共用时差用皿6 表示， i f , 6 = t e 一，f 6 ( 2 7 ) ( 4 ) 前单时差：工序f 的前单时差用6 髓表示， 6 巧= 强一珥 ( 2 - 8 ) 其中，工序k 是工序f 的紧前工序。 ( 5 ) 前共用时差：工序i 的前共用时差用6 瞒表示， 6 职= 弼一6 朋 ( 2 - 9 ) 工序的时间参数反映了工序与项目中其他工序之间的联系，工序某些时间参数 的大小是平行工序间在展开资源角逐时的优势或劣势所在，直接决定了其在项目计 划安排中的前后次序。因为，到目前为止，基于优先规则的启发式方法大都是以工 序的时间参数作为其优先规则【1 9 】。 2 2 平行工序顺序优化研究 平行工序顺序优化是指在资源约束的条件下，为项目计划中原本独立进行的平 行工序安排先后次序，并使项目计划总工期推迟量最少。这一问题是项目管理中的 实际问题，对这一问题的研究具有很强的现实意义。因为项目执行过程中，由于意 外因素导致项目使用的资源数量发生改变，例如某种资源的供应量减少，就会使原 本可以顺利进行的平行工序之间产生资源冲突。为使项目在缩小了的资源供应量下 继续进行，就不得不推迟某一个或几个工序的开始时间。一般情况下，工序开始时 间的推迟会导致项目工期的延长。为保证项目工期短、成本低的目标，很有必要研 究平行工序调整最优化的问题。乞建勋教授首先开始了这方面问题的研究，并取得 了一系列成果【”】，包括两个平行工序的顺序优化、三个平行工序的顺序优化、二元 行偶的顺序优化，三元行偶的顺序优化、三元序链的顺序优化、n 元网格的顺序优 化、带松弛量的两个平行工序的顺序优化、带松弛量的两个平行工序的顺序优化、 6 华北电力大学硕士学位论文 带松弛量的三个平行工序的顺序优化、带松弛量的二元行偶的顺序优化、带松弛量 的三元行偶的顺序优化等。 2 2 1 基本概念和基本定理 ( 1 ) 平行工序：在项目网络图中，不在同一条路线上的工序称为平行工序。而 在同一条路线上的工序就称为顺序工序。平行工序之间没有前后关系的限制，顺序 工序之间存在前后关系的约束 ( 2 ) 序偶及序偶的亏值：把项目网络图中的两个平行工序f ，_ ，调整为顺序工序对 i 寸j 后，这个工序对就称为一个序偶，记为( 刃。项目工期因此被推迟的天数称为 序偶的亏值，记为【刃。 ( 3 ) 工序的重心：工序i 的最早开始时间e s , 与最迟结束时间l f , 之和称该工序的 重心，记为g ， q = e s , + 奶= 弼+ 硒 ( 2 - 1 0 ) 前主链定理：在项目网络图中，任意工序i 与首工序1 之间( 不包括工序i ) 的最大 路长西等于该工序的最早开始时间e s , ，即 越= e s l ( 2 1 1 ) 证明：见附录a 。 后主链定理： 在项目网络图中，任意工序_ ，与尾工序w 之间( 不包括工序j ) 的最大路长? 等于关键路线路长与工序_ ，的最迟结束时间之差，即， 潆= 矿一l f ? ( 2 - 1 2 ) 证明：见附录b 。 2 2 2 两个平行工序的顺序优化研究 问题描述t 工序f ，- ，是项目网络图中的两个平行工序，它们使用同种资源且每天耗用量相 等。现在，由于意外原因导致该种资源的供应量只能够保证一个工序进行，且已知 工序开始时问的变动不会导致其他资源冲突。确保项目工期延长量f ，1 最小，应该如 何调整工序f ，的开始时间? 定理：把项目网络图中的两个平行工序f ，_ ，调整为顺序工序对i j 后， l 】! ，】= m a x ( e f f - l s j ) ，o ) ( 2 - 1 3 ) 证明： 当把项目网络图中的两个平行工序f ，调整为顺序工序对i j 后，其它工序及 其前后关系都没有发生变化，所以网络图中的所有原始路线都没有发生变化但是， 7 华北电力大学硕士学位论文 网络中由此增加了_ 部分路线。这部分新增路线的特点是，既经过工序i 又经过工序_ ， 设这部分新增路线中的最长路线为服，路线长度为肛，7 ，原来网络图中的 关键路线为t 7 ，路线长度为t 9 ， ( 1 ) 当肛卅7 7 时，关键路线仍然是卢7 ，项目工期不变。即【f 】- o 。 ( 2 ) 当肛，9 t 9 时，“，7 成为网络图中的新关键路线，项目工期也就变为 q l 。j t 因此，项目工期的延长量为 玎】= 肛，- t 9 证毕。 f l j ( 2 - 11 1 知 由( 2 1 2 ) 知 畦= e s t l i ；= 口一l 壬| 由前主链和后主链的定义可知，既经过工序f 又过工序_ ，的最长路线为： p 。? = p ：懈p p ? ：p b ? = e s i + | + t i 七矿一l f = 口+ 疆l 一璐r ? m 叫9 一7 = 媚一工墨= 【胡 i 7 即- - v ，【 ，】= 竭一鹕 0 7 j j ，【驴】= e 巧一l 马 【驴】= n 姒 ( e 巧一马) ，o 重心定理： 当把项目网络图中的两个平行工序f ，- ，调整为顺序工序时，为保证项目工期延长 量最小，应该安排重心较小的工序先开始，即， 若q q ，则f 寸， 若g i 2 g j 黜i j j 证明： 8 华北电力大学硕士学位论文 ( 1 ) 由亏值定理知， 当【j o ，【玎】 o 时，【玎】= e 巧一三q ，【驴】= e 弓一l 墨 则，【玎卜【_ ，f 】= ( e 只一l 马) 一( e 乃一l 墨) = ( e 只+ 工墨) 一( e + l s j ) ：m - i ：d - - g , 一g i 7 当q s g ，则眇】 【卅，则，哼f 工期延长较小。 ( 2 ) 由亏值定理知， 当【列 【】= o 时，( 啦一鹕) o ， e f j - l $ 1 ) = 0 则，( e e l s a 一( e 弓一l s , ) o ，( e f , + 工墨) 一( e 一十珥) o ：g i g j 0 g | gj 当q 2 q ，则【刃 p 1 ，则_ ，哼f 工期延长较小 ( 3 ) 当【j = o ，【州 o 时，同理可证重心定理成立。 ( 4 ) 当【e l - - o , n = o h = 于，此o c a - + a 与曰寸彳均可。 ：由( 1 ) ( 2 ) ( 3 ) ( 4 ) 可知重心定理成立。 重心的概念用于解决两个平行工序的顺序优化问题时方便有效。平行工序顺序优化 的内容是人为设定平行工序的先后顺序，实质上是考虑有资源约束时如何安排项目计划 中平行工序开始时间的闯题。以项目工期延长量最小为目标时，重心定理的结果确保能 够得到如上问题的最优解。本文试图利用重心的概念解决项目使用的资源不止一种，发 生资源冲突的平行工序不止两个，且资源冲突也不止在一个计划阶段上发生的项目调度 问题。这类问题在项目进度管理的理论体系中属于r c p s p ，迄今为止已有5 0 年的历史， 已经发展成一个理论丰富，分类细致，结构完整的经典问题。参考文献中，我们发现有 众多学者针对这类问题提出了大量的模型、解法和算法，求解效果也在求解技术的进步 和所有研究人员的努力之下越来越优。但是，在众多的方法中，至今没有发现以重心概 念为优先规则的启发式方法。本文正是在这个背景之下开展了基于重心优先规则的启发 式方法研究。 9 华北电力大学硕士学位论文 第三章资源约束项目调度问题的概念、分类、模型与发展 3 1 资源约束项目调度问题的提出 传统的c p m 和p e r t 都假设项目使用的资源无限供给，但是在项目的实际执 行过程中，可以使用的资源往往受到一定的约束。某些可以同时开始的平行工序由 于资源约束，其开始时间只能向后推迟，等安排在前面的工序完成，释放出资源之 后才能开始进行。资源约束项目调度问题r c p s p 就是研究如何在满足工序间的 前后关系约束和资源约束的前提下，将有限的资源分配给各个工序，确定工序的实 际开始时间，并使项目工期最短。 资源约束项目调度问题的表述是，某一个项目由工序集合j = l ，2 ，l 组成， 其中工序0 和工序分别代表项目的首工序和尾工序。项目中的工序受前后关系约 束，即工序，在其紧前工序集只中的工序全部结束之前不能开始；同时，项目工序 受资源约束，假设项目中使用k 种资源，资源种类集合为r = l ，2 ，七 ，所有资源 的类型都是不可更新资源。项目工期以每天为单位，工序- ，在其工期乃内每天需要 。个单位的第k 种资源，k r 。项目中对第k 种资源每天可提供的容量( 供应量) 为 风。参数c ，。和置都是确定值。项目的首工序和尾工序的工期为0 ，且不需要 任何资源。r c p s p 问题就是在满足工序间前后关系约束和资源约束的条件下，确定 每个工序的开始时间，并使项目工期最短。 1 l5 墨。5 图3 - 1r c p s p 实例a o n 网络图 下面的例子是选自文献2 1 中的经典实例。图3 1 所示的是一个由n = 9 个工序组 成的a o n 项目网络图，项目中使用k = 1 种资源，这种资源每天可使用的容量足= 5 ， 1 0 。 华北电力大学硕士学位论文 最优项目工期为7 天的一个可行调度计划如图3 2 所示。 资源量 容量5 o7 天) 图3 2r c p s p 实例最优调度计划 以e 表示工序的完成时间，则这个项目的一个可行进度计划s 可以用工序完 成时间的向量表示，s = ( 最，最，目) 。假设4 = u - ，旧一乃f 巧 表示在f 时刻正 在进行的工序集合r c p s p 的一般模型为( c h r i s t o f i d e se ta 1 ) 【2 0 】： m i n 目 ( 3 一1 ) s t ，巧- r , c，= l ，乏，；i 0 ( 3 2 ) 艺s 爆 k k ；t 0( 3 3 ) 。只0_ ，= l ，2 ，n( 3 4 ) ( 3 1 ) 式为模型的目标函数，表示项目尾工序的完成时间最小，由于尾工序的工 期为0 ，目标函数值实际上等于项目工期；( 3 - 2 ) 式表示项目工序之间的前后关系约 束；( 3 - 3 ) 式表示在时刻t 同时进行的各个工序对第七种资源的需求量之和不超过第七 种资源的供应量；( 3 - 4 ) 式列举了模型中定义的决策变量。 资源约束项目调度问题除了多数的以项目工期最小化为目标函数外，还有的以 净现值最大化【2 0 1 ，成本最小化 2 1 】瞄1 等为目标函数。另外，根据项目工序执行方式的 不同，r c p s p 也分为不同的类型，如果项目工序的持续时间固定，且只消耗一定量 的资源，则称之为单模式资源约束项目调度问题( s i n g l e - m o d er c p s p ) 。上面的实例 问题就是单模式资源约束项目调度问题。如果项目工序的持续时间及其消耗的资源 有多种选择，工序的工期就不再是固定不变的，而是所耗用资源的函数，这类问题 称为多模式资源约束项目调度问题( m u l t i m o d er c p s p ) 1 2 q 。 3 2 资源约束项目调度方法综述 资源约束项目调度问题属于多元学科的交叉问题，该问题一出现就引起了运筹 学、应用数学、最优化方法、生产管理、项目管理等多门学科研究学者们的关注。 华北电力大学硕士学位论文 由于其算法复杂性的原因，又引起了计算数学领域的学者的重视。b l a z e w i c ze t a 1 ( 1 9 8 3 ) 证明了r c p s p 是由静态j o bs h o p 问题推广而来的一般化形式，因此属于 n p h a r d 问题【2 j 。在众多领域科研工作者的共同努力下，求解资源约束项目调度问题 的方法数量迅速增加，现在已经初步形成了一个比较完整的方法体系，这些研究成 果主要分为两大类：精确算法( e x a c ta l g o r i t h m ) 和启发式方法( h e u r i s t i ca l g o r i t h m ) 1 2 5 1 。精确算法包括分枝定界法( b r a n c ha n db o u n da l g o r i t h m ) ，数学规划中的0 1 规划 2 6 1 、动态规划【2 7 】等：启发式方法包括传统的基于优先规则的启发式方法【2 8 1 和试图寻 求局部最优解的现代优化算法，例如禁忌搜索( t a b us e a r c h ) 【2 9 1 、模拟退火 ( s i m u l a t e da n n e a l i n g ) 1 3 0 和遗传算法( g e n e t i ca l g o r i t h m ) 【3 u 等。 在使用0 - 1 规划算法时，求解变量随着工序的增加呈指数级增长，因此对它的 研究并不多。j o h n s o n 首先提出运用分枝定界法解决r c p s p 的思路，s t i n s o n ( 1 9 7 8 ) 【3 2 1 ，c h r i s t o f i d e s ( 1 9 8 7 ) 1 3 3 和d e m e u l e m e e s t e r ( 1 9 9 2 ) 1 3 4 等陆续提出用分枝定界法来 解决该类问题，从而求得最优解。但是由于分枝定界法运行时间较长，所以不适合 应用在大型项目中。 基于优先规则的启发式方法出现于精确解法之后，主要是为了弥补后者计算时 间长、效率低下、不适合实际运用等的缺陷。k e l l y 于1 9 6 3 年在文献【3 5 1 中首次提出 了解决经典的r c p s p 的启发式方法，文中提出的顺序调度方案和平行调度方案为后 来启发式方法的发展奠定了基础1 9 6 5 年，s h a f f e r 将分离弧( d i s j u n e t i v e a r c ) 弓i 入到 项目网络中以打破最小禁集( f o r b i d d e ns e t ) ，提出了r s m ( r e s o u r c es c h e d u l i n g m e t h o d ) 3 6 1 。之后，该研究领域的科学家和实际生产中的工程师相继提出了多种适用 的基于优先规则的启发式方法，共同促进了求解r c p s p 及同类问题的启发式方法的 发展。b o e t o r l 3 ”在1 9 9 0 年研究了将多个优先规则相结合生成可行进度计划与用一个 优先规则单独地生成可行进度计划的比较问题。1 9 9 3 年白思俊在文章1 ”1 中对启发式 方法进行了很全面的总结研究。 采用传统的方法多数情况下都可以得到可靠的可行解，但是在大型项目网络 中，这些方法计算量都很大。而且很难判定使用这些方法获得的解是不是最优。现 代优化方法的兴起，克服了上述的缺陷，逐渐地应用到该领域中，这些方法包括 k o l i s c h ( 1 9 9 6 ) 的禁忌搜索方法( t a b us e a r c h ) 、b o u l e i m e n ( 1 9 9 8 ) 的模拟退火方法 ( s i m u l a t e da n n e a l i n 曲、h a r t m a n n ( 1 9 9 8 ) 的遗传算法( g e n e t i ca l g o r i t h m ) 等。k o l i s c h 和h a r t m a n n ( 2 0 0 0 ) 在对大多数启发式方法进行比较时，发现模拟退火法和遗传算法 的性能是最好的【”j 。 1 2 华北电力大学硕士学位论文 第四章基于重心优先规则的启发式方法研究 本章阐述了基于重心优先规则的启发式方法，并通过一个简单的实例说明了方 法的可行性和实用性。 4 1 基于优先规则的启发式方法起源 基于优先规则的启发式方法就是对项目中存在潜在资源冲突的平行工序按照 规则排列优先次序，通过推迟安排优先系数较低的工序来满足资源约束的项目调度 方法。在所有类别r c p s p 解法中，基于优先规则的启发式方法出现于最优化解法之 后，主要是为了弥补最优化解法效率较低的不足，以适应求解大型项目的实际需要。 早在1 9 6 1 年，l e v ye ta 1 就在其文献m 】中提出了一种称为r a m p s 的用于多项 目资源约束调度问题。k e l l y 于1 9 6 3 年在文献【3 习中首次提出了解决经典的r c p s p 的启发式方法，文中提出的顺序调度方案和平行调度方案为后来启发式方法的发展 奠定了基础。1 9 6 5 年，s h a f f e r 将分离弧( d i s j u n c f i v ea r c ) 弓i 入到项目网络中以打破最 小禁集( f o r b i d d e ns e t ) ( 最小禁集，即项目中存在潜在资源冲突的平行工序的最小集 合，去掉集合中的任意一个工序，该集合就不再造成资源冲突) ，提出了r s m ( r e s o u r c e s c h e d u l i n g m e t h o d ) p ”。之后，该领域的科学家和实际生产中的工程师都相继提出了 理想适用的启发式方法，b r o o k ( 1 9 6 3 ) 、w e s t ( 1 9 7 6 ) 、d a i v s ( 1 9 7 3 1 9 7 4 ，1 9 7 5 ) 、 b e d w o r t h ( 1 9 7 3 ) 、w o o d w o r t h 和w i l l i e ( 1 9 7 5 ，1 9 7 6 ) 、b t o w n ( 1 9 7 6 ) 、t h e s e n ( 1 9 7 6 ， 1 9 7 8 ) 、w h i t c h o u s e 和b r o w n ( 1 9 7 9 ) 、e l s a y e d ( 1 9 8 2 ) 、e l a s a y e d 和n a s r ( 1 9 8 6 ) 、u l u s o r 和o z d e m r ( 1 9 8 9 ) 等人分别提出了不同的启发式方法，共同促进了求解r c p s p 及 同类问题的启发式方法的发展，l a w r e n c e ( 1 9 8 5 ) 、a l v a r e z v a l d c sa n d t a m a r i t ( 1 9 8 9 曲 和白思俊在文献【4 1 1 、h 2 1 和【3 8 1 中对这些启发式方法进行了总结。 尽管基于优先规则的启发式方法是解决r c p s p 的最古老的方法之一，但是在今 天，它仍然是生产实际中最重要、使用最多的方法。这是因为，基于优先规则的启 发式方法操作简单方便，且容易被商业软件采用，耗费的计算时间相对较短，无论 对于多大规模多么复杂的项目，都可以在人们可以接受的时间内给出结果，这是它 与其他局部寻优算法( 如人工智能算法) 相比的优越之处。现在，人们可以从多种 待选启发式方法中选择一个或是通过多种启发式方法的结合，计算问题的最优解或 较优解。基于优先规则的启发式方法的实用性因素使得研究者们从未放松过对它的 研究，这些研究工作既包括新方法的提出也包括对各种方法在计算效果和效率上的 比较评价。 华北电力大学硕士学位论文 4 2 基于优先规则的启发式方法调度生成方案 一般，基于优先规则的启发式方法由调度生成方案和优先规则两部分组成。调 度生成方案包括两类，即顺序调度生成方案和平行调度生成方案1 4 4 1 。这两种方案对 应两类常用的基于优先规则的启发式方法，即顺序调度法和平行调度法。这两种调 度生成方案都是在部分调度计划的基础上逐步生成完整的可行调度计划。部分调度 计划就是只安排了项目中部分工序的调度计划。在每一步迭代中，用优先规则确定 存在潜在资源冲突的工序的先后安排顺序，不能在该步迭代中安排进入调度计划的 工序被推迟到下一步，参加下一步的迭代【4 3 1 。 4 2 1 顺序调度生成方案 顺序调度生成方案以工序为处理目标，由，步迭代组成，= l ，2 ，j ( ，为项目 中工序的个数) 。每步迭代都考虑一个开始时间点t ，和两个不相容的工序集合c ，和 层，c ，是到本步迭代开始前已被安排进入调度计划的工序集合，e ，是在本步迭代 可以被安排进入调度计划的工序集合。所谓可以被安排进入调度计划的工序，是指 那些未被安排调度计划而其紧前工序都已被安排进入调度计划的工序。 在每一步迭代中，首先确定迭代开始时间点t ，即c ，中完成时间最早的工序 的完成时间。然后确定e ，e ，由两部分组成，即占。中未被安排进入调度计划的工 序集合l e 。和在t ，时刻完成的工序的紧后工序中其紧前工序已全部完成的工序的 集合。先对e ，中的工序按照所选择的优先规则排列先后次序( 优先系数相等的工序 按照编号先后排列) ，再按照这个次序逐个检查每个工序是否满足资源的约束，跳 过不满足资源约束的工序，对于满足资源约束的第一个工序在尽可能早的开始时刻 安排其进入调度计划，并将这个工序从e ，移到c ， 顺序调度生成方案在经典的机器排序中起着重要的作用【4 5 】【4 6 】，且对于一般的 r c p s p ，顺序调度生成方案总能够生成一个最优的调度计划，这也是和平行调度生 成方案相比的优点所在。 4 2 2 平行调度生成方案 平行调度方案最早由k e l l y 提出，其算法有k e l l y 式算法和b r o o k s 式算法两类 p ”。在文献中，研究人员引用后者较多，本文也选择后者作为研究对象。平行调度 方案都是以时间为处理对象，由n 步迭代组成，每有工序完成即开始一步迭代每 步迭