（工商管理专业论文）基于蚁群算法的多模式资源受限项目调度问题研究.pdf

基于蚁群算法的多模式资源受限项f j 凋度问题研究 摘要 自上世纪5 0 年代，项目管理理论产生以来，伴随着社会经济的发展，项目管 理所涉及的领域愈来愈广泛，其所研究问题的深度也日益增加。如何在资源受限 制的前提下，通过对项目中各活动作出合理安排从而确保项目如期按质完成已经 是企业管理领域普遍关注的问题。研究结果显示，资源受限项目调度问题 ( 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 ) 已经成为了广大学者的 研究热点。 随着社会经济的发展，企业在临时面对某一不确定性要求时，由于受资源、 工艺等各类环境因素影响，项目中某一活动可能允许采用多种模式来执行，并且 每一种模式对应着不同的工期和资源需求量，因此，对于项目管理者而言，为了 尽可能完善地实现企业目标，往往需要灵活地选择最合理的执行模式，以便在满 足资源和工期要求的前提下，高效地实现既定的项目管理目标。然而，目前国内 学者对r c p s p 问题的研究大都基于一个活动只有一种固定工期的执行模式等假 设之上，对多模式资源受限项目调度问题( m u l t i 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 c t s c h e d u l i n gp r o b l e m ，m r c p s p ) 研究得还很少。因此，本文对多模式资源受限项目 调度问题展开研究，以期能在一定程度上用于指导实际。 首先，在对多模式瓷源受限项目调度问题( m u l t i m o d er e s o u r c ec o n s t r a i n e d p 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 ) 特点进行界定以及对项目调度优化模型回 顾的基础之上，构建了基于活动存在多种执行模式，每一个活动执行模式对应着 不同工期和资源需求量的m r c p s p 问题的数学模型；为了求解上述模型，本文在 详细阐述蚁群优化算法的基本原理以及当前的改进研究成果的基础上，提出了一 种新的改进蚁群算法，并对其在m r c p s p 问题的应用过程进行了设计；最后，为 了检验m p c p s p 模型的有效性及算法的优越性，采用了在学术界广泛使用的 p s l i b 中的标准多模式算例集进行了仿真试验。实验结果证明了本文模型的有效 性及算法的优越性。 本文的研究成果，不仅拓展了r c p s p 问题的研究领域，而且也为项目管理者 如何在项目持续时间和成本间实现均衡提供了一定的指导借鉴意义。同时将在很 多组合优化问题中得到成功应用的新型智能算法一蚁群算法应用于m r c p s p 问 题，既拓展了蚁群算法的应用领域，也为m r c p s p 等组合优化问题的求解提供了 全新的思路和方法。 关键词：资源受限；项目调度；多模式；蚁群优化算法 i i a b s t r a c t s i n c et h e5 0 so fl a s tc e n t u r y ，p r o j e c tm a n a g e m e n tt h e o r yh a s b e e na p p l i e dv e r y w i d e l vw i t ht h es o c i o e c o n o m i cd e v e l o p m e n t ：t h ea r e a so fs t u d y i n ge x p a n d i n g ，t h e d e p t ho ft h e i rr e s e a r c hi n c r e a s i n g n o w , a st h e w o r l de c o n o m yd e v e l o p sa n dt h e c o o p e r a t i o nl e db yt h ee c o n o m i cg l o b a l i z a t i o nd e e p e n s ，t h ep r o j e c tm a n a g e m e n t 1 s c o n s i d e r e dm o r ea n dm o r ei m p o r t a n tb yt h ee n t e r p r i s e s h o w t om a k eap r o g r a m b e c o m p l e t e do ns c h e d u l eu n d e r r e s o u r c ec o n s t r a i n e db ym a k er e a s o n a b l ea r r a n g e m e n t s f o rt h ev a r i o u sa c t i v i t i e sh a sb e c o m ea ni s s u e so fc o m m o nc o n c e r nf o rm a j o r i t l e so f t h ee n t e r p r i s e s i ti ss a i dt h a tr c p s ph a s b e e ns t u d y i n gb ym o r ea n dm o r es c h o l a r a s a st h ee c o n o m yd e v e l o p s ，u n c e r t a i n t y o fe n t e r p r i s e sl e db ye n v i r o n m e n t i n c r e a s e s p r o j e c tm a n a g e r so f t e nn e e dm a k eaf l e x i b l e a n de f f e c t i v ep l a nf o rt h e a l l o c a t i o no fr e s o u r c e sb e t w e e n t h ea c t i v i t i e so ft h ep r o g r a mt o a c h i e v et h e e s t a b l i s h e do b j e c t i v e so fp r o j e c tm a n a g e m e n t t h e r e f o r e ，i t i sv e r yi m p o r t a n tt o a c h i e v et h eb e s tb a l a n c eb e t w e e nt h e c o s ta n dt i m eu n d e ru n c e r t a i np r o j e c t e n v i r o n m e n t h o w e v e r ，t h ed o m e s t i cr e s e a r c h o nr c ps pi sm o s t l yb a s e do nt h e a s s u m p t i o nt h a to n ea c t i v i t y s h o u l db ef i n i s h e di no n em o d ew i t hf i x e dd u r a t i o n ， r e s e a r c ho nm r c p s pi ss t i l lv e r yl i t t l e t h e r e f o r e ，w es t u d yt h em r c p s p t h a tr e f e r s t ot h em u l t i m o d ea c t i v i t yt oi n s t r u c tt h ep r a c t i c e f i r s t l v ，o nt h eb a s i st h a td e f i n i n gt h ec h a r a c t e r i s t i c so fm r c p s p a n dr e v i e wt h e m a t h e m a t i c a lm o d e l sf o rr c p s p , w ec o n s t r u c tt h em a t h e m a t i c a lm o d e lf o rm r c p s p u n d e r t h ec o n d i t i o nt h a to n ea c t i v i t yh a sa t l e a s to n ee x e c u t i o nm o d ea n de a c hm o d e c o r r e s p o n d st o o n ed u r a t i o n i no r d e rt o s o l v ea b o v em o d e l ，w ee m p h a t i c a l l y d i s c u s s e dt h eb a s i cp r i n c i p l eo ft h es w a r mi n t e l l i g e n c ea l g o r i t h m - - t h e a n tc o l o n y a i g o r i t h m a sw e l la si m p r o v e m e n tr e s e a r c hf o rc u r r e n ta l g o r i t h m ，a n dt h e np r o p o s e da n e wi m p i r o v e da n tc o l o n ya l g o r i t h ma n da n a l y s e si t sa p p l i c a t i o np r o c e s sm t n e 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 ts c h e d u l i n gp r o b l e m ；l a s t l y , i n o r d e rt o c o n f i r mt h ev a l i d i t yo ft h em o d e la n dt h ea l g o r i t h m ，w et a k ea ne x p e r i m e n tb a s e do n t h es t a n d a r di n s t a n c e so fp sl i b t h ee x p e r i m e n t a lr e s u l ti n d i c a t e dt h a tt h em o d e l a n d t h ea i g o r i t h mp r o p o s e di nt h i sd i s s e r t a t i o na r eb o t he f f i c i e n ta n de f f e c t i v e t h i sr e s e a r c hn o to n l yb u r d e n st h er e s e a r c hf i e l do fr e s o u r c e s c 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 ，b u t a l s om a k e sc e r t a i ng u i d a n c ef o ra c h i e v i n gt h e b a l a n c e b e t w e e nc o s ta n dt i m ei nt h ep r o c e s so fp r o g r a mm a n a g e m e n t o nt h eo t h e r h a n d s ，t h e 1 1 1 基于蚁群算法的多模式资源受限项目调度问题研究 a p p l i c a t i o no ft h ea n tc o l o n ya l g o r i t h mi nm r c p s p , w h i c ha l w a y su s e di no t h e r o p t i m i z a t i o np r o b l e m s ，p r o v i d e ss o m ei m p o r t a n tt r a i no ft h o u g h ta n dm e t h o df o r r e s o u r c e sc o n s t r a i n e d p r o j e c ts c h e d u l i n gp r o b l e m ，w h a t sm o r e ，w i d e n s t h e a p p l i c a t i o na r e ao fa 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 m k e yw o r d s ：r e s o u r c e sc o n s t r a i n e d ；p r o j e c ts c h e d u l i n g ；m u l t i - m o d e ；a n tc o l o n y a l g o r i t h m i v 硕。l 学位论文 插图索引 图1 1研究框架4 图2 1项目管理研究进程7 图3 1a o n 网络节点图2 4 图3 2a o a 网络节点图2 5 图3 3单代号网络示意图2 6 图3 4 双代号网络图2 7 图4 1基本蚁群算法运算流程3 4 图4 2活动模式链一41 v i i 基于蚁群算法的多模式资源受限项目调度问题研究 表2 1 表4 1 表4 2 表4 3 附表索引 v i i i o o 6 o o o o 4 4 4 程 一计 一 进 统 一 展果据 发结数 术解关 技求相组划例果数计算结参络验验应网实实对 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名： 旅研 日期：1 删肛日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密昭。 ( 请在以上相应方框内打“4 ) 作者签名： 导师签名： 功伽 月月 年叩 年年 竹j1 仉 时 争盆 期期 硕一j ：学位论文 1 1 研究背景及意义 第1 章绪论 项目( p r o j e c t ) 是一个特殊的将被完成的有限任务集合，它是在一定时间内， 满足一系列特定目标的多项相关工作的总称t lj 。 项目管理( p r o j e c tm a n a g e m e n t ) 是以项目为对象的系统管理方法，通过一个临 时性的专门柔性组织，对项目进行高效率的计划、组织、指导和控制，以实现项 目全过程的动态管理和项目目标的综合协调和优化【2 j 。随着社会经济的迅速发展， 项目管理在生产经营等社会经济活动中的重要性日益凸显。特别是进入上世纪 8 0 9 0 年代以来，随着信息系统工程、网络工程、软件工程、大型建设工程以及 高科技项目开发等项目管理新领域的出现，项目管理在理论和方法等方面不断发 展和现代化，项目管理进入了现代项目管理阶段。在此阶段，项目管理的应用领 域迅速扩展到社会生产和生活的各个领域和各行各业，并在企业的战略发展和日 常经营中的作用越来越重要，现代项目管理已成为发展最快和使用最为广泛的管 理方式之一1 2 j 。项目管理有三个重要目标：成本、工期和质量要求【3 】。其中，项 目调度管理是项目管理的重要组成部分，合理有效的项目调度计划是决定项目成 败的关键因素之一。它在工程建设、软件开发等行业中尤其有着广泛的应用。在 一个项目运行过程中，能否对它实施有效的调度管理，直接关系到项目能否按预 定工期完成，最终影响到项目的成本及其最终盈利能力。 项目调度( p r o j e c ts c h e d u l i n g ，p s ) 是为实现项目预定目标而确定和实施恰当策 略的过程，在项目管理中占有极其重要的作用。近年来，无论在研究和实践中， 它日益引起人们的关注。实践和理论研究均显示，项目调度问题是整个项目实施 过程中最容易引发各类冲突，对成功实现项目目标影响最为重要的关键因素之一。 项目调度问题是指在一定的约束条件下，将既有资源合理地分配给所要调度的活 动，从而达到预定项目目标的过程( 一般是以项目完工时间最小化为目标) 。项目 调度管理包括为确保项目按期完成所必须执行的一系列活动，其主要内容可以概 括为：活动定义和排序，作业工期估计，编制调度计划以及调度控制等。调度问 题，简单来说，就是以一个或多个项目为研究对象，在满足一定约束条件的基础 上合理地安排活动执行顺序d j 。项目调度问题中的约束条件是指在对各活动进行 调度时要满足活动与活动之间的逻辑先后顺序和资源限制双重约束。项目调度中 的资源通常是一种泛指，通常包括资金、机器、人力资源、材料和能源等在现实 生活中具有稀缺性的资源。然而，在关键路线法( c p m ) 和计划评审技术( p e r t ) 等 基于蚁群算法的多模式资源受限项目调度问题研究 经典项目调度计划方法中，出于简化问题的需要，通常假定项目中每一组成活动 所需的资源供给是不受限制的，项目管理者仅需要依据工序间的逻辑先后关系确 定项目的关键路线，所有活动均可以在其直接紧前活动结束后立即启动。但是， 在实际的工作环境下，由于资源具有稀缺性，任何一个行业、任何一个企业，其 所拥有的资源数量都是受到不同程度限制的，其结果就使得在实际项目调度过程 中，一些原本依据活动逻辑关系可以并行操作的活动由于某些稀缺资源为关键线 路和关键线路上的活动所共享而不得不推迟开工，最终导致其所在的项目延期。 伴随着社会进步和项目的复杂化，尤其是信息时代的来临和高新技术产业的 飞速发展，资本、服务、信息、技术、劳务人才在全球范围内流动空前加快，项 目的特点发生了显著变化，项目本身和执行环境的不确定性及复杂性不断增多和 增强，传统的项目调度方法越来越难以适应现代项目管理的实际需求。因此，结 合项目实际情况对资源约束下的项目调度问题进行研究就具有十分重要的理论和 实践意义。 资源受限项目调度问题( 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 ) 是指在满足项目时序和资源双重约束的条件下，为项目中的所有活动分配 资源并合理安排所有任务的开始和结束时间，以达到某一既定目标的最优化( 如工 期最短，成本最小，资源均衡等) 【2j 。该问题在建筑工程、软件开发等单件或小批 量生产方式的企业中有着较为广泛的应用，如作业车间( j o bs h o p ) 调度，流水车间 ( f l o ws h o p ) 调度等。理论研究证明，该问题属于n p 问题，模型多样，是一类重 要的组合优化问题，且涉及生产制造，科技研发等众多行业，与实践结合紧密， 因此吸引了国内外众多学者在此领域进行研究，其中，b o w m a n 、p r i t s k e r 、 p a t t e r s o n 、s t i n s o n 、c h r i s t o f i d e s 等学者都在此领域取得了一定成果。 目前，国内外学者对r c p s p 的研究主要从两个方面进行展开：一方面是通过 研究新的求解算法或对原有算法进行改进来对关于调度问题的结果进行优化，如 利用粒子群算法、蚁群算法等智能算法来对各类型r c p s p 问题进行求解。另一方 面则从企业生产运作实际出发，对r c p s p 模式不断进行改进，通过不断将新的与 企业实际运营相关的项目特征纳入研究范畴来对项目调度理论研究进行改进。上 述两个方面的研究共同推动了项目调度研究理论的发展。伴随着经济全球化导致 市场竞争的日趋激烈，现代项目日趋复杂，其对项目工期、质量、成本的要求越 来越苛刻，因此，越来越多的学者开始从事后一方面的研究并提出了一些新的具 有实际指导意义的r c p s p 模型，从而大大加速了项目管理研究的现代化、科学化 和合理化。其中多模式资源受限项目调度问题( m u l t i m o d er e s o u r c ec o n s t r a i n e d p 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 ) 就是在此背景下结合生产实际所提出的一种 新的r c p s p 模型。 多模式资源受限项目调度问题( m u l t i - 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 c t 硕l ：学位论文 s c h e d u l i n gp r o b l e m ，m r c p s p ) 又可以称为多执行模式资源受限项目调度问题，所 谓多模式( 又称多执行模式) 指的是在实际的项目管理中，由于受资源分配不同等 项目环境影响，项目中某一活动可能允许采用多种模式来执行，该活动的每一种 模式对应着不同的工期和资源需求量，因此，m r c p s p 是对普通资源受限项目调 度问题模型的扩展。该问题模型在资源受限项目调度问题的基础之上考虑了不可 更新资源限制，并且假定每一种活动可能有多种可供选择的执行模式【4 】。在实际 的项目管理过程中，资源总是稀缺的，为了提高资源利用率，项目负责人出于某 种考虑，往往会依据项目中各活动的轻重缓急程度来决定对各个活动的资源投入 量，而在实际工作过程中，各工作所获得的实际资源投入量影响着该活动的工期： 当活动比较紧急时，通过加大对该活动的资源投入量，可以缩短完成该活动所需 要的工期；当活动可以适当延缓且不会对整个项目工期产生延误时，可以考虑通 过减少对该活动的资源投入量以便降低项目成本，获得更大收益。所以，在一般 的实践工作中，各活动会由于所获得的资源不同而具有不同的工期，即同一活动 可以有多种执行模式活动，不同的活动执行模式会有不同的活动工期以及相应的 资源需求量，最终会形成不同的工期，因此，与传统的资源受限项目调度问题模 型相比，m r c p s p 模型更贴近项目管理实践工作，更有可能解决好项目管理实际 工作中的问题，因此，也就更具有理论与实践价值。 1 2 研究思路与框架 通过对资源受限项目调度问题研究现状进行阐述，结合目前项目管理工作的 实际要求与未来的发展趋势，本文指出了对多模式资源受限项目调度问题进行研 究的必要性和意义；然后在对任务多模式特征进行界定和分析的基础上，对多模 式资源受限项目调度问题进行了数学建模研究；针对普通蚁群优化算法在解决组 合优化问题时所存在的不足，提出用改进的蚁群优化算法求解上述模型，即在阐 述蚁群优化算法的原理、流程、优缺点的基础上，对蚁群算法进行了改进并结合 m r c p s p 问题实际特征设计了算法结构；最后，为了验证本文所提出的模型和蚁 群优化算法的优越性，选择了有关多模式资源受限项目调度问题的的标准算例集 进行了仿真实验并对实验结果进行了分析。本文的研究框架如图1 1 所示： 基于蚁群算法的多模式资源受限项目调度问题研究 图1 1 研究框架 本文通过结合项目管理实际情况，在总结已有资源受限项目调度问题研究成 果的基础上，提出了多执行模式活动概念，并对其特征进行了描述和界定，构建 了多模式资源受限项目调度问题数学模型，并且对其进行了仿真研究，本文主要 创新之处在于： ( 1 ) 结合国内外研究的最新成果，从项目本身的特点出发，对多模式项目调 度问题进行了研究。该研究是在项目管理日趋复杂化的背景下，针对企业在实际 工作中所面临的实际环境所提出来的，适应性更强，对项目管理实践工作也更具 有借鉴和指导意义。 ( 2 ) 模型所阐述的多执行模式活动理念是在结合企业实际运营情况基础之上 对传统资源受限项目调度问题的拓展，本文中所构建的多模式资源受限项目调度 问题模型，丰富了传统r c p s p 的理论与实践内涵，为更好地研究相关调度问题提 供了一定的理论准备。 ( 3 ) 本文提出运用元启发式算法一改进蚁群优化算法来求解m r c p s p 模型。 在对蚁群优化算法特征进行分析基础上，提出了多模式资源受限项目调度问题的 活动模式表达方式以及活动模式列表的生成方式并设计了针对m r c p s p 问题的 求解步骤，并且采用c + + 编程进行了实现。将改进蚁群优化算法应用于求解 m r c p s p 问题，在充分利用蚁群算法搜索能力强、鲁棒性强等优点的基础上，结 合m r c p s p 问题实际，通过借鉴文献【5 】和文献【6 】中提出的转移概率准则和信息 素更新策略有效地克服蚁群算法易陷入局部最优解的缺陷，从而确保了蚁群算法 硕- 二学位论文 关于m r c p s p 问题求解的全局最优。最后通过仿真实验证明了该算法求解的有效 性，因此，这种改进蚁群算法是一种有效的解决资源受限项目调度问题的新思路。 基于蚁群算法的多模式资源受限项日调度问题研究 第2 章理论基础与文献综述 本章对m r c p s p 相关研究成果以及求解进行了总结。其中，2 1 节对项目调 度问题进行了分类；2 2 节对有关r c p s p 研究进行了综述；2 3 节对有关m r c p s p 研究进行了较为详尽的论述；2 4 节对有关m r c p s p 的求解方法进行了论述。 2 1 多模式资源受限项目调度问题的提出 资源受限项目调度理论是在考虑资源受限前提下对项目调度问题进行相关研 究，被提出以来，一直受到国内外学者的关注。随着社会经济的飞速发展以及项 目管理工作的日益复杂，尤其是网络信息技术、经济全球化所导致的项目自身特 点显著改变以及项目所处环境不确定性及复杂性的不断增强，使得资源受限项目 调度理论得到了很大的发展。目前，针对该领域的研究范畴已经由最初只研究资 源不受限条件下的项目调度问题( p s p ) 逐步扩展至对各种类型的资源受限条件下 项目进行调度，研究内容日益丰富，具体包括多项目调度问题、多模式调度问题、 活动可拆分调度问题等，这些研究越来越与实践中的项目具体特征相符合，因此 更具理论研究和实践指导意义。概括而言，关于项目调度问题的研究历程可概括 如下： 资源不受限的项目调度问题( p r o j e c ts c h e d u l i n gp r o b l e m ，p s p ) ，即图2 1 中的 最低层，是各类型资源受限项目调度问题研究的基础。针对该问题，在研究中一 般采用关键路径法( c p m ) 和计划评审技术( p e r t ) 等传统方法进行求解1 2 j 。c p m 和 p e r t 方法都仅仅考虑活动的时序约束而不考虑资源约束，即都假定项目中的任 何活动所需资源的供给都是无限的，项目中的某一活动在其所有直接紧前活动都 完成后就可以马上开始。但项目管理实践表明，资源总具有稀缺性，在对项目实 施调度的过程中，对于在技术上可同时开工的几项活动，为了确保项目调度的顺 利执行，必须对资金、机器等有限资源进行合理考虑。即如果多项可同时开工的 活动所需资源量超过所能提供的资源量，那么就必须推迟若干可同时进行的活动 从而导致整个项目的结束时间可能晚于在不考虑资源约束时的项目关键路径长 度。伴随着这类在经典c p m p e r t 项目调度模型中加入资源约束因素，传统的 p s p 也就逐步拓展至更具实际意义的r c p s p 研究领域。即图2 1 中的第二层。第 三层则是在充分考虑了不同项目所具有的不同特征和执行环境下的r c p s p 问题， 主要涉及多项目调度问题、多模式r c p s p 问题等。如图2 1 中第三层所示。 硕i 学位论文 图2 1 项目管理研究进程 在本文中，为了研究的简明，按照项目中活动是否具有多种执行模式，可以 将项目调度问题分为单执行模式项目调度问题和多执行模式项目调度问题。通常， 所有的资源不受限项目调度问题都属于单执行模式项目调度问题；资源受限项目 调度问题类型多样，总体而言，依据其所研究涉及的实际问题，可以分为单模式 资源受限项目调度问题( s i n g l e - 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 t s c h e d u l i n g p r o b l e m ，r c p s p ) 和多模式资源受限项目调度问题( 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 je c ts c h e d u l i n gp r o b l e m ，r cp s p ) 。 2 1 1 单模式项目调度问题 2 1 1 1 资源不受限项目调度问题 有关项目调度问题的研究源于上世纪5 0 年代，最初是研究资源不受限项目调 度问题( p s p ) ，较早用于解决项目调度问题的工具是苷特图( g a n tc h a r t ，又称条形 图) 。苷特图是由h e n r y g a n t 于上世纪设计开发出来的。该方法具有绘画简单，明 了易懂，容纳信息多，适合于项目管理人员随时检测和计算资源需求量的优点。 但苷特图作为一种简单的应用工具，在解决实际项目调度问题时，存在着不能准 确全面反映各项活动间相互关系以及不能准确表示整个项目中各关键活动和非关 键活动之间的联系等诸多缺陷。因此，苷特图般只适用于小而较简单的项目调 度而很难满足现代项目管理工作的要求。 针对苷特图存在的上述不足，2 0 世纪5 0 年代末，网络计划技术应运而生。 网络计划技术是一种运用网络计划对活动的工作调度进行安排和控制，以保证实 现既定目标的计划管理技术。一般而言，运用网络计划技术来解决p s p 时应包括 如下步骤：( 1 ) 将项目中各活动的先后顺序及其相互关系以网络图形式表示出来； 基于蚁群算法的多模式资源受限项目调度问题研究 ( 2 ) 按某种方法来确定计划中的关键活动以及关键路径，并通过不断改善优化， 选择最合理调度方案并付诸实施；( 3 ) 对计划执行过程实行严格监督和有效控制， 以确保有效利用资源和尽快好省的完成目标任务。 网络计划技术的种类很多，如果依据项目中各任务的工期和逻辑关系来划分， 通常可归纳为四种类型。 表2 1 网络计划技术发展进程 关键路径法( c p m ) ：该方法由兰德公司和杜邦公司于1 9 5 8 年提出。通过该方 法可以确定出项目中每个活动的最早、最晚开始和结束时间，并通过计算最早时 间和最晚时间的时差可确定出各个活动的完工紧迫性及重要性。在c p m 中，一 般将时差为零的活动称为关键活动。运用c p m 来解决项目调度问题的实质就是 根据重点论思想，通过确定项目的关键活动和关键线路来重点解决项目调度过程 中的主要问题，从而确保项目的顺利实施。 计划评审技术( p e r t ) 是在美国海军制定的北极星导弹研制计划基础上发展 起来的，该方法是一种活动工期具有不确定性的网络计划图，其基本形式与c p m 网络计划基本相同。 图形评审技术( g e r t ) 是研究者充分考虑了项目执行过程中所存在的随机性， 把概率论引入到p e r t 中产生的一种网络计划技术。与c p m 等方法相比，该方 法的网络逻辑和任务工期都是不确定的，即除了活动工期的不确定外，该方法还 允许项目中的活动存在概率分支，即项目中活动的完成结果不是唯一的，而是存 在多种结果。 上世纪8 0 年代初，人们又通过把风险决策理论引入g e r t 提出了风险评审 技术( v e r t ) ，该技术能够对项目活动的质量、时间、费用三坐标进行综合仿真和 决策，但由于在对上述三坐标进行仿真和决策的过程中必须涉及到某些很难解决 的数学难题，所以大大限制了风险评审技术( v e r t ) 在实践中的运用。 2 1 1 2 单模式资源受限项目调度问题( s r c p s p ) 1 资源受限项目调度问题的产生及描述 在项目管理实践中，对项目中每一个活动进行执行都是需要耗费多种类型的 资源的，一般来说，资源都具有稀缺性，所以资源的使用都受到一定程度的制约。 因此，如何在有效利用各种有限资源的前提下确保项目顺利完成就成为了一个具 有积极现实指导意义的理论问题。 硕一l 学位论文 上述网络计划技术，如p e i 玎c p m 等作为非常有效的项目调度工具，被广泛 应用于项目管理中，但由于忽略了资源稀缺性的限制，所以根据这些方法编制的 计划和控制方案在资源受限的情况下很难确保其实际可行性，在此背景下，资源 受限项目调度问题( 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 ) 就应 运而生了。 单模式资源受限项目调度问题( s 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 c t s c h e d u l i n gp r o b l e m ，s r c p s p ) 通常是指个项目由一系列相互关联的活动组成， 这些活动一般只采用一种执行模式来完成，每一活动对应着相应确定的工期和资 源需求量，关于此类问题的解是在满足紧前关系和资源双重约束条件下产生的一 种能使某些项目管理目标实现最优的调度方案。研究表明，s r c p s p 在理论上属 于n p h a r d 问题，是一类重要的组合优化问题，同时也是工程管理中最常涉及的 问题类型之一，关于这类问题的模型十分丰富，实际工作中的许多问题，如作业 车间( j o bs h o p ) 调度，流水车间( f l o ws h o p ) 调度等都是r c p s p 的特殊情形【2 1 。此 外r c p s p 在建筑工程，软件开发等以单件或小批量作为生产模式的企业中也有 广泛应用，因此研究r c p s p 具有重要的理论和现实意义。 2 资源受限项目调度问题的组成要素 在r c p s p 问题中，依据问题中相关数据在进行调度前是否已知，可以分为确 定性资源受限项目调度问题和模糊性资源受限项目调度问题。本文讨论的是有关 确定性项目调度问题的分类。 资源受限项目调度问题由资源、活动、目标函数三要素组成【7 l 。实质上，正 是由于资源的不同数量和类型、与任务相关的错综复杂的约束条件，再加上用来 度量不同指标的目标函数，才构成了种类繁多的r c p s p 问题。 ( 1 ) 资源 按照文献【2 】的分类方式，在项目调度中，资源可分为可更新资源、不可更新 资源和双重资源三种类型。可更新资源是指该种资源的使用量在项目工期的每个时 段都受到约束；不可更新资源则是指某类资源在整个项目工期内受限；双重约束资 源是指某类资源使用量既在整个项目工期内受限，同时又在每个时段内受到限制。 在项目管理的日常工作中，依据上述定义，通常把劳动力、机器设备等视为可更新 资源，将能源、原材料等划为不可更新资源，而将双重约束资源分配问题转化成对 应的可更新资源和不可更新资源分配问题来进行解决。( 如：资金，当项目投资总 量为定值时，其被看作为不可更新资源，而在每个阶段运作的资金流又被认为是可 更新资源1 。随着s r c p s p 研究理论的日益深入，有学者提出了部分可更新资源定 义，用来定义那些处在某特定时间段内的可更新资源或不可更新资源。 ( 2 ) 活动 活动是项目最基本的组成要素，也是项目调度管理的对象。依据所研究项目 基于蚁群算法的多模式资源受限项日调度问题研究 特征的差异，活动又可称为作业、任务、工序等。在s r c p s p 模型中，除了事先 设定的虚活动，其它活动的执行都需要消耗一定数量的资源和时间。依据所描述 活动的特征差异，活动可分为多种类型。依据活动在执行过程中是否可被中断可 分为可拆分活动和不可拆分活动，其中，不可拆分活动是指活动一旦开始就不允 许被中断，直至完工，而可拆分活动在加工过程中允许被中断，然后在中断点处 可继续加工，任务中断前后加工时间的总和等于不中断情况下的活动加工时间； 依据活动的执行工期是否确定，活动又可以定义为确定性活动和不确定性活动， 确定性活动的资源需求量为常量而不确定性活动的资源需求量通常为变量；依据 活动对于资源需求的特性，活动又可以分为资源需求确定型活动和资源需求变量 型活动。此外，在进行项目调度时，一般都需要考虑活动与活动之间的时序关系( 逻 辑关系) 。所谓活动间的时序关系是指项目中各活动被执行的时间先后顺序，如果 活动j 必须在活动k 完工之后，则称活动k 和j 之间存在时序约束关系，其中活 动j 就是活动k 的紧前活动。项目管理中，通常用网络图来表示活动与活动之间 的时序关系。 ( 3 ) 目标函数 目标函数是项目管理者进行项目调度所希望达到的优化目标，能否按计划成 功达到既定的目标是衡量项目管理绩效优劣的重要指标，一般而言，关于r c p s p 的目标函数可以分为两类。一类主要包括项目总工期最小、项目总成本最低、项 目延误最小等，这类目标函数通常满足两个条件：( 1 ) 目标函数是求最小值；( 2 ) 目标函数是完工时间的单调非降函数。另一类则通常包括最大净现值、提前完工 费用和误工费用最小等目标。 3 资源受限项目调度问题的分类 如上所述，s r c p s p 一般是由活动、资源、目标函数三要素组成的，因此， 依据上述三要素分类的不同，r c p s p 也可以归纳为不同的类型。 依据主要约束条件之一的资源类型的不同，调度问题可以分为可更新资源问 题，不可更新资源问题以及双重约束资源问题。 依据调度过程同时处理的项目个数，可以分为单项目资源受限项目调度问题 和多项目资源受限项目调度问题。与单项目( s i n g l ep r o j e c t ) r c p s p 相比，多项目 r c p s p 是一个更为复杂的问题，其不但要求满足每个项目内部各任务的时序约束 和资源约束，还需要考虑在资源和时序双重约束下，对所有项目活动进行调度安 排以实现项目总工期的最小化。目前，关于资源受限单项目排序问题研究国内外 学者已经取得了丰富的研究成果，而对资源受限多项目排序问题的相关研究还比 较少，很难满足解决实际工作中存在的各种不同类型的多项目资源受限项目调度 问题的需要。 依据项目中正在执行的活动能否可被中止，r c p s p 可分为抢占式 硕七学位论文 ( p r e e m p t i v e ) r c p s p 和非抢占式( n o n p r e e m p t i v e ) r c p s p 。前者规定项目中的活动 一旦启动，就必须不问断地执行下去直至最后完成，后者则假定项目中所包含的 活动在项目环境发生变化时，可以暂停某些正在执行的活动，待条件重新满足时 再继续执行该活动。 依据项目管理目标的差异，调度问题又可具体分为离散时间成本权衡项目调 度问题、项目工期最短r c p s p 问题、现金流优化r c p s p 问题、以最大净现值为 目标的资源受限项目调度问题、带最小最大时间滞后的资源受限项目调度问题等。 根据活动工期是否确定，r c p s p 可划分为确定性r c p s p 问题和随机分布 r c p s p 问题。 2 1 2 多模式资源受限项目调度问题 依据上述单模式资源受限项目调度问题( s 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 d p 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 ) 和多模式资源受限项目调度问题 ( m u l t i m o d er 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 ，m r c p s p ) 的分类， 两者的根本区别在于项目中活动可执行模式的个数，前者假设项目中每个活动都 只有一种执行模式且不考虑不可更新资源，一般是在满足活动问紧前关系约束和 可更新资源约束的情况下，求达到项目工期最短这一优化目标的调度方案；后者 则在单模式资源受限项目调度的基础上增加了不可更新资源约束，并且认为同一 活动有多种执行模式，但同时认为活动的执行模式一旦确定下来，多模式资源受 限项目调度问题就转变成为了单模式资源受限项目调度问题。本文就是针对活动 多执行模式来进行项目调度的相关研究。 在多模式资源受限项目调度问题中，同一活动所选择的执行模式不同，所需 要的资源需求量和活动工期也往往不同，本文就是研究活动具有多种执行模式的 项目调度问题。 依据上述关于资源受限项目调度问题的分类，多模式资源受限项目调度问题 属于图2 1 中的第三个层次。该层次充分考虑了项目管理实际过程中，资源供给 量的不同对项目活动工期的影响，并进而对整个项目工期