（管理科学与工程专业论文）基于蚁群优化算法的资源受限项目调度问题研究.pdf

基于蚁群优化算法的资源受限项目调度问题研究 摘要 项目管理是管理科学的一个重要分支，项目计划与调度是项目管理的重要 组成部分，项目调度方面的研究对于发展项目管理理论、提高项目管理水平有 重要意义。 考虑到资源受限项目调度问题已经被证明是n p 难问题，我们试图将蚁群优 化算法应用于该问题的求解。蚁群优化算法是受自然界中真实蚁群觅食行为的 启发而提出的一种智能优化算法，在求解t s p 等组合优化问题中表现优良，为 资源受限的项目调度提供了高效的求解方法。 本文主要工作包括以下内容：( 1 ) 总结了国内外资源受限项目调度问题研 究现状的基础上，对几种比较重要的求解方法进行了比较；( 2 ) 总结概括蚁群 优化算法的研究现状，深入研究几种重要的改进算法，总结蚁群优化算法的应 用领域，讨论该算法应用于资源受限项目调度问题的基本思路；( 3 ) 在此基础 上设计了一种基于蚁群优化算法的单执行模式资源受限项目调度问题优化算 法。该算法以满足紧前关系的工作链表作为人工蚂蚁的巡游路径，针对问题特 点设计了信息素及启发式信息策略，采用伪随机比例规则。根据正交法设计实 验，并采用项目调度标准问题库中的基准问题进行试验。实验结果验证了算法 的有效性；并通过对计算结果的分析得到了算法的优化解参数设置，在此参数 设置下对较大规模的基准问题进行求解，得到了较好结果。最后对全文进行总 结并提出未来研究方向。 关键词：项目管理项目调度资源受限蚁群优化算法串行调度 4 r e s e a r c ho nr 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 ep r o b l e m b a s e do na n tc o l o n yo p t i m i z a t i o n a b s t r a c t p r o j e c tm a n a g e m e n ti sa ni m p o r t a n tb r a n c ho fm a n a g e m e n ts c i e n c e p r o je c t p l a n n i n ga n ds c h e d u l i n gi sa ni m p o r t a n ta r e ao fp r o j e c tm a n a g e m e n t t h er e s e a r c h o np r o j e c ts c h e d u l i n gi s i m p o r t a n tf o rt h ed e v e l o p m e n to fp r o j e c tm a n a g e m e n t t h e o r y r e s o u r c ec o n s t r a i n e dp r o je c ts c h e d u l i n gp r o b l e m sh a v e b e e np r o v e dt ob e n p h a r d w et r yt oa p p l ya n tc o l o n yo p t i m i z a t i o na l g o r i t h mt ot h i sp r o b l e m a n t c o l o n yo p t i m i z a t i o ni sa ni n t e l l i g e n to p t i m i z a t i o na l g o r i t h m ，d e r i v e df r o mt h er e a l f o o ds e e k i n ga c to fa n tc o l o n y ，a n di tp e r f o r m sw e l lo nc o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e ms u c ha st s pe t c t h ep r i n c i p a lt a s k sin clu d e ： ( 1 ) b a s e do nt h es u m m a r yo fs t a t u sq u oo nt h er e s o u r c ec o n s t r a i n e dp r o je c t s c h e d u l i n gp r o b l e m ，p r e s e n t sac o m p a r i s o no fm a i ns o l u t i o n si sp r e s e n t e d ( 2 ) a n a l y s e ss t a t e s o ft h ea r to fa n tc o l o n yo p t i m i z a t i o na n ds e v e r a l i m p o r t a n ti m p r o v e da l g o r i t h m s b ys u m m a r i z i n gt h e m a i na p p l i c a t i o n a r e a s ， d i s c u s s e st h ef e a s i b i l i t yo ft h i sa p p l i c a t i o ns t u d y ( 3 ) p r e s e n t sa na l g o r i t h mb a s e do na n tc o l o n yo p t i m i z a t i o nf o rt h es i n g l e m o d er e s o u r c ec o n s t r a i n e dp r o j e e ts c h e d u l i n gp r o b l e m ，u s i n gp r e c e d e n c ej o b c h a i na sa r t i f i c i a l a n t s t o u r i n gr o u t e 。w ed e s i g np h e r o m o n e a n dh e u r i s t i c i n f o r m a t i o n s t r a t e g y a n d p s e u d o - r a n d o m r u l e sa c c o r d i n gt ot h er e s o u r c e c o n s t r a i n e dp r o je c ts c h e d u l i n gp r o b l e m t h i sp a p e ra l s od e s i g n sa no r t h o g o n a l e x p e r i m e n tb yt h ei s s u eo ft h eb e n c h m a r k t e s t s t h er e s u l t so ft h ee x p e r i m e n ts h o w e f f e c t i v e n e s so ft h ea l g o r i t h m ，a n dt h er e l a t i o n s h i pb e t w e e nt h ea l g o r i t h m p a r a m e t e r sa n dt h ea l g o r i t h mp e r f o r m a n c e p e r f o r m st e s t sb yl a r g es c a l eb e n c h m a r k i n s is t e n c e s ，a n dg o o dr e s u l t sa r ea c h i e v e d f i n a l l y ，t h ew h o l es u mu pa n da n o u t l o o ko nf u t u r er e s e a r c ha r ep r e s e n t e d k e y w o r d s ：p r o j e c tm a n a g e m e n t ；p r o j e c ts c h e d u l i n g ；r e s o u r c ec o n s t r a i n e d ；a n t c o l o n yo p t i m i z a t i o n ；s e r i a ls c h e d u l i n g 5 表格清单 本文论述中所用到的参数及其含义1 1 优先规则列表1 5 基本蚁群算法参数及意义一2 0 蚁群优化算法应用领域一览一2 5 j 3 011 问题2 8 实验参数、含义及水平3 3 p s p l i b 特性参数列表3 4 调度计划a 3 9 调度计划b 一4 0 调度计划c 4 0 三组实验统计数据比较4 l j = 1 2 0 基准问题计算结果4 1 9 1 2 1 2 1 2 3 4 5 6 7 8o孓舡舡缸舢舢缸舡舢表表表表表表表表表表表表 插图清单 信息素作用示意图一1 9 算法流程图一3 2 实验系统流程图3 4 q o n 关系图一3 7 a l p h a n 关系图3 8 a l p h a n 关系图，q o = o 1 一3 8 a l p h a n 关系图，q o = o 9 一3 8 r h 0 1 1 1 关系图3 8 r h o1 n 关系图，q o = o 1 3 9 r h 0 1 n 关系图，q o = o 9 3 9 l o 1 1 2 3 4 5 6 7 8 9孓舡舡舡舡舡舡缸舡舢图图图图图图图图图图 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 金目曼王些态堂或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签字： 学位论文版权使用授权书 本学位论文作者完全了解 金月巴王些厶堂 有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人 授权 金蟹王些太堂可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名： 陡好、，、 l j 导师签名： 任叫红 签字日期：可旷嚼年r 月侈日 签字日期：2 叩铲亏月f 弓日 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 3 致谢 值此论文完成之际，谨向我的导师任明仑老师致以最衷心的感谢和最崇高 的敬意! 感谢任老师在学业上对我的谆谆教导，感谢任老师在撰写论文期间给 予我的细心指导和帮助。任老师渊博的专业知识，严谨的治学态度，精益求精 的工作作风，诲人不倦的高尚师德，严以律己、宽以待人的崇高风范，朴实无 华、平易近人的人格魅力对我影响深远。不仅使我树立了远大的学术目标、掌 握了基本的研究方法，还使我明白了许多待人接物与为人处世的道理。 感谢合肥工业大学计算机与网络研究所的杨善林老师、胡小剑老师、马溪 骏、余本功等老师对我的关心、指导和帮助，感谢网络所所有同学对我在学习 和生活上的关心和帮助。 感谢我的父母这么多年来对我学业的支持，他们的关爱是我在漫长的求学 路上支持下来的精神源泉。在论文完成之际，我愿与他们分享其中的甘苦，并 感谢他们对我殷切的期望和无私无悔的支持。 感谢各位论文评审专家，感谢他们在百忙中抽出时间对我的论文进行了仔 细的评阅。 在此，向所有帮助和关心过我的人们致以最衷心的感谢1 6 第一章绪论 项目是人们为了实现一定的目标而进行的一次性的、临时性的任务。实践 中所指的项目管理是为完成项目目标而进行的计划、组织、指挥、控制和协调 等一系列管理活动。作为学科名词的项目管理指的是项目管理实践中所应用的 理论、方法、技术的总和。一般意义上的项目计划指的是围绕项目目标实现， 对各项项目组成工作的实施做出的安排，包括项目任务确定、任务进度安排、 资源分配方式等方面。本文中所提到的项目调度计划是对一般意义进行简化的 概念，仅对各项工作的计划开始时间做出规定。合理的项目优化调度能显著提 高项目管理水平，进行相关领域的研究有广泛的应用前景和很高的研究价值。 本文尝试从智能优化算法与项目优化调度相结合的角度进行研究，实现一种基 于蚁群优化算法的资源受限项目调度问题求解方法。 1 1 研究背景与意义 一般认为，项目是一项专门任务，是在一定的组织机构内，在限定的资源 条件下，在计划的时间里，按满足一定性能、质量与数量的要求去完成的一次 性任务1 1j 。社会发展过程中曾经出现过众多各式各样的项目，大量项目实践的 积累推动了项目管理理论的发展，逐步经历了潜意识的项目管理、传统的项目 管理和现代项目管理几个阶段。今天项目管理已经广泛应用于各行各业，同时 项目管理也由最初的工程管理发展成为拥有较为完整理论的独立学科。 现代项目管理作为一种系统的管理理论和技术，最早出现于2 0 世纪4 0 年代 美国军方的武器研制活动。经过半个多世纪的发展，现代项目管理已经形成了 一套完整的理论和知识体系，主要包括项目组织、管理和实施等方面的概念、 工具、技术，涵盖项目管理的全过程，广泛应用于建筑工程、软件开发、飞机 及轮船制造等单件或小批量生产方式的企业中。随着企业间竞争的加剧，市场 的不确定性和风险日益提高，产品的生命周期日益缩短，企业迫切需要改革以 往不合理的管理方式，引入先进的管理方法，以适应市场环境的要求。在这样 的情况下，现代项目管理作为一种有效的管理方法体系，受到了各行业的重视， 并在实践中广泛应用，创造了巨大的经济效益和社会效益。 随着经济发展水平不断提高，全球经济一体化进程不断推进，现代项目越 来越趋于大型化、复杂化，要求工期更短、成本更低。再加上行业细分越来越 发达，企业间联系日趋紧密，企业必须加强合作，以获得最大的竞争优势。这 种组织结构和管理模式越来越体现出面向项目( p r o j e c t o r i e n t e d ) 的特征【2 】。这 种新情况给项目管理带来了更高的要求。如何在更短时间内，在保证质量的前 提下，以更低的成本完成项目，成为项目管理人员关心的问题。探索适用范围 更广、能更好地指导项目管理实践的理论、方法，不断推进项目管理研究，吸 引了许多学者进行相关领域的研究。 项目调度( p r o j e c ts c h e d u l i n g ，p s ) 作为项目管理的一个重要部分，其目 的是通过合理地确定各项工作的开展顺序、开始及完成时间，使项目目标最优 化【3 j 。项目管理知识体系的一个重要组成部分就是各种项目调度工具。传统的 调度方法在时间、资源约束不太强的情况下表现较好。特别值得一提的是在实 践中得到广泛应用的网络计划技术，曾经在美国大力推进的军方项目中起到很 大作用。但是这些调度方法一个很明显的缺点是没有考虑资源约束，导致所制 定的调度计划在实施中经常要做较大的改动，由此产生了资源受限项目调度问 题。 在有限的资源约束下达到某种最优目标( 如最小化项目周期) 的问题称为 资源受限的项目调度问题( 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 m ， r c p s p ) 。这类问题广泛存在于新产品的开发、单件全订货型( e n g i n e e r i n gt o o r d e r ) 生产的规划与调度管理、基建项目施工调度等领域，在现代化企业中显 示出重要的研究价值。在理论上，该问题模型丰富，而且多属于n p h a r d 问题， 一直吸引着国内外众多学者的关注和研究。 1 2 项目调度发展过程 项目调度技术是项目管理知识体系的一个重要组成部分。传统的计划技术 有：甘特图( 或称横道图，g a n tc h a r t ，g c ) 、关键活动图、网络计划技术。 几种典型的网络计划技术有：关键路线法( 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 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 d m ) 、图解评审技术( g r a p h i c a le v a l u a t i o na n dr e v i e w ，g 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 wt e c h n i q u e ，v e r t ) 。 甘特图是最早的项目调度方法，该方法形象直观、易于掌握，便于检查和 计算资源需求量【4 j 。这些优点使甘特图在实际项目调度中得到广泛应用。但是 甘特图也存在一些明显的不足：不能体现工作间的相互依赖关系，从而制定的 项目计划无法保证满足时序约束；不能体现工作过早开始或过晚开始所造成的 后果，不利于项目进程的动态控制；适用于小型项目，处理问题的规模有限， 难以应用于大型、复杂的项目调度问题。 网络计划技术是用网络计划对任务的工作进度进行安排和控制，以保证实 现预定目标p j 。网络计划由两部分组成，网络图和网络参数。网络图是由箭线 和节点组成的，用于表示工作流程的有向、有序的网状图形。网络参数是根据 各项工作的延续时间和工作间顺序依赖关系计算得到的反映各种工作时间的参 数。 关键路线法和项目计划评审技术是两种比较著名的网络计划技术，兴起于 2 2 0 世纪5 0 年代的美国，在项目管理实践中有广泛的应用。这两种方法相似，都 是采用平面网络结构表示项目的工作细分结构，很好的反映了项目各组成工作 之间的时序依赖关系，体现了高度的逻辑性。两种方法的区别在于对项目中各 工作的执行时间的估计方法。关键路线法采用一点估计法，即直接根据历史数 据和以往经验给出唯一的估计值，不考虑执行过程中可能出现不确定因素，适 用于各工作的执行时间能够在很大程度上根据以往知识确定的项目，如建筑工 程项目。显然这种估计方法可能会造成与项目实际情况的较大偏差。项目计划 评审技术进行了一定的改进，采用三点估计法，即以经验丰富的项目管理者所 掌握的完成一项工作所需的可能最少时间、可能最多时间及最大可能时间为基 础，采用下式得到工作的估计执行时间 口d - 4 mq - b el = ( 1 - 1 ) 6 其中，a 为对工期的乐观估计值；m 为对工期的最可能估计值；b 为对工期的 悲观估计值。为了衡量实际工期发生偏离的可能性大小，项目计划评审技术引 入了数理统计中方差的概念，采用如下公式进行计算： 仃2 ：( 掣) 2 ( 1 2 ) z ：墼z d - - i e( 1 - 3 ) 厶丽 “。3 其中，仃2 为单一工作工期方差；z 为总工期方差；瓦为设定的项目完成时 间；砭为利用计算出的e t 值求解出的项目总工期；仃r 2 p 为关键线路上各关键作 业工期的方差。第一步估算各工作工期可能产生的偏差，第二步在此基础上计 算总工期偏差。 以上两种计划技术相比，关键路径法较为简便，计算简单，易于理解。但 是，没有考虑实际工作执行时间与估计时间的偏差，所制定的计划质量较低。 网络计划评审技术通过应用数理统计的基本理论，对实际工期可能发生的变化 给项目进度带来的影响进行了定量分析，能够得到质量较高的计划。但是这两 种方法的一个共同缺点是没有考虑资源约束，即假设资源是无限的。这种假设 显然与实际情况不符合，采用这两种方法编制的项目计划在资源受限的情况下 往往无法顺利实施，由此便产生了资源受限项目调度问题。 1 3 资源受限项目调度问题研究现状 项目管理的核心问题之一是项目计划与优化调度的理论与方法。资源受限 项目调度属于生产调度的范畴，自2 0 世纪6 0 年代提出以来，许多运筹学、应用 3 数学等领域的学者进行了这一领域的研究。已有的研究主要是在假设项目信息 完全已知的确定性环境下设计优化调度方法，以求得在某一目标下最优的项目 调度计划。优化方法包括分支定界算法、基于优先规则的启发式算法、智能优 化算法等。随着项目规模增大、复杂度的提高，传统的项目调度方法已经无法 完全满足现代项目管理的实际需求，这一矛盾推动了项目调度领域的研究。资 源受限项目调度问题的研究主要包括四个方面的内容：优化目标与资源类型、 问题模型、调度方案、基准问题。下面从这四个方面对资源受限项目调度问题 的研究现状进行总结。 1 3 1 优化目标及资源分类 根据已有研究，资源受限项目调度问题的优化目标有多种，如最小化项目 工期、最小化资源消耗、最大化网络收益、时间成本权衡、最大净现值等。大 致分为三类：1 ) 最小化工期问题，在满足时序约束和资源约束的条件下，确定 所有工作的开始时间，使项目工期最短；2 ) 资源均衡问题，合理安排项目各活 动进度，解决资源供需矛盾，可进一步按照优化资源目标的方式细分为规定工 期的资源均衡问题和有限资源的合理分配问题；3 ) 现金流优化问题，以最大净 现值为优化目标，建立带有贴现率的最大化网络净现值的数学模型，采用优化 策略使目标最优。 资源类型对问题复杂程度有很大影响。按照s l o w i n s k i t 6 m 和w e g l a r z 8 的 分类方式，项目资源可以分为三类：1 可更新资源，这类资源的消耗和获得是 以项目调度阶段为基础的。例如劳动力和机器资源，它们在每一项目调度阶段 的获得是有限的，但消耗之后在下一阶段可更新。2 不可更新资源，这类资源 的获得和消耗是以项目的总工期为基础的。例如资金、能源和原材料资源，这 些资源在消耗之后就不会再有了。3 双重约束资源，这种资源的获得和消耗既 在工期的每一阶段受限，又在整个工期的总量上受限，这种资源约束可以通过 增加可更新资源和不可更新资源约束来代替，一般不予考虑。可更新资源根据 获得量是否随时间变化又分为随时间可变资源和随时间不可变资源。 1 3 2 问题模型 r c p s p 在4 0 多年的发展过程中模型不断得到丰富，可进一步分为单执行模 式资源受限项目调度问题( s i n g l em o d er e s o u r c e c o n s t r a i n e dp r o je c ts c h e d u l i n g p r o b l e m ，简称s r c p s p ) 、多执行模式资源受限项目调度问题( m u l t i m o d e 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 m ，简称m r c p s p ) ，离散时间 成本权衡项目调度问题( d i s c r e t et i m e c o s tt r a d e 0 f fp r o b l e m ，简称d t c t p ) 、 单执行模式资源水平问题( s i n g l em o d er e s o u r c el e v e l i n gp r o b l e m ，简称s r l p ) 、 多执行模式资源水平问题( m u l t i m o d er e s o u r c el e v e l i n gp r o b l e m ，简称m r l p ) 、 带最d , 最大时间滞后的资源受限项目调度问题( r c p s p m a x ) 【1 0 儿1 1 】【12 1 、以最 大净现值为目标的资源受限项目调度问题( n e tp r e s e n tv a l u e ，简称n p v ) 【1 3 】等。 4 1 3 3 求解方法 资源受限项目调度问题正式提出之后很快引起了学者的注意，相关领域的 研究进展很快，取得了很多成果，陆续提出了有针对性的优化方法。这些方法 主要可以分为精确算法和启发式算法两类引。 初期的研究主要集中于用数学规划方法来对这类优化调度问题进行建模和 求解，采用整数规划的手段来求解这类优化调度问题的精确解。之后提出了分 支定界方法，这种方法能在较低计算成本下获得较小规模问题的精确解。经过 很多学者的不断努力，在计算机技术快速发展的基础上，分支定界算法的求解 能力和求解速度得到了大幅度的提高。c h r i s t o f i d e s 等人引入冲突工作集n g 和 替代集a ( i ) 概念，提供了新的分支定界算法研究方向【”】。d e m e u l e m e e s t e r 等 人发展了替代集的思想，提出基于最小延迟替代集概念的分支定界算法，并结 合先进的计算机技术改进了算法，取得了良好效果【l 引。p a t t e r s o n 等人提出了基 于紧前关系树概念的分支定界算法【l7 】，s p r e c h e r 等人针对对该分支方法提出了 多种定界方法，采用p s p l i b 中s r c p s p 的4 8 0 个问题进行的求解实验表明该算法 是最好的精确算法之一【1 8 j 。 启发式算法主要包括传统基于优先规则的启发式算法、采样算法和智能优 化算法等。k e l l y 提出了串行调度方案和并行调度方案，指出了重要的研究方向 【l 引。陆续有学者在此基础上提出了采用不同优先规则的算法，第二章中总结了 其中的一些。采样算法采用了与传统基于优先规则的算法不同的优先权系数利 用方式，引入了概率式选择的方式。许多学者进行了这方面研究，先后提出了 随机采样算法( r a n d o ms a m p l i n g ，r s ) 、带有偏好的随机采样算法( b i a s e d r a n d o ms a m p l i n g ，b r s ) 1 2 、基于后悔值的随机采样算法( r e g r e t b a s e dr a n d o m s a m p l i n g ，r b r s ) 1 2 ，等等。应用于r c p s p 的智能优化算法主要有模拟退火 ( s i m u l a t e da n n e a l i n g ，s a ) 2 2 儿2 3 1 、禁忌搜索( t a b us e a r c h ，t s ) 2 4 1 和遗传 算法( g e n e t i ca l g o r i t h m ，g a ) 【2 5 】【2 6 1 等方法【2 7 儿2 引。 另外，以色列学者高德拉特将约束理论( t h e o r yo fc o n s t r a i n t s ，t o c ) 应 用于项目管理领域，提出了基于关键链的项目管理理论，从中发展出一种新的 项目调度理论：基于关键链的项目调度理论【3 。 1 3 4 基准问题 衡量各种r c p s p 优化方法的可行性和效率需要标准化的项目调度问题实 例，如何生成这些问题实例也是r c p s p 研究的一个重要方面。r c p s p 提出之后， 很快在模型建立以及求解方面取得了进展。与此同时，在基准问题的系统化生 成方面进行的研究却相对较少。根据掌握的资料，唯一明确地对项目调度问题 实例生成器进行讨论的文献是d e m e u l e m e e s t e r 等人的论文。文章中提出了一种 依据节点数及弧数随机生成网络图的问题生成器。除了d e m e u l e m e e s t e r 等人之 外，还有a l v a r e zv a l b e s 和t a m a r i t ( 1 9 8 9 ) ，d r e x l ( 1 9 9 1 ) ，k u r t u l u s 和d a v i s 5 ( 1 9 8 2 ) ，p a s c o e ( 1 9 6 6 ) ，p a t t e r s o n ( 1 9 8 4 ) ，p a s c o e ( 1 9 6 6 ) ，d a v i s ( 1 9 8 2 ) ， c o o p e r ( 1 9 7 6 ) 以及p a t t e r s o n ( 19 9 0 ) 等学者，陆续发表了各自获得测试问题 的方法。 1 9 8 4 年，p a t t e r s o n 比较了四种以项目工期最小化为目标的求解包含1 l o 项工 作的s r c p s p 的精确算法，其研究所使用的测试问题被许多其他学者认可，应 用于各自的研究。包括b e l l 和h a n ( 1 9 9 1 ) ，d e m e u l e m e e s t e r 和h e r r o e l e n ( 1 9 9 2 ) ， 以及s a m p s o n 和w e i s s ( 19 9 3 ) 都使用过p a t t e r s o n 问题集，从而使该问题集近似 于标准测试问题集。 r k o l i s c h 等人在基准问题生成领域进行的研究成果显著。r k o l i s c h 、 a s p r e c h e r 等人对如何生成控制难度下的同时存在紧前关系约束和资源约束的 项目调度问题实例进行了研究，提出了一种项目网络生成方式，主要考虑以下 几点：1 ) 网络拓扑约束；2 ) 资源因素；3 ) 资源强度。深入的计算研究证实， 所选参数有效反映了问题的特性。所得出的结果说明，以往研究所使用的测试 问题复杂度并不高。另外，研究表明有的规模并不大的测试问题可能难度相当 大，要得到这些问题的最优解可能需要很长的时间，这说明问题的难度不仅仅 由规模决定。 r k o l i s c h 等人在研究中提出了一个测试问题生成器p r o g e n ，可以根据参数 设置生成测试问题。实验证明这些参数可以有效的控制生成的测试问题的难度。 标准项目生成器p r o g e n 生成的测试问题构成了项目调度问题库( p s p l i b ) 的主 体。k o l i s c h ，r 和a s p r e c h e r 详细阐述了p s p l i b 中各种模型所代表的问题类型、 问题生成的细节、生成问题的实验设计、问题参数等【3 l 】【3 2 1 。之后，r k o l i s c h ， c s c h w i n d t 和a s p r e c h e r 等学者通过研究提出了另外的一些测试问题，对 p s p l i b 进行补充p 引。p s p l i b 逐渐发展成为包含了多种类型的r c p s p 的问题集， 以及这些问题的最优解和启发式解法。这些数据可以用来评价单执行模式或多 执行模式r c p s p 的解法，从而被很多这一领域的研究所采用。r k o l i s c h 、 s h a r t m a n n 将针对p s p l i b 中的实例而设计的启发式方法进行了精确的比较【3 4 1 。 1 4 本文主要工作及文章结构 在对r c p s p 和a c o 进行了深入研究的基础上，本文设计了一种基于a c o 的 s r c p s p 优化算法。该算法以满足紧前关系的工作链表作为人工蚂蚁的巡游路 径，针对问题特点设计了信息素及启发式信息策略，采用伪随机比例规则。对 结果的分析显示了问题参数设置与算法性能之间的关系，并在所得的参数设置 下对较大规模的问题进行了求解实验，取得了良好结果，表明这是一种可行的 s r c p s p 求解算法。 本文结构如下：第一章，介绍本文研究意义，概括资源受限项目调度问题 的国内外研究现状，指出本文主要研究内容；第二章，介绍资源受限项目调度 6 问题的基本概念、定义、定理，以及主要解决方法，并对这些方法进行比较； 第三章，分析研究蚁群算法的基本思想、基本原理及几种典型的改进型算法， 总结蚁群算法的主要应用领域；第四章，结合s r c p s p 的特点，设计相应的信 息素和启发式信息策略，利用p s p l i b 中的基准问题对提出的算法进行检验并对 实验结果进行分析，根据较小规模基准问题的求解结果得到了算法优化解参数 设置，并在此参数设置下对较大规模问题进行了求解实验，取得了较好的结果； 第五章，总结全文并提出未来的研究方向。 7 第二章资源受限项目调度基本理论 本章首先对r c p s p 作简要概述，并介绍r c p s p 的一些基本概念和特性参数； 然后从基本模型、定义、定理等方面对s r c p s p 做详细介绍，阐述主要的求解 方法，并对这些方法进行分析比较。 2 1r c p s p 概述 r c p s p 是复杂的生产调度问题，同时处理时序约束和资源约束的要求增大 了问题的求解难度。一般认为，在r c p s p 中，项目由一系列相互关联的工作组 成，这种关联体现在工作间的前后次序上。每项工作可能有几种不同模式，所 谓模式是指完成该工作所需的不同的工期和资源条件组合。问题的解是满足时 序约束和资源约束条件下，规定了各工作的开始时间和完成时间的调度方案， 这一方案应当满足使预定目标最优化的要求。根据不同的优化目标、资源类型、 问题模型，r c p s p 可以划分为很多种类，下面对一般的情形作简要介绍。 2 1 1 典型r c p s p 典型的r c p s p 可以描述为：在一个项目中，包含着j 项工作。使用j = l ，2 ， j 表示包括所有工作的集合。其中的每个工作一旦开始执行不允许被打断。记 p j 为工作j 的紧前工作集，s j 为工作j 的紧后工作集。工作j 只能在它的全部紧前工 作都完成之后才能开始。整个项目的结构用一张a o n ( a c t i v i t yo nn o d e ) 有向 网络图表示，图中节点代表工作，弧线代表工作间关系。图中各工作按顺序编 号，确保p i 中的工作编号小于j 。工作1 是唯一最早开始的工作，即项目起点； 工作j 是唯一最晚完成的工作，即项目收尾，均为虚工作( 执行时间为0 且不消 耗资源) 。项目调度计划可以用j 元组s = ( s l ，s 2 ，s j ) 表示，其中s j 为工 作j ( j _ 1 ，2 ，j ) 的计划开始时间。一个可行调度方案应当同时满足紧前 关系约束及资源约束。 一般情形下，一项工作的实施可以在增加投入缩短工期与减少投入延长工 期之间进行选择。r c p s p 通过给工作设定多种执行模式来反映这种现实情况。 设工作j ( j _ l ，j ) 必需选择m j 种执行模式( 或称为执行方案，对应于一定 的执行时间、可更新资源需求、不可更新资源需求) 之一执行，并且在执行过 程中不能中断或改变执行模式。在第m ( 1 m m j ) 种模式之下执行工作i 需要 第k ( k = l ，k ) 种可更新资源量为，需要第1 1 ( n = l ，n ) 种不可更 新资源量为，二。，执行时间为d j m 。通常将工作执行模式按照d i m 从小到大顺序排 列，即d j l _ d j 2 ，- 0 完成工作j 所需的第k 种可更新资源的消耗量 r 第k 种可更新资源的总量 s t j工作j 的计划开始时间 e s j 工作j 的最早开始时间 e f j工作j 的最早完成时间 l s j工作j 的最迟开始时间 l f j工作j 的最迟完成时间 p j 工作j 的紧前工作集合 其中，e s i 、e f j 、l s i 、l f i 根据p e r t 方法计算。 2 2 2 基本定义、定理 在已经进行的研究中，为了便于分析问题，逐渐形成了一系列广为认可的 定义，下面列举的是一些进行s r c p s p 研究所需的基本定义。 定义2 1 设s t j 为s r c p s p 中工作i 的开始执行时间，则称j 元组s = ( s t l ， s t 2 ，s t j ) 为s r c p s p 的一个调度计划，或称为s r c p s p 的一个解。同时 满足紧前关系约束和资源约束的调度计划称为可行调度计划。 定义2 2 设s = ( s t l ，s t 2 ，s t j ) 为s r c p s p 的一个可行调度计划， ( s ) 为s r c p s p 的极小化目标函数，如果( s ) 是s t j ( i _ l ，2 ，j ) 的单 调递增函数，即m ( s ) ( s ) 暗示s t j _ s t j ( j = l ，2 ，j ) ，且j i ，1 j j ， s t j s t i ，则称( s ) 为正规目标函数，否则称西( s ) 为非正规目标函数。 定义2 3 对于s r c p s p 的一个可行调度计划s ，改变工作i 的开始时间为s t i ， s t i s t i ，其他工作的开始执行时间保持不变，如果改变后的调度计划仍为可 行计划，则称此操作为左移操作( 1 e f ts h i f t ) 。 对于正规目标函数( s ) ，如果可行调度计划s 经左移操作得到计划s ， 则s 优于s 。 定义2 4 对于s r c p s p 的可行调度计划s ，如果经过对工作i 的左移操作可以 得到计划s ，且s t j s t j = l ，则称此左移操作为单步左移操作( o n e p e r i o dl e f t s h i f t ) 。 定义2 5 对于s r c p s p 的可行调度计划s ，工作j 的单步左移操作或连续单步 左移操作称为局部左移操作( 1 0 c a ll e f ts h i f