（管理科学与工程专业论文）求解资源受限项目调度问题算法的研究.pdf

中文摘要 资源受限项目调度问题( 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 ) 调度等。此外i 配p s p 广泛存在于建筑工程，软件开发， 飞机和轮船制造等单件或小批量生产方式的企业中。因此研究i 配p s p 具有重要的 理论和现实意义。本文主要研究内容如下： 1 遗传算法( g a ) 已经应用于经典r c p s p 中并取得了显著的效果。在此基础 上，本文设计了一种新的编码方法用于遗传算法求解经典r c p s p 。此编码方法为 带有解码规则和解码方向的任务链表，亦即在任务链表后面加上两个基因，一个 是表示解码规则的基因，另一个是表示解码方向的基因，由这两个基因同时控制 任务链表的解码规则和解码方向。选用标准数据库p s p u b 中的1 5 6 个例子进行验 证该算法的有效性，结果表明本算法优于用任务链表和带有解码规则的任务链表 两种编码的遗传算法。 2 在实际的项目调度中，不确定因素往往会导致项目调度无法按预定方案 正常执行。为了更好地反映实际情况，本文研究了以排序健壮性最大为优化目标 具有模糊工期和模糊交货期的资源受限项目调度问题，采用六点模糊数表示模糊 工期和模糊交货期，引入了两种模糊数的弱比较方法，即积分值法和重心距离法。 针对这一优化问题我们设计了一种基于任务链表编码形式的遗传算法。数值实验 结果表明，该算法优于文献中的相关算法，同时也表明基于两种模糊数的弱比较 方法对算法的性能影响较弱。 3 采用基于非支配性排序的多目标遗传算法( n s g a i i ) ，设计了一种求解 多模式、多种类资源约束的多目标资源受限项目调度问题的遗传算法，该算法采 用了任务链表和模式向量的编码方案，适应值是个体的非支配等级和其局部拥挤 距离，采用一种新的比较算子，比较两个个体的适应值的大小，特殊的精英选择 策略。将所设计的算法用于求解以项目总工期和资源均衡为目标的农业项目调度 问题，结果表明此算法对于求解多目标r c p s p 是有效的。 针对本文研究的r c p s p 的特点设计了三种不同的遗传算法进行求解，均取得 了较好的计算效果。本文研究表明了遗传算法在求解资源受限项目调度问题上具 有较好的应用前景。 关键词：遗传算法资源受限项目调度模糊项目调度多目标项目调度 a b s t r a c t 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 ni st os o h e d d et h e a c t i v i t i e ss u c ht h a tp r e c e d e n c ea n dr e s o u r c ec o n s t r a i n t sa r es a t i s f i e dw h i l eo p t i m i z i n g s o m em a u a g e r i a lo b j e c t i v e a p p l i c a t i o n sc 锄b ef o u n di nd i v e r s ei n d u s t r i e s e s p e c i a l l y i nm a k e - t o - o r d e ra n ds m a l lh a t o hp r o d u c t i o ns u c ha sc o n s t r u c t i o ne n g i n e e r i n g , s o f t w a r ed e v e l o p m e n t , s h i p sa n dp l a n e se t e n em o d e l si nt h i sf i e l da r er i c h , m a n y w e l l - k n o w no p t i m i z a t i o np r o b l e m sa l es p e c i a lc a s e s ，f o ri n s t a n c ej o bs h o ps c h e d u l i n g a n df l o ws h o ps c h e d u l i n g s o ，r e s e a r c h e si nt h i sa r e ah a v ei m p o r t a n tv a l u e si nt h e o r y a n dp r a c t i c a la p p l i c a t i o n s 1 1 1 cm a i nc o n t e n t so f t h i st h e s i sa r e 雒f o l l o w s ： 1 g e n e t i ca l g o r i t h m ( g a ) i sa l le f f e c t i v em e t h o df o rs o l v i n gt h ec l a s s i c a l r c p s p ht h i sp a p e rw ep r o p o s ean e wg aa p p r o a c ht os o l v et h i sp r o b l 鼬o u r a p p r o s o he m p l o y san e wr e p r e s e n t a t i o nf o rs o l u t i o n st h a ti saa c t i v i t yl i s tw i t ht w o a d d i t i o n a lg e n e s t h ef i r s td e t e r m i n e sw h i c ho ft h et w od e c o d i n gp r o c e d u r e si su s e d t oc o m p u t e ras c h e d u l ef o rt h ea c t i v i t yl i s t 1 1 1 es e c o n di n d i c a t e st h e d i r e c t i o ni n w h i c ht h ea c t i v i t yl i s ti ss c h e d u l e d n l et w og e n e sd e t e r m i n et h ed e c o d i n gp r o c e d u r e a n dd e c o d i n gd i r e e t i o nf o rt h er e l a t e da e t i v i t yl i s ts i m u l t a n e o u s l y t h ep e r f o r m a n c e e v a l u a t i o nd o n eo nt h e1 5 6b e n c h m a r ki n s t a n c e ss h o w st h a to u rg ay i e l d sb e t t e r r e s u l t st h a nt h eo t h e rt w og a sw h i c hm a k eu s eo ft h ea c t i v i t yl i s tr e p r e s e n t a t i o na n d t h ea c t i v i t yl i s tw i t hd e c o d i n gp r o c e d u r er e p r e s e n t a t i o nr e s p e c t i v e l y 2 嘣st h e s i ss t u d i e st h er c p s pw i t hf u z z yp r o c e s s i n gt i m ea n df u z z yd u ed a t ei n w h i c ht h eo b j e c t i v ei st om a x i m i z et h es c h e d u l i n gr o b u s t n e s s f u z z yp r o c e s s i n gt i m e a n df u z z yd u ed a t ea l ed e n o t e db ys i x p o i n tf u z z yn u r n b e r s w bi n l r o d u c et w ow e a k e o m p a r i s o nr u l e s ( w e r ) f o rf u z z yn u m b e r s 。i e i n t e g r a lv a l u em e t h o da n dc e n t r o i d d i s t a n c em e t h o d ag e n e t i ca l g o r i t h mw i t ha e t i v i t yl i s tr e p r e s e n t a t i o ni sp r o p o s e df o r s o l v i n gt 1 1 i sp r o b l e m 1 1 1 ec o m p u t a t i o n a le x p e r i m e n ts h o w st h a tt h ep e r f o r m a n c eo f t h ep r o p o s e da l g o r i t h mi sb e t t e rt h a nt h eb e s th e u r i s t i c sa p p e a r i n gi l lt h el i t o r a t u r e 。 t h e r ei sn od i f i e r e n e eb e t w e e nt h et w ow c ro nt h ep e r f o r m a n c eo f t h ea l g o r i t h m 3 删st h e s i sp r o p o s e sam u l t i - o b j e c t i v ee v o l u t i o n a r ya l g o r i t h mc a l l e dt l l ef a s t e l i t i s n o n - d o m i n a t e ds o r t i n gg e n e t i ca l g o r i t h m ( n s g a - i i ) t os o l v et h ei t c p s p w i t hm u l t i p l ea e t i v i t yp e r f o r m a n c em o d e sa n dt w oo b j e c t i v e st om i n i m i z ep r o j e c t m a k e s p a na n dr e s o u r c eu t i l i z a t i o ns m o o t h n e s s t h es o l u t i o ni sr e p r e s e n t o db ya p r e e e d e n c ef e a s i b l ea e t i v i t yl i s ta n dam o d ea s s i g n m e n t a na g r i c u l t u r a le x a m p l ew i t l l t w oo b j e c t i v e si su s e dt o t e s tt h ep e r f o r m a n c eo fa l g o r i t h mp r o p o s e d t h er e s u l t s s h o wt h a tn s g a i ii se f f i c i e n tf o rs o l v i n gt h em u l t i - o b i e c t i v er c p s p i nt h i st h e s i s w ed e v e l o pt h eg af o rs o l v i n gt h r e ed i f i e r e n tm o d e l so fr c p s p a n dt h ep r o c e d u r e sa r ed e s i g n e du s i n gi n f o r m a t i o nr e l a t e dt os o m ec h a r a c t e r i s t i c so f r c p s p t h et h r e ep r o c e d u r e sw ep r o p o s e dy i e l db e t t e rr e s u l t s t h i ss t u d ys h o w st h a t g ai sap r o m i s i n ga p p r o a c hf o rr c p s p k e yw o r d s ：g e n e t i ca l g o r i t h 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 g , f u z z yp r o j o c ts c h e d u l i n g ，m u l t i - o b j e c t i v ep r o j e c ts c h e d u l i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞盘茎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：王暖签字日期：撕争年i t 月牛日 学位论文版权使用授权书 本学位论文作者完全了解鑫鲞盘茎有关保留、使用学位论文的规定。 特授权苤鲞盘茎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：嚷 导师签名： 套弼苏 签字日期：暑防年垃月牛日签字日期：砀矿年月眵日 天津大学博士学位论文求解资源受限项目调度问题算法的研究 第一章绪论 知识经济的到来，对以增产为主要创造利润手段的企业提出了新的挑战。企 业必须通过运用知识去开展各种的技术、管理、体制等创新活动，以适应激烈的 市场竞争，根据客户需求，快速重组资源，组织生产，及时提供用户需要的“个 性化产品”。这一切都要求企业必须以创新活动( 项目) 为中心，开展项目管理 去管理好各种各样的创新活动。本章将首先简要的介绍项目、项目管理、项目调 度的有关知识，然后介绍选题的意义及其本文研究的主要内容。 1 1 项目管理 1 1 1 项目 由于所处的实际环境和考虑问题的角度不同，关于项目的定义，目前尚没有 统一的结论，下面介绍几个比较典型的定义： 美国项目管理学会出版的项目管理知识体系指南一书中给出的定义为： 项目具有独特的过程，由一系列有着明确起点和终点的相互协调和受控的任务组 成。过程的实施是为了达到规定的目标，包括满足时问、费用和资源等约束条件。 ( i s 0 8 4 0 2 ，转引自 1 ) 现代项目管理【2 】中项目的定义为：项目是一个特殊的将被完成的有限任 务，它是在一定时间内，满足一系列特定目标的多项相关工作的总称。 实用项目管理翻中认为项目是数量众多、相互依赖、需要人员和资源一 起进行的一组活动。它有一个明确的开始和结束日期，有鉴定其是否成功完成的 一系列具体标准。当这些活动结合在一起的时候，它们能产生出希望的结果。 但一般来说，项目具有下列共性： 1 目标性。项目是一种有着规定要求的最终产品或服务的一次性活动。 2 独特性。表示项目最终提供的产品或服务总是在某些方面与其他所有的 产品或服务具有显著的差别，没有两个项目会是完全相同的。 3 临时性。一个项目一定有明确的开始和结束 4 不确定性。因为项目的独特性，项目的执行无章可遵，项目经理对于能 否达到目标应具有风险意识。 5 生命周期性。任何项目都会经历概念设计、项目定义、项目计划、项目 第一章绪论 实施和项目结果的提交这样一个过程，人们常称这一过程为“生命周期”。 6 过程性。项目是为实现目标而开展的任务的集合，它不是一项独立的活 动，实现目标的过程必然是一个不断优化的过程。 人类早期的项目可以追溯到数千年以前，中国的古长城、埃及的金字塔和古 罗马的尼姆水道都是人类历史上运作大型复杂项目的范例，那时对项目的管理只 是凭个别人的经验、智慧和直觉，依靠个别入的才能和天赋，可以称那时的项目 管理为潜意识的项目管理。随着现代项目规模越来越大，投资越来越高，涉及专 业越来越广泛，项目内部关系越来越复杂，传统的潜意识的管理模式已经不能满 足运作一个项目的需要，于是产生了对项目进行管理的模式，并逐渐发展成为主 要的管理手段之一。而真正把项目作为一个系统来进行管理的是从曼哈顿原子弹 计划开始的。 1 1 2 项目管理 项目管理是以项目为对象的系统管理方法，通过一个临时性的专门的柔性组 织，对项目进行高效率的计划、组织、指导和控制，以实现项目全过程的动态管 理和项目目标的综合协调和优化【2 】。 所谓实现项目全过程的动态管理是指在项目的周期内，不断进行资源的配置 和协调，不断做出科学决策，从而使项目执行的全过程处于最佳运行状态，产生 最佳的效果。所谓项目的综合协调与优化是指项目管理应综合协调好时间、费用 及功能等约束性目标，在相对较短的时间内成功地达到一个特定成果性目标。 项目管理的基本职能主要有： 1 项目计划。项目计划就是根据项目目标( g o a l 确切的说要满足哪些要求) ， 对项目范围( p r o j e c ts c o p e ：记录在案的一系列客户确定成功完成的标准) 内的各 项活动做出合理安排。它包括两个阶段：( 1 ) 计划编制阶段。它包括对项目分解 为一系列任务( a c t i v i t y ：是- - d 部分耗费时间的工作，有着明确的起点和终点) 、 估计各任务的工期( d u r a t i o n ：一项任务从开始到结束所消耗的时间) 及完成任务 和项目所需的资源等。( 2 ) 调度阶段。确定各任务的开工期和完工期，并计算项 目在每一阶段所需的资源量。任何项目的管理都要从制定项目计划开始，项目的 成败首先取决于项目计划工作的质量。项目计划作为项目执行的法律，是项目中 各项工作开展的基础，是项目经理和项目工作人员的工作依据和行动指南。 2 项目组织。项目组织是指为进行项目管理、完成项目计划而进行的项目组 织机构的建立，组织运行与组织调整等。项目组织是实现项目计划、完成项目目 标的基础条件，组织的好坏对于能否取得项目成功具有直接的影响，只有在组织 合理化的基础上才谈得上其他方面的管理。 2 天津大学博士学位论文求解资源受限项目调度问题算法的研究 3 项目评价与控制。项目计划只是根据预测而对未来做出的安排，由于在编 制计划时难以预见的问题很多，因此在项目组织实施过程中往往会产生偏差。如 何识别偏差，消除偏差或调整计划，保证项目目标的实现，这就是项目管理的评 价与控制职能所要解决的。 一个成功的项目是在预算内满足客户需求按时完工的项目。然而拖延项目交 货期，超过预算，不能满足客户的需求的项目有很多。以信息系统开发项目为例， 国外一家大型咨询公司调查表明嗍，有2 5 的项目因无法继续而被取消，6 0 的 项目严重超支，7 5 的项目有严重的质量问题，只有少于1 的项目能保质保量 按期完成。对于一般的大型项目，延期4 0 - 2 0 0 也很普遍。而项目计划被认 为是造成项目失败的最普遍的原因之一。 1 2 项目调度及资源项目调度问题 项目计划中对多个任务，如何安排它们的执行顺序并给出各个任务的开始执 行时间的问题被称为项目调度问题。 2 0 世纪5 0 年代末发展起来的一种编制大型工程进度计划的有效方法：网络 计划技术【5 1 ，该技术是用网络计划对任务的工作进度进行安排和控制，以保证实 现预定目标的科学的计划管理技术。1 9 5 6 年美国杜邦公司在制定企业不同业务 部门的系统规划时，制定了第一套网络计划关键路径法( c r i t i c a l p a t h m e t h o d , c p m ) 。1 9 5 8 年美国海军在研究开发“北极星导弹计划”时使用了被称为计划 评审方法( p r o g r a m e v a l u a t i o n a n dr e v i e w t e c h n i q u e ，p e r t ) 的网络计划技术。在 这两种方法得到应用推广之后，又陆续出现了其他类型的网络计划技术，但其基 本原理与c p m p e r t 相似。六十年代，我国开始使用c p m 和p e r t ，并根据其 基本原理与计划的表达形式，称它们为网络技术或网络方法。下面将介绍网络计 划技术的有关知识。 1 2 1 网络计划技术 网络计划是在网络图上加注任务的时间参数等而编制成的调度计划。网络计 划主要由网络图和网络参数两大部分组成。网络图是由有向弧和节点组成的用来 表示任务流程的有向，有序的网状图形。网络参数是根据项目中各项任务的工期 和网络图所计算的各种时间参数。 网络计划技术的种类很多，但以每项任务的工期和逻辑关系来划分，可归纳 为四种类型，如表1 - 1 所示。 关键路径法( c p m ) 可以计算出项目各任务的最早、最晚开始和完工时间， 第一章绪论 通过最早时间和最晚时间的差额可以分析每一任务时间紧迫程度及重要程度。这 种最早和最迟时间的差额称为时差，时差为零的任务通常称为关键任务c p m 主要目的就是确定项目中的关键活动和关键线路，以保证项目实施过程中能抓住 主要矛盾，确保项目按期完成。计划评审技术( p e r t ) 是一种任务工期不确定 的网络计划图，其基本形式与c p m 网络计划基本相同。图形评审技术( g e r t ) 与c p m 法相比，该方法在网络逻辑和任务工期方面就有一定的概率陈述，即除 了任务工期的不确定外，还允许任务存在概率分支，一项任务的完成结果可能有 多种情况。风险评审技术( 弧t ) 可对项目的质量、时间、费用三坐标进行综 合仿真和决策。 表1 - 1 网络计划技术的分类 工期 类型 确定不确定 确定型关键路径法( c p m ) 计划评审技术( p e r t ) 逻辑关系 决策关键路径法( d c p m )图形评审技术( g e r t ) 不确定型 随即网络技术( q g e r t ) 风险评审技术( v e r t ) 1 2 1 1 网络图 网络图是由结点、边及权所构成的有向图。将项目的所有任务，按照它们之 间的相互关系和流程，用若干有向弧和结点从左向右绘制成的网状图即称网络 图。网络图分为双代号和单代号网络图两种。 1 双代号网络图。双代号网络图用一个有向弧代表一个任务，弧尾表示任务 的开始，弧首表示任务结束。每一项任务都存在这一个开始时刻和结束时刻。每 个任务要待紧前任务全部结束后，才有可能开始此项任务。网络图中第一个结点 称起始结点，代表项目的开始，最后一个结点称终止结点，代表项目的结束。 2 单代号网络图。单代号网络图与双代号网络图并无本质上的差别，仅是表 示方法不同。单代号网络图以结点表示任务，有向弧表示任务之间的逻辑关系。 有向弧的始点称为该弧终点的紧前节点，弧的终点称为该弧始点的紧后节点。由 于此图易画易读，本文采用单代号网络图。 1 2 1 2 网络计划时间参数计算 网络图的绘制仅完成了网络计划编制的第一项任务，更重要的任务是网络计 划时间参数的计算，这是网络计划实施、优化、调整的基础。 4 天津大学博士学位论文求解资源受限项目调度问题算法的研究 记胁表示活动f 的工期( 加工时间) ； e s 表示活动i 的最早开始时间； e f 表示活动i 的最早完工时间； 工s 表示活动i 的最晚开始时间； l f , 表示活动珀q 最晚完工时间； t s l a c k , 表示活动i 的总时差( 松弛时间) ； f s l a c k , 表示活动i 的单时差( 松弛时间) ； 1 活动工期的确定方法 活动工期的确定方法有两种： 确定型( 一点) 估计法。确定型估计是指对任务工期做出比较确定的估计， 只给出一个时间值。关键路径法( c p m ) 就是研究确定型时间的网络计划技术。 非确定型( 三点) 估计法。对于未知的和难以估计的因素较多的任务的工 期可给出彳、m 、口三个估计值。4 乐观时间，在顺利情况下，完成任务 所需的时间，其实现的可能性很小。肘最可能时间，在正常情况下，完成 任务所需要的时间。口悲观时间，在不顺利情况下，完成任务所需要的时间， 其实现的可能性也很小。完成任务所需要的上述三种时间都具有一定的概率。根 据经验，这些时间的概率分布可以认为近似于正态分布，按下列公式计算任务工 期的均值p 和方差仃 ( 1 - 1 ) f o ，；口：掣( 1 - 2 ) 这种工期估计方法主要用在计划评审技术( p e r t ) 中。 2 任务最早时间的计算 从网络图的起始结点开始，沿着有向弧，从左向右逐一确定各任务i 的最早 开始时间点s 和最早完成时间e 只，直到终止结点。若无规定起始结点的最早开 始时间为o ，即e $ 1 。- 0 。任务f 的最早开始时间计算公式为： e s t 吨蝌e s ，+ p 其中只为任务f 的所有紧前任务所组成的集合。 任务f 的最早完工时间计算公式为： e f , = z s , 岬 ( 1 - 3 ) ( 1 - 4 ) 第一章绪论 3 任务最晚时间的计算 从网络计划的终止结点开始，逆着有向弧的方向依次逐项计算。终止任务i ， 的最晚完工时间l b _ e e ，其它任务i 的最晚完工时间计算公式为： 明嘞 蜗叩， 其中s 为任务i 的所有紧后任务组成的集合。 任务i 的最晚开始时间为： l s 尸l f | - p , ( 1 5 ) ( 1 - 6 ) 4 任务松弛时间的计算 在不影响项目最早完工时间的条件下，任务i 最早开始( 或完工) 时间可以 推迟的时间，称为任务f 的总时差( 松弛时间) ，计算公式为： t s l a c k , = l f l e f , = e f i e s l ( 1 7 ) 在不影响紧后任务最早开始时间的条件下，任务i 最早完工时间可以推迟的 时间，称为任务i 的单时差，计算公式为： 毛哟 西一明 ( 1 - 8 ) 总时差为零的任务称为关键任务。从网络图起始结点开始到终止结点结束的一系 列依次联接的关键任务组成的路线称为关键路线。关键路线上的所有任务的工期 的累计等于项目总工期。一个网络图可以有多条关键路线，在计划执行过程中， 如关键任务提前完工或其他任务拖延时间超过其时差，则网络图中的关键路线可 能改变。任务总时差越大，表明该任务在网络中的机动时间越大，可以在一定范 围内将该任务的资源利用到关键任务上去，已达到缩短项目总工期的目的。 1 2 2 资源受限项目调度问题 1 2 2 1 资源受限项目调度问题的产生及描述 项目在执行过程中需要各种各样的资源，一般来说，资源的使用都是受限的， 因为在绝大多数项目中，资源本身是有限的或者获得额外资源的成本过高而不可 6 天津大学博士学位论文求解资源受限项目调度问题算法的研究 行。因此如何充分利用各种有限资源完成项目就成为项目管理过程中的一个重要 的问题。 p e r l c p m 作为项目管理非常有效的工具，被广泛应用于项目计划和控制过 程中，但是这两种方法在应用中忽略了对资源的限制，所以根据这两种方法编制 的计划在资源受限的情况下一般不能够得到保证，由此产生了资源受限项目调度 问题( r e s o u r c e - c o n s t r a i n c 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 是指项目中具有一系列相互关联的任务，其中，每一任务可以采用 几种模式完成，每一种模式以已知的工期和资源需求量为特征，此问题的解是在 满足时序和资源约束条件下产生一种使某种管理目标为最优的调度方案。r c p s p 在理论上属于n p - h a r d 问题【6 】，是一类重要的组合优化问题，是工程设计中最典 型的问题之一，该问题模型丰富，许多问题都是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 具有重要 的理论和现实意义。 1 2 2 2 资源受限项目调度问题的分类 在r c p s p 中，如果所有的数据在进行决策之前都是已知的，则称其为确定 性资源受限项目调度问题( d e t e r m i n i s t i cr e $ o u r o 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 p r o b l e m ) 。如果有的数据，例如任务的工期，准备时间和交货期等，在做决策时 是未知的，是一些随机变量，其分布是己知的，则称其为随机资源受限项目调度 问题( s t o c h a s t i cr 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 ) 。若数据在决策 时不是确定的，且分布也不能确定，但可以表示为模糊数，则称其为模糊资源受 限项目调度问题( f u z z 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 t s c h e d u l i n g p r o b l e m ，f r c p s p ) 。 下面我们主要讨论确定性资源受限项目调度问题的分类，随机、模糊r c p s p 的分类与确定性的分类是平行的。 资源，任务和目标函数三要素组成了资源受限项目调度问题。资源的不同数 量和类型、任务错综复杂的约束条件，再加上度量不同指标的目标函数，形成了 种类繁多的r c p s p 问题。在此采用机器排序的分类形式，用三个参数口p r 来 描述r c p s p 的类型【7 】。o 表示空集，可以省略。 1 参数口= 珥, a 2 3 表示资源的特性( r e s o u r c ee h a r a e t e r i s t i c s ) 。 参数磁 o ，m 描述资源种类数。 口，：o 表示排序中不考虑任何资源。 第一章绪论 强= m 表示有m 种资源。 参数 o ，1 ，r ，l r ，v 描述所使用资源的类型。 按照b l a z e w i c z 的分类方式【8 1 ，在项目调度中，资源可分为可更新资源、不 可更新资源和双重资源三种。可更新资源是指在每个时段获得一定量的资源，这 种资源的获得和消耗是以每一阶段为基础的( 如：机器、场地、设备和劳动力等) ； 不可更新资源是指在整个工期内只能获得一定量的资源( 如：原材料、能源等消 耗品) ；双重资源是指资源的获得和消耗既在工期的每一阶段受限，又在整个工 期的总量上受到限制。双重约束的资源分配问题可以被转化为相应的可更新资源 和不可更新资源来处理( 如：资金，当一个项目的投资总量为一定量时资金被看 作为不可更新资源，每个阶段运作的资金流看作为是可更新的资源) 。后来， $ c h i r m e r 和d r e x l 定义了一类新的资源部分可更新资源【9 l ，是指在某一特定 的时间内为可更新资源或不可更新资源。( 例如：在1 到5 的时间段内，此类资 源可看作不可更新资源，总量为5 个单元，在第六个时间段可用量为7 个单元， 在7 到9 时问段内可用量为0 个单元) 。 岛一表示资源类型缺省； 嘏- l 表示可更薪资源； = r 表示不可更新资源； t t 2 - - - - - 1 t 表示双重资源； = p 表示部分可更新资源。 参数= o ，懈 描述资源的使用量。 口，一表示( 部分) 可更新资源的使用量为常数； 口，= 啦表示( 部分) 可更新资源的使用量是变量。 2 参数脚，尻溉，屈，屈，展属描述任务的特性( 枷v 时c h a r a c t e r i s t i c s ) 。 参数a o ，p m t n ，p 研加呻眵 描述任务在加工时中断( p r e e m p t i o n ) 的可能性。 屈= o 表示任务在加工时不允许中断，直到完工为止； 屈= p m t n 表示任务在加工过程中可中断，然后在中断点处继续加工，任务中 断前后加工时间的总和与不中断的加工时间是一样的，此中断称为可续 性中断( p r e e m p t i o n - r e s u m e ) ； 崩= p m l n - r e p 表示任务加工过程中可中断，但不允许在中断点处继续加工， 必须从头开始，此中断被称为重复性中断( p r e e m p t - r e p e a t ) 。 参数尾。，c p m ，m i i l ，g p r ，p ，d 6 描述任务的时序( p r e c e d e n c e ) 约束。 如果要求任务_ ，完工后才能开始加工任务k ，我们称在这两个任务之间存在 时序约束，时序约束是种偏序关系。如果两个任务之间不存在时序约束，则称 为是独立的。时序约束可以用一个网络图表示。 8 天津大学博士学位论文求解资源受限项目调度问题算法的研究 尻一表示各任务独立，即任务之间无时序约束； 尻= c p m 表示各任务之间是无延误的完髓开始时序约束关系。 厦= r a i n 表示各任务具有最小延误时间的开始开始，完成一开始，开 始一完成和完成完成的时序约束关系； 屈弓矽表示任务间具有最小和最大延误时间的广义的时序约束关系； 注：最小延误时间是指只有在其紧前任务开始( 完成) 一段时间后该任务才 能开始( 完成) 。最大延误时间是指任务应该在另一任务开始( 完成) 后的某一 时间内开始( 完成) 。 反= p r o b 表示任务的网络图具有一定的概率，即允许任务存在概率分支。 参数尼o ，r j 描述任务的准备时间。 压一表示准备时间为0 ； 厉爿，表示各任务具有不同的准备时间。 参数质 o ，c o 雕 描述任务的工期。 反= o 表示任务的工期为离散的整数； 尻= c o n t 表示任务的工期为任意实数； 屈= d 表示各任务具有相同的工期。 参数屈= o ，艿，瓦 描述交货期。 展一表示无交货期； 屈笱，表示任务的交货期； 屈= 玩表示项目的交货期。 参数尻= o ，v r ，d 缸c ，c 0 耐 描述资源需求的特性。 反一表示任务在同一执行模式下所需资源为常数； 展- - - l r r 表示任务在同执行模式下所需资源为变量； 鼠- - d i s c 表示任务的资源需求量是任务工期的离散函数； 成= c o n t 表示任务的资源需求量是任务工期的连续函数。 参数岛 o ，m l f 代表任务的执行模式。 厉一表示任务只有一种执行模式( 或称单模式) ； 厉- - - m , 表示任务具有多种执行模式( 或称多模式) 。 3 参数，表示优化的目标。 在项目调度中，优化的目标函数可分为两类，一类为正则目标函数，这类目 标函数满足以下两个条件：( 1 ) 目标函数是求最小值；( 2 ) 目标函数是完工时间 的单调非降函数，例如：项目总工期最小、项目总成本最低、项目延误最小等。 另一类为非正则目标函数，例如：最大净现值、提前完工费用和误工费用最小等。 下面介绍几种目标函数： 第一章绪论 y = c e 表示最小项目总工期； y f t , 表示项目误i ( t a r d i n e s s ) 最小； ，铆，表示加权误工任务数最小； y = n p v 表示项目净现值最大； y = x _ b s 如v 表示资源需求量与平均量之差的绝对值总和最小。 需要指出的是对于没介绍或目前没有考虑到的资源类型、约束条件和度量指 标还可以加在口、和y 域中。此外在项目调度中一般只优化一个目标函数，即 单目标项目调度问题。目前，多目标决策问题在解决经济、管理、工程、军事和 社会领域中起着越来越重要的作用，因此有必要研究多个目标同时优化的项目调 度问题，此类问题称为多耳标项目调度问题。下面看几个例子： 模型m ，i i c p m l c 代表项目是单模式，任务加工时不允许出现中断，需要m 种 可再生资源，各任务之间的时序约束是无延误的完成开始关系，目标函数为 最小化项目总工期。此模型描述的问题通常被称为经典资源受限项目调度问题。 模型m ，1 l 印所，危i t 膨属于模糊r c p s p ，代表项目是单模式、带有模糊工期 和交货期，任务加工时不允许中断，需要历种可再生资源，各任务之间的时序约 束是无延误的完成开始关系，最小化调度健壮性( r o b u s t n e s sm e 嘲u 1 e 。r m ) 。 模型m , 1 , t l c p m ，搠甜l ( c 一，曲s 盔叻属于多目标r c p s p ，代表项目是多模式、 任务加工时不允许出现中断，需要m 种可再生资源和不可再生资源，各任务之间 的时序约束是无延误的完成开始关系，目标函数为任务总工期和资源需求量 与平均量之差的绝对值总和最小。 1 3 资源受限项目调度问题的研究现状 在上节r c p s p 的分类中可以看出，该问题模型丰富，且多属于n p h a r d 问 题，求解困难。此类问题的另一特点是适用某一模型的算法，只要将模型的条件 稍加变化，该算法将不再适用。从六十年代初至今，资源受限项目调度问题已吸 引了大量学者的注意，有很多公开发表的文章和专题论文从不同的角度研究该问 题，较好的综述有i l ”。本文的研究重点为脚，1 切i c _ ，m , l c p m ，d ，瓯l r m ， m ，1 ，t c p m , m u l ( c m ，e a b s a e v ) - - 个模型，下面主要将经典资源受限项目调度、模 糊资源受限项目调度和多目标资源受限项目调度问题的研究现状做一介绍。 1 3 1 经典资源受限项目调度问题的研究现状 用于求解经典资源受限项目调度问题的算法有两大类：精确类算法和启发式 算法。精确类算法主要有0 1 规划方法【1 6 1 1 7 ，隐含枚举的分支定界【1 8 洲等，精确类 1 0 天津大学博士学位论文求解资源受限项目调度问题算法的研究 算法的研究主要集中在分支定界方法上。由于此问题属于n p - h a r d 问题，精确类 算法对于中小规模的项目可取得最优解，但对于超过6 0 个任务的项目此类算法则 无法实施。 自从k e f i e y 提出调度产生方案( s c h e d u l eg e n e r a t i o ns c h e m e , s g s ) 2 5 1 的概念 后，各种不同的启发式算法相继被提了出来。对于大规模的项目来说，启发式算 法虽然不能保证求得最优解，但计算速度快，可以在计算质量和计算效率上取得 很好的平衡。启发式算法主要包括基于优先规则的简单算法 2 6 - 4 6 1 ，分离弧 ( d i s j u n c t i v ea c s ) 概念【4 刀，局部搜索技术嗍，智能优算法( m e t a h e u r i s t i c s ) 【4 9 】等。 基于优先规则的简单启发式算法由两个要素组成：调度产生方案和优先规 则。根据调用调度产生方案的次数将其分为一次调用方法和多次调用方法。 首先用于求解精典r c p s p 的启发式算法是一次调用方法，该方法只采用一 次调度产生方案和一个优先规则，产生一个调度。目前，研究者们针对经典r c p s p 定义了多种多样的优先规则卿司，较好的优先规则有资源调度方法m ) 【2 司；最 晚完成时间( l f l ) 鲫；最小松弛时间o “s l k ) 唧；最短加工时间( s p l ) 口2 1 ；最高排 列位置权重( g i 冲w ) f 3 2 】；最多紧后工作数o 讧t s ) 口2 】；最晚开始时间s d 田1 ； 最 坏情况下的松弛时间( w c s ) p 习；基于局部约束分析( l c b a ) 网。 多次调用方法是多次调用调度产生方案，产生多个调度，从中选择结果好的 调度作为最优调度。b o c t o r 3 8 】采用多次调用方法，每次使用不同的优先规则，最 后选择其中的最好解作为调度计划：l i 等 3 9 1 和0 z d 锄盯等 4 0 1 采用向前向后回溯 法求解经典r c p s p ，此方法多次调用一种调度产生方案和一个优先规则，交替 使用向前和向后排序的方法产生调度直到项目的总工期不再降低时算法停止； a l v a r e z - v a l d e s 等【4