（系统工程专业论文）基于启发式算法的柔性资源受限项目调度研究.pdf

摘要 随着经济全球化导致市场竞争的日趋激烈，现代项目日趋复杂，要求周期 更短、准时完工率更高、成本更低。传统的项目进度计划方法虽然在解决工程 单目标优化如工期优化、费用优化或资源均衡优化方面，给项目管理者带来了 极大方便，但是现代项目不但考虑工期、费用和资源均衡目标的优化，还要综 合考虑工程质量、风险、安全等诸多因素，有时甚至要考虑在资源均衡、安全、 风险约束下的项目质量、费用、工期的多目标优化，使项目调度计划具有更高 的稳定性、适应性和准确性。因此必须对传统的项目进度计划与方法进行改进 或提出新的项目调度技术与方法，以满足现代项目管理的需求。 在资源受限的项目调度过程中存在着资源冲突问题，严重影响着项目活动 的执行。在解决资源冲突问题上并没有一个很好的方法，资源的柔性能力为解 决这一问题开辟了出路。一些学者从全柔性资源开始研究，逐渐将全柔性资源 向部分柔性资源延伸，并且发现部分柔性资源通过合理有效的管理和利用，也 可以达到全柔性资源的效果。论文通过对资源受限的项目调度进行研究，将资 源拓展为柔性资源，并进行了探讨。 论文首先综述了国内外学者对资源受限项目调度研究的现状；在前人研究 的基础上对资源受限的项目调度的分类进行了研究，并主要按照活动的执行模 式将资源受限的项目调度分为单模式资源受限的项目调度、多模式资源受限的 项目调度、离散时间成本权衡问题的项目调度、单模式资源水平问题的项目调 度和多模式资源水平问题的项目调度，对这些不同类型的资源受限的项目调度 模型进行了分析，并研究了其数学求解方法，分析了各种方法的优缺点。 其次，将资源拓展为柔性资源，并提出了柔性资源的概念、分类以及对其 有效性进行了探讨；基于资源受限的项目调度模型中的一种：。建立了单模式柔 性资源受限的项目调度模型。 接着最后将启发式算法运用于项目调度模型的求解，提出了解决柔性资源 受限的项目调度模型的算法步骤，用m a tl a b 语言进行了编程，同时用一个具体 的算例论证了该算法的有效性：通过合理管理和使用部分柔性资源可以达到全 柔性资源的效果 关键词：柔性资源，资源受限，项目调度，启发式算法 a b s t r a c t a l o n gw i t ht h ee c o n o m i cg l o b a l i z a f i o n , c o m p e t e n c 2o f t h em a r k e tw a s g r a d u a h y s e v e d t y ，m o d e mp r o j e c ti sg r a d u a l l yc o m p l i c a t e d , w h i c hr e q u e s t ss h o r t e rp e r i o d , h i g h e rp u n c t u a lc o m p l e t i o no fw o r kr a t e a n dl o w e rc o s t a l t h o u g ht r a d i t i o n a l s c h e d u l i n gp l a no fp r o j e c tc o u l ds o l v et h ea s p e 虻- t so fs i n g l et a r g e to p t i m i z a t i o ns u c h a st h eo p t i m i z a t i o no ft i m e ，c o s t sa n dr e s o u r c e s b a l a n c e ，m o d e mp r o j e c tn o to n l y c o n s i d e r st i m e ，e x p e n s e sa n dr e s o u r c e sb a l a n c e dt a r g e to p t i m i z a t i o n ，b u ta l s oh a st o s y n t h e s i z e dc o n s i d e rp r o j c dq u a l i t y , r i s k , s e c u r i t ya n dm a n yo t h e rf a c t o r s ，s o m e t i m e s e v e nt oc o n s i d e rm u l t i - t a r g e t so p t i m i z a t i o nl i k er e s o u r c e sb a l a n c e d , t h es e c u r i t ya n d t h er i s kr e s t r i c t i o nu n d e rp r o j e c tq u a l i t y , c o s t sa n dt h el i m i tt i m ea n ds oo n , w h i c h m a k ep 加j c c is c h e d u l i n gp l a nh a v eh i g h e rs t a b i l i t y , a d a p t a b i l i t ya n da c c u r a c y t h e r e f o r e ，i no r d e rt os a t i s f yt h ed e m a n do fm o d e mp r o j e c tm a n a g e m e n t ，w em u s t m a k ei m p r o v e m e n tt ot h et r a d i t i o n a lp r o j e c tp r o g r e s sp l a no rp r o p o s en e wm e t h o d s t h e r ei sr e s o u r c e sc o n f l i c tp r o b l e mi n t h ep r o c e s so fr e s o u r c e - c 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 , w h i c hs e r i o u s l ya f f e c t st h ee x e c u t i o no fp r o j e c ta c t i v i t y b u tt h e r e i sn o tag o o dm e t h o da b o u tw h e nt or e s o l v er e s o u r c e sc o n f l i c tp r o b l e m ，t h ef l e x i b i l i t y o fr e s o u r c ep r o v i d e sag o o dm e t h o dt or e s o l v et h i sp r o b l e m s o m es c h o l a r sr e s e a r c h “塔o u 瞄f l e x i b i l i t yf l - o mw h o l ef l e x i b l er e s o u r c e st op u r t i a lf l e x i b l er e s o u r c e s ，a n d t h e nd i s c o v e rt h a tt h ep a r t i a lf l e x i b l e 脚u “翳a l s om a ya c h i e v et h ee f f e c to f w h o l e f l e x i b l er e s o u r c e st h r o u g hr e a s o n a b l ea n de f f e c t i v em a n a g e m e n t t h et h e s i se x t e n d s t h er e s o u r c e st op a r t i a l f l e x i b i l i t yr e s o u r c e st h r o u g h t h er e s e a r c ho fr 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 f i r s t l y , t h et h e s i ss u m m a r i z e dt h ep r e s e n tr e s e a r c h0 1 r 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 mb yd o m e s t i ca n df o r e i g ns c h o l a r s b a s e do nr e s e a r c hb e f o r e ，t h e c l a s s i f i c a t i o n so fr e s o u r c a - c o n s t r a l n e dp r o j e c ts c h e d u l i n gw a sd i s c u s s e d a c c o r d i n g t oa c t i v i t ym o d e s ，i tw a ss o r t e dt of i v ec a t e g o r i e s ：s i n g l em 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 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 ts c h e d u l i n g p r o b l e m ，d i s c r e t et i m e c o s tt r a d e - o f fp r o b l e m ，s i n g l em o d e r e s o u r c el e v e l i n gp r o b l e m , 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 ，a n da n a l y s i sd i f f e r e n tt y p e so fr e s o u r c e c o n s t r a i n e dp r o j c c ts c h e d u l i n g , s t u d i e dm a t h e m a t i c so fs o l v em e t h o da n da t t a i n e dt h e a d v a n t a g e sa n dd i s a d v a n t a g e so fe v e r ym e t h o d s e c o n d l y , t h et h e s i se x p a n d sr e s o u r c e st op a r t i a lf l e m b i l i t yr e s o u r c e s ，a n dp u t f o r w a r dc o n c e p t ，c l a s s i f i c a t i o no ff l e x i b i l i t yr e s o u r c e sa n di t sv a l i d i t yw a ss t u d i e d , b a s e do nm o d e lo fr e s o u r c ec o n s t r a i n e dp r o j e f ts c h e d u l i n g , t h ep a p e rb u i l tu ps i n o e m o d ep a r t i a lf l e x i b i l i t yi 。e s o u f t t , e sc o n s t r a i n e dp r o j e c ts c h e d u l i n gm o d e l t h e n , h e u r i s t i ca l g o r i t h mw a su t i l i z e dt os o l v et h ep r o j e c td i s p a t c hm o d e l ，a n d a l g o r i t h ms t e po fs o l v i n gs i n g l em o d ep a r t i a lf l e x i b i l i t yr e s o u r c e sc 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 gm o d e lw a sp u tf o r w a r d d e p e n d i n g o nt h ep r o g r a m m i n gw i t hm a t l a b ，c o n c r e t e e x a m p l ew a su s e dt od e m o n s t r a t ev a l i d i t y o ft h e a l g o r i t h m ：t h r o u g hr e a s o n a b l e m a n a g e m e n ta n du s i n gp a r t i a lf l e x i b i l i t yr e s o l l r ss t i l lc a na t t a i nt h er e s u l to fw h o l e g e n t l er e s o u i s k e y w o r d s ：r e s o u r c ef l e x i b i l i t y , r e s o u r c e - c 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 , h e u r i s t i c a l g o r i t h m 此页若属实请研究生及导师签名。并装订在学位论文的摘要前。 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 研究生( 签名) ： 牵鲤鲤日期罂1 2 ：! ! ：， 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即：学校有权保留送 交论文的复印件，允许论文被查阅和借阅；掌校可以公布论文的全部内容，可以采用影 印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 研究笋c 签孙拿翻丝导师c 签名， 绊期班 武汉理工大学硕士学位论文 1 1 研究背景与意义 第1 章引言 资源受限项目调度问题是最常见的生产调度问题，是项目管理中最典型的 问题之一，也是最复杂的、最具难度的一种调度问题。该问题属于组合优化问 题的范畴，虽然问题本身描述非常容易，但是对问题求解方法的有效改进是非 常困难的。目前对于此类问题的研究成果较少，还没有十分有效的求解策略和 方法，只有个别特殊情况下一定规模的问题找到了有效算法。因此探求理论基 础并寻求有效地求解策略，具有重大的研究价值。同时在实践上，目前的生产 调度方法研究与现实调度状况的需求还存在很大的差异，理论成果与实际问题 相对比存在着很大的局限性，因此如何缩小理论研究与解决实际问题能力的差 距，把丰富的项目调度理论成果应用于实际生产调度也是研究的实际意义所在。 自从7 0 年代以来，整个世界经济环境发生了极大变化：市场需求日趋多变， 技术进步日新月异。几乎所有产业都在不同程度上具有动态性、易变性和不确 定性等特性，体现着许多具有重大不连续性的因素。这些特性、因素不仅对管 理活动提出了一套新的要求，并进一步增大了环境的动态性、无序性和不均衡 性等特点，给管理者带来了严峻挑战。尤其是现代项目存在如下的发展趋势： 项目的规模越来越大；项目的复杂程度不断增加；业主对工期和成本的要求越 来越苛刻。而柔性就是有效的响应变化的环境的能力，于是柔性成为众多研究 学者的关注对象。因而对柔性资源受限的项目调度研究具有重要的研究意义。 1 2 国内外项目调度问题的研究现状 项目的概念虽然很早以前就己经存在，但是直到世纪4 0 、5 0 年代第二次世 界大战的爆发期间，军事上出现了众多技术复杂、参与人员数量大、时间又非 常紧迫的项目，促使项目管理技术取得突破性成就，项目管理这个词才逐步被 认识，人们开始关注如何有效地实行项目管理来实现既定的目标【“。 2 0 世纪6 0 年代出现的两个国际性项目管理组织以欧洲国家为主的“国际项 目管理协会( 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 ) ”，和美国的“项目管 理协会( p r o j e c tm a n a g e m e n ti n s t i t u t e ) ”，致力于项目管理理论与方法的研究探索 武汉理工大学硕士学位论文 和推广工作，大大地推动了项目管理的发展。 2 0 世纪7 0 年代后，制造型企业所面i i 缶的市场从相对稳定变得动态多变。随 着产品生命周期缩短，生产模式向小批量、多品种的方向发展，用户对产品的 交货期、价格以及质量提出了更高的要求。9 0 年代后，市场竞争围绕新产品的 开发而展开，现代企业要在激烈的市场竞争中占据一席之地，必须提高自身竞 争力，而企业的核心竞争力依赖于独有关键技术支撑的新产品。因此利用知识 和技术快速响应市场的新需求，以准确的时间、低廉的成本和优质的服务将顺 应市场需求的新产品投放出去，将使企业获得更大的生存发展空间、市场竞争 力以及经济效益。 伴随着社会的进步和项目的复杂化，尤其是信息时代的来临和高新技术产 业的飞速发展，资本、服务、信息、技术、劳务人才在全球范围内流动空前加 快，项目的特点发生了显著变化，项目本身和执行环境的不确定性及复杂性不 断增多和增强，各行各业开发生产力的过程对有效的项目管理的依赖也越来越 高。而有效的计划和控制活动、资源、时间三个变量是确保项目成功的关键。 目前项目管理中突出存在的问题主要表现在三个方面：项目工期的延迟； 项目成本的超支；为满足项目成本或工期的目标要求，而简略项目的部分内 容( 规模或设计内容等) 。 这说明目前的项目管理理论和方法还不能满足现代企业项目管理的实际需 要，需要进一步加强研究和深入改进，提出更为实际和有效的项目管理方法。 1 2 1 项目调度问题 项目调度问题就是针对项目过程的各项活动，研究和解决如何按时间对资 源进行安排，使预定目标最优化的问题。项目调度问题是运筹学的一个分支， 基本上属于组合优化问题类。其中的活动和资源都是抽象的概念，其具体指代 的实体对象是非常广泛的。面对复杂的实际生产调度问题，在生产计划与调度 决策过程中，必须把人工智能与管理科学、知识工程与系统工程、计算技术与 通信技术、软件工程与信息工程等多技术学科相互结合、相互渗透，才能进一 步开发有效的调度方法，并在实际研发或生产中得到广泛的应用。 项目调度问题在各个行业都普遍存在，项目中任务安排顺序的不同将直接 导致项目完成效果的不同，若按照合理的排序和调度理论及方法管理生产，可 以在最大程度上满足企业的经济要求及发展需求。随着生产规模、生产方式及 2 武汉理工大学硕士学位论文 社会需求状况的变化，传统的调度理论也不断进行改进、增补和发展，融入与 结合了大量的先进理论、思想和方法。在制造业! 计算机软硬件行业、建筑行业 等众多领域，项目调度问题具有很强的实际意义和重大应用价值。 在制造型行业中，调度是普遍使用和必需采用的控制管理方法，应用范围 非常广泛。近年来，关于调度问题的研究范围越来越大，发展日趋迅速。针对 不同的生产领域形成了各具特点的调度问题体系，且随着新思想方法及科学技 术的诞生和发展，调度问题越来越具有鲜明的时代感，其研究的现时性大大增 强。应用于制造企业的调度问题主要可分为以下五个方面： ( 1 ) 作业车间调度问题( j o b - s h o p s c h e d u l i n g p 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 ) ： ( 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 m 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 ) 以快速响应需求为目标； ( 3 ) 以遵守交货期、满足顾客需求为目标。 1 2 2 项目调度的研究现状 项目调度问题自2 0 世纪中期被提出以来，引起了研究学者的广泛关注。最 初广泛应用于项目进度计划的工具是甘特图技术。它以二维坐标的形式，用线 条在二维空间中表示出整个项目期间计划和实际的活动完成情况，直观表明项 目中所含各项活动的执行顺序，及每项活动的开始结束时间和持续时间。甘特 图作为一种计划、控制管理工具，形象地描绘了各项活动的进度并有效的监督 项目了进程，适用于周期性和重复性项目的进度，可以帮助管理者发现实际进 度偏离计划的情况。 2 0 世纪5 0 年代中期发展起来的网络计划技术作为一种科学的计划管理技 术，迅速渗透到项目调度领域，具有代表性的是关键路径法( c r i t i c a lp a t hm e t h o d ) 与计划评审技术( 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 ) 。它以网络图的形式来 表示项目进度计划。网络图是由箭线和节点组成，加注工作时间参数，用来表 3 武汉理工大学硕士学位论文 示工作流程的有向、有序的网状图形。它能够明确的反映各活动间的先后顺序 和相互制约的逻辑关系，通过计算时间参数，可找出计划中的关键活动及关键 线路，反映出各活动的时差。其主要思想是通过压缩关键工作线路的持续时间， 从而使工程的工期、费用实现优化。管理者可以此为根据抓住主要矛盾，更好 的调配和使用人力、物科和设备资源，对计划进行有效的控制与监督，使其缩 短工期，降低成本，加强项目的管理工作。因此网络计划在控制进度节约资源 等方面发挥着重要作用。 随着经济全球化导致市场竞争的日趋激烈，现代项目日趋复杂，要求周期 更短、准时完工率更高、成本更低。传统的项目进度计划方法虽然在解决工程 单目标优化如工期优化、费用优化或资源均衡优化方面，给项目管理者带来了 极大方便，但是现代项目不但要考虑工期、费用和资源均衡目标的优化，还要 综合考虑工程质量、风险、安全等诸多因素，有时甚至要考虑在资源均衡、安 全、风险约束下的项目质量、费用、工期等多目标优化，使项目调度计划具有 更高的稳定性、适应性和准确性。因此必须对传统的项目进度计划与方法进行 改进或提出新的项目调度技术与方法，以满足现代项目管理的需求。 随着最优化技术的不断发展，国内外科学家陆续提出了一系列性能优良的 优化算法，并将这些算法应用于解决项目调度问题，常用的优化方法主要有分 枝定界法、基于规则的启发式算法、进化算法、局部搜索算法等。 在项目调度问题的发展过程中，除了对现有算法的改进和创新，项目调度 问题的模型也在不断改革。目前现有的研究模型主要是：在假设项目信息完全 己知的确定性环境下设计调度方法，以求得在某一目标下最优的项目调度计划。 研究的主要问题主要集中在项目周期最短、资源消耗水平最低、时间成本权衡 以及以最大净现值为目标的单目标优化问题上。新的优化技术在解决这些复杂 优化问题中表现出了巨大的潜力和作用。近年来，非确定性环境下的项目与优 化调度方法引起了广大学者的关注和研究，研究方法主要有模糊项目调度和基 于关键链的项目优化调度方法。 国内外也有一些学者对柔性资源受限的系统进行了研究，国外学者对柔性 资源的研究大部分是从柔性制造开始的，对于柔性资源受限的项目调度相对而 言就寥寥无几了。d a n i e l s r l ，m a z z o l a j 、d a n i e l s r l ，h o o p c s b i ，m a z z o l a j 3 1 、s i g u r d u ro ，s h il a 1 4 j ，z a v a l a v ，m c c l a i na n dt h o m a s l 5 】研究了完全柔性资 源( 资源可以被运用到生产的任何环节) 对调度的影响，他们通过使用完全柔 4 武汉理工大学硕士学位论文 性资源能有效地提高生产效率。d a n i e l srl a n ds h id 嘲，d a a i e l sr l ，m a z z o l a ja n ds h id 7 1 将研究领域从完全柔性资源拓展到部分柔性资源，并且发现通过合 理地管理和利用部分柔性资源，可以获得完全柔性资源的效果。j o r d a na n d g r a v e s 嗍( 1 9 9 5 ) 则提出了关于在生产设施中的部分柔性资源的绩效和在这些 设施中产品分配的一些原则。t a l b o t l 9 ( 1 9 9 2 ) 、l a w r e n c ea n dm o r t o n 1 0 】( 1 9 9 3 ) 、 o z d a m a ta n du l u s o y ( 1 i j ( 1 9 9 5 ) 对关于项目调度的柔性资源调度进行了研究。而 在国内，陈荣秋教授【l2 】等研究了组织管理系统、技术系统柔性以及企业整体柔 性等；李必强教授等【1 3 】研究了企业生产组织的均衡性与弹性；邓明然教授等【4 】 研究了企业理财系统的柔性，罗荣桂教授等1 1 5 16 】对具有柔性资源约束的调度问题 进行了研究，提出柔性资源的最优分配和使用的智能算法，具有重要的理论意义 和实用价值 1 2 3 资源受限项目调度问题 在现代化制造业及生产中都离不开项目的实施，而任何项目的策划和执行 都包含大量不同的活动及各种人力、物力资源。在项目活动的组织安排中，有 些活动是可以同时进行的，而有些活动则必须在其他若干项活动完成之后才能 进行，活动之间的这种限制关系就是通常所说的时序关系。同时，每项活动本 身还需要一定的持续时间，且使用不同种类、不同数量的资源如机器设备、物资 材料、劳动力等。资源是项目执行过程中不可缺少的重要组成部分，而这些资 源的有效可用量往往具有局限性。如何以最佳方式安排执行项目中的各个活动， 以使其顺利完成，就构成了资源受限项目调度问题的基本概念。资源受限项目 调度问题是项目管理领域中的重要研究方向之一。 资源受限项目调度理论从资源受限出发研究项目调度问题，从其被提出至 今，一直受到全世界众多研究学者关注。典型r c p s p 问题可简单描述为在满足 项目紧前关系约束与资源约束的前提下，对项目所有活动的开始时间和结束时 间合理安排，以便最小化项目总工期。 早期对求解这一问题的研究工作主要集中在两个方面： ( 1 ) 利用数学规划方法解决这类优化调度问题，求得最优解； ( 2 ) 利用启发式方法来得到满足条件的最优解。 人们曾经采用整数规划的手段来求解这类优化调度问题的精确解，后来人 们发展了各种枚举性方法，如分枝定界法，来获得这一问题的最优解。随着现 武汉理工大学硕士学位论文 代项目管理理论及技术的不断发展和逐渐完善，r c p s p 问题的模型和算法研究 也日趋深入，并渐成体系。人们熟知的s i n g l em a c h i n e ，j o b - s h o p ，f l o ws h o p 等优化调度问题模型都是问题的特殊情况。而随着科学技术研究的不断发展， r c p s p 问题的求解方法也日益多样化。 1 3 本文的研究方法及章节安排 1 3 1 本文的研究方法 本文在分析了资源受限的项目调度问题研究及相关求解方法的基础上，将 资源扩展为柔性资源，并建立柔性资源受限的项目调度研究，采用启发式算法 进行求解，并用m a tl a b 语言进行编程，以实现柔性资源受限项目调度的优化目 标。 1 3 2 本文的章节安排 本文的章节安排如下： 第一章全面分析了项目的定义、特性，项目调度等等，资源受限项目调度 的分类，单模式资源受限项目调度和多模式资源受限项目调度模型及常用的模 型求解方法如甘特图、关键路径法、计划评审技术分析、图标评审技术分析等 等，还分析了相关算法实现的求解方法，如分支定界法、整数规划法、启发式 算法等等。 第二章对资源、柔性、柔性资源的定义、分类等进行了分析，提出了资源 技能矩阵概念，并对其度量方式进行了分析，并在第一章的基础上建立了o - l 整 数规划的柔性资源受限的项目调度的模型。 第三章重点分析了启发式算法的相关内容，并在前面两章的基础上分析了 柔性资源受限项目调度模型，结合启发式算法，提出求解步骤，并采用一个具 体的实例进行了实证分析验证。 第四章总结了本文研究的内容，并对关于柔性资源受限项目调度研究的以 后研究方向提出展望。 6 武汉理工大学硕士学位论文 第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 ) 要求在满足项目时序约束和资源约束的条件下，安排所有任务的开工期 和完工期，使项目总工期最短。r c p s p 广泛存在于建筑工程、软件开发、飞机 和轮船制造等单件或小批量生产方式的企业中。理论上该问题属于n p h a r d 问 题，模型丰富，许多组合优化问题是r c p s p 的特殊情形。因此研究r c p s p 具 有重要的理论和现实意义。 2 1 项目调度 2 1 1 项目的定义和特征 ( 1 ) 项目的定义u i 项目的定义有很多，人们从不同的角度给出了许多不同的定义。质量管理 专家朱兰( j m j u r a n ) 提出，一个项目就是一个计划要解决的问题。美国项 目管理协会( p r o j e c tm a n a g e m e n ti n s t i t u t e ，p m ) 给项目下的定义是：项目是为 完成某一独特的产品、服务或任务所做的一次性的努力。而国际标准化组织 ( 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 ) 项目的特征 项目的定义虽多，但是使用比较多的定义还是国际标准化组织提出的定义。 项目的特征可以归结为以下几条： 目的性项目的目的性就是任何一个项目都要有一个比较明确的目标， 比如，使项目的工期最小、费用最省、资源使用量最少等等。保持项目目标明 确的最好办法是使其可以验证或可以衡量，通常的做法是将项目的目标依照项 目范围、进度计划和质量、成本等来定义，使之明确或量化，例如，在多长的 时间内化肥多少完成什么任务或工作。 相关性项目的相关性是指项目的完成要通过执行一系列相互关联的活 动。项目是由一系列不重复的活动构成，这些活动由于其关联性，必须按照一 定的顺序执行( 即活动的优先关系) 。例如，有些活动在其前项活动完成之前不 能启动，而另外一些活动则可以同时开工，从这个意义上看，项目可以当成一 个系统来看，并且有内在的相关性。 制约性项目的制约性是指每个项目在一定的程度上都受到客观条件和 资源的约束。项目需要运用各种资源来完成活动，如人、资金、技术、时间、 7 武汉理工大学硕士学位论文 技术、信息，这些限制条件和项目所处的环境带来的客观环境等构成了项目的 制约性。如果项日的制约性比较小的话，则项目的成功机率很大；反之大大降 低。 不确定性项目在执行的过程中包含着一些不确定性。一个项目在开始 之前，一般都在一定的假定和预算上准备一份计划，而这种假定和预算往往与 项目的真实情况难免会有偏差从而给项目带来一定程度上的不确定性。 周期性项目的周期性是指项目有具体的时间计划或有限的寿命。项目 是在有限的期限内完成的，有明确的开始时间和结束时间。 其他特性项目还有不可逆性、动态性和开放性等等。 2 1 2 项目调度 项目调度即在一个项目确定后根据项目的活动前后顺序( 即活动的优先顺 序) 、资源获得量、总工期、资金和所处的环境等约束条件，来合理的安排一个 工序。尤其是要解决好瓶颈区的资源冲突问题，使项目的工期最短、费用最省、 资源使用量最少，达到业主的质量要求等等。而这仅仅是项目的一个初步的实 施计划。项目的不确定性和动态性等特征表明项目在执行的过程中难免会出现 这样那样的问题，这就需要项目调度人员去根据实际情况去解决项目活动在执 行过程中出现的问题。 2 2 资源受限的项目调度的类型 r c p s p 问题是研究具有优先关系约束活动的项目在资源受限的条件下使某 些管理目标最优的调度问题，它是项目活动排序方法与活动时间调度方案的统 一。因此将从以下几个方面对资源受限项目调度问题分类，以便于对其进行较 为全面的分析和研究。 2 2 1 按项目调度目标分类 资源受限项目调度问题的目标随着实际需求的不同而发生变化。当目的是 节约能源、充分利用有限资源时以最小化资源消耗( 均衡使用资源) 为调度 指标当目的是提高经济效益时，则以最大化网络收益为调度指标等诸多优化指 标。因此，在本文中，资源受限项目调度问题以调度指标不同分成以下三类最 小化工期问题、资源均衡问题和现金流优化问题。 ( 1 ) 项目工期最小化问题 项目工期最小化问题是资源受限项目调度问题中的基本问题，也是最普遍 武汉理工大学硕士学位论文 采用的项目管理目标，该类问题是以加快项目执行过程，缩短完工时间为目标。 资源受限项目调度问题中的最小化工期问鹿是在时序约束和资源约束条件 下的组合优化问题，即如何在满足这两个约束的条件下，确定出所有活动的开 工时间，并使项目工期达到最小。一般资源受限项目调度的最小化工期问题的 求解可分为二个阶段，第一步是对该问题的进行描述并构建其数学模型；第二 步是运用各种算法来获得最优解或近似最优解。该类问题的研究不仅具有一定 的理论意义，而且具有很高的实用价值。 ( 2 ) 资源均衡问题( l e v e l i n gr e s o u l v 七u s a g e ) 资源均衡问题是资源受限项目调度问题中的重要研究目标之一。项目执行 必然受到资源限制的影响，一个满足项目工期的调度计划，如果工作进度安排 不能使资源均衡使用，就会在项目执行的某时段对某些资源有较高需求量，而 在另一些时段对这些资源的需求量较少。这种剧烈波动现象的存在容易造成资 源供、需量冲突或形成资源积压，因此合理地安排项目中的各个活动进度，解 决资源供需矛盾是急需解决的问题。 在资源均衡问题的研究中，由于资源限制因素较多，因此该问题的分类方 式也较多。如按优化资源目标的方式，可将资源均衡问题分为规定工期的资源 均衡问题和有限资源的合理分配问题；按所需资源类型的方式又可将该问题分 为可更新资源类、不可更新资源类与双重约束资源类 ( 3 ) 最大净现值问题 资源受限项目调度问题中的优化目标一般采用最小化工期或资源的均衡使 用。但是，随着制造业的发展及市场竞争的日趋激烈，项目效益不仅成为生产 与研发的主要衡量指标，而且也是一个企业团队生命力和竞争力的体现，因此 资源受限项目调度中的现金流优化问题逐渐成为该领域的研究热点。 此类问题的研究是在资源受限项目调度问题一般性假设的基础上，以项目 的最大净现值作为优化指标，建立带有贴现率的最大化网络净现值 ( m a x i m i z a t i o n o f t h e n e t p r e s e n t v a l u e ) 的数学模型，进而实施优化策略及优化 求解。 2 2 2 按资源类型分类 在资源受限项目调度问题的研究中，资源约束是主要的约束条件之一。在 实际工程项目的开发过程中，资源经常出现如下约束形式： 9 武汉理工大学硕士学位论文 ( 1 ) 某一种资源存在于整个项目的每一个时间段内，且其在任一时间段内 的使用量受限： ( 2 ) 某一种资源在整个项目的工期内总使用量受限； ( 3 ) 某一种资源的使用量不仅在整个工期中受限而且在工期内的每一个时 间段内也受限。 我们可将资源受限项目中的调度问题分为可更新资源问题、不可更新资源 问题以及双重约束资源问题。 2 2 3 按模型的不同分类 r c p s p 问题在半个多世纪的发展过程中，针对不同的特定问题构建出各异 的模型，且随着问题研究的深入，这些模型渐成独立的体系，到目前为止常见 r c p s p 问题大致可分为以下几种i l7 】： ( 1 ) 单模式资源受限项目调度问题( s i n g l em o d er e s o u l v 七c 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 ) ，是早期研究项目调度的主要问题模型，它 假设项目中每个活动都只有一种执行模式且不考虑不可更新资源，一般是在满 足活动间紧前关系约束和可更新资源约束的情况下，求达到项目工期最短这一 优化目标的调度方案。 ( 2 ) 多模式资源受限项目调度问题( m u l t i m o d er e s o m - c 跫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 的扩展，自1 9 9 7 年首次提出后，受 到研究学者的广泛关注。该问题在的基础上增加了不可更新资源约束，并且允 许活动有多种执行模式。但是一旦活动的执行模式确定下来，则m r c p s p 退化 为s r c p s p 。 ( 3 ) 离散时间成本权衡项目调度问题( d i s c r e t et u n e c o s tt r a d e - o f f p r o b l e m , d 1 r c l l 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 ) ， 与s r c p s p 的假设条件相同，即假设项目中每个活动都只有一种执行模式且不 1 0 武汉理工大学硕士学位论文 考虑不可更新资源，但其求解目标是在满足项目工期约束条件下，使项目工期 各阶段内各种可更新资源的最大消耗成本最低。 ( 5 ) 多模式资源水平问题( m u l t i m o d e r 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 ) 与m r c p s p 的模型类似，区别在于m r l p 的求解目标是在满足项目工期约束条 件下，使项目消耗的资源总成本最低。 ( 6 ) 带最小最大时间滞后的资源受限项目调度问题( r c p s p m a x ) 即带时 间窗约束的r c p s p 。在实际应用中，由于受到场地、贵重设备使用时间、气候 或重要人力资源等因素的影响，必须预先确定某些活动具备执行条件的可行时 间范围，以保证重要稀缺资源在不同活动中的合理分配和项目的正常进行， r c p s p m a x 中的时间窗口是活动之间的相对时间约束。优化目标是当并行活动 发生资源冲突时，如何选择优先执行的活动和被推迟执行的活动，使项目工期 最短或如何保证受预约时问窗口约束的活动的可行性，即在确保此特殊活动在 满足时序、资源约束的前提下，活动开始时间和完成时间在预约时间窗口内。 ( 7 ) 以最大净现值为目标的资源受限项目调度问题( r 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 mw i t hc a s hf l o w , r c p s p c f ) 假定活动持续时间与费用 是有一定的函数关系，而且活动的持续时间与资源需求无关