（管理科学与工程专业论文）柔性资源受限多项目进度安排问题研究.pdf

摘要 近年来，项目管理在世界范围内越来越受到重视，而且在企业和各种组织中发挥了越来 越重要的作用。资源受限项目进度安排是项目管理领域中一个十分重要而义比较复杂的问 题，近几十年来国内外很多学者对该问题进行了研究，提出了各种解决方法。随着全球化经 济的发展，世界市场的竞争越来越激烈，企业项目的规模和数量也越来越大。目前大多数项 目进度安排方面的研究是针对单项目环境下对资源进行分配来优化某个项目指标，对资源受 限多项目进度安排问题研究不多。在企业同时开展多个项目时，由于企业资源的有限性，各 个项目之间经常会产生资源冲突问题，因此研究如何在多项目之间合理配置资源，安排项目 活动的次序，实现多项目总工期最小、总成本最小等优化目标，这是企业实践中具有现实意 义的问题。 本文首先介绍了项目管理的发展及内容，在此基础上引出项目管理研究中的一个重要问 题，即资源受限项目进度安排问题，从不同角度讨论了资源受限项目进度安排问题的分类， 给出了问题的网络模型及数学模型，对近年来一些学者对该问题的解决方法进行了总结。接 着论文对资源受限单项目进度安排问题进行了研究，以项目总工期最小作为优化目标建立数 学模型，讨论了智能算法在求解该问题中的应用，并设计了一种遗传算法来求解该问题，通 过算例说明算法的有效性。现实中企业经常同时开展多个项目，论文提出资源受限多项目进 度安排问题，基于单一优先规则的启发式算法往往不能有效解决多项目进度安排问题，因此 论文设计了一种基于综合优先规则的启发式算法来求解问题，并通过实例仿真说明算法的有 效性。由于企业中的资源总是有限的，因此如果将项目中的资源拓展为柔性资源，对于降低 企业成本，提高企业效益具有现实意义。论文提出了柔性资源受限多项目进度安排问题，建 立了数学模型，利用遗传算法求解该问题。在遗传算法中，针对问题设计了编码方案，在拓 扑排序的基础上生成初始种群，并设计了选择、交叉、变异等遗传操作算子。论文最后给出 了柔性资源受限多项目进度安排问题算例，采用c 语言编写遗传算法程序，通过仿真实验 说明本算法可以有效解决该问题。 关键词：资源受限项目进度安排，多项目管理，柔性资源，遗传算法 a b s t r a c t i nr e c e n ty e a r s ，t h em e t h o d so f p r o j e c tm a n a g e m e n ta n dp r o g r a m m i n ga r ep a i dm o r ea n dm o r e a t t e n t i o nw i t h i nt h es c o p eo fw o r l d ，a n dp l a y e dm o r ei m p o r t a n tr o l ei nb o m e n t e r p r i s ea n do t h e r o r g a n i z a t i o n s 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 mi sv e r yi m p o r t a n ta n d c o m p l e xp r o b l e mi nt h ef i e l do fp r o j e c tm a n a g e m e n t r e c e n t l y ，m a n yr e s e a r c h e r sa l lo v e rt h e w o r l dh a v ei n v e s t i g a t e dt h i sp r o b l e m ，a n dp r o p o s e ds o m es o l u t i o n s a l o n gw i mt h ed e v e l o p m e n t o fg l o b a l i z a t i o ne c o n o m y ，t h ec o m p e t i t i o no fw o r l dm a r k e ti sb e c o m i n gs t r o n g e r ，m e a n t i m et h e s c a l ea n da m o u n to ft h ep r o j e c t si nb u s i n e s se n t e r p r i s eb e c o m eb i g c u r r e n t l y ，t h em a j o r i t yo f p r o j e c ts c h e d u l i n gr e s e a r c h e sa r ea i ma ta r r a n g i n gt h er e s o u r c e si ns i n g l ep r o j e c te n v i r o n m e n tt o o p t i m i z es o m ei n d e x ，w h i l et h er e s e a r c h e so nr 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 ga r e l i t t l e w h e nt h ee n t e r p r i s e dd e v e l o ps e v e r a lp r o j e c t si nt h em e a n t i m e ，b e c a u s eo ft h el i m i t e d r e s o u r c e si nb u s i n e s se n t e r p r i s e s ，e a c hp r o j e c tu s u a l l ya r i s e sr e s o u r c e sc o n f l i c tp r o b l e m ， s o r e s e a r c ho nh o wt oa l l o c a t er e s o u r c e sr e a s o n a b l y ，a r r a n g eo r d e ro fs e q u e n c ea m o n gp r o j e c t a c t i v i t i e s ，r e a l i z em i n i m i z i n gt a r g e t si n c l u d i n gm u l t i - p r o j e c tt o t a lw o r kp e r i o d ，t o t a lc o s ta n ds oo n t h o s ea r er e a l i t yp r o b l e me n t e r p r i s ef a c i n g t h i sp a p e rf w s ti n t r o d u c et h ed e v e l o p m e n ta n dc o n t e n t so fp r o j e c tm a n a g e m e n t ，i ns u c c e s s i o n w ep r o d u c ea n dd i s c u s so n eo fi m p o r t a n tp r o b l e m sa b o u t p r o j e c tm a n a g e m e n t ，n a m e l y 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 ，p r o p o s en e t w o r ka n dm a t h e m a t i c sm o d e l ， s u m m a r i z es o l u t i o ns o m es c h o l a rp r o d u c e df o rt h ep r o b l e m si nr e c e n ty e a r s p r o j e c t se n t e r p r i s e 爆 d e v e l o p p e da r eu s u a l l ym o r et h a no n e ，t h ep a p e rp r o p o s e sr e s o u r c ec o n s t r a i n e dm u l t i - p r o j e c t s c h e d u l i n gp r o b l e m o w i n gt os i n g l ep f i o r i t yr u l eu s u a l l yc a n ts o l v em 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 mv a l i d l y t h ep a p e rd e s i g nan e wm e t h o db a s e do nm u l t i - p r i o r i t yr u l et os o l v et h i s p r o b l e m i ft h er e s o u r c ei sf l e x i b l e ，i tm u s td e c r e a s et h ec o s ta n di n c r e a s et h eb e n e f i t t h ep a p e r r e s e a r c hf l e x i b l er e s o u r c ea n dp u tf o r w a r df l e x i b l er e s o u r c ec 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 ，a n dt r yt oa d o p tg e n e t i ca l g o r i t h m - - am o r ea d v a n c e do p t i m i z e da l g o r i t h mt os o l v e i t a i m i n ga tt h ep r o b l e m ，c o d i n gm o a ni sd e v i s e d ，a n dw ed i s c u s ss e l e c t i o n ，c r o s s o v e ra n d m u t a t i o no p e r a t o r b a s eo nt o p o l o g y ，i n i t i a lp o p u l a t i o ni sc r e a t e d t h r o u g hn u m e r i c a le x p e r i m e n t a n a l y s i sa n dv e r i f i c a t i o n ，t h ea l g o r i t h mi se f f e c t i v ei ns o l v i n gr 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 t s c h e d u l i n gp r o b l e m k e yw o r d 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 g ，m u l i - p r o j e c tm a n a g e m e n t ， f l e x i b l e r e s o u r c e s ，g e n e t i ca l g o r i t h m i i 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：互l l 鱼二_ 二一导师签名： e l 期：加矽j 次 第一章绪论 第一章绪论 随着知识经济的到来，企业面临着更加激烈的竞争。用户需求的多样化和个性化，市场 及制造的全球化，以及以时间为驱动的市场竞争，使传统的企业管理方式在市场竞争中逐渐 暴露出弱点。项目由于具有较大的柔性、较强的市场适应能力和创新能力，将逐渐成为企业 业务活动开展的主要形式，项目管理将成为企业管理的主要战略。项目管理是为一个相对短 期的目标( 这个目标是为了完成一个特定的大目标和目的而建立的) 去计划、组织、指导和控 制公司的资源。进一步说，项目管理就是利用系统的管理方法将职能人员( 垂直体系) 安排到 特定的项目( 水平体系) 中去。 1 1 本文研究背景 项目管理是在2 0 世纪5 0 年代后期发展起来的一种全新而又重要的管理技术，它一出现 就引起举世瞩目。其一是美国的“阿波罗”登月，在实施此项耗资百亿美元、涉及数万企业 的庞大计划中，计划评审技术应运而生，正是这项技术使登月计划提前两年实现；其二是美 国杜邦公司在投产一大型化工厂时，引入关键线路法，开发的此项技术推行一年后，成本大 幅度降低。正是这两种技术，构成了项目管理的核心思想一网络计划技术。此后国际上许多 人对它的研究产生了浓厚的兴趣，这为后来项目管理研究体系的成立奠定了基础。目前有两 大项目管理研究体系：以欧洲为首的国际项目管理协会( 1 p m a ，i n t e r n a t i o n a lp 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 m i ，p r o j e c tm a n a g e m e n ti n s t i t u t e ) ，它的成员主要以企业、大学、研究 机构的专家为主。在过去的3 0 多年中，他们都做出了卓有成效的工作，包括研究和发展、 培训和教育、标准和认证、以及举行各种研讨会等，为推动项目管理现代化发挥了积极的作 用。 早在6 0 年代初华罗庚教授就将项目管理这种技术在中国普及推广，称作统筹方法，我 们现在通常称为网络计划技术。我国对项目管理的系统研究和行业实践起步较晚，一些高校 7 0 年代末期开始这方面的工作，到1 9 9 1 年成立全国性的项目管理协会。8 0 年代以来我国建 筑业开始广泛使用项目管理，鲁布革水电站是利用世界银行贷款的项目，于1 9 8 4 年在国内 采用国际招标，实行项目管理，取得了明显的经济效益。此后，建设部、电力部、化工部等 相继展开了项目管理的培训，高校也相继开出了项目管理课程，我国的项目管理专业人才培 养已有了一定的基础，但在数量和质量上还远不能满足实际需求。 随着全球网络化经济的发展，世界市场的竞争变得越来越激烈，企业项目的规模和数量 也越来越大，对项目管理的要求也越来越高。在某些大型企业( 如建筑业、船l i a s u 造业和航 空工业) ，经常会遇到多个项目需要并行执行的情况。为了一些经济方面的原因和更有效的 配置和使用企业的各类资源，这些大型企业通常会采用一种全新的项目管理方法一多项目管 1 东南大学硕士学位论文 理。 多项目管理是一种全新的项目管理方式，它是站在整个企业层面上，对现行组织中所有 的项目进行计划、组织、执行与控制的项目管理方式。与单个项目管理不同的是，多项目管 理侧重于解决多个项目同时运作的情况下产生的资源配置、成本和效率等问题。 多项目管理的实施成功与否，直接影响企业的经济利益。企业的最终目的在于盈利，良 好的多项目管理可以降低项目成本，优化企业资源配置，从而提高企业的利润率。所以，多 项目管理更能适应当代企业的发展需要。 资源受限项目进度安排是项目管理中一个重要研究领域，近几十年来众多的专家学者在 此领域进行了广泛的研究。在传统的c p m p e r t 进行项目进度安排时都假设资源无限，某 一活动在其所有前驱活动都完成之后可以立即开工，仅考虑了时间因素，而忽略了资源约束 因素。但在项目的实际执行过程中，可以使用的资源往往有一定的限制。某些可以并行开始 的活动由于资源约束，其开始时间只能向后延迟，等其他活动完成之后，释放出资源才能开 始执行，针对这一情况，资源受限项目进度安排问题被提出并成为项目管理中的一个热点问 题。 在项目进度安排中，有些活动是可以同时进行的，而有些活动则必须在其他若干项活动 完成之后才能进行，活动之间的这种限制关系就是我们通常所说的时序关系。同时，每项活 动本身还需要一定的延续时间和利用或使用不同种类的资源( 如机器、设备、材料、劳动力 等) 。资源是工程筹划中不可缺少的重要组成部分，而这些资源的可使用量常常是有限制的。 无论是建筑业中施工，还是高科技信息系统的研制，甚至在非工程设计领域，例如；学校的 课程安排，政府机关的会议筹备等，都普遍有上述出现的筹划情况。那么如何按可能有的最 佳方式安排实现项目中的各个活动，以期筹划圆满完成，就形成了资源受限项目进度安排问 题的基本概形。资源受限项目进度安排问题产生历史比较长，是项目管理中的古典问题之一。 一般的资源受限项目进度安排问题可以描述如下：给定一组互相关联的活动( 具有紧前 紧后序列关系) ，每个活动能以几种可执行模式中的一种执行，每种执行模式有一已知的持 续时间和给定的资源需求量。为了优化所要达到的目标，每个活动应在什么时候开始，应选 择哪种执行模式? 显然求解该类问题必须考虑时序约束和资源限制。正是由于资源受限项目 进度安排问题必须同时处理时序约束和资源约束，所以，它比一般调度问题更难解决，属于 n p - h a r d 问题类。资源受限项目进度安排问题的调度决策要同时服从于项目活动之间的时序 ( p r e c e d e n c e ) 约束和已知的资源( r e s o u r c e ) 约束。 随着世界市场的竞争变得越米越激烈，很多企业为了生存和发展往往同时开展多个项 目。因而如何在多项目间合理分配企业有限资源，安排项目进度，已经是很多企业面临的一 个现实问题。显然，资源受限的多项目进度安排问题比单项目进度安排要复杂得多，多项目 进度安排问题是研究怎样把有限的资源在几个项目之间分配，每个项目由一组活动组成，这 些活动之间具有确定的前后关系，并且完成每个活动需要一定量的资源。各项目所要达到的 目标可能是项目总工期最小、资源消耗最少、或项目的净现值最大等。 2 第一章绪论 1 2 资源受限进度安排问题研究现状 自从六十年代初k e l l y 和w i e s t 开始研究资源受限项目进度安排问题以来，大量学者从 不同的角度对这个问题进行了深入细致的研究。 p a t t e r s o n 和r o t h t 3 2 】采用o 1 整数规划的方法求解资源受限项目进度安排问题。& 伽伽【3 】、 c h r i s t o f i d e s 4 1 和d e m e u l e m e e t e f l s 等陆续提出用分枝定界法来解决该类问题，从而求得最优 解，它们的不同之处在于分枝方案和淘汰规则等细节问题上【6 j ，其中后者求解所用的平均时 间最短。对于大型项目，由于分枝定界法运行时间较长，所以不得不借助于启发式方法 b d c f d 一7 1 在1 9 9 0 年研究了将多个优先级规则结合起来生成进度安排与用一个优先级规则单 独地生成进度安排的关系。k o l i s c h 【8 】于1 9 9 6 年研究了串行进度安排方法和并行进度安排方 法，样本方法( 同时生成多个进度安排，从中选取最好的一个) 与单遍方法的关系。由于现 代优化方法的兴起，这些方法逐渐地应用到该领域中，取得的效果比优先级规则所得到的还 要好一些，这些方法包括诸如k o l i s c hf 9 】的禁忌搜索方法、肋“肠拥绷【1o 】的模拟退火方法、 z 渤砌加，l 1 1 】的遗传算法等，在资源受限项目进度安排问题中应用g a 首要关键是设计编码方 式和有效的解码规则。h a r t m a n n 提出了编码为任务链表、解码规则为串行调度方案的遗传 算法【l 。后来，h a r t m a n n 在任务链表后面加上一个代表解码规则的基因s p ，由该基因的 值指定前面的任务链表的解码规则为串行或并行。a l c a r a z 和m a r o t o 基于对于同一任务链表 向前和向后解码结果不一样的事实，在任务链表后面加上一个表示解码方向的基因f b 来自 适应地控制解码方向【1 3 1 。王宏等在任务链表后面加上两个基因，一个是表示解码规则的s ：，尸 基因，另一个是表示解码方向的f b 基因，由这两个基因同时控制任务链表的解码规则和解 码方向【1 4 1 。 在对单项目进行优化的同时，一些学者开始重视多项目资源约束问题的重要性。 l o v a 1 s 1 1 9 9 7 年向西班牙v a l e n c i a n 地区的公司发出1 0 0 0 份有关项目管理的问卷调查表，在 收回的2 0 2 份中发现该地区有8 4 的公司正在从事多项目管理。f e n d l e 矿16 】首创研究多项目 进度安排问题的先河。k u r t u l u s 和d a v i s l l 5 , 1 9 】分别研究了在对等延迟惩罚和不等延迟惩罚的 情况下，如何根据项目的特征来选取最佳的优先级规则。d u m o n d 和m a b e 一2 0 】研究了在动态 ( 有些项目有可能在将来以不可预知的时间加入到现有的进度安排中，同现有的项目竞争资 源) 的多项目环境中，如何选择优先级规则，为所有的项目较准确地预测完工日期问题。 k i m 和l e a c h m a n 2 1 1 研究了在动态的多项目环境中，假设每个项目有一个指定的完工日期， 项目在其完工日期的前后有一个相应的惩罚，如何解决总的延迟成本最小化的问题。r o b e r t c a s h 2 2 1 研究了在动态的多项目环境中，如何通过仿真方法从所考虑的优先级规则集合中选 取适合该问题的最佳优先级规则。郭研等研究利用遗传算法解决多项目资源平衡问题，尽量 使单位时间内所有项目的总资源消耗方差最小【2 3 1 。谈烨等提出利用两层决策方法建立多种 资源受限多项目排序问题数学模型，采用基于直接搜索法的随机全局优化方法求解 2 6 】。 在已有的关于项目进度安排问题研究中大多没有考虑柔性资源的因素。虽然国内外一些 3 东南大学硕士学位论文 学者对柔性资源的有效使用进行了研究，但是大部分集中在制造业的车间调度上。如国际上， d a n i e l s 和m a z z o l a 3 4 1 ， s i g u 栅3 5 1 和册f 【3 6 1 ， z a v a d l a v ，m c c l a i n 和刀l d ， l 3 刀研究了完全 柔性资源( 资源可以被运用于生产流程的任何环节) 对生产调度的影响，他们发现通过使用 完全柔性资源能有效地提高生产率。s h i ，d a n i e l s ，m a z z o a 3 8 , 3 9 】将研究领域从完全柔性资源 拓展到部分柔性资源，并且发现，通过合理地管理和利用部分柔性资源，可以获得完全柔性 资源对生产率的提高的同样效果。在国内，陈荣秋等1 4 0 1 研究了组织管理系统、技术系统柔 性以及企业整体柔性等；李必强等【4 l 】研究了企业生产组织的均衡性与弹性；邓明然教授等【4 2 l 研究了企业理财系统的柔性。罗荣桂等 4 3 1 对具有柔性资源约束的f l o ws h o p 调度问题进行了 研究，提出柔性资源的最优分配和使用的智能算法具有重要的理论意义和实用价值。 综上所述，可见资源受限项目进度安排问题在项目管理领域中地位十分重要。近几十年 大量的学者对该问题进行了研究，提出了各种各样的求解方法，概括起来可以分为精确算法， 启发式算法及智能优化算法。已有的项目进度安排问题研究大多是在单项目环境下进行的， 由于企业规模的不断扩大，越来越多的企业面临如何在多项目之间合理分配资源问题。此外， 企业为了在激烈的市场竞争中生存发展，纷纷采用柔性生产技术，发展柔性资源。因此研究 柔性资源受限多项目进度安排问题对企业具有战略意义。 1 3 本文研究的主要内容 从企业的实践来看，9 0 以上的项目是在多项目环境下开展的。目前大多数项目进度安 排方面研究的是针对单项目环境下对资源进行分配，来优化某个项目指标。对资源约束下多 项目进度安排问题研究不多。多项目是指在企业内同时进行的项目多于一个。由于企业拥有 的资源有限，当企业中同时存在多个项目时，如何正确合理地在各个项目之间分配资源将变 得更加复杂。已有的项目管理资源分配问题研究大多将资源分为可再生资源、非可再生资源 及双重性质的资源，而现实中企业中的资源往往具有一定的柔性，例如人力资源，某些项目 成员可以加入多个项目中，柔性资源下的项目进度安排研究将会提高企业的效益。论文提出 了柔性资源受限多项目进度安排问题。 论文主要进行以下研究工作： 第一章，主要介绍资源受限项目进度安排问题的研究背景，讨论该问题的研究现状，针 对已有研究存在的不足，引出本论文所要研究的柔性资源受限多项目进度安排问题。 第二章，讨论了柔性资源受限的多项目进度安排问题理论基础。在介绍了网络图基础知 识的基础上，给出建立网络模型的方法。描述资源受限项目进度安排问题，对已有的求解方 法进行分类，最后概述了企业中存在的柔性问题。 第三章，研究了资源受限单项目进度安排问题。建立资源受限单项目进度安排问题的数 学模型，概述了模拟退火、禁忌搜索、遗传算法等智能算法在求解该类问题中的应用。最后 设计遗传算法来求解资源受限单项目进度安排问题，通过实例仿真说明方法的有效性。 第四章，研究了资源受限多项目进度安排问题。在平衡计分卡确定多项目评价指标体系 4 第一章绪论 基础上，采用层次分析法确定指标权重，以此确定项目的优先级。针对基于单一优先规则的 启发式算法在解决资源受限项目进度安排问题时存在有效性不好的问题，设计基于多种优先 规则的启发式方法对问题求解，通过算例验证方法的有效性。 第五章，基于遗传算法的柔性资源受限多项目进度安排问题研究。首先描述柔性资源受 限多项目进度安排问题，设计一种遗传算法求解该问题。编码采用基于活动顺序和基于资源 分配两种编码方法，初始种群通过随机和基于优先规则两种方式产生，根据编码方案分别设 计遗传算子，通过算例验证方法的有效性。 第六章，对论文进行了总结和展望，指出了未来需要进一步研究和讨论的问题。 5 东南大学硕士学位论文 第二章柔性资源受限的多项目进度安排问题相关理论 在本章，先介绍网络图的基本概念，它是理解本文其余部分的基础。然后详细讨论资源 受限项目进度安排问题( 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 t s c h e d u l i n g p r o b l e m ，r c p s p ) 的产生、 分类、求解方法，最后讨论资源柔性问题。 2 1 网络图的基本内容 网络图是一种普遍运用的项目计划方法，最早出现于欧洲，但真正的开发使用始于1 9 世纪5 0 年代美国的国防计划中。网络图的发展突飞猛进，后来广泛应用于各个行业。网络 图又称箭线图，它是用图解的形式表示一个生产任务或工作项目中几个组成要素之间的逻辑 关系，是计划的图解模型。通过网络图可以清楚地反映计划任务的结构安排和各项活动之间 的衔接关系，表达完成计划任务的各种方案和设想，以便在实施中统筹兼顾，合理安排，为 计划的编制和项目的管理提供科学依据。项目网络分析中主要采用两种方法：计划评审技术 ( p r o g r a me v a l u a t i o na n dr e v i e wt e c h n 幻u e ，p e r t ) 、关键路径法( c r i t i c a lp a t hm e t h o d ， c p m ) 。p e r t 是由美国海军，博思管理顾问公司( b o o z - a l l e nh a m i l t o n ) 和洛克西德飞机公 司( 现在的洛克西德马丁公司) 研究提出的。c p m 是由杜邦公司提出的。它们产生时， 两种方法有重大的差别。例如，p e r t 使用活动历时的概率( 或不确定性) 估算，而c p m 使用决定性的( 或确定的) 估算，包括时间和成本的估算，以便用于时间成本之间的权衡。 两种方法都使用网络图来计划任务的进度和显示任务的顺序。两种方法都可以确定出关键路 径上的活动，这些活动的延误会引起整个项目的延误。两种方法都可以确定出带有时差( 或 浮动时间) 的活动。这些活动在不延长项目完成时间的前提下，可以有某种程度的延误。虽 然p e r t 和c p m 在绘制活动网络图时所用的方法略有不同，但可以用p e r t 做的事也可以 用c p m 来做，反之亦然。 下面介绍一下p e r t c p m 网络分析中使用的一些概念。 活动项目要求的一项任务或任务组。活动使用时间和资源。 事件由于完成一个或多个活动而形成的可识别的状态。事件不消耗资源或时间。 在一个事件完成或实现前，所有的前导活动必须完成。 里程碑可以识别并值得注意的事件。标志着项目的重大进展。 路径在网络中两个事件之间一系列相连的活动( 或中间的事件) 。 关键路径在某条路径上从项目开始事件到结束事件的一组活动。如果延误了，则 会延误整个项目的完成的时间。 建立网络图有两种方法。一种是活动用箭头表示，事件用节点表示，这就形成了双代号 ( a o a ) 网络图，通常与p e r t 在一起。另一种是单代号( 彳伽) 网络图，每项活动作为一 个节点，用显示其技术关系的箭头连接节点。a o n 网络图经常与c p m 在一起。 6 第二章柔性资源受限的多项目进度安排问题相关理论 双代号网络图及单代号网络图中有1 0 种基本逻辑关系，可以表示如下表2 1 。 表2 1 双代号网络图及单代号网络图中的逻辑关系 序 逻辑关系双代号表示方法单代号表示方法 号 l彳完成后进行曰 丑完成后进行c 2 彳完成后同时 进行b 、c b 、c 都完成后 进行d c u 3 彳完成后同时 进行b 、c 一4 彳和占都完成后 进行c 一 5 彳和口都完成后 同时进行c 和 d 6 彳完成后进行c 彳和b 都完成后 进行d o 与6 旦旬 7彳、b 都完成后 进行d 4 、曰、c 都完成 后进行e d 、e 都完成后 进行， 8 彳、b 都完成后 ，_ 、 进行c 曰、d 都完成后 进行e 7 东南大学硕士学位论文 续表2 1 9 么完成后进行c 一 4 、口都完成后 进行d b 完成后进行e 1 0a 、b 两项先后 2 进行的工作各 分为三段进行。 彳l 完成后进行 彳2 、b i ；a 2 完成 后进行a 3 、b 2 ； 口i 完成后进行 b 2 、a s ：b 2 完成 后进行曰3 2 2r c p s p 的产生及描述 项目在执行过程中需要各种各样的资源，一般来说，资源的使用都是受限的，因为在绝 大多数项目中，资源本身是有限的或者获得额外资源的成本过高而不可行。因此如何充分利 用各种有限资源完成项目就成为项目管理过程中的一个重要的问题。 p e r t c p m 作为一种项目管理非常有效的工具，被广泛应用于项目计划和控制过程中， 但是这两种方法在应用中忽略了对资源的限制，所以根据这两种方法编制的计划在资源受限 的情况下一般不能够得到保证，由此产生了r c p s p 。 r c p s p 是指项目中具有一系列相互关联的任务，其中，每一任务可以采用几种模式完 成，每一种模式以已知的工期和资源需求量为特征，此问题的解是在满足时序和资源约束条 件下产生一种使某种管理目标为最优的调度方案。r c p s p 在理论上属于n p - h a r d 问题，是 一类重要的组合优化问题，是工程设计中最典型的问题之一，该问题模型丰富，许多问题都 是r c p s p 的特殊情形，例如作业车间( j o bs h o p ) 调度，流水车间( f l o ws h o p ) 调度等。此 外r c p s p 广泛存在于建筑工程、软件开发、计算机行业( 如操作系统中的资源管理、处理 器的任务调度) 及飞机、轮船等单件或小批量生产方式的企业中，企业可利用有限资源，合 理地安排生产任务降低生产成本，以提高经济效益。因此研究r c p s p 具有重要的理论和现 实意义。 项目一般是由多个相互关联、相互制约的活动所组成。在众多模型( 数学模型、物理模 型、模拟模型等) e o ，网络模型是最直观、简捷、有效的。网络模型既是图示模型，又是能 8 第二章柔性资源受限的多项目进度安排问题相关理论 反映出各组成要素和参数间的相互关系，并按照一定的拓扑逻辑关系进行分析和计算的标准 模型。因此在工程技术、生产管理等领域中的工程项目描述一般都采用网络模型。应用网络 模型不仅可以直接表明各变量、各约束条件间的相互关系，同时可以应用网络理论对问题进 行分析、计算、求解和优化。 其一般步骤如下： ( 1 ) 确定项目的性质和目标，并加以正确的描述，即确定项目的范围； ( 2 ) 确定项目活动，并将项目分解，构造项目工作分解结构图( 翮卿； ( 3 ) 确定各个活动之间的逻辑关系； ( 4 ) 搜集资料，估计各个活动的有关参数及变量，构造网络模型，使用节点、箭线和流 三要素反映项目中各个活动之间的关系及参数； ( 5 ) 进行数据处理、符号调整和逻辑关系检查； ( 6 ) 求解模型。依据网络模型的逻辑关系及其相应的参数与变量，进行计算、分析、优 化模型； ( 7 ) 修改和调整模型。 由于r c p s p 涉及的范围较广，自从r c p s p 提出以来，已经出现了种类繁多的r c p s p 问题。根据r c p s p 问题的项目数量、资源类型、执行模式、活动和目标函数等4 种属性的 不同可以对r 卿问题进行分类。 根据同时处理的项目个数，可分为单项目( s i n g l e - p r o j e c t ) r c p s p 与多项目 ( m u l t i - p r o j e c t ) 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 问题的扩展，允许活动可以以多种执行模式之 一进行操作，每种执行模式对应一种资源组合和相应的活动执行时间。活动的执行时间是所 使用资源组合的函数。 根据活动是否可中断，可分为不可中断活动和可中断活动。不可中断活动指一旦开始 执行便不能中断的活动，可中断活动指在执行过程中可以暂时停止执行，等待条件满足后继 续执行的活动。 9 东南大学硕士学位论文 根据目标函数将r c p s p 问题分为： ( 1 ) 最小化项目工期问题 最小化项目工期问题( p r o j e c t d u r a t i o n ) 是资源受限项目进度安排问题中的基本问题，也 是最普遍采用的管理指标；2 2 一，该问题的研究不仅具有一定的理论意义，而且具有明显的 实用价值。 从本质上来看，资源受限项目进度安排问题中的最小化工期问题是在时序约束和资源约 束条件下的组合优化问题，即如何在满足这两个约束的条件下，确定出所有活动的开工时间， 使项目工期达到最小。 ( 2 ) 资源均衡问题 资源均衡( l e v e l l i n gr e s o u r c eu s a g e ) 问题是资源受限项目进度安排问题中的重要研究目 标之一。一项符合工期要求的项目计划，由于受到资源限制的影响，如果工作进度安排不恰 当，就会在计划的某时段出现资源的需求“高峰”，而在另一些时段出现“低谷”现象。这 种“峰”与“谷”的存在容易造成资源供、需量冲突或形成资源积压，因此合理地安排项目 中的各个活动进度，解决资源供需矛盾是急需解决的问题。在资源均衡问题的研究中，由于 资源限制因素较多，因此，该问题的分类方式也较多。如：按优化资源目标的方式，可将资 源均衡问题分为规定工期的资源均衡问题和有限资源的合理分配问题；按所需资源类型的方 式又可将该问题分为可更新资源类、不可更新资源类与双重约束资源类。 ( 3 ) 现金流优化问题 资源受限项目进度安排问题中的优化指标一般采用最小化工期以及均衡使用资源。但 是，随着生产、制造业的发展及市场竞争的日趋激烈，项目效益不仅成为生产与开发的主要 衡量指标，而且也是一个企业、集团的生命力的体现，因此，资源受限项目进度安排中的现 金流优化问题已逐渐成为该领域的研究热点。在对问题的研究中，首先基于该问题的一般假 设，然后以项目的最大净现值作为优化指标，建立带有贴现率的最大化网络净现值 ( m a x i m i z a t i o no f t h en e tp r e s e n tv a l u e ) 的数学模型，进而实施优化策略及优化求解。 ( 4 ) 最小化项目运作总成本问题 项目执行包含各种资源，每种资源都消耗一定的成本，该问题以资源折算成成本，在满 足时序约束和资源约束条件下，以最小化项目运作总成本为目标进行优化调度。 2 5r c p s p 的解决方法 资源受限项目进度安排问题的研究有近4 0 年的历史，其相关理论与方法的研究一直受 到学者和实际管理人员的关注。解决资源受限项目进度安排方法基本上可以分为：精确最优 方法、启发式算法和基于局域搜索的启发式算法。 1 0 第二章柔性资源受限的多项目进度安排问题相关理论 2 5 1 精确最优算法 早期解决资源受限项目进度安排寻求问题精确最优解的方法，主要包括整数规划，有界 枚举( b o u n d en u m e r a t i o n ) ，分枝定界1 4 ”l 】等。 整数规划是将优化目标和各种约束条件表示为线性不等式或等式，通过求解整数规划问 题得出最优调度。其特点是只要问题的最优解存在，就可以利用规划方法找到。但是若实际 进度安排问题使整数规划涉及的约束关系过多，则容易形成“组合爆炸”问题，因此应用性 不好。而枚举方法是通过枚举出可行解集合内的所有可行解，来求出精确最优解的方法。但 是以一般的连续函数为例，该方法要求先对其进行离散化处理，而这样就有可能产生离散误 差而永远达不到最优解。另外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至 在目前最先进的计算工具上都无法求解。分枝定界法最初来自于整数规划，它是一种树搜索 算法，通过选取有效的界限规则，来剪掉搜索树中那些不可能达到最优解的分枝，缩小搜索 空间的范围，直到找到最优解。分枝定界算法可以求得问题的最优解，但由于占用的计算机 空间大，求解时间长，因此可求解的规模小，不利于大规模问题的求解。 2 5 2 启发式算法 资源受限项目进度安排问题是n p h a r d 问题。在这种情况下，为寻找近优解可采用启发 式解决方法，基于优先规则的启发式算法是求解r c p s p 的主要启发式方法，由调度生成方 案( s g s ) 和优先规则( p r i o r i t yr u l e ) 构成【4 5 】。调度生成方案包括串行调度( s e r i a l s c h e d u l i n g 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 ) 。两种调度方案都是通过分阶 段方式扩展一个半调度计划直至生成一个完整的可行调度计划。半调度计划指的是所有活动 中只有部分活动给出完成时间。在每个调度阶段，算法生成一个可调度的活动集合，通过具 体的优先规则，从该可调度的活动集合中选出一个或几个活动，安排选出的活动的开始执行 时问。 2 5 3 智能算法 在解决进度安排问题时，将智能化局域搜索技术与启发式方法相结合便形成智能算法。 很多智能算法就是基于局域搜索的启发式方法，例如利用模拟退火、禁忌搜索、遗传算法等 方法解决实际中的进度安排问题。基于局域搜索的进度安排方法的共同特点是基于某种邻域 结构，在可行解集合的一个子集内进行邻域搜索操作，由当前解在邻城内寻找新的改善解， 进行迭代寻优，最终找到问题的最优解或近优解。该方法虽然保证不了一定能够得到问题的 最优解，但若适当地利用一些启发知识，就可以在近似解的质量和求解效率上达到一种较好 的平衡。这些方法包括诸如k o l i s c h1 9 的禁忌搜索方法、b d “昆砌p 1 0 l 的模拟退火方法、 觑z ，拥口刀以【1 i 】的遗传算法等。 1 1 东南大学硕士学位论文 2 6 企业柔性概述 我们正处在一个巨变的时代，科技进步加速，知识创新渐频，消费者需求易变，产品市 场寿命渐短，企业竞争白热化。而对如此变幻多端的经济环境，企业界纷纷把“企业柔性