（管理科学与工程专业论文）资源受限项目组合选择及调度优化研究.pdf

浙江大学硕士学位论文摘要 摘要 随着经济全球化和市场竞争的日益激烈，项目组合选择与项目调度愈来愈成 为理论与实践关注的热点问题。在实务中，许多组织希望在有限时间内，并行开 展多个项目；由于资源受限，它们迫切需要寻找有效的方法，从众多备选项目中， 确定一个最佳的项目组合方案；并事先对这些项目进行合理的调度与资源分配， 以实现收益的最大化。在理论研究方面，越来越多的学者投身于项目组合选择与 项目调度领域；但现有大多数研究只单独涉及项目选择问题或者项目调度问题， 很少出现结合考虑项目组合与项目调度的文献。然而，项目组合选择与调度并不 是项目管理中完全独立的两个决策阶段；在资源约束情况下，项目调度计划往往 影响着项目的选择。 本研究尝试整合项目组合选择与项目调度，在项目选择过程中引入项目调度 问题，以最大化项目组合收益为目标函数，建立一般化的资源受限项目组合选择 及调度问题模型。进一步，基于蚁群优化算法和多智能体进化算法，本研究提出 了两种求解资源受限项目组合选择及调度问题的优化求解方法。两种方法均包含 项目组合选择主程序与项目调度子程序两个部分：( 1 ) 主程序部分分别采用改进 的蚁群算法与多智能体进化算法；( 2 ) 子程序部分则采用基于规则的并行项目调 度启发式算法。最后，通过多个算例的求解，本研究对两类方法的参数进行了深 入探讨，并验证了其求解资源受限项目组合选择及调度问题的有效性。此外，由 于不存在广泛适用的项目组合选择及调度问题库，本研究算例均基于 p a t t e r s o n l l 0 个问题和p s p l i b 标准问题库随机生成。 关键词：资源受限，项目组合选择及调度，蚁群优化算法，多智能体进化算法 i i i 浙江大学硕士学位论文 a b s t r a c t a b s t r a c t w i t ht h ee c o m o m i cg l o b a l i z a t i o na n dt h e i n c r e a s i n gf i e r c e n e s s o ft h em a r k e t c o m p e t a t i o n ，p r o j e c tp o r t f o l i os e l e c t i o na n dp r o j e c ts c h e d u l i n gh a v eg r a d u a l l yb e c o m e p o p u l a rt o p i c sb o t hp r a c t i c a l l ya n dt h e o r e t i c a l l y i np r a c t i c e ，m o s to r g a n i z a t i o n sh o p e t od e v e l o pv a r i o u sp r o je c t ss i m u l t a n e i t y f a c i n gl i m i t e dr e s o u r c e sa n dn u m e r o u s p r o j e c tc a n d i d a t e s ，e s p e c i a l l yt h er & dp r o j e c t sw i t hh i g hi n v e s t m e n ta n dh i 曲r i s k ， t h em a n a g e r su r g e n t l yn e e da ne f f e c t i v em e t h o dt of i n dt h eo p t i m a lp r o j e c t p o r t f o l i o ， a n dm a k eas u i t a b l ep l a nf o rp r o j e c ts c h e d u l i n ga n dr e s o u r c ea l l o c a t i o n i ns t u d y , m o r ea n dm o r es c h o l a r sh a v ed o n a t e dt h e m s e l v e si nt h ef i e l do fp r o j e c ts e l e c t i o na n d p r o j e c ts c h e d u l i n g m o s to ft h e m ，h o w e v e lf o c u s e de i t h e ro np r o j e c ts e l e c t i o no ro n p r o j e c ts c h e d u l i n g ，s e p a r a t e l y , i g n o r i n gt h ei n t e r a c t i o nb e t w e e nt h e s et w op r o j e c t m a n a g e m e n tp r o b l e m s i nt h i sr e s e a r c h ，a ni n t e g r a lm o d e lf o rr e s o u r c ec o n s t r a i n e dp r o je c tp o r t f o l i os e l e c t i o n a n ds c h e d u l i n gi sd e v e l o p e d ，w h i c ht r e a t sm u l t i p r o j e c t ss c h e d u l i n ga sa s u b - p r o b l e m o fp r o j e c ts e l e c t i o na n ds e e k st om a x i m i z et h ep r o f i to fp r o j e c tp o r t f o l i o t os o l u t i n g t h i sn p - h a r dp r o b l e m ，t w o ( a l t e r n a t i v e ) o p t i m i z a t i o n a la l g o r i t h m sa r ed e s i g n e d ，w h i c h a r eb a s e do nt h ea n tc o l o n yo p t i m i z a t i o na n d m u l t i - a g e n ts y s t e mr e s p e c t i v e l y b o t ho f t h e ma r ec o m p o s e do f ( 1 ) ah e u r i s t i cf o r t h ep r o j e c ts c h e d u l i n g ；( 2 ) am e t a h e u r i s t i cf o r t h ep r o j e c ts e l e c t i o n s o l v i n gas e r i e so fi n s t a n c e s ，w h i c ha r eg e n e r a t e df r o mp a t t e r s o n 110p r o b l e m sa n dp s p l i b ，t h et w oa l g o r i t h m s p a r a m e t e r sa l ea n a l y z e da n dt h e i r e f f e c t i v e n e s sa n de f f i c i e n c ya r et e s t e d k e yw o r d s ：r e s o u r c ec o n s t a i n e d ，p r o j e c tp o r t f o l i os e l e c t i o na n ds c h e d u l i n g ，a n t c o l o n yo p t i m i z a t i o n ，m u l i t - a g e n te v o l u t i o n a r ya l g o r i t h m v 浙江大学硕士学位论文 图目录 图目录 图1 1p a t t e r s o n1 1 0 问题库一实例p a t 8 。6 图1 2 关键路径法求解结果( p a t 8 ) 7 图1 3 项目调度资源负荷示意图8 图2 1 启发式算法求解项目调度问题( p a t t e r s o n1 1 0 一p a t 8 ) 2 9 图2 2r c p s pc h e n 问题a o n 结构图和c p m 调度3 4 图2 3 基于优先规则的项目顺序调度一3 5 图2 4 项目并行调度3 5 图3 1t s p 拓扑结构4 2 图3 2 多智能体网格5 2 图3 3 多智能体进化算法流程5 6 图4 1 时间符号( “时刻”与“阶段”) 说明5 8 图5 1 项目组合选择蚁群优化算法结构( n = 8 ) 7 0 图5 2r c p p s s 蚁群优化算法流程7 4 图5 3 智能体自学习过程7 7 图5 4 染色体非可行修复机制8 0 图5 5 资源受限项目组合选择及调度多智能体进化算法8 l 图6 1 蚂蚁数量对算法求解结果的影响9 0 图6 2 蚂蚁数量对算法运算时间的影响9 1 图6 3r c p p s s m a 算法收敛性( m = n ) 9 l 图6 4o 【与d 对r c p p s s a c o 算法性能的影响9 2 图6 5 信息素挥发系数p 对r c p p s s a c o 算法性能的影响。9 3 图6 6 信息素更新常量q 对r c p p s s a c o 算法性能的影响9 3 图6 7 智能体网格大小对r c p p s s m a 算法结果的影响。9 5 图6 8 智能体网格大小对r c p p s s m a 算法运算时间的影响。9 5 图6 9 参数d 6 对r c p p s s m a 算法性能的影响9 8 图6 1 0 不同规则下r a n k i n g 与m k p + r a n k i n g 方法性能比较1 0 0 图6 1 1r c p p s s a c o 算法和r c p p s s m a 算法收敛状况1 0 4 浙江大学硕士学位论文表目录 表目录 表2 1 项目组合选择问题的约束类型。1 5 表2 2 常用项目( 组合) 选择方法性能比较2 3 表2 3r c p s p 数学模型符号说明2 4 表2 4 启发式优先规则。2 8 表2 5 项目选择与调度研究现状。3 6 表3 1 蚁群优化算法相关文献4 4 表3 2t s p 蚁群算法符号说明4 5 表3 3 蚁群算法参数。5 0 表3 4 部分蚁群算法最优参数表。5 0 表4 1r c p p s s 模型符号说明5 9 表4 2r c p p s s 约束条件归类6 2 表5 1r c p p s s a c o 算法符号说明6 8 表6 1p a t t e r s o n l1 0 问题库的7 2 个p a t 实例8 4 表6 2 实验情境8 8 表6 3 全因子实验设计8 9 表6 4 网格大小厶切与迭代次数n c m a x 对算法性能的影响9 4 表6 5 竞争感知范围对r c p p s s m a 算法性能的影响9 6 表6 6 自学习感知范围对r c p p s s m a 算法性能的影响9 7 表6 7 项目排序优先规则1 0 0 表6 82 4 个实例运算结果1 0 2 表6 9 含交互项的项目组合收益多因素方差分析1 0 3 表6 1 0 不同算法对项目组合收益影响均值的两两比较结果1 0 3 表6 1 1r c p p s s 优化算法运算时间1 0 5 x i i i 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝婆盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名：签字日期： 少p 年月彭日 学位论文版权使用授权书 本学位论文作者完全了解逝姿态堂有权保留并向国家有关部门或机 构送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝江盘堂 可以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：撇 签字日期：d 刀夕年月椭 导师签名： l 泸圹 签字日期：，d 年月硝日 浙江大学硕士学位论文 致谢 致谢 时光飞逝，我的研究生生涯即将画上完满的句号。回首将将过去的点点滴滴， 有欢笑，亦有辛酸。如今心中，即怀着对未来的美好憧憬，更有对往昔的不舍。 通过在浙江大学管理学院两年半的学 - - j 与生活，自己着实成长了不少。在这里， 我学到了扎实的专业知识和系统的研究方法。在这里，我有幸结识了众多良师益 友，他们的关怀和鼓励一直是我前进的动力。这一切都是我无比珍贵的人生财富， 在此，我感谢你们! 我要感谢我的导师一一寿涌毅副教授。学位论文从最初的选题、算法设计到 后期的程序编写和行文结构都是在老师的悉心指导下完成的。可以说，论文的顺 利完成倾注了老师大量的心血。寿老师严谨的治学态度、深厚的理论功底、敏捷 的思路以及踏实的科研和工作作风都给我留下了深刻的印象，也为我树立了终身 学 - - j 的榜样。在生活上，寿老师如同一位兄长，传授我人生的阅历，为我指明前 行的方向，并总是宽容我所犯的错误，帮助我改进有幸成为寿老师的弟子，我 感到万分的自豪! 我要感谢我的师兄傅奥、师姐李敏以及同门王伟，在相近的研究领域，与他 们的讨论帮助我解决了研究过程中的各种问题，受益颇多。 我要感谢同门夏雪娇、汪洁、宋纯江、孙宇、吴璐缤以及赖昌涛，每次例会 精彩的学术报告和激烈探讨都让我获得学术上的进步，而每次的聚会更是让我的 生活变得多姿多彩。 最后，我要感谢身边的每一位亲人和朋友，感谢你们对我一如既往的关心和 支持! 姚伟建 二零一零年一月 于浙江大学管理学院 浙江大学硕士学位论文引言 1 引言 随着人类社会的不断发展，项目管理在企业、政府开展的经济、社会业务中 扮演着越来越重要的角色。项目管理以顾客为导向，以高效完成既定任务为目标， 能够帮助企业或政府充分利用现有资源，有效规划任务实施进度，合理控制成本 与风险，因而受到社会各界的广泛青睐。项目选择与项目调度作为项目管理领域 内两个重要的问题，无论在理论研究还是管理实务中都已成为学者与管理人员关 注的焦点。本章首先将对项目、项目管理、项目选择以及项目调度的相关内容进 行简要介绍，进而阐述本文选题意义及相关研究的主要内容。 1 1 项目及项目管理 项目管理( p r o j e c tm a n a g e m e n t ，p m ) 是管理科学与工程学科的一个重要分支， 是一种综合性管理方法体系，最早产生于二战之后的美国曼哈顿计划。并于上世 纪5 0 年代，由我国著名学者华罗庚教授引入中国( 当时习惯称之为统筹法或者 优选法) ，在台湾省惯称专案管理。 上世纪5 0 年代7 0 年代，是项目管理传播和现代化的重要阶段，其重点在于 网络评审技术的开发、推广与应用。网络评审技术主要包括关键路径法( c p m ) 和计划评审技术( p e r t ) 。2 0 世纪五六十年代的项目管理主要应用于国防和军 工项目，最成功的案例是美国的“阿波罗登月”；随后逐渐扩展到建筑、制造生 产、电子通讯、金融保险等领域。7 0 年代，两大国际性项目管理协会，即国际 项目管理组织( i n t e r n a t i o n a lp r o j e c tm a n a g e m e n ta s s o c i a t i o n ，i p m a ) 和美国项目 管理协会( 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 ) 的建立为项目管理的发展做出了积 极的贡献。9 0 年代之后，随着信息技术和高科技产业的飞速发展，传统制造业 经济环境中强调的标准化、重复性活动被信息经济环境中对事物独特性和动态变 化所取代，项目管理从而成为了个人、企业乃至政府部门灵活管理的关键手段。 “项目”一词出现在汉语中是在2 0 世纪5 0 年代“项目管理”传入中国后不 久。从上世纪6 0 年代初，老一辈科学家华罗庚推广“统筹法”、钱学森推广系统 工程理论和方法开始，我国在项目管理领域引进国外的先进技术、方法，并不断 在应用实践方面取得丰富成果。 浙江大学硕士学位论文引言 经过数十年的发展，“项目”一词已深入社会各个领域，学术界对“项目” 的理解和定义也不尽相同，其中具有代表性的描述包括： 美国项目管理协会( 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 ) 认为，项目是为了创 造特定( u n i q u e ) 产品或服务的一项有时限的一次性( t e m p o r a r y ) 努力。 现代项目管理( 白思俊，2 0 0 3 ) 将项目定义为：一个特殊的将被完成的 有限任务，是在一定时间内，满足一系列特定目标的多项相关工作的总称。 r j 格雷厄姆认为，项目是为了达到特定目标而调集到一起的资源组合； 它与常规任务之间的区别关键在于，项目通常只做一次，是一项独特的工作努力， 而且这种工作努力应当在限定的时间、成本费用、人力资源以及资财等项目参数 内完成。 因此，总结起来，项目侧重于过程，是一个动态的概念，就是在一定的时间、 资源等约束条件下，为了达到某一( 或某些) 特定目标所做的一次性任务或努力， 其具有以下被学术界公认的几个典型特征( 骆殉等，2 0 0 3 ) ： 1 ) 一次性。这是项目与日常运营的最大、最本质区别。项目具有明确的开 始和结束时间，并且在此之前没有发生过，而且将来也不会在相同的情境下再次 发生。 2 ) 独特性。项目所产生的产品、服务或者完成的工作、任务同已有的相似 产品、服务或任务有着明显的差别。每一项目都有自身特定的目标、具体的时间 期限、相关资源的约束，因此，项目过程具有独特性。 3 ) 目标的明确性。任何项目都有自身明确的目标，为了在满足各类约束条 件的情况下达成既定目标，项目实施人在项目实施前必须进行周密的计划( 包括 项目调度) 。 4 ) 组织的临时性与开放性。由于项目的一次性特点，项目伊始，需要建立 项目组织，项目结束时该组织将会解散；并且，项目组织中的成员及其职能在项 目的执行过程中将不断变化，以应对不同阶段的项目需求。 5 ) 后果的不可挽回性。项目是一个“努力”过程，而且没有完全相同的案 例可以遵循，因此具有一定的不确定性，潜伏着各类风险。它在一定条件下启动， 一旦失败就永远失去了重新进行相同项目的机会。 项目管理活动贯穿于项目的整个生命期。对于项目管理，许多学者都做过精 浙江大学硕士学位论文引言 辟的定义，如现代项目管理( 白恩俊，2 0 0 2 ) ，项目管理教程( 骆殉等，2 0 0 3 ) 以及项目价值管理理论与实务( 邱菀华等，2 0 0 7 ) 。总结概括后，本文认为项 目管理是以项目及其资源为对象，通过项目经理和项目组织的努力，运用系统地 项目管理理论与方法，在时间、资源等约束条件下，对项目进行有效地计划、组 织、实施与控制，以实现项目目标的管理方法体系。 项目的实现过程都是一系列项目阶段或项目工作的有机构成。一般认为，项 目管理的过程可以划分成如下5 个阶段：启动过程( i n i t i a t i n gp r o c e s s e s ) 、计划 过程( p l a n n i n gp r o c e s s e s ) 、执行过程( c o n t r o l l i n gp r o c e s s e s ) 以及收尾过程( c l o s i n g p r o c e s s e s ) 。根据美国项目管理学会制定的p m b o k ，项目管理的基本职能可以 概括为如下9 大知识领域：范围管理( s c o p em a n a g e m e n t ) 、时间管理( t i m e m a n a g e m e n t ) 、成本管理( c o s tm a n a g e m e n t ) 、质量管理( q u a l i t ym a n a g e m e n t ) 、 采购管理( p r o c u r e m e n tm a n a g e m e n t ) 、风险管理( r i s km a n a g e m e n t ) 、人力资源 管理( h u m a nr e s o u r c em a n a g e m e n t ) 、沟通管理( c o m m u n i c a t i o nm a n a g e m e n t ) 以 及项目整体管理( i n t e g r a t i o nm a n a g e m e n t ) 。 1 2 项目组合选择 随着经济全球化和市场竞争的日益激烈，许多组织都希望在有限的时间内， 并行开展多个项目。但是，如果项目组合选择不恰当，项目组合结构搭配不合理， 那么组织的发展将会受到很大影响，甚至有可能面临灾难性风险。正确的项目选 择在企业未来的成功中扮演着非常重要的角色。资源有限情况下，面临成百上千 的备选项目，尤其是高投入、高风险的r & d 项目，企业迫切需要寻找有效的方 法来确定一个“最佳”的组合方案；并事先对这些项目进行合理的调度与资源分 配。 项目组合选择问题是一类经典的组合优化( c o m b i n a t i o n a lo p t i m i z a t i o n ，c o ) 问题。组合的概念最早起源于金融领域的投资组合研究。m a r k o w i t z ( 1 9 5 2 ) 使 用“均值一方差”( m e a n v a r i a n c e ，m v ) 构建金融投资组合模型，以获得同等风 险水平下收益最大或同等收益水平下风险最低的投资组合；m o t t l e y ( 1 9 5 9 年) 发表关于项目选择的文献至今，关于项目选择的模型及相关求解方法已经获得的 巨大的发展。 浙江大学硕士学位论文引言 按照决策的形式不同，项目组合选择问题可以分成两种类型：动态项目选择 问题和静态项目选择问题( e i l a t 等，2 0 0 6 ) 。动态项目组合选择问题有时问维度， 在时间维度上存在多个决策点，每个决策点上有若干个已经开始的项目，即现行 项目；并且，每个决策点上还拥有若干个备选项目或候选项目；决策空间包含所 有两类项目集合。静态项目组合选择问题，在一个决策点考虑所有的备选项目。 本文主要讨论静态项目选择问题。 另一方面，根据规划周期( p l a n n i n gh o r i z o n ) 的不同，有的学者将项目组合 的执行过程抽象成单阶段的问题( h a l l ，1 9 9 2 ；p e e r e n b o o m & b u e h r i n g ，1 9 8 9 ) ，而 有的学者将项目组合决策问题视为是多阶段的( g h a s e m z s d e h & a r c h e r ，2 0 0 0 ； g u t j a h r 等，2 0 0 8 ) 。单阶段项目组合选择较为简单，它往往认为各个项目是不可 分割的，它只需要对备选项目做出取舍。多阶段问题则复杂的多：一方面，它需 要考虑项目组合的时间效应( k y p a r i s i s 等，1 9 9 6 ) ；另一方面，可能具有更庞杂的 目标函数群( s t u m m e r & h e i g e n b e r g e r , 2 0 0 3 ；g u t i a h r 等，2 0 0 8 ) ；再者，由于规 划周期的多阶段性，在项目选择的时候往往需要确定被选项目何时实施或者投资 ( k y p a r i s i s 等，1 9 9 6 ；g h a s e m z s d e h ，1 9 9 9 ) ，进而需要考虑更多的约束条件，如项目 间的紧前约束( m e d a g l i a , 2 0 0 8 ) 、时间约束、可更新资源约束( g h a s e m z s d e h 等， 2 0 0 0 ) 。 在过去的数十年里，项目组合选择方法和技术得到了广泛的研究，也有不少 学者对不同的项目评价与选择方法进行了归纳与总结。项目( 组合) 选择方法划 分为如下6 类：基于项目评价的方法、传统经济方法、数学规划、决策分析方法、 仿真、( 元) 启发式方法。 1 3 项目调度 项目调度是项目计划制定的关键环节。从理论上讲，项目调度就是为项目制 定一个进度计划安排，该进度表明确了各任务资源分配情况及具体的任务开始时 间。项目调度在项目管理中的重要性不言而喻，它关注项目进度的计划与安排， 直接决定了项目目标能否及时有效达成。 简单的项目调度问题由一系列有待实施的任务( t a s k s ，或称活动) 组成。一 般情况下，这些任务的完工持续时间( d u r a t i o n ) 已知，并且各任务之间满足一 浙江大学硕士学位论文引言 定的紧前紧后关系( p r e c e d e n c er e l a t i o n s ) 。问题的关键是为该项目制定一个切实 可行的调度计划，明确各个任务的开始时间和结束时间，以最小化项目工期。 在项目管理的发展过程中，产生了多种有效的项目计划方法，其中最为经典 的是关键路径法( c r i t i c a lp a t hm e t h o d ，c p m ) 和计划评审技术( p r o j e c te v a l u a t i o n a n dr e v i e wt e c h n i q u e ，p e r t ) 。c p m 和p e r t 在上世纪6 0 年代传入我国，由于其 使用网络结构图的形式描述并安排项目进程，因而被称为网络技术或网络方法。 关键路径法和计划评审技术是被实践证实的简单而有效地项目计划工具，在 项目管理邻域得到了广泛的应用。但是，这两种方法对项目模型的假设与现实情 况有着不小的差别，最主要的是它们都忽略了项目执行过程中的资源限制，因而 得出的计划往往是不切实际的，其编制的项目调度计划在资源受限情况下往往无 法顺利实施。 1 3 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 ts c h e d u l i n gp r o b l e m r c p s p ) 。 p c p s p 将可再生资源约束引入项目调度问题，考虑项目活动对可再生资源 的需求量，而项目的在各时间段内可再生资源的总量是有限的。研究表明，经典 的r c p s p 问题属于n p h a r d 问题，传统的c p m 和p e r t 方法已无能为力。为了 说明简单的项目调度问题与r c p s p 问题之间的差别，以p a t t e r s o n1 1 0 问题库中 的p a t 8 为例进行简要说明( 见图1 1 ) 。 浙江大学硕士学位论文 引言 42 图1 ip a t t e r s o n1 1 0 问题库一实例p a t 8 p a t 8 问题由9 个任务构成( 包括2 个虚拟开始、结束任务) ，涉及1 种可再 生资源约束。在描述项目的a o n 结构图中( 图1 1 ) ，每一节点表示一个任务， 节点间的连线代表任务间的紧前紧后关系。其中，项目的开始与结束分别用虚拟 任务1 和任务9 表示。每一任务节点上方的数值为该任务的“持续时间”，下方 数值为该任务的“资源需求量”；可再生资源在各时间段内的可用量为4 个单位。 在不考虑资源约束情况下，使用c p m 方法对p a t 8 问题进行分析。首先，从 0 时刻开始，通过一次正向的调度，求得各个任务的最早开始( e s ) 时间( 等于 紧前任务集中最早结束时间的最大值) ，进而计算其最早结束( e f ) 时间( 等于 自身最早开始时间加上自身持续时间) ；其次，通过一次逆向调度( 一般地，设 开始时间为虚拟结束任务的最早结束时间) ，求得各个任务的最迟结束( l f ) 时 间( 等于紧后任务集中最迟开始时间的最小值) ，进而计算任务的最迟开始( e s ) 时间( 等于最迟结束时间减去自身持续时间) 。最后，在一次正向和一次逆向调 度的基础上，便可计算各任务的总时差( t f ，或称松弛时间) 与自由时差( f r e e f l o a t ，f f ) 。总时差是指不影响整个项目完工时间的前提下，任务的l s 与e s 之 间的差值，即t f = l s e s ；自由时差是指不影响后续活动的最早开工时间的前提 下，任务的自由机动时间，即e f = m i n e s 后襞) e s d u r a t i o n 。其中，松弛时间t f = o 的任务便构成的整个项目实施的关键路径，关键路径长度( c r i t i c a lp a t hl e n g t h ， 6 浙江大学硕士学位论文 引言 c p l ) 等于关键路径上各任务持续时间的总和，即 c p l = d u r a t i o n ( i ) i c r i t i c a lp a t h ， ( 1 1 ) 具体的计算结果见图1 2 ，关键路径为1 - 3 679 ，c p l = 8 。 图1 2 关键路径法求解结果( p a t 8 ) 根据c p m 分析结果与“越早越好”原则绘制如下项目调度示意图( 见图1 3 ) 。 显然，在资源受限情况下，c p m 的调度方案并不能顺利实施；即使对非关键路 径上的项目2 ，4 ，5 ，8 在其时间窗内进行调整，也无法满足资源约束条件。因 此，需要开放其他方法来求解r c p s p 问题，从而获得可行的项目调度方案。 7 浙江大学硕士学位论文引言 资源消耗量 85 4 ，、 lli 疽 m m 3 7 图1 3 项目调度资源负荷示意图 经典的r c p s p 问题是其他资源受限项目调度问题的基础，通过扩展可以衍 生去更为复杂的优化问题。如，考虑任务执行模式( m o d 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 t s c h e d u l i n gp r o b l e m ，m r c p s p ) ；考虑多个项目需要并行进行调度，形成了资源受 限多项目调度问题( 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 gp r o b l e m ， r c m p s p ) 。从而，求解经典r c p s p 问题的方法也成为了处理m r c p s p 和 r c m p s p 等问题的基础。因此，该部分将对r c p s p 问题模型和求解方法做一定 程度的介绍。 1 3 2 资源受限( 多) 项目调度问题求解方法 传统的c p m 和p e r t 方法可以有效处理不考虑资源等约束情况下的项目调 度问题，但对r c p s p 却显得无能为力。 多年来，针对r c p s p 问题，学者们提出了各种优化求解方法，概括起来可 以分为3 类：精确算法、启发式算法以及智能优化算法( 王梦光等，1 9 9 6 ；刘士 新等，2 0 0 1 ) 。精确算法主要包括穷举算法、整数规划以及分支定界法等，其优 点是可以求得问题的最优解。 从理论上讲，只要拥有足够的时间，精确算法都能给出最优解。因此，该类 方法在处理小规模问题时，效果较好。但是，当问题规模比较大时，精确算法往 往显得无能为力，其无法在合适的时间内求出问题的最优解。 启发式算法恰恰相反，求出的问题解往往不能保证最优，但是其最大的特点 浙江大学硕士学位论文 引言 是求解速度快。在处理大规模问题是，启发式方法表现出时间短、能力强的特征， 通常能够给出理想的解，尽管理想解与最优解之间存在一定得偏差。具体的讲， 启发式算法又可以分为基于优先规则的启发式算法、抽样算法等。h a r t m a n n 等 ( 2 0 0 0 ) 与k o l i s c h 等( 2 0 0 6 ) 先后对求解r c p s p 的混合整数规划方法、对基于 优先规则的单路算法( s i n g l ep a s s ) 和多路算法( m u l t ip a s s ) 以及禁忌搜索、遗 传等元启发式算法进行了总结和探讨。 智能优化算法( i 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 s ) ，又称为元启发式算法， 都以人类、生物的行为方式或物质的运动形态为背景，经过数学抽象建立算法模 型，通过计算机的计算来求解组合最优化问题。智能优化算法具有描述简单、鲁 棒性强的特点，主要有禁忌搜索算法( t s ) 、遗传算法( g a ) ，模拟退火算法( s a ) 以及蚁群算法( a c o ) 等。 1 4 项目选择及调度问题 项目组合选择和项目调度都是经典的组合优化n p h a r d 问题，受到国内外学 者的广泛关注。现有大多数学者只单独研究项目选择问题或者项目调度问题。但 是在很多情况下，项目组合选择与调度并不是项目管理中完全独立的两个决策阶 段；在资源约束情况下，项目的调度往往影响着项目选择。 s t u m m e r 等( 2 0 0 3 ) 等在研究多阶段项目组合选择时，虽然考虑了项目组合 实施的多阶段性，但是只是停留在了收益测量和资源消耗分析上，假设所有的被 选项目都是在第一阶段便开始实施，因而并没有考虑多项目调度问题。在考虑项 目调度的项目选择研究中，传统的做法是在项目选择完毕后才对项目进行调度； 一旦选定的项目集合超过了预期的完工时间，那么再对当前的项目集合进行适当 地调整；完全割裂了项目调度与项目选择直接的影响关系。 近年来，有部分学者开始考虑项目组合选择与项目调度相结合，尝试在将项 目调度整合到项目组合选择过程中去，取得了一定的成果。相关研究主要可以分 成两大类： 1 ) 项目选择与项目整体调度。k y p a r i s i s 等( 1 9 9 6 ) 、c o f f i n 等( 1 9 9 6 ) 以及 g h a s e m z s d e h 等( 1 9 9 9 ) 的相关研究都属于这一类。他们将项目视为不可分的整 体，调度只涉及项目整体连续实施的多阶段性，并没有考虑更低层面的任务调度 9 浙江大学硕士学位论文引言 问题。 2 ) 项目选择与项目任务调度。在项目组合的选择过程中，对被选项目中的 任务进行调度。这类问题可以用数学规划的形式给出模型，但是由于问题具有极 高的复杂度，求解一般采取搜索树、启发式或元启发式等非精确的求解方法 ( g u t j a h r 等，2 0 0 8 ；c h e n 等，2 0 0 9 ) 。 1 5 课题研究目的及意义 项目管理已经在建筑工程、新产品研发、机械制造等众多领域得到广泛的应 用；其中，项目组合选择和项目调度作为项目计划环节的关键，越来越受到项目 管理者的重视。随着经济全球化和市场竞争的日益激烈，许多组织都希望在有限 的时间内，并行开展多个项目。成功的项目选择在企业未来的成功中扮演着非常 重要的角色。资源有限情况下，面临众多的备选项目，尤其是高投入、高风险的 r & d 项目，企业迫切需要寻找有效的方法来确定一个“最佳”的组合方案；并 事先对这些项目进行合理的调度与资源分配。 在项目选择与调度的研究中，多数学者割裂了项目选择与项目调度间的内在 联系，要么只单独考虑项目的选择，要么只考虑项目的调度。然而，项目组合选 择与调度并不是项目管理中完全独立的两个决策阶段；在资源约束情况下，项目 的调度往往影响着项目选择。因此，本研究在项目组合选择时考虑项目调度问题， 提出项目组合选择及调度的整体框架，无论在理论上还是在实践上都具有开拓意 义。另一方面，蚁群算法、多智能体进化算法等智能优化算法自诞生至今，已被 证明在求解n p h a r d 组合优化问题方面具有良好效果。本研究在使用智能优化算 法基础上，结合并行项目调度启发式算法解决资源受限项目组合选择及调度问题 进行尝试，具有一定的创新价值。 1 6 论文框架 资源受限项目组合选择及调度优化研究的主要内容包括： 建立数学模型 建立资源受限项目组合选择及调度( r c p p s s ) 数学模型，主要考虑以下几 方面的内容：最大化项目组合收益目标函数、问题约束条件( 项目层面与任务层 1 0 浙江大学硕士学位论文引言 回) 。 算法结构设计 r c p p s s 优化算法包括基于蚁群算法( 或多智能体进化算法) 的项目组合选 择主程序和基于启发式算法的并行项目调度子程序 设计项目并行调度算法 多项目调度采取基于m i n s l k 规则和串行进度生成机制的启发式算法。 设计项目组合选择算法 1 ) 蚁群优化算法 设计蚁群算法主要步骤：( 1 ) 将待求解问题表示成相应的结构图；( 2 ) 确定 问题结构本身的启发式信息；( 3 ) 建立状态转移规则；( 4 ) 定义正反馈过程，确 定信息素更新机制；( 5 ) 建立约束机制，即设计算法的禁忌表；( 6 ) 确定算法的 循环、迭代形式。 2 ) 多智能体进化算法 设计多智能体进化算法主要步骤：( 1 ) 智能体定义；( 2 ) 智能体竞争与自学 习行为设计；( 3 ) 建立约束机制，和智能体非可行修复机制；( 4 ) 确定算法的循 环、迭代形式。 编写程序 优化算法将通过v i s u a lc + + 实现。 算法参数设定 算法及改进措施中有许多需要确定的参数，本研究将在文献结论的基础上， 通过试验比较确定a c o 和m a 算法各参数。 结果与分析 由于并不存在广泛使用的r c p p s s 问题集，所以将通过p s p l i b 和p a t t e r s o n 1 1 0 问题库，随机生成r c p p s s 问题。通过随机r c p p s s 问题的计算，对项目组 合选择及调度优化算法的各性能进行评价 本文正文部分包括7 章内容。第一章为引言，简要介绍项目管理、项目选择 及项目调度的相关概念、解决方法以及本研究的主要内容和意义。第二章为文献 综述，回顾和总结了项目组合选择和资源受限( 多) 项目调度领域国内外学者的 研究进展。第三章对蚁群优化算法和多智能体进化算法进行了简要介绍。第四章 浙江大学硕士学位论文 引言 提出了本研究目标问题及资源受限项目组合选择及调度问题的数学模型。第五章 则针对本研究目标问题，设计了基于智能优化算法和启发式算法的求解算法。第 六章通过数例运算，确定优化算法各参数，并对算法性能进行讨论。第七章对整 个研究进行总结，并展望未来的研究方向。 浙江大学硕士学位论文项目组合选择与项目调度研究现状 2 项目组合选择与项目调度研究现状 为了便于下文提出资源受限项目组合选择及调度模型，本章对项目组合选 择、项目调度研究现状进行余绍。 2 1 项目组合选择问题 项目组合选择( p r o j e c tp o r t f o l i os e l e c t i o n ，p p s ) 问题可以表述为：在有限资 源约束下，决策者从一组有限的备选项目中选择一个项目子集作为一个组合，以 使得该组合在满足约束条件的情况下带来最大的收益(