（系统工程专业论文）蚁群算法在资源受限项目调度中的应用.pdf

东北大学硕士学位论文 蚁群算法在资源受限项目调度中的应用 摘要 资源受限项目调度问题是一类典型的运筹学难题。随着经济全球化导致市场 竞争的日趋激烈，现代项目日趋复杂，要求周期更短、准时完工率更高、成本更 低。应用遗传算法，模拟退火，禁忌搜索等启发式算法求解资源受限项目调度问 题已有很多研究。本文将蚁群算法( a n tc o l o n yo p t i m i z a t i o n ，简称a c o ) 应用到 资源受限调度项目问题求解中，详细介绍了蚁群算法求解资源受限项目调度问题 的求解过程，并进一步探索了在资源项目调度问题中有局部发生变化时，蚁群系 统对这些变化的适应性。 本文描述了在应用蚁群算法求解资源受限项目调度问题时，蚂蚁如何在项目 网络图上巡游并动态生成最优解，以及蚁群信息素的更新方式和多种启发式信息 的定义方法，验算了算法在不同的参数组台下对测试案例的求解效果。 在项目执行的过程中存在许多不确定因素，这些不确定因素对项目的执行会 造成一定影响。例如某项工作的执行时间延长会导致项目拖期。在本文设计的算 法中，蚂蚁根据已有的信息做出相应的局部调整，使原有计划在改变魅可能小的 情况下保证项目继续执行。实验中，当项目中某项工作执行时间发生变化时，作 者分别采用了以下两种应对方法；( 1 ) 重新运行蚁群算法求解发生变化后的项目； ( 2 ) 利用蚁群对原项目求解过程中的学习经验( 表现为信息素的浓度) 求解发 生变化后的项目。两种方法的对比结果表明：采用第( 2 ) 种方法对项目计划的 调整更加有效。 关键词：项目调度；资源受限# 蚁群算法；串行调度；并行调度 i i 东北大学硕士学位论文 a b s l = r a c t a p p f i c a t i o no f a n tc o l o n yo p t i m i z a t i o ni n 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 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 o c ts c h e d u l i n gp r o b l e m ( r c p s p ) i sak i n d o fb a r d p r o b l e mo fo p e r a t i o n a lr e s e a r c h b e c a u s eu fs c v e r em a r k e tc o m p e t i t i o nb r o u g h tb y d e v e l o p m e n to fe c o n o m i cg l o b a l i z a t i o n ，m o d e r np r o j e c t sb e c o m em o r ea n dm o i t 。 c o m p l e xa n dr e q u i r es h o r t e rp r o j e c td u r a t i o n s ，h i g h e rj u s t - j n - t i m ec o m p l e t i o nr a t e s ， a n dl e s sc o s t 。s o m em e t a h e u r i s t i c s ，s u c ha sg e n e t i c a l g o r i t h m ( o a ) ，s i m u l a t e d a n n e a l i n g ( s a ) a n dt a b us e a r c hf r s ) ，h a v eb e e na p p l i e dt 。s o l v et h er c p s p , 。i nt h i s p a p e r , a n tc o l o n yo p t i m i z a t i o n ( a c o ) i sa p p l i e dt os o l v et h er c p sp i tn o to n l y d e s c r i b e sh o wa c 0c a l ls o l v et h er c p s pi nd e t a i l b u ta l s od i s c b s s e $ t h a tl i f es y s t e m i sw e l la d a p t i v et 0l o c a lc h a n g ei nap l a no f r c p s e t h i sp a p e rd e s c r i b e sh o wa n t st r a v e lt h en e t w o r ka n dt h em e t h o do fd y n a m i c g e n e r a t i o no f t h eb e s tm s u l t sw h e na p p l y i n ga c o t os o l v et h er c p s ei ta l s op r e s e n t s t h em e t h o do f u p d a t i n gp h e r o m o n e i n f o r m a t i o na n dd e f m i t i o mo fh e u r i s t i c i n f o r m a t i o n b yt e s t i n ga c ot os o l v es o m e o fp r o b l e m sf r o mp s p l i b ，t h e c o m p u t a t i o n a lr e s u l t ss h o wt h a tt h ea c oa l g o r i t h mi s e f f e c t i v e t h e r ea r cm a n yu n c e r t a i nf a c t o r sw h e np r o j o c ti se x e c u t e d ，w h i c hp r o b a b l yh a v e e f f e c to nt h ec o m p l e t i o no f t h ep r o j e c t f o re x a m p i e ad e l a yo fa l la e t i v i t ym a yl e a dt o t h ed e l a yo f w h o l ep r o j o c t o u rr e s e a r c h e ss h o wt h a ti ti sn o tn e c e s s a r yt oa b a n d o nt h e f o r m e rp l a ni n s t e a dw ec a nl o c a l l ya d j u s tt h ef o r m e rp l a nb ym a k i n gu s eo ft h e d e p o s i t e dp h e r o m o n ei n f o r m a t i o no nt h ep a t h t h u s ，t h ef o r m e rp l a ni sc h a n g e dv e r y l i t t l eb u ts t i l lv a l i d s oa c oi sf l e x i b l ea n da d a p t i v e i nt h i sp a p e r , ap m b l e mf r o m p s p l i bi sc i t e d w k nt h ed u r a t i o no fs o m ea e t i v i t yi sc h a n g e dt e m p o r a l l y , t w o d i f f e r e n tm e t h o d so fm a k i n ga s eo fd e p o s i t e dp h e r o m o n ei n f o r m a t i o no i n o ta r e c o m p 丑r e d i ti sp r o v e dt h a tt h ef o r m e ri sm o r ee f f e c t i v e k e yw o r d s ：p r o j e o ts c h e d u l i n g ；r e s o u r c e - c o n s t r a i n e d ；a r i tc o l o n ya l g o r i t h m ( a c o ) ， s e r i a ls e h e d u f i n gs c h e m e ；p a r a l l e ls c h e d u l i n gs c h e m e i i l 独创声明 本人声明所星交的学位论文是在导师的指导下完成的。论文中取得的研究成 果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的研究成果，也 不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示诚挚的谢意。 学位论文作者签名： 篆，仑：妈 签字日期： 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规 定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论 文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关 数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 学位论文作者签名：童亿：电导师签名： 签字日期： d 3 押签字日期 东北大学硕士学住论文 第一章绪论 第一章绪论 1 1 研究背景与意义 项目是指由一组有起止时间、相互协调的受控活动所组成的特定过程i “，该 过程要达到符合规定要求的目标，包括时间、费用和质量等。作为现代管理科学 研究的重要分支，项目管理理论与方法的研究已成为当今世界各国十分关注的科 学课题脚。 国家和地方各省市每年都会有很多“重点工程”，这些重点工程所涉及的金额 十分巨大，关系国计民生与社会发展，意义非常重大。随着经济全球化的发展， 市场竞争程度越来越激烈，本来在管理上处于劣势的中国企业要想在激烈的市场 竞争中立于不败之地，就必须加强管理，而项目管理正是其中的童妻内容。项目 管理不仅在经济建设中有重要应用，在科学研究、国防建设与牡会事务中也有重 要应用，例如“阿波罗登月计划”、四年一度的奥运会等。由此可见，现代社会对 项目管理的需求是十分旺盛的。 起源于2 0 世纪5 0 年代的传统项目管理理论至今已走过半个世纪的历程，其 研究已取得巨大进展，其应用已取得巨大成功，为全世界的科技进步、经济和社 会发展做出了不可磨灭的贡献。但是，随着信息时代的来临和高新技术产业的飞 速发展，资本、服务、技术、信息、劳务( 人才) 在全球范围内流动空前加快， 项目的特点发生了显著变化，项目本身和执行环境的不确定性及复杂性不断增多 和增强各行备业对项目管理的要求越来越高。目前项目管理中仍旧存在非常突 出的问题，主要表现在：( 1 ) 项目拖期完成；( 2 ) 项目成本超支；( 3 ) 为了控制 成本或工期，不得不牺牲项目的规模或设计内容。这些问题表明，目前的项目管 理理论还不能满足项目管理的实际需要，还需要进一步加强研究，提出更新、更 有效的管理方法。 目前国际上有两大项目管理研究组织：欧洲的国际项目管理协会 ( i n t e r n a t i o n a l p r o j e c t m a n a g e m e n t a s s o c i a t i o n ，简称i p m a ) 和美国的( 美国) 项 目管理协会( p r o j t m a n a g e m e n t i n s t i t u t e ，简称p m i ) 。几十年来，两大组织在项 目管理理论与方法的研究和推广应用中做了许多卓有成效的工作，为推动项目管 东北大学项士学住论文第一章绪论 理现代化做出了杰出的贡献。在欧美发达国家，项目管理已经普遍应用于各行各 业，成为各行各业经营管理的中心模式。而我国无论在项目管理理论酌研究上， 还是在项目管理理论的应用上都明显落后于欧美发达国家还没有形成自己的理 论体系和学科体系，极其缺乏高水平、专业的项目管理人才。这对我国的经济发 展和现代化建设极为不利，因此，需要加强对项目管理理论的研究。 项目调度是项目管理的重要组成部分，合理的项目调度计划是决定项目管理 成败的一个关键因素。它广泛存在于建筑工程、软件开发、飞机及轮船制造等单 件或小批量生产方式的企业中。近年来兴起的全球制造方式经常需求多家企业的 合作以获得最大的竞争力，这种组织结构和管理模式越来越趋向于面向工程 口r e j e c t - o r i e n t e d ) 的方式。整个制造过裎具有网络结构特点，各项目成员分布在网络 的节点上，负责整个项目的项或几项工作，拥有各自的资源并共享某些公共资源； 项目成员的共同目标是快速响应市场，以获得最大经济效益。因此，资源受限的工 程调度问题在现代化企业中显示出越来越重要的研究价值。在理论上，该问题模 型丰富，而且多属于n p h a r d 问题。一直吸引着国内外众多学者的关注和研究。 1 2 资源受限项目调度问题的研究进展 资源受限项目调度口”( r e s o u r c e c o m 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 ) 理论从资源受限的前提出发研究项目调度问题，从诞生之日起，一直受 到全世界众多学者和实践者的研究和关注。该问题要求在满足项目紧前约束与资 源约束的前提下，调度项目所有任务的开工期和完工期，以便晟小化项目总工期。 人们熟知的s i n g l em a c h i n e j o bs h o p 、f l o ws h o p 等优化调度问题都是它的特殊 情形。由于这类调度问题多属n p 难，目前的精确算法只能针对中小规模的项目进 行求解。在可接受的计算资源和计算时间条件下，尽管精确解法目前无法适用于大 规模的项目优化调度问题求解。但是，任何精确算法的研究进展，往往会给人们带 来十分有益的启示，使人们能够提出更为有效的启发式求解策略和算法。因此，研 究r c p s p 的精确求解算法有着重要的理论意义和现实的应用前景。 人们已经发展了多种求解r c p s p 的方法，文献【5 。】给出了早期这一领域研究 成果的综述。文献f 8 1 1 比较了单项目r c p s p 的最优调度方案与次优调度方案问 的差异。文献”“3 】研究了多项目r c p s p 的优化调度方案。早期人们求解这一问 2 东北大学硕士学位论文 第一章绪论 题的努力主要集中在两个领域：( 1 ) 利用数学规划方法来对这类优化调度问题进 行公式化和求解；( 2 ) 研究启发式求解步骤来获得令人满意的解。那时人们曾经 采用整数规划的手段来求解这类优化调度问题的糟确解：后来人们发展了各种枚 举性( 分枝定界) 方法来获得这一问题的最优解 1 4 。”。 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 j e 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 er e $ o u r o e c 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 ，简称m r c p s p ) 、离散时间成本权衡项目 调度问题( d i s c r e t et i m e d c o s tt r a d e o f f p r o b l e m ，简称d t c r i p ) 、单执行模式资源水 平问题( s i n g l em o d er e s o h 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 e l e v e l i n g p r o b l e m ，简称m r l p ) 、带最小最大时间滞 后的资源受限项目调度问题( r c p s p m a x ) 、以最大挣现值为目标的资源受限项目 调度问题( n e t p r e s e n t v a l u e 。简称n p v ) 等。随着模拟退火( s i m u l a t e d a n n e a l i n g ， s a ) 、禁忌搜索d “( t a b us e a r c h ，t s ) 和遗传算法i ”“1 ( g e n e t i ca l g o r i t h m ，g a ) 等现代优化方法的出现，大型资源受限项目调度问题得到了更加有效的求解。从 总体来说，求解r c p s p 的方法和途径综台起来包括：( 1 ) 研究在有限的资源约 束下，优化项目的总工期；( 2 ) 研究在有限的项目总工期的约束下，优化项目的 总成本；( 3 ) 研究项目总成本与总工期之间的相互折中关系。所采用的方法主要 也可以分为三大类：( 1 ) 精确算法f 4 “4 4 t 。精确类算法的研究主要集中在利用分 枝定界方法来对项目调度问题进行求解。这类算法虽然在某种程度上能够得到最 优解，但它只能解决中小规模项目的调度问题，对多于6 0 个任务的大型项目来 说，这种方法在求解时将耗时很长。( 2 ) 局部搜索算法。在局部搜索类算法研究 中，先后出现过通过漂移量来产生调度计划的局部搜索方法和针对多模式的j o b s h o p 调度的禁忌搜索算法。( 3 ) 基于优先规则的启发式算法。在基于优先规则的 启发式算法研究中，有s a s p ( s h o r t e s ta c t i v i t yf r o mt h es h o r t e s tp r o j e c t ) 、l a l p ( l o n g e s ta c t i v i t yf r o mt h el o n g e s tp r o j e c t ) 、m o f ( m a x i m u mo p e r a t i o nf i r s t ) 、 ( m a x i m u ms l a c kf i r s t ) 、m i n t w k ( m i n i m u mt o t a lw o r kc o n t e n t ) 、m a x t w k ( m a x i m u mt 0 t a i w o r k c o n t e n t ) 六个优先规则，后来又出现了四种项目延误惩罚 规则，m a x d p ( m a x i m u md u r a t i o na n dp e n a l t y ) 、m a x p ( m a x i m u mp e n a l t y ) 、 东北大学硕士学位论文第一章绪论 m a x t d p ( m a x i m u mt o t a ld u r a t i o np e n a l t y ) 、s s p ( s i m u l t a n e o u s l ys l a c ka n d p e n a l t y ) ，通过对现有的一些在串行调度和并行调度中取得较好效果的优先规则 进行比较，并在此基础上出现了三种新的针对并行调度计划的优先规则，后来出 现了一种基于分析的局部约束概念_ i ，c b a ( l o c a lc o n s t r a i n tb a s e da n a l y s i s ) 和相应的迭代算法，并在基于分离弧概念的基础上出现了一种两阶段法。 调度计划一般是在确定环境中进行的，在项目执行的动态环境中存在着许多 不确定性，这些不确定性往往会导致项目无法按计划完成。资源受限项目调度理 论对这个问题没能给出有效地处理方法。本文应用蚁群算法( a n tc o l o n y o p t i m i z a t i o n ，简称a c o ) 求解r c p s p , 并对局部发生变化后，应用蚁群的自学习和自 适应能力对项目调度计划进行有效地调整。使在原项目计划变化尽可能小的情况 下继续执行项目计划。 典型的r c p s p 可以描述如下；在一个项目中，使用j = f o ，l ，2 ，n + l 表示包 括所有工作的集合，其中的每个工作一旦开始执行不允许被打断。由于技术上的 要求，某些工作间存在着紧前关系，只为工作j 的紧前工作集，s ，为工作j 的紧后 工作集。整个项目的结构由一张有向网络图表示，图中节点代表工作，弧线代表 工作间紧前关系。圈中各工作顺序编号，保证只中的工作编号小于j 。工作0 是 唯一最早开始的工作，工作n + l 是唯一最晚完成的工作均为虚工作( 不消耗资源 且执行时间为0 ) ，分别代表整个项目的开始和结束。工作j0j 卸，l ，+ l 的完成 需要第k 种资源量为，执行时间为d j 第k ，k = l ，2 ，k 种资源在第t ，t 2 1 ，2 ，t ( t 为工期的上限) 阶段的可用量为巩。项目调度计划可以用j 元组s 2 ( s o ，8 1 t ，b “) 表示，其中s ；为工作j ，j = o ，2 ，n + 1 的计划开始时间。资源受限项目调度的数学模 型为： r a i n s i j 一j 。d i , i _ ，的所有前驱 8 上r k ，t = 1 ，2 ，s n + l ，k = l ，2 ，k j n 表示满足资源约束和紧前紧后关系且使周期最短。 图1 1 给出了一个简单项目实例网络图，该项目包含1 ，2 ，3 ，4 ，5 ，6 六个 工作及0 和7 两个虚工作，从虚工作0 ，= f ：始，至瘟工作7 结柬。此项目总菇有一 东北大擘硕士学位话丈第一章绪论 种可更新资源，资源容量为4 ，工作编号上方位该工作的工期及资源使用量。图 i + 2 给出了该活动了一个可行调度方案。 r 躅1 1 项目网络图 n 9 11 a n e t w o r k o f a r c p s p i n s t a i l c o _ 4 5 l23 6 12345 67 891 01 11 2 1 3 t 41 51 6 p 图12 一种调度方案 f i g1 2 af e a s i b l es c h e d u l e 在r c p s p 中工作的完成时间f i = s 。+ d ；，其中s j 为工作j 的开始时间，d ，为工 作j 的执行工期。对于整个项目来说，项目开始时间就是所有工作开始时间的最 小值，即m i n s i | j ej ，项目完成时问是所有工作完成时间的最大值，g p m 奴+ d ，d j ，= 者之差就是该调度的工期。很容易得到，第0 个工作的开始 时间就是整个项目的开始时间，第n 十1 个工作的完成刚间就是整个项目的完成时 间。而一个可行性调度必须满足两点：( 1 ) 满足紧 j 紧后关系约束。对所有工作 东北大学硕士学位论文 第一章绪论 j j 必须开始于其所有前序工作完成之后，即s ，s + d ，i p j ( 2 ) 满足资源约 束限制对于每个时间段t ，所有调度工作所需资源量不能超过资源可用量，对 于每个时间单元t ，类型i 的资源必须满足：，。地。一昏- r j 。如果不满足资源 约束，只满足了紧前约束，工作就不会按照最早开始时间调度，而是推迟一段时 间才被调度。 一个完成时间上界为t 项目，最晚开始时间l s 和最晚完成时间l 只通过从后 向前递推算出来：l s n “= l e 。= t l f = m j l l l s ，l i s ， ，l s j 锄一d j ，其中 j = n ，0 最早开始时间e s j 和最早完成时间e 鼍通过下面的递推公式计算出来： e s o _ e f 。3 0 ，e s j 2 m “ e i i 乍p j ，e f j = e s j + d j ，其中j ；1 ，n + 】。工作n + l 的最早开始时间e s 。是可行调度工期的一个重要下界。资源受限项目调度的目标 就是调度每个工作，在满足资源约束和紧前紧后关系约束的条件下使得项目韵工 期最短。r c p s p 和调度符号意义如表1 1 所示。 东北大学硕士学位论文 第一章绪论 表1 1 符号定义 t 曲i e1 1n o t a t i o n s 定义 ， q r 。 d s j l s j ( e s j ) 蝎( e f j ) f j s ： 所有工作集台 资源类型集 类型资源自蹿量 执行工作j 需要第k 种资源的数 工作i 的工期 工作的数目 j 工作的开始时间 j 工作完成的时间 j 工作的最晚( 最早) 开始时问 j 工作的最晚( 最早) 完成时间 j 工作所有前驱的最大完成时 j 工作所有后继的集台 兰! 三竺竺! 旦竺竺苎竺 1 3 串行调度与并行调度 基于优先规则的启发式算法是解决r c p s p 的最常用方法，也是最重要的启 发式算法之一。基于优先规则的启发式算法有以下优点：( 1 ) 方法很直观，容易 实现，适合用于商业包j ( 2 ) 时间性能好。基于优先规则的启发式算法一般由两 个部分构成，调度方案和优先规则【4 s l 。调度方案包括串行调度( s e r i a ls c h e d u l i n g 东北大学硕士学位论文 第一章绪论 s c h e m e ，简称s s s ) 和并行调度( p a r a u e ls c h e d u l i n gs c h e m e ，简称p s s ) 。两种调 度方案都是通过分阶段方式扩展一个半调度计划直至生成一个完整的可行调度 计划。半调度计划指的是所有工作中只有部分工作给出完成时间。在每个调度阶 段，算法生成一个可调度的工作集合，通过具体的优先规则，从该可调度的工作 集合中选出一个或几个工作，安排选出的工作的开始执行时间。比较好的优先规 则包括：最小自由时间( m i n s l k ) 、最迟完成时间( l f t ) 等。 1 3 1 串行调度方案 串行调度方案是由k e l l e y 在1 9 6 3 年提出的。串行调度方案在0 时间开 始于一个只包含工作0 的半调度计划，经过n 个阶段形成一个完整的调度过程， 在每个阶段都有一个工作被包含到当前的半调度工作集合中。在每个阶段，均存 在一个可调度集合f ( g ) ，该集合包含所有当前尚未被调度且其所有的前序工作都 已经被调度过的工作集合，通过某种优先规则，从该集合中选出一个工作。并在 满足紧前紧后关系和资源约束的最早开始时间对它进行调度，从而完成该阶段的 调度，之后将该工作从可调度工作集合曩g ) 中移出，并放进半调度工作集合中。 这样的调度过程持续进行，直到经过了n 个阶段，所有的工作都已经添加在半调 度工作集合中，即调度集合中后，串行调度算法终止。串行调度结束后得到一个 所有工作的序列。串行调度的程序如下： f o r g ；0 t o n + l 计算出可调度集合“g ) ； 根据优先规则选择最优先工作jef ( g ) ； 在满足紧前关系和资源约束条件下尽可能早地调度工作j _ e n d f o r 1 3 2 并行调度 k e l l e y 和b r o o k s 都曾经对并行调度进行过研究。并行调度至多包含i 3 个阶段， 每个阶段，一组工作集可以被调度，当然该工作集可以是空集。在并行调度中， 用c g 表示到调度时间t ；已经被调度完的工作集合，a 。表示在调度时间t 。正在执 行的工作集合，每个阶段的半调度工作集合就是由己调度完的工作集合c 。和正在 东北走学硕士学位论文 第一章绪论 s c h e m e ，简称s s s ) 和并行调度( p a r a l l e ls c h e d u l i n gs c h e m e ，简称p s s ) 。两种调 度方案都是通过分阶段方式扩展一个半调度计划直至生成一个完整的可行调度 计划。半调度计划指的是所有工作中只有部分工作给出完成时间。在每个凋度阶 段，算法生成一个可调度的工作集合，通过具体的优先规则，从该可调度的工作 集合中选出一个或几个工作，安排选出的工作的开始执行时间。比较好的优先规 则包括：擐小自由时阃( m i n s l k ) 、最迟完成时间( l f t ) 等。 1 3 1 串行调度方案 串行调度方案是由k e l l e y 在1 9 6 3 年提出的。串行调度方案在0 时间开 始于一个只包含工作0 的半调度计划，经过n 个阶段形成一个完整的调度过程， 在每个阶段都有一个工作被包含到当前的半调度工作集合中。在每个阶段，均存 在一个可调度集合f ( g ) 。该集合包含所有当前尚末被调度且其所有的前序工作都 已经被调度过的工作集台，通过某种优先规则，从该集合中选出一个工作，井在 满足紧前紧后关系和资源约束的最早开始时间对它进行调度，从而完成该阶段的 调度，之后将该工作从可调度工作集合“g ) 中移出，并放进半调度工作集合中。 这样的调度过程持续进行，直到经过了n 个阶段，所有的工作都已经添加在半调 度工作集合中，即调度集合中后，串行调度算法终止。串行调度结束后得到一个 所有工作的序列。串行调度的程序如下： f o r g = o t 0 1 7 1 + l 计算出可调度集合f ( g ) ； 根据优先规则选择最优先工作j e f c g ) ； 在满足紧前关系和资源约束条件下尽可能早地调度工作j ； e n d f o r 1 3 2 并行调度 k e l l e y 和b r o o k s 都曾经对并行调度进行过研究。并行调度至多包含n 个阶段， 每个阶段，一组工作集可以被调度，当然该工作集可以是空集。在并行调度中， 用q 表示到调度时间t ；已经被调度完的工作集合，a ；表示在调度时间t 。正在执 行的工作集合，每个阶段的半调度工作集合就是由己调度完的工作集合c 。和正在 行的工作集台，每个阶段的半调度工作集合就是由已调度完的工作集合c 。和正在 东北大学硕士学位论文 第一章绪论 s c h e m e ，简称s s s ) 和并行调度( p a r a u e ls c h e d u l i n gs c h e m e ，简称p s s ) 。两种调 度方案都是通过分阶段方式扩展一个半调度计划直至生成一个完整的可行调度 计划。半调度计划指的是所有工作中只有部分工作给出完成时间。在每个调度阶 段，算法生成一个可调度的工作集合，通过具体的优先规则，从该可调度的工作 集合中选出一个或几个工作，安排选出的工作的开始执行时间。比较好的优先规 则包括：最小自由时间( m i n s l k ) 、最迟完成时间( l f t ) 等。 1 3 1 串行调度方案 串行调度方案是由k e l l e y 在1 9 6 3 年提出的。串行调度方案在0 时间开 始于一个只包含工作0 的半调度计划，经过n 个阶段形成一个完整的调度过程， 在每个阶段都有一个工作被包含到当前的半调度工作集合中。在每个阶段，均存 在一个可调度集合f ( g ) ，该集合包含所有当前尚未被调度且其所有的前序工作都 已经被调度过的工作集合，通过某种优先规则，从该集合中选出一个工作。并在 满足紧前紧后关系和资源约束的最早开始时间对它进行调度，从而完成该阶段的 调度，之后将该工作从可调度工作集合曩g ) 中移出，并放进半调度工作集合中。 这样的调度过程持续进行，直到经过了n 个阶段，所有的工作都已经添加在半调 度工作集合中，即调度集合中后，串行调度算法终止。串行调度结束后得到一个 所有工作的序列。串行调度的程序如下： f o r g ；0 t o n + l 计算出可调度集合“g ) ； 根据优先规则选择最优先工作jef ( g ) ； 在满足紧前关系和资源约束条件下尽可能早地调度工作j _ e n d f o r 1 3 2 并行调度 k e l l e y 和b r o o k s 都曾经对并行调度进行过研究。并行调度至多包含i 3 个阶段， 每个阶段，一组工作集可以被调度，当然该工作集可以是空集。在并行调度中， 用c g 表示到调度时间t ；已经被调度完的工作集合，a 。表示在调度时间t 。正在执 行的工作集合，每个阶段的半调度工作集合就是由己调度完的工作集合c 。和正在 东北走学硕士学位论文第一章绪论 执行的工作集合a 。构成。并行调度在时间0 也开始于一个只包含工作0 的半调度 巢含 每个调度阶段g 均有一个开始时间t 。，用来表示在工作实际褴调度之前可 以开始的调度的时间，t 。为上个阶段正在被调度的工作集合a 。中所有工作的最早 完成时间；在t 。时间满足紧前关系和资源约束的工作集合用可调度集合乒t 。) 表 示。在每个阶段g ，有两步工作要做；( i ) 新的调度时间的计算和把那些完成时 间和新调度时间相同的工作从正在执行的工作集合a 。移入到已经被调度过的集 合c b 中：这样由于更多地工作加入到已经被调度的集合c ；，就会有更多的工 作加入到可调度集合甄t 。) 。中，晕为有更多的工作的前驱已经被添加到已经被调度 的工作集合中。( 2 ) 根据某种优先规则，从可调度集合“t 。) 中选出一个工作，在 当前的调度时间进行调度，当然此时要将该工作从可调度集合甙t i ) 中穆到正在执 抒的工作集合a ；中。第( 2 ) 步一直重复执行- 直到可调度榘合f ( t 。) 为空，也_ 就 是说在每个阶段可以调度多个工作，这点与串行调度不同。并行调度过程如下： 9 2o ，t e 2 0 ，c 9 2 o ； w h i l e 还有工作没有调度 计算可调度集合( t 。) ： w h i l e 可调度集合f ( t 。) 不为空 根据优先规则从可调度集合掣t 。) 中选择工作j ； 调度工作j ； 将j 添加到c 。中： 重新计算可调度集台( t 。) ； e n d w h i l e ； 计算正在执行的工作集合a 。； g g + l ，更新t 。： e n d w h i l e ； 并行调度方案生成的是没有延迟的调度方案，串行调度方案生成的是积极的 调度方案，对于每个资源受限项目调度实例，使用串行调度方案可能得到一个最 优解，也就是说通过串行调度过程，存在一个工作序列的选择，使得其为最优调 度i 使用并行调度方案产生的虽然为非延迟的调度，也就是说只有当没有可行工 东北大学硕士学位论文第一章绪论 作可以取到的时候才在调度中引入空阑时间，但是使用并行调度未必会得到最优 调度。大量研究表明：对于基于某些启发规则的项目调度过程，并行调度生成的 方案比串行调度生成的方案好；而对于另外一些启发规则来说，串行调度生成的 方案比并行调度生成的方案好【4 6 4 i 。 1 4 本文的主要工作 1 4 1 研究内容 本文主要研究工作包括：( 1 ) 蚁群算法在资源受限项目调度中的应用；( 2 ) 蚁群算法在资源受限项目调度应用中的扩展。资源受限项目调度问题属于n - p 难 问题，多年来得到很多学者的研究，并且提出了很多解决的办法，比较熟悉的模 拟退火、遗传算法等都在其中得到了运用，井地较成功的解决了问题。蚁群算法 是一种比模拟退火和遗传算法起步较晚的一种根据生命系统得到肩发的一种解 决组合优化较好的算法，将蚁群算法应用于资源受限项目调度问题的研究尚属少 见，本文试着将蚁群算法的思想应用到资源受限项目调度中，并观察结果的好坏： 本文不但将蚁群算法应用到资源受限项目调度问题的解决中，并且提出了蚁群算 法在资源受限项目调度中的扩展，其思想主要是根据现实生活中突发情况发生 时，如何在原有已制订计划的基础上，尽可能通过较少的变化生成新的调度方案， 并顺利解决问题。 1 4 2 组织结构 论文组织结构如下：第一章介绍了r c p s p 的研究背景、研究现状，以及一 些资源受限调度理论的基本知识；第二章介绍了蚂蚁算法的思想、发展、应用以 及蚂蚁算法在解决旅行商问题时的应用过程，以备后续章节描述蚂蚁算法在 r c p s p 中应用打下基础；第三章介绍了蚂蚁算法在资源受限项目调度中的使用、 思想、算法，以及各个参数代表的设定，各个参数的意义，实验结果的总结；第 四章提出了蚁群算法在r c p s p 中的扩展；第五章对未来的研究做出了展望。 东北大学硕士学位论文 第：章蚁群算法的基础知识 第二章蚁群算法的基础知识 2 1 蚁群算法简介 自2 0 世纪8 0 年代以来，人们提出了一类模拟大自然的元启发式算法：智能 优化方法。元启发式算法通过模拟或揭示某些自然现象或过程而得到发展，其思 想涉及数学、物理学、生物进化、人工智能等方面，为解决复杂问题提供了薪的 思想和手段。由于元启发式算法本身是一个优化系统，具有自适应性，所以对于 有多个局部最优解的问题，可以跳出局部最优解。目前研究最多的元启发式算法 有蚁群算法、模拟退伙、遗传算法、禁忌搜索等。其中蚁群算法是一种比较新的 元启发斌方法，并迅速得到广泛的研究与虚甩。+ 众所周知，社会性昆虫如蚂蚁、蜜蜂等，虽然其单个个体行为非常简单、随 机，但是它们却可以凭借集体的力量进行觅食、御敌、筑巢辞复杂活动。这种群 体所表现出来的功能，称之为群集智能。从社会性昆虫相互合作中得到启发，人 们通过对社会性昆虫这种复杂系统的模拟，提出了一系列对于传统闸题的新的解 决方法，即群集智能算法。群集智能中的群体指的是一组相互之间可以进行间接 通信的主题，这组主体能够合作进行分布式问题的求解。而所谓群集智能指的是 低智能的主体通过合作表现出高智能行为的特性。群集智能在没有集中控制并且 不能提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了基础， 蚁群算法正是群集智能算法中的最重要的分支之一。 生物学家通过长期观察发现，蚁群有一个令人感兴趣的特性，即蚁群在觅食 的时候总是可以找到从蚁巢通向食物的最短路径。事实上，当蚂蚁寻找食物时， 在从蚁巢到食物( 或者从食物返回蚁巢) 的途中，会在其经过的路径上释放一种 挥发性的化学物质，称作信息素。信息素可以沉淀在路径上，并随着时间逐步挥 发，当蚂蚁在选择路径的时候，它们倾向于沿着信息素气味比较浓的路径前进。 因此，信息紊可以引导蚂蚁通向食物( 或者返回巢穴) 。如图2 1 所示，刚开始蚂 蚁可以直接从巢穴到达食物，在蚂蚁的路途中放上一个障碍物后，蚂蚁需要选择 路径，即a b h d e ( e d h b a ) 或者a b c d e ( e d c b a ) ，最初蚂蚁选择这两条路 径的概率是相同的，但由于路径a b c d e 比路径a b h d e 短，假设蚂蚁速度相同 东北大学硕士学位论文 第二章衄群算法的基础知识 的情况下，走完路径a b c d e 比走完路径a b h d e 所需要的时间短，因此，在一 段时间后，路径a b c d e 会有相对多的蚂蚁选择，在该路径就会释放相对多的信 息素，一定时间以后，所有的蚂蚁就会都选择较短的路径a b c d e 了，就像图2 1 c 所显示的那样，从而实现了蚂蚁对路径的选择。这就是蚁群的自催化行为，其原 理是一种正反馈机制，蚁群具有增强型学习的能力。 c 峥鸷辱 圈2 1a ) 蚂蚁在a 和e 之间的路径上行走 b ) 出现障碍物，蚂蚁必绠绕过它 c ) 达到蚂蚁选择最短路径的稳定状态 f i g2 1a ) s o m ea n t sr r ew a l k i n go l lap a t hb e t w e e np o i n t saa n de ”a oo b s t a c l es u d d e n l ya 印e a r 8a n dt h ea n t sm u s tg o ta r o u n di t c ) a ts t e a d y - s t a t et h ea a t sc h o o s et h es h o r t e rp a t h c 通过上述蚂蚁行为的描述可以看出信息素交流是蚂蚁寻找最短路径最重要 的媒介和手段。蚂蚁通过信息素进行间接交流，个体信息的收集与接个群体信息 的共事，信息的学习，在系统内部进行交流与学习，不断优化系统，即自适应系 统。 d e n e u b o u r g 和g o s s 等人h 8 】为了研究蚁群的这种自组织行为，设计了对称二 叉桥实验。1 9 9 1 年，d o r i g o ，c o l o m i 和m a n i e z z o 等人1 4 9 】在研究组合优化问题计 算机智能解决方法时，将d c n e u b o u r g 等入的概率模型进一步深化，提出了最初的 蚁群优化算法 5 0 - s t l ，并对小规模旅行葡问题进行了求解。 目前，蚁群算法的研究主要集中在两个方面问题的求解：静态组合优化问题 东北大学硕士学位论丈 第= 章蚁群算法的基础知识 和动态组合优化问题。静态组合优化问题指的是在解决问题的时候，该问题的拓 扑分布和转换开销不会发生变化。例如，经典旅行商问题中城市的位置和城市间 的距离在旅行商巡游过程中不会发生变化。动态组合优化问题的求解过程中，该 问题的拓扑分布或转换开销可能会发生变化。例如，通信网络中的路由问题该 问题求解过程中的各种网络状态都是不停发生变化的。 蚊群算法是一种新颖的仿生进化算法，提出至今短短韵十几年的时间，其理 论尚未形成完整的体系，其应用的领域也是十分有限。因而对蚁群算法的研究领 域的扩展有一定的理论和使用价值。一方面，