（计算机应用技术专业论文）基于蚁群算法的虚拟企业制造资源局部调度技术研究.pdf

桂林理工大学硕士学位论文 摘要 虚拟企业是为了适应快速反映而提出的一种先进制造生成组织方式。虚拟企业的 制造资源调度分配过程是虚拟企业运营过程中的重要环节，调度效率的提高将在很大 程度上改善整个虚拟企业的运营效率。其局部调度问题可以归结为资源受限项目调度 问题。 虚拟企业资源受限项目调度问题已成为广大专家学者的研究热点。其中，单模式 资源受限项目调度问题是一类典型的项目调度问题，他属于n p h a r d 问题的范畴，目 前已有学者应用遗传算法、模拟退火算法等启发式算法求解此类问题，但将蚁群算法 应用于此类问题的研究较少。因此，本文尝试将蚁群算法应用于单模式资源受限项目 调度问题的求解。 本文在对国内外资源受限项目调度问题研究现状作了详细的综合论述并介绍了其 相关理论基础之后，对蚁群算法作了较深入探讨，并且提出了采用双种群蚁群算法来 求解单模式资源受限项目调度问题，该算法针对r c p s p 问题的特点进行设计。然后， 为了验证算法的性能和有效性，用p s p l i b 中的基准问题对算法进行了仿真实验。结 果表明该算法用于求解r c p s p 有比较好的性能，并且在求解大规模问题时其效果也是 显著的。最后，将本文设计的算法应用于一个汽车设计制造虚拟企业制造资源局部调 度问题，也即某个成员企业完成汽车前端设计项目的资源调度问题，得出了使得工期 最小化的调度方案。 本文的研究成果，不仅拓展了r c p s p 的研究领域，为r c p s p 的求解提供了一种 新的思路和方法，而且也为解决虚拟企业制造资源调度分配问题提供了一定的指导借 鉴意义。 关键词t 蚁群算法；资源分配；项目调度：虚拟企业。 桂林理工大学硕士学位论文 a b s t r a c t v i r t u a le n t e r p r i s e si sa na d v a n c e dm a n u f a c t u r i n go r g a n i z a t i o n a lf o r mw h i c hw a s p r o p o s e dt oa d a p tt or a p i dr e s p o n s e m a n u f a c t u r i n gr e s o u r c e ss c h e d u l i n gp r o c e s si st h e i m p o r t a n ts t a g e si nv i r t u a le n t e r p r i s e so p e r a t i o n s i m p r o v e m e n t so fs c h e d u l i n ge f f i c i e n c y w i l lg r e a t l yi m p r o v et h eo v e r a l lo p e r a t i o n a le f f i c i e n c yo fv i r t u a le n t e r p r i s e s 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 nv i r t u a le n t e r p r i s e si sah o ts p o to f r e s e a r c h t h es i n g l e m 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 gp r o b l e m ( s r c p s p ) i sa k i n do ft y p i c a lp r o j e c ts c h e d u l i n gp r o b l e m s ，i tb e l o n g st ot h en p - h a r dp r o b l e m s af e w s c h o l a r ss o l v et h i s p r o b l e mu s i n gh e u r i s t i ca l g o r i t h m s ，s u c ha sg e n e t i ca l g o r i t h m s ， s i m u l a t e da n n e a l i n ge t c b u tt h er e s e a r c ho fs o l v i n gt h i sp r o b l e mu s i n ga n tc o l o n y o p t i m i z a t i o n ( a c o ) i sl e s s ，s ot h i sp a p e rt 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 f i t h r nt o s o l v et h i sp r o b l e m ，a n di n t r o d u c et h ep r o c e s so fu s i n gt h ea c ot os o l v et h i sp r o b l e m d e t a i l e d l y b a s e do nt h ea n a l y z i n go ft h ed e v e l o p m e n to fs r c p s pa th o m ea n da b r o a d ，s r c p s p b a s i ct h e o r y , t h ea d v a n t a g e so fa c oa led i s c u s s e d , a n dam e t h o dt h a ta p p l y i n gd u a l p o p u l a t i o na c o t os o l v es r c p s pi sp r o p o s e d t h ep h e r o m o n ea n dh e u r i s t i ci n f o r m a t i o n s t r a t e g ya r ed e s i g n e da c c o r d i n gt ot h ec h a r a c t e r i s t i c so ft h es r c p s p a n dt h e n , i no r d e rt o c o n f i r mt h ev a l i d i t ya n df u n c t i o no ft h ea l g o r i t h m ，a ne x p e r i m e n ti st o o kb a s e dt h ei s s u eo f t h eb e n c h m a r kt e s t so ft h ep s p l i b t h er e s u l t so ft h ee x p e r i m e n ts h o we f f e c t i v e n e s so ft h e a l g o r i t h ma n dt h ep e r f o r m a n c eo ft h ea l g o r i t h mi sn o tb a d p e r f o r m st e s t sb yl a r g e b e n c h m a r ki n s i s 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 l a s t l y , t h ea l g o r i t h mo fd e s i g n e di n t h i sp a p e rw i l lb ea p p l i e dt oaa u t o m o t i v ed e s i g na n dm a n u f a c t u r i n gv i r t u a le n t e r p r i s e m a n u f a c t u r i n gr e s o u r c el o c a l l ys c h e d u l i n gp r o b l e m ，t h a ti sam e m b e rc o m p a n yo ft h e v i r t u a le n t e r p r i s et o c o m p l e t et h ed e s i g n o fa u t o m o t i v ef r o n t e n dp r o j e c tl e s o u r c e s c h e d u l i n gp r o b l e m ，c o m et ot h ep r o g r a mo fm a k et h em i n i m u md u r a t i o no ft h es c h e d u l i n g t h i sr e s e a r c hn o to n l ye x p a n d st h er e s e a r c hf i e l do fs r c p s p , p r o v i d e ss o m ei m p o r t a n t t r a i no ft h o u g h ta n dm e t h o df o rs o l v i n gt h es r c p s p , b u ta l s om a k e sc e r t a i ng u i d a n c ef o r l o c a l l ys c h e d u l i n go fv i r t u a le n t e r p r i s e sm a n u f a c t u r i n gr e s o u r c e s k e y w o r d s ：a n tc o l o n yo p t i m i z a t i o n ；r e s o u r c ea s s i g n m e n t ；r e s o u r c e - c o n s t r a i n e d p r o je c ts c h e d u l i n g ；v i r t u a le n t e r p r i s e s 研究生学位论文独创性声明和版权使用授权书 独创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含他人已经发表或撰 写过的研究成果，也不包含为获得其它教育机构的学位或证书而使用过的材料。对论 文的完成提供过帮助的有关人员已在论文中作了明确的说明并表示谢意。 学位论文作者( 签字) ： 签字日期： 学位论文版权使用授权书 本学位论文作者完全了解( 学校) 有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的印刷本和电子版本，允许论文被查阅和借阅。本人授 权( 学校) 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学技术信息研究所将本 学位论文收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：亏乇勰羁 答字日期：叫年6 月j f 日 = e 黧l 搿眇日 签字期：弘叼年么月c _ 日 桂林理工大学硕士学位论文 1 1 研究背景与意义 第1 章绪论 新型工业化是我国经济建设和现代化的必由之路，而发展先进的制造业则是实现 工业化的基本支撑点。制造技术的网络化是先进制造技术发展的必由之路。制造业在 市场竞争中，面临多方面的压力：采购成本不断提高，产品更新速度加快，市场不断 变化，全球化所带来的冲击利益加强等等。企业要避免这一系列问题，就必须在生产 组织上实行某种深刻变革。科学技术特别是计算机技术、网络技术的发展，使这种变 革有可能完成。制造技术的网络化导致一种新的制造模式的产生，即虚拟制造组织， 这是由地理上异地分布的、组织上平等独立的多个企业，在谈判协商的基础上，建立 密切合作关系，形成动态的“虚拟企业”。虚拟企业是为适应快速反映而提出的一种先 进制造生产组织方式，为企业提供了一种如何快速适应市场变化的制造系统构造与设 计思路。 虚拟企业【l 】是一种从最大限度发挥和提升企业核心竞争力着眼，以“共赢”为目 的的全新企业合作模式，他强调充分利用各企业已有的资源优势，通过组织动态联盟， 快速响应市场变化，把握市场机遇。虚拟企业克服了传统的封闭性、局限性和设计、 制造到销售的整体柔性和敏捷性，增强了企业的竞争能力。随着适于虚拟企业生存的 经济条件的日趋成熟，虚拟企业已步入快速发展时期。 蚁群算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 是最近几年才提出的一种新型的模拟进 化算法，由意大利学者m d o r i g o 等【2 】人于1 9 9 1 年首先提出来，用蚁群在搜索食物源 的过程中所体现出来的寻优能力来解决一些离散系统优化中的n p h a r d 问题。从此， 具有n p h a r d 性的组合优化的调度问题成为了蚁群系统的一个重要研究方向。蚁群算 法由于采用分布式并行计算机制，易于与其他方法相结合，具有较强的鲁棒性等特点， 已经在许多组合优化问题中获得了成功的应用，这些问题大体可以分为两类：一是静 态组合优化问题，这类问题的参数特性不会在求解过程中发生变化，如t s p ( t r a v e l i n g s a l e s m a np r o b l e m ) 、q a p ( q u a d r a t i ca s s i g n m e n tp r o b l e m ) 、s o p ( s e q u e n t i a lo r d e r i n g p r o b l e m ) 、v r p ( v e h i c l er o u t i n gp r o b l e m ) 及j s p ( j o b - s h o ps c h e d u l i n gp r o b l e m ) 等；另一 类是动态组合优化问题，这类问题的参数特性会在求解过程中发生变化，如网络路由 问题等。 虚拟企业运营过程中的一个关键环节，就是管理分布在各组织成员中的资源，并 根据虚拟企业的目标和任务来合理的调度这些资源。资源调度的好坏将很大程度上决 定虚拟企业，尤其是制造型虚拟企业的运营效率。然而，由于制造资源的复杂性、多 样性、特殊性和分散性，虚拟企业中的资源调度问题是非常复杂的。因此，制造资源 桂林理工大学硕士学位论文 的调度是虚拟企业实现和运营中的一个重要问题。 虚拟企业的制造资源调度分为分布式调度和局部调度两个阶段。分布式调度是将 制造总任务分解为多个制造任务，根据每个制造任务选择合适的成员企业，并将制造 任务分配给该成员企业节点。局部调度是将分布式调度分配到的任务分解成多个制造 子任务，然后选择最适合承担该制造子任务的制造资源，并将制造子任务分配给该制 造资源。因此，局部调度阶段可以归结为资源受限项目调度问题( r c p s p ， 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 m ) 。 1 2 国内外研究现状 针对网络化环境下制造资源的动态优化配置与共享问题，国内外开展了以“利用 外部资源而不必拥有为特征 的虚拟企业、网络化制造、基于a s p 的制造资源共享、 e 制造系统、制造网格等先进制造模式的理论和应用研究。为了解决各先进制造模式 中的制造资源调度问题，相应的制造资源调度模型相继被提出，同时给出了许多解决 资源调度问题的算法。 虚拟企业是企业间利用网络技术集成资源进行联合竞争的一种形式，英国的 d a v i dt 0 d d 、法国的m t m a r t i n c z 研究了虚拟企业环境下任务分配、资源管理、调度 和系统控制模型，为网络化环境下虚拟企业间的资源调度、管理和控制提供了参考【3 a l 。 西北工业大学的马雪芬等1 5 1 人建立了网络化制造环境下资源优化调度模型，以总的运 行成本、运行时间和加工质量为优化目标，给出了基于遗传算法的资源调度方法，并 对算法作了相应的改进。西安交通大学的张映峰等【6 】人设计了e 席0 造调度系统的求解 机制和数学模型，并开发了基于遗传算法的争制造单元调度系统，实现了资源调度求 解工程。北京理工大学的王大震等【7 】人为解决网络环境下的资源优化调度问题，在综 合考虑成本价格和作业执行时间的基础上，提出了经济模型下基于时间预算和作业价 格预算的成本和时间综合最优调度策略。l 四j l l 大学的廖敏等【b 】人对p e t r i 网进行扩展， 建立了基于p e t r i 网的工作流模型，并利用扩展p e t r i 网来实现资源配置。上海大学的 刘丽兰等【9 l0 1 人提出了基于层次分析法的制造网格资源调度方法，通过建立基于 t q c s 的多目标、多层次模型来选择满足用户需求的制造资源。 1 3 研究内容与论文结构 1 3 1 课题来源 本论文来源于广西科学研究与技术开发计划项目“面向中小企业的虚拟企业网络 化服务平台技术研究与建设( 桂科攻0 7 1 9 0 0 1 1 7 ) 。该项目主要面向中小企业、结合 2 桂林理工大学硕士学位论文 广西制造业信息化网络服务体系建设，研究和建设虚拟企业网络化服务平台。该平台 为一个相对独立的虚拟企业创建与运作技术支撑与服务子系统，主要起到利用网络对 广西中小企业进行优化组合，共享有限的资源、成本、技术和市场等，快速、及时的 为中小企业解决产品设计、制造、供销等经营过程中的技术问题，同时促进广西制造 业信息化的技术水平和建设步伐。 作为该项目的一个重要组成部分，资源调度系统主要研究在虚拟企业环境下资源 的建模及管理，并结合虚拟企业的特点详细研究其中的资源调度算法，从而实现制造 资源的优化调度和有效管理。本文主要研究其中的一部分内容，即虚拟企业制造资源 的局部调度分配问题。该问题可以归结为资源受限项目调度问题。 1 3 2 主要研究内容及章节安排 在将虚拟企业制造资源的局部调度分配问题归结为资源受限项目调度问题的基础 上，对r c p s p 和蚁群算法进行了深入的研究，设计了一种双种群蚁群算法用于求解 s r c p s p 。该算法将满足紧前关系的工作链表作为蚁群的巡游路径，针对问题的特点 设计了信息素更新机制和启发式信息策略，采用基于列表的s s g s 生成项目调度计划。 用m a t l a b 语言实现该算法，并用p s p l i b 中的基准问题对算法的性能和有效性进行测 试，取得了良好的结果，表明该算法用于求解s r c p s p 是可行的。 本文的章节安排如下：第一章介绍了本文研究背景及意义，概括了虚拟企业资源 调度问题的研究现状，指出了本文的研究方法和主要研究内容；第二章介绍了资源受 限项目调度的理论基础，回顾和总结了资源受限项目调度领域内近几年来国内外学者 的研究进展；给出了数学模型，以及主要的求解方法，并对这些方法进行了比较；第 三章介绍了蚁群算法的概念、模型及其应用，并与其他算法进行了比较；第四章介绍 了单模式资源受限项目调度的模型，设计一种了用于求解该问题的双种群蚁群算法， 利用p s p l i b 中的基准问题对该算法进行了验证，并对计算结果进行了分析比较：第 五章将本文设计的双种群蚁群算法应用于汽车设计制造虚拟企业的制造资源局部调度 问题，得出了汽车前端外观设计项目的最优资源调度分配方案，使得获得该项目的成 员企业以最小工期完成该项目；第六章对整个研究进行了总结，并对未来的研究方向 进行了展望。 3 桂林理工大学硕士学位论文 第2 章资源受限项目调度问题 资源受限项目调度问题( r c p s p ) 要求在满足任务紧前关系和资源约束的条件下， 安排所有任务的开工时间，最优化项目的某一个或者几个目标，如使项目总工期最短 等。在建筑工程、软件开发、飞机和轮船制造等单件或小批量生产的企业中，广泛存 在着r c p s p 。该问题已经被证明是n - p h a r d 问题，其模型非常丰富，作业车间调度问 题( j o b s h o ps c h e d u l i n gp r o b l e m ) 、流水车间调度问题( f l o w - s h o ps c h e d u l i n gp r o b l e m ) 等组合优化问题都是r c p s p 的特殊形式。因此，研究r c p s p 具有重要的理论和现实 意义。 2 1 项目调度 2 1 1 项目调度的定义和特征 ( 1 ) 项目的定义【川 项目的定义有很多，人们从不同的角度给出了许多不同的定义。质量管理专家朱 兰提出，一个项目就是一个计划要解决的问题。美国项目管理协会( p r o j e c tm a n a g e m e n t i n s t i t u t e ，p m i ) 给项目下的定义是：项目是为完成某一独特的产品、服务或任务所做 的一次性的努力。而国际标准化组织( i n t e r n a t i o n a ls t a n d a r do r g a n i z a t i o n ，i s o ) 从项 目管理过程的角度对项目下的定义是：项目是由一系列具开始和结束日期、相互协调 和控制的活动组成，通过实施活动而达到满足时间、费用和资源约束条件和实现项目 目标的独特过程。 ( 2 ) 项目的特征 项目的定义虽多，但是使用比较多的定义还是国际标准化组织提出的定义。项目 的特征可以归结为以下几条： ( 1 ) 目的性。项目的目的性就是任何一个项目都要有一个比较明确的目标，比如， 使项目的工期最小、费用最省、资源使用量最少等等。保持项目目标明确的最好办法 是使其可以验证或可以衡量，通常的做法是将项目的目标依照项目范围、进度计划和 质量、成本等来定义，使之明确或量化，例如，在多长的时间内花费多少完成什么任 务或工作。 相关性。项目的相关性是指项目的完成要通过执行一系列相互关联的活动。项 目是由一系列不重复的活动构成，这些活动由于其关联性，必须按照一定的顺序执行 ( 即活动的优先关系) 。例如，有些活动在其前项活动完成之前不能启动，而另外一些 活动则可以同时开工，从这个意义上看，项目可以当成一个系统来看，并且有内在的 4 桂林理工大学硕士学位论文 相关性。 ( 3 ) 制约性。项目的制约性是指每个项目在一定的程度上都受到客观条件和资源的 约束。项目需要运用各种资源来完成活动，如人、资金、技术、时间、信息等，这些 限制条件和项目所处的环境带来的客观环境等构成了项目的制约性。如果项目的制约 性比较小的话，则项目的成功几率很大：反之大大降低。 不确定性。项目在执行的过程中包含着一些不确定性。一个项目在开始之前， 一般都在一定的假设和预算上准备一份计划，而这种假设和预算往往与项目的真实情 况会有偏差，从而给项目带来一定程度上的不确定性。 周期性。项目的周期性是指项目有具体的时间计划或有限的寿命。项目是在有 限的期限内完成的，有明确的开始时间和结束时间。 其他特性。项目还有不可逆性、动态性及开放性等。 2 1 2 项目调度 项目调度问题就是针对项目过程的各项活动，研究和解决如何按时间对资源进行 安排，使预定目标最优化的问题。项目调度问题是运筹学的一个分支，基本上属于组 合优化问题类。其中的活动和资源都是抽象的概念，其具体指代的实体对象是非常广 泛的。面对复杂的实际生产调度问题，在生产计划与调度决策过程中，必须把人工智 能与管理科学、知识工程与系统工程、计算技术与通信技术、软件工程与信息工程等 多技术学科相结合、相互渗透，才能进一步开发有效的调度方法，并在实际研发或生 产中得到广泛应用。 项目调度问题在各个行业中普遍存在，项目中任务安排顺序的不同将直接导致项 目完成效果的不同，若按照合理的排序和理论及方法管理生产，可在最大程度上满足 企业的经济要求及发展需求。随着生产规模、生产方式及社会需求状况的变化，传统 调度理论得到了不断的改进、增补和发展，融入与结合了大量的先进理论、思想和方 法。在制造业、计算机软硬件行业、建筑行业等众多领域，项目调度问题具有很强的 实际意义和重大应用价值。 在制造行业中，调度是普遍使用的控制管理方法，应用范围非常广泛。近几年来， 关于调度问题的研究范围越来越大，发展日趋迅速。针对不同的生产领域形成了各具 特点的调度问题体系，且随着新方法及科学技术的诞生和发展，调度问题越来越具有 鲜明的时代感，其研究的现实性大大增强。应用于制造企业的调度问题主要可以分成 一下五方面： ( 1 ) 作业车间调度问题( j o b s h o ps c h e d u l i n gp r o b l e m ) ： ( 2 ) 流水车间调度问题( f l o w s h o ps c h e d u l i n gp r o b l e m ) ； ( 3 ) 机器调度问题( m a c h i n es c h e d u l i n gp r o b l e m ) ： 5 桂林理工大学硕士学位论文 ( 4 ) 运输调度问题( t r a n s p o r t a t i o ns c h e d u l i n gp r o b l e m ) ； ( 5 ) 工程项目中的调度问题，其中包括资源约束项目调度问题 ( 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 c d u f i n gp r o b l e m ) 。 调度问题的优化目标也具有多样性，主要分为三类： ( 1 ) 以资源有效利用为目标； ( 2 ) 以快速响应需求为目标； ( 3 ) 以遵守交货期、满足客户需求为目标。 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 gp r o b l e m ， r c p s p ) ，涉及到一系列的具体任务( a c t i v i t i e s ) 与一个有限的资源( r e s o u r c e s ) 集合， 这些任务之间存在逻辑上的关系，同时每项任务的执行又需要特定数量的全部或部分 资源，而项目调度就是要合理非配这些资源，安排这些任务的开始时间，从而优化一 个或若干个目标函数。 2 2 1 资源受限项目调度问题的提出 在实际项目的实施过程中，离不开各种资源的支持，比如设备、劳动力、物质材 料等，而这些资源并不是无限供应的。传统的解决项目调度问题的方法，往往忽视了 项目执行工程中的资源限制，由此便产生了资源受限项目调度问题r c p s p 。典型的 r c p s p 就是研究在满足项目紧前紧后约束和资源约束的前提下，确定项目中各项任务 的开始时间和结束时间，并使项目工期最短。 2 2 2 资源受限项目调度问题的类型 r c p s p 从资源约束的角度出发来研究项目调度问题，更加符合实际要求，因此， 一经提出就受到广泛关注，其模型也得到不断的丰富。根据调度目标、资源、执行模 式、任务执行的连续性、项目数量等五种属性的不同组合，项目调度问题可分成多种 类型。为了说明本文研究的具体模型，下面介绍一下项目调度问题的各个属性及其类 型。 2 2 2 1 调度目标 典型的r c p s p 的目标是使项目工期最短，然而根据实际问题的不同，其目标还有 其他类型。 ( 1 ) 最小化项目工期。基本r c p s p 问题的目标，即追求项目工期最短。 ( 2 ) 资源均衡利用。在项目执行过程中，如果不能均衡的利用资源，会出现时而 6 桂林理工大学硕士学位论文 资源紧张，。时而资源闲置的现象，从而造成资源不足或浪费的情况。因此，资源均衡 问题研究的就是在合理安排各项任务的前提下，如何充分利用资源。 ( 3 ) 最大化项目净现值。以项目的最大净现值为优化目标，建立带有贴现率的最 大化网络净现值的数学模型。该模型的应用以提高项目的经济效益为目标。 ( 4 ) 最小化项目运作成本。项目过程中的各种资源是有成本的，以此为目标的 r c p s p 将资源折算成成本，在满足约束的前提下，以最小化项目运作成本为目标。 本文的问题模型以最小化项目工期为目标。 2 2 2 2 资源 按照资源类型的不同，r c p s p 可以分为可更新资源问题、不可更新资源问题以及 双重约束资源问题。 ( 1 ) 可更新资源。资源的可使用量在项目工期中的每段时间内有限，但这段时间 过后可以再生或重用，如劳动力、设备场地等。 ( 2 ) 不可更新资源。资源的可使用量在项目启动时以总量形式出现，并随着项目 的推进而逐渐消耗掉，如原材料。 ( 3 ) 双重约束资源。资源在项目各阶段的供应量有限，并且在整个项目中的总量 也受限，如资金，其可以在整个项目和项目的各阶段都存在预算。 本文考虑的是可更新资源对r c p s p 的约束。 2 2 2 3 问题模型 依据问题模型的不同，r c p s p 可以分成以下几种类型【3 2 】：。 ( 1 ) 单执行模式资源约束项目调度问题( s i n g l e m o d er c p s p ，s c p s p ) 。其假设项 目中各任务都只有一种执行模式且不考虑不可更新资源，即在满足任务紧前紧后关系 约束和可更行资源约束的情况下，求达到项目工期最短这一优化目标的调度方案。 ( 2 ) 多执行模式资源约束项目调度问题( m u l t i m 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 t s c h e d u l i n gp r o b l e m ，m r c p s p ) 。该问题在s r c p s p 的基础上增加了不可更新资源约束， 并且允许任务有多种执行模式。 ( 3 ) 离散时间成本权衡项目调度问题( d i s c r e t et i m e c o s tt r a d e o f rp r o b l e m ， d t c t p ) 。该问题是由一般的时间成本权衡问题发展而来。d t c t p 中，假设项目中每 个活动的持续时间与其成本存在一定的函数关系，即分配给活动的资源越多则其持续 的时间越短。其求解过程就是为各个活动确定执行模式的过程，即寻找一种各活动执 行模式的组合，使各个活动在该组合确定的模式下执行能到达最好的效果。调度的目 标是在满足总资源约束条件下使项目工期最短；或者满足项目工期约束条件下使项目 总成本最小。 ( 4 ) 单模式资源水平问题( 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 ) 。该 7 桂林理工大学硕士学位论文 问题与s r c p s p 的假设条件相同，即假设项目中每个活动都只有一种执行模式且不考 虑不可更新资源，但其求解目标是在满足项目工期约束条件下，使项目工期各阶段内 各种可更新资源的最大消耗成本最低。 ( 5 ) 多模式资源水平问题( 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 ) 。该 问题与m r c p s p 的模型类似，区别在于m r l p 的求解目标是在满足项目工期约束条件 下，是项目消耗的资源总成本最低。 ( 6 ) 带最小最大时间滞后的资源约束项目调度问题( r c p s p m 缸) 。该问题就是 带时间窗约束的r c p s p 。在实际应用中，由于受到场地、贵重设备使用时间、气候或 重要人力资源等因素的影响，必须预先确定某些活动具备执行条件的可行时间范围， 以保证重要稀缺资源在不同活动中的合理分配和项目的正常进行，r c p s p m 积中的时 间窗口是活动之间的相对时间约束。优化目标是当并行活动发生资源冲突时，如何选 择先执行的活动和推迟执行的活动，使项目工期最短或如何保证受预约时间窗口约束 的活动在可行性，即在确保此特殊活动在满足时序、资源约束的前提下，活动开始时 间和完成时间在预约时间窗口内。 ( 7 ) 以最大净现值为目标的资源受限项目调度问题( r e s o u r c ec o m t r a i n e dp r o j e c t s c h e d u l i n gp r o b l e mw i t hc a s hf l o w ，r c p s p c f ) 。该问题假定活动持续时间与费用是有 一定的函数关系，而且活动的持续时间与资源需求无关，优化目标是项目净现值最大 化。 本文研究的是单模式资源约束项目调度问题j 2 2 2 4 任务执行的连续性 任务的执行方式可以根据是否可以被中断而分为两种类型： ( 1 ) 抢先式( p r e e m p t i v e ) 。任务在执行过程中可以先暂停执行，让其他任务先执 行，等满足一定条件后再继续执行。 ( 2 ) 非抢先式( n o n p r e e m p t i v e ) 。任务一旦开始执行就不能中断。本文研究的是 非抢先式r c p s p 。 2 2 z - 5 项目数量 根据问题所包含的项目数量，可以分为两类。 ( 1 ) 资源约束下单项目调度问题( r e s o u r c e - c o n s t r a i n e ds i n g l e - p r o j e c ts c h e d u l i n g p r o b l e m ，r c s p s p ) 。从狭义上讲，r c p s p 一般就是指单项目环境下的调度问题。如无 特别说明，研究学者提出的r c p s p 解决方法都是针对单项目而言的。 ( 2 ) 资源约束多项目调度问题( r e s o u r c e c o n s t r a i n e dm u l t i p r o j e c ts c h e d u l i n g p r o b l e m ，r c m p s p ) 。将r c p s p 扩展到多个项目同时进行，每个项目包含多个任务。 本文研究的是单项目调度问题。 8 桂林理工大学硕士学位论文 2 2 3 项目网络 通常，项目的一系列任务可以表示为一个节点式( a c t i v i t y - o n - n o d e ，a o n ) 有向 网络。在a o n 网络中，每一个节点表示一个任务，箭线表示任务之间的逻辑关系。例 如，在图3 1 中给出了一个a o n 网络的示例。 图2 1 节点式项目网络图 通常情况下，为了便于调度，要求各节点依次编号，原则上要求编号小的任务可 以是编号大的任务的前导任务( p r e c e d i n ga c t i v i t y ) ，但编号小的任务不可是编号大的 任务的后续任务( s u c c e e d i n g a c t i v 时) ，且网络内不允许出现循环和反馈。 2 2 4 目标函数 一般而言，项目调度的目标是最小化项目的总工期。通常情况下，提前项目的开 始时间，有助于缩短项目总工期。w i e s t 于1 9 6 4 年总结分析了两种任务开始时间的调 整方式。 最小项目总工期被认为是项目调度的常规目标函数，除最小化项目总工期外，最 小化项目总成本一般也被认为是常规目标函数，因为提前认为完工时间可以优化这类 目标函数值。 当然也存在所谓非常规目标函数。对于这类目标函数，提前任务完工时间或开始 时间，可能无助于改善目标函数。在某些情形下，延迟任务完工或开始时间，反而有 助于改善目标函数。如项目的净值就是这类目标函数的典型代表。资源约束下项目调 度问题的一些常见目标函数列于表2 1 。 表2 1 常见目标函数 目标名称文献 目标值计算方法 最小项目工s l o w i n s k im i f i f 知 期( 1 9 8 9 ) 最小平均延s i o w i n s k im i n 专( 卜以) b 9 桂林理工大学硕士学位论文 迟( 1 9 8 9 ) 晟小延期任 s p r e c h e r m i i l h 务数 ( 1 9 9 4 ) 最大净值 s p r e c h e r m a x 以 ( 1 9 9 4 ) 最小平均加 s p r e c h e r m i i l ；“一d t a 权时间流( 1 9 9 4 ) 最小加权延锄a 等m i i i m ( f - 嘭) 靠 迟( 2 0 0 0 ) 最小资源超 v i a n a 等m i i l m 觚 o ，( g 一嘭) + p ：m a x o , ( c 。一吖) 支 ( 2 0 0 0 ) 由于目标函数性质上的不同，对这两类目标函数，必然要求有不同的项目调度方 式。 2 2 5 约束条件 基本r c p s p 重要涉及到三类约束，一类是任务之间存在的逻辑约束( p r e c e d e n c e r e l a t i o n s ) ，一类是有限资源造成的资源约束( r e s o u r c ec o n s t r a i n t s ) ，一类是时间约束 ( t e m p o r a lc o n s t r a i n t s ) 。 在a o n 网络中，节点之间的箭线用于表示任务之间的逻辑关系。通常只考虑f s = 0 的情形，即一个任务的所有紧前关系结束后，该任务可以立即开始。 2 2 6 项目调度问题库 由于r c p s p 的复杂性，众多专家学者对此进行了研究，提出了大量算法。为了比 较分析这些算法的效率，需要有共同的项目样本。目前，在研究中大量用到的样本主 要有两套，一是p a t t e r s o n 于1 9 8 4 年总结的1 1 0 个经典调度问题，另一个是k o l i s c h 3 3 】 等于1 9 9 5 年采用实验设计方法设计的4 8 0 个典型调度问题。 2 2 6 1p a t t e r s o n 问题库 p a t t e r s o n 【5 7 1 于1 9 8 4 年所总结的项目调度问题库共有1 1 0 个项目调度问题，每个问 题包含7 5 0 个任务，涉及1 3 种可更新资源，其中4 个问题只涉及到1 种资源，3 个 问题涉及到2 种资源，其余问题都涉及到3 种资源。p a t t e r s o n 问题库在研究中被广泛 应用，已成为项目调度问题研究领域事实上的标准问题库。 2 2 6 1p s p l i b p a t t e r s o n 问题库虽然被广泛应用，其问题也非常经典，但存在一个无法克服的缺 1 0 桂林理工大学硕士学位论文 点，即这1 1 0 个问题不可能有效代表项目调度的各种情形。因此，k o l i s c h 等人于1 9 9 5 年在研究中提出了一个测试问题生成器p r o g c n ，可以根据参数设置生成符合要求的具 体调度问题。实验证明这些参数可以有效的控制生成的测试问题的难度。p r o g e n 生成 的测试问题构成了项目调度问题库( p s p l i b ) 的主体。k o l i s c h t 4 5 】等人详细阐述了 p s p l i b 中各种模型所代表的问题类型、问题生成细节、生成问题的实验设计及问题参 数等。之后，s c h w i n d t 等学者通过研究提出了另一些测试问题，对p s p l i b 进行补充。 p s p l i b 逐渐发展成为包含多种类型的r c p s p 的问题集，以及这些问题的最优解和启 发式解法。这些数据可以用来评价求解单执行模式与多执行模式r c p s p 的算法的有效 性，从而被广泛使用，形成了新的标准问题库。 2 3 资源约束项目调度问题的研究现状 项目管理的核心问题之一是项目计划与优化调度的理论与方法。资源约束项目调 度属于生产调度的范畴，自2 0 世纪6 0 年代提出以来，许多运筹学、应用数学领域的 学者进行了这一领域的研究。已有的研究主要是在假设项目信息完全已知的确定性环 境下设计优化调度方法，以求得在某一目标下最优的项目调度计划。优化方法包括分 枝定界法、基于优先规则的启发式算法、智能优化算法等。随着项目规模增大、复杂 度的提高，传统的项目调度方法已经无法满足现代项目管理的实际需求，这一矛盾推 动了项目调度领域的研究。 2 3 1 基于优先规则的启发式算法研究现状 k e l l y 1 1j 于1 9 6 3 年首先提出了解决基本r c p s p 的启发式方法，文中提出的调度生 成机制( s c h e d u l ec m n e r a t i o ns c h e m e ，s g s ) 为后来启发式方法的进展奠定了基础。此 后，各种不同的启发式算法相继被提出来。对于大规模的项目来说，启发式算法虽然 不能保证求得最优解，但速度快，可以在计算质量和计算效率上取得很好的平衡。 最早用于求解基本r c p s p 的启发式算法是基于优先规则启发式算法的单路算法， 这种方法只利用一次调度生成机制和一个优先规则，产生一个调度。目前，研究者针 对经典r c p s p 定义了多种多样的优先规则。 在单路算法之后，b o c t 0 1 - 1 1 2 】于1 9 9 0 年采用7 个不同的优先规则，进行了大量实验 测试，最后给出了较好的优先规则组合方法：t h o m a s 等人于1 9 9 7 年在此基础上提出 采用1 个不同的优先规则的凸组合，产生多于1 个的调度，再从中选择一个最优解作为 最优调度方案。 b e l l 1 3 等人于1 9 9 1 年在一种基于分离弧概念的基础上提出了一种两阶段方法。该 方法先构造一个时序可行解，再修复成一个时序和资源均可行的初始解，然后对此初 桂林理工大学硕士学位