（计算机软件与理论专业论文）改进的蚁群算法求解资源受限项目调度问题.pdf

中山大学硕卜学位论文 改进的蚁群算法求解资源受限项目调度问题 专业 计算机软件与理论 硕士生 周玉苗 指导教师 郭清顺研究员 摘要 随着经济的发展 项目管理变得越来越重要 项目调度作为项目管理的重要 组成部分 具有网络结构特点 各个项目成员分布在网络的节点上 负责整个项 目的一项或几项工作 拥有各自的资源或者共享某些公共资源 项目成员的共同 目标是快速响应市场 以获得最大经济效益 因此 资源受限项目调度问题成为 了研究的热点 研究如何在满足项目时序约束和资源约束的条件下 安排所有活 动的开工期和完工期 以达到最优的目标 如工期最短 成本最小等 该问题已 被证明是n p h a r d 问题 本文的核心部分是用改进的蚁群算法求解r c p s p 在前人研究的基础上 提 出了两点改进意见 一是基于任务序列关系的局部搜索机制 可以直接用于改善 r c p s p 的解 二是提出优先规则池 作为启发信息 综合运用优先规则的优势 本文的主要内容如下 首先 对r c p s p 的国内外研究现状以及主要研究算 法进行了归纳总结 接着 简要介绍了a c o 的产生 发展以及改进算法 给出 了a c o 求解典型r c p s p 的流程图 然后 基于调度问题的性质和r c p s p 本身 的特点 提出了基于活动序列的局部搜索机制 基于优先规则池的启发信息两点 改进方案 随后 设计了改进的a c o 求解r c p s p 的实验 验证了提出的改进方 案是可行的 有效的 并对实验参数和结果进行了详细的分析 最后 对r c p s p 的前景和进一步研究方向进行了展望 关键词 资源受限项目调度 局部搜索机制 优先规则池 中山人学硕上学位论文 i m p r o v e da c oa l g o r i t h m f o rr 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 gp r o b l e m m a j o r c o m p u t e rs o f t w a r ea n dt h e o r y n a m e y u m i a oz h o n s u p e r v i s o r p r o f e s s o rq i n g s h u ng u o a b s t r a c t w i t ht h ed e v e l o p m e n to f e c o n o m y p r o j e c tm a n a g e m e n ti sb e c o m i n gi n c r e a s i n g l y i m p o r t a n t a sa ni m p o r t a n tp a r to fp r o j e c tm a n a g e m e n t p r o j e c ts c h e d u l i n gh a st h e c h a r a c t e r i s t i cc a l l e dn e t w o r ks t r u c t u r e p r o j e c tm e m b e r sw h oa r ed i s t r i b u t e do nt h e n o d e so fn e ts t r u c t u r et a k ec h a r g eo fo n eo rm o r eo ft h ew o r k a n dp o s s e st h e i ro w n r e s o u r c e so rs o m ek i n d so fc o m m o nr e s o u r c e si no r d e rt og a i nm a x i m u mb e n e f i t s t h e r e f o r e 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 h a sb e c o m ea r e s e a r c hf o c u sw h i c hs t u d i e sh o wt op l a nt h es t a r tt i m eo fa l la c t i v i t i e sa n da c h i e v et h e o p t i m a lg o a l s u c ha st h es h o r t e s tp e r i o do rt h es m a l l e s tc o s t u n d e rt h ec o n d i t i o no f t h et i m i n gc o n s t r a i n t sa n dr e s o u r c ec o n s t r a i n t s r c p s ph a sb e e np r o v e dt ob ea n p h a r dp r o b l e m t h ec o r ec o n t e n to ft h i sa r t i c l ei si m p r o v i n ga n tc o l o n ya l g o r i t h mt os o l v er c p s e a c c o r d i n gt op r e v i o u ss t u d i e s t w op o i n t so fi m p r o v e m e n tw e r em a d ea sf o l l o w s f i r s t l y t h el o c a ls e a r c hm e c h a n i s m b a s e do np r e c e d e n c er e l a t i o n s h i p c o u l db e d i r e c t l yu s e dt oi m p r o v et h er c p s ps o l u t i o n s e c o n d l y a sh e u r i s t i ci n f o r m a t i o n 面o n t y r u l e sp o o li n t e g r a t e dt h ea d v a n t a g eo fa l lp r i o r i t yr u l e sc o m p r e h e n s i v e l y n em a i nc o n t e n t so ft h i sp a p e ra r ei n t r o d u c e da sf o l l o w s f i r s t l y t h i sp a p e r g e n e r a l i z e dr e s e a r c ha n dm a i na l g o r i t h m sa th o m ea n da b r o a df o rt h er c p s et h e n i n t r o d u c e dt h ee m e r g e n c e d e v e l o p m e n ta n di m p r o v e da l g o r i t h mo ft h ea c o b r i e f l y a n dg a v et h ef l o wc h a r to ft h ea c of o rt h et y p i c a lr c p s p a f t e rt h a t a c c o r d i n gt o c h a r a c t e r i s t i c so ft h es c h e d u l i n gp r o b l e ma n dr c p s p i t s e l f t h i sp a p e rp r o p o s e dl o c a l i i i 改进蚁群算法求解资源受限项k l 调度问题 s e a r c hm e c h a n i s mb a s e do np r e c e d e n c er e l a t i o n sa n dp r i o r i t yr u l ep o o la sh e u r i s t i c i n f o r m a t i o n n e x t i td i dad e t a i l e da n a l y s i so ft h ep a r a m e t e r sa n dt h er e s u l t s a n dt h e e x p e r i m e n t a lr e s u l t ss h o w e dt h ei m p r o v e m e n ta b o v ew a sf e a s i b l ea n de f f e c t i v e f i n a l l y t h i sp a p e rp o i n t e dp r o s p e c ta n df u r t h e rr e s e a r c hd i r e c t i o n so fr c p s p 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 l o c a ls e a r c hm e c h a n i s m p r i o r i t yr u l e sp o o l i v 学位论文原创性声明 本人郑重声明 所呈交的学位论文 是本人在导师的指导下 独 立进行研究工作所取得的成果 除文中已经注明引用的内容外 本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果 对本文 的研究做出重要贡献的个人和集体 均已在文中以明确方式标明 本 人完全意识到本声明的法律结果由本人承担 学位论文作者签名 j 封玉萄 日期 汤 年5 月 日 学位论文使用授权声明 本人完全了解中山大学有关保留 使用学位论文的规定 即 学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版 有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆 院系资料室被查阅 有权将学位论文的内容编入 有关数据库进行检索 可以采用复印 缩印或其他方法保存学位论文 学位论文作孝签名 ij 司王萄 i v v 导师签名 印哆rf 久 日期 刀呷年5 月 日 中i b 人学硕l 二学位论文 第1 章引言 1 1项目管理和项目调度 1 1 1项目管理 随着社会经济的不断发展 企业面临着越来越大的生存 发展压力 企业必 须开展各种技术 管理 体制等创新活动 以适应激烈的市场竞争 管理方法的 改进是企业在市场竞争中立于不败之地的一个关键 而当今的管理越来越具有项 目的特质 项目管理无论在理论研究上还是在管理实践上都已成为人们关注的焦 点 项目管理是以项目为对象的系统管理方法 通过一个临时性的专门的柔性组 织 对项目进行高效率的计划 组织 指导和控制 以实现项目全过程的动态管 理和项目目标的综合协调和优化 n 项目管理的基本职能主要有 1 项目计划 项目计划就是根据项目目标 对项目范围内的各项活动做 出合理安排 它包括两个阶段 计划编制阶段 对项目分解为一系列活动 制定 各活动的工期及所需的资源等 调度阶段 根据各活动的工期约束和资源约束 安排活动的开工期和完工期 并计算出整个项目的总工期和总资源需求量 任何 项目的管理都要从制定项目计划开始 项目计划是项目中各项工作开展的基础 2 项目组织 项目组织是指为进行项目管理 完成项目计划而进行的项 目组织机构的建立 组织运行与组织调整等 项目组织在项目开展过程中 履行 协调 监督的职责 组织的好坏对项目能否按项目计划按时完成具有直接的影响 只有在组织合理化的基础上其他方面的管理才能顺利开展 3 项目评价与控制 项目计划只是对未来做出的安排 没有考虑到项目 进行过程中出现难以预见的问题 因此在项目组织实施过程中往往会产生偏差 项目评价就是对项目的进展情况进行实时跟踪 评估执行进度和资源使用率 以 及给出风险分析 根据项目评价的结果调整计划 保证项目目标的实现 一个成功的项目是在不超支的情况下按时完成且达到客户要求的项目 然而 1 改进蚁群算法求解资源受限项目调度问题 拖延项目工期 超过预算的项目有很多 以信息系统开发项目为例 国外一家大 型咨询公司调查表明1 2 有2 5 的项目因无法继续而被取消 6 0 的项目严重超 支 7 5 的项目有严重的质量问题 只有少于1 的项目能保质保量按期完成 对于一般的大型项目 延期4 0 2 0 0 也很普遍 而项目计划被认为是造成项 目失败的最普遍的原因之一 1 1 2项目调度 项目调度属于项目计划的制定过程 项目调度就是为项目中的每个活动分配 资源以及确定开始时间 在项目管理的发展过程中 有几种经典的项目调度方法 如关键路径法 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 na n dr e v i e w t e c h n i q u e p e r t 在本文中 使用c p m 计算项目中每个活动的最早 最迟开始 时间和最早 最迟完成时间 下面简要介绍关键路径法和计划评审技术这两种方 法 关键路径法的基本原理是通过计算各个活动的重要程度 优先处理重要程度 高的活动 首先 根据各活动工期和活动间的逻辑关系计算出活动的最早 最迟 开始时间和最早 最迟完工时间 然后计算最早时间和最晚时问的差额 这个差 额反映了活动的重要程度 差额为零的活动即为关键活动 将关键活动依次连接 起来 就得到了关键路径 进而得到了项目从开始至结束的过程中不能延迟执行 的一系列活动 从而保证在项目执行过程中有效的控制项目进度 在关键路径法中每个活动的工期是确定的 而计划评审技术解决的是活动工 期不确定的情况 该方法的主要思想是对项目中的每个活动估计三个时间 分别 为乐观时间a o p t i m i s t i ct i m e 最可能时间m m o s tl i k e l yt i m e 和悲观时间 b p e s s i m i s t i ct i m e 这些时问的概率分布可以近似为正态分布 按下列公式计 算活动工期的均值夕和方差盯 a 4m bp 1 1 一 ll l 6 疗2 b a i 2 盯2 百 l 2 中山人学硕 f 学位论文 计划评审技术使用与关键路径法相同的调度方法 1 1 3资源受限项目调度 关键路径法和计划评审技术法虽然广泛应用于各种项目调度中 但这两种方 法忽略了项目中资源的限制 因而对资源受限项目调度问题不能取得很好的结 果 在企业生产制造过程中 资源的种类和数量是有限的 企业必须合理安排活 动的先后顺序 使得项目在满足资源约束的条件下能够尽早完成 因此 为了让 项目调度更加接近实际情况 便产生了资源受限项目调度问题 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 资源受限项目调度问题 涉及一系列的具体活动 a c t i v i t i e s 与一个有限的资 源 r e s o u r c e s 集合 这些活动之问存在序列上的约束关系 同时每项活动需要特 定数量的一种或几种资源 项目调度就是要合理分配这些资源 安排这些活动的 先后顺序 从而实现项目目标如工期最小化 费用最小化 资源均衡等 资源受 限项目调度问题将在第二章详细介绍 1 2本文研究的目的和意义 近年来兴起的全球制造方式经常要求多家企业合作以获得最大的竞争力 这 种组织结构和管理模式越来越趋向于面向项目的方式 项目调度过程越来越具有 网络结构特点 各个项目成员分布在网络的节点上 负责整个项目的一项或几项 工作 拥有各自的资源或者共享某些公共资源 项目成员的共同目标是快速响应 市场 以获得最大经济效益 因此 资源受限的项目调度问题在现代化企业中显 示出越来越重要的研究价值 求解资源受限项目调度问题的主要算法大致有三类 精确算法 启发式算法 以及人工智能算法 随着经济的发展 项目的规模越来越大 使用的资源的种类 越来越多 精确算法已不能在可接受的时间内求得解 启发式算法虽然能够在有 限的时间里求得问题的解 却无法保证是否为最优解 人工智能算法在求解复杂 的大规模问题方面本身具有优势 蚁群算法在求解离散性组合优化问题优于其它 智能算法 因此用蚁群算法求解资源约束项目调度问题受到了一些学者的关注 并进行研究和实验 验证了蚁群算法具有一定程度的优越性 3 改进蚁群算法求解资源受限项目调度问题 本文在研究了近几年的相关文献后 针对以前文献中存在的缺陷 提出了两 点改进方案 并通过实验验证了改进方案的有效性 本文在用蚁群算法求解资源 受限项目调度问题方面做出了一定贡献 并且一些改进方案可应用于一般的调度 问题 为其它学者的研究工作提供了一定的借鉴和参考 1 3 本文研究的主要内容 本文在蚁群算法求解r c p s p 的模型上 提出了两点改进方案 并通过实验验 证了改进方案的可行性和有效性 本文的主要内容包括 首先 给出了r c p s p 的概念和数学模型 对r c p s p 的国内外研究现状进行了 归纳综述 分析了目前主要的研究算法 其二 简要介绍了a c o 的产生 发展以及当前几种主要的改进算法 给出了 a c o 求解典型r c p s p 的流程图 其三 基于调度问题的性质和r c p s p 本身的特点 针对以往文献中不足 在 a c o 上提出了基于活动序列关系的局部搜索机制 优先规则池两点改进方案 其四 通过设计改进的a c o 求解r c p s p 的实验 验证了实验的可行性和有效 性 并对实验结果进行了分析 证明了实验比以往仿真算法求解r c p s p 在不同程 度上有所提高 在本文的最后对r c p s p 的前景和研究方向做了进一步的展望 本文主要分为6 章 相关的章节主题如下 第1 章介绍了项目管理等基本概念以及本文研究的目的和意义 阐述了本文 的组织结构 第2 章给出了r c p s p 数学模型 总结了r c p s p 国内外的研究现状和主要算法 第3 章简要介绍了a c o 的发展历史 给出了a c o 求解r c p s p 的流程图 并指 出了以往文献中存在的不足 第4 章针对第3 章指出的不足 结合调度问题和r c p s p 的本身特点 提出了两 点改进方案 第5 章设计实验 将改进方案应用于a c o 求解r c p s p 中 验证了算法的有效 性 分析了参数性能和实验结果 第6 章对全文进行了总结和展望 并讨论了进一步的研究工作 4 中山人学硕上学位论文 第2 章资源受限项目调度问题的研究现状 本章介绍了资源受限项目调度问题的研究现状 2 1 节详细介绍了经典资源受 限项目调度问题的数学模型 2 2 节介绍了资源受限项目调度问题的主要算法 包括精确算法 启发式算法和元启发式算法 并且总结了资源受限项目调度问题 的国内外研究现状 2 1资源受限项目调度问题的数学模型 经典的资源受限项目调度问题研究如何在满足活动间的序列关系和资源约 束的前提下 将有限的资源分配给各个活动 确定活动的实际开始时间 从而使 项目工期最短 资源约束项目调度问题在理论上属于n p h a r d l h j 题 3 1 是一类重 要的组合优化问题 是工程设计中最典型的问题之一 2 1 1 项目网络图 本文采用a o n a c t i v i t yo i ln o d e 网络图来表示项目中活动之间的逻辑关系 在a o n 图中 每个节点表示一个活动 活动间的逻辑关系用带箭头的弧线表示 不允许出现循环 为了便于调度 a o n 规定 编号小的活动可以是编号大的活 动的前序活动 p r e c e d i n ga c t i v i t y 但不可以是其后序活动 s u c c e e d i n ga c t i v i t y 图2 一la o n 图 在图2 1 中 活动1 是唯一最早开始的活动 活动8 是唯一最晚完成的活动 均 为不消耗任何资源且执行时间为0 的虚拟活动 且分别代表整个项目的开始活动 和结束活动 s 改进蚁群算法求解资源受限项目调度问题 2 1 2目标函数 项目调度问题的目标函数一般分为两类 一类是常规目标函数 r e g u l a r o b j e c t i v ef u n c t i o n 如最小化项目总工期及最小化项目总成本 这类目标函数 通常可以通过提前活动的开始时间达到 另一类是非常规目标函数 n o r e g u l a r o b j e c t i v ef u n c t i o n 如最大化净观值 n e tp r e s e n tv a l u e 通过提前活动的开始 时间 可能无助于这类目标函数的实现 资源受限项目调度问题一些常见的目标 函数列于表2 1 具体参数意义可参考相应文献 表2 1 常见目标函数表 目标名称文献目标值计算方法 最小项目工期s l o w i n s k i 4 m i n ff 厶 x j t 最小平均延迟s l o w i n s k i t 4 m i n 了1 f d f 协 最小延期任务数 s p r e c h e r l 5 m i n z 声 最大净观值 s p r e c h e r 5 m a x p z 最小平均加权时间 s p r e c h e r 5 m i n t x f l 最小加权延迟v i a n a s o u s a l 6 m i n v t d t 却 不同的目标函数 要求有不同的项目调度方式 由于有较多的目标函数 学 者们在研究资源受限项目调度问题上形成了单目标优化问题和多目标优化问题 本文的研究内容属于单目标优化问题 目标函数是最小化项目总工期 2 1 3约束条件 经典r c p s p 主要涉及到三类约束 一类是活动之间存在的逻辑约束 p r e c e d e n c er e l a t i o n s 一类是有限资源造成的资源约束 r e s o u r c ec o n s t r a i n t s 另一类是时间约束 t e m p o r a lc o n s t r a i n t s 活动之间的关系不只包括紧前关系约束 还有时间约束 即限定活动在特定 时间区域或者特定时间点启动 即活动可能在其所有紧前活动完成后 不能马上 6 中山人学硕上学位论文 开始 在本文中 不考虑时间约束的情况 即一个活动的所有紧前活动结束后 该活动可以立即开始 项目资源可分为三类 可更新资源 不可更新资源和双重限制资源 可更新 资源在项目整个过程中总量保持不变 不会随着项目的进展而消耗 活动完成后 会释放该类资源 如场地 机器等 不可更新资源在项目开始前给定的总量固 定 但是会随着项目的进展而越来越少 如原材料 能源等 双重限制资源在 项目整个过程中有总量的限制 在活动执行期间也有量的限制 如资金 在本 文中 只考虑可更新的资源 即资源随一个活动的完成而被释放 其它活动可以 再次使用该资源 在项目调度的实际过程中 由于资源的限制 活动被中断的情况经常出现 等到资源满足要求后 活动又继续执行 活动被允许中断使得项目调度的灵活性 增加 可以更有效的优化项目目标 但是这类问题的算法复杂性也急剧增加 在 本文中 活动被要求一次性执行完 不允许出现中断后再次执行的情况 在经典的资源约束项目调度问题中 活动的工期都是固定的 而在实际情况 中活动的工期可能与其它因素有关 具有不确定性 在前文中 采用p e r t 的三 点时间估计对不确定工期进行处理 在本文中 不考虑活动工期不确定的情况 2 1 4资源约束项目调度的数学模型 r c p s p 问题的数学模型所需符号如下表所示 7 改进蚁群算法求解资源受限项目调度问题 表2 2 经典r c p s p 符号表 符号说明 l活动序号 歹 j 2 3 其中助项目所含活动的总数量 t时间序号 t o 1 2 乃其中确项目工期上限 后资源序号 k 1 2 3 k 其中肭项目所需可更新资源种类数 d j活劫的工期 pi活动 的紧前活动集合 sj活劫的紧后活动集合 s t j活劫的开始时间 c t y活劫的结束时问 it在时n t 处于执行状态的活动集合 r项目需要可更新资源集合 r j 活动 所需要的可更新资源集合 七 资源k 的供给量 在任何时刻 项目对资源k 的总需求不超过 k 活动 所需要的资源k 的数量r j 则r c p s p 数学模型可是描述为 m m c t j 2 1 s f c t s t v h p j 2 2 一 v 后 r t 0 2 3 其中 公式 2 1 表示活动 项目的虚拟结束活动 的开始时间最短 即目 标函数为总工期最小 公式 2 2 表示活动 的所有紧前活动的完成时间小于 的开始时间 即活动之间满足序列约束关系 公式 2 3 表示在 的时间区域 内 所有正在执行的活动使用的某类资源的总和不大于该类资源的总量 即活动 8 中山人学硕 i 学位论文 之问满足资源约束关系 2 2资源受限项目调度问题的算法综述 用于求解资源受限项目调度问题大致分为三类 精确算法 启发式算法和元 启发式算法 智能优化算法 2 2 1精确算法 精确算法主要有0 一l 规划方法穷举法 分支限界法 动态规划法等 这类算 法的优点在于只要有足够的时间 就可以得到精确解 然而在可接受的时间范围 内 只能处理小规模问题 对于超过6 0 个活动的项目此类算法则无法实施 2 2 2启发式算法 启发式算法是基于一定的启发式规则 给出待解决的组合优化问题的一个可 行解 可行解不一定是最优解 往往与最优解之间存在偏差 但是这种算法的速 度快 能在较短的时间得到质量可接受的解 因此启发式算法自从产生以来就得 到了大量的研究 从广义上说 启发式算法包括基于优先规则的启发式算法 局 部搜索技术 元启发式算法等 基于优先规则的启发式算法是求解r c p s p 的一 类最为重要的算法 是本节介绍的重点 基于优先规则的启发式算法由两个要素组成 优先规则 p r i o r i t yr u l e p r 和进度生成机制m 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 该类算法凭借进度生成 机制从可安排活动集合中选择活动 逐步扩展局部进度计划 生成一个完整的可 行性调度方案 优先规则用于在进度生成的过程中赋予每个活动一定的优先权 算法根据每个活动的优先权决定活动的选择顺序 1 进度生成机制 广泛应用的进度生成机制有两类f 8 以活动为阶段变量的串行进度生成机制 s e r i a ls c h e d u l eg e n e r a t i o ns c h e m e s s g s 和以时间为阶段变量的并行进度生成 机制 p a r a l l e ls c h e d u l eg e n e r a t i o ns c h e m e p s g s 进度生成机制是启发式算法 包括元启发式算法的重要组成部分 进度生成机制将活动分为三类集合 已安排活动集 可行性活动集和非可行 9 改进蚁群算法求解资源受限项h 调度问题 性活动集 已安排活动集是指在开始时间已经被确定的活动集合 可行性活动集 是指其紧前活动已经全部安排 同时满足资源约束条件的活动集合 非可行性活 动集是除了已安排活动集和可行性活动集之外的活动集合 串行进度生成机制包含 个阶段 在每个阶段j 铲j z j 中 从可行性活 动集中根据优先规则选择一个活动 确定活动的最早开始时间且将它添加到已安 排活动集中 然后重新确定可行性活动集 开始下一个阶段 直到所有的活动被 安排为止 k o l i s h t 8 1 已证明采用串行进度生成机制产生的调度计划为活动调度 a c t i v es c h e d u l e 对于具有正规目标函数的r c p s p 其最优调度一定为活动 调度 并行调度产生方案最多包含j 个阶段 在每个阶段中 对应一个调度时间t 从可行性活动集中依次安排每个活动 加入到已安排活动集中 直到可行性活动 集为空 根据已安排活动集合确定下一个调度时问t 和可行性活动集 进行调度 直到所有的活动被安排为止 k o l i s c h t 8 1 已证明并行调度产生方案生成非延迟调 度 在一个非延迟调度中 即使活动在执行过程中允许被中断 不存在不需要延 迟其他活动而可以提前开工的活动 非延迟调度的集合是串行调度集合的子集 因此并行调度产生方案有丢失最优解的可能 2 优先规则 在产生可行调度的过程中 需用根据优先规则来确定可行性活动集中活动的 调度序列 目前己有许多学者提出了各种优先规则 各自有不同的性能和适应领 域 一些常用的启发规则列于下表 中山人学硕 f 学位论文 表2 3 求解经典r c p s p 的优先规则 优先规则名称选择方法计算方法 最迟完成时间 9 l f t m i n l f j 最迟开始时间1 9 1 l s t m i n l s j 最小松弛时间 1 0 m s l m i n l s j e s j 最多紧后活动 1 1 1 m t s m a x ls l 最大分级位置权重 11 g r p w a m a x p j 啄 p 加权资源用量及紧前关系 1 2 w r u p m a x 国i s j l 卜缈 l e 8 华r i 最短加工时剐1 1 1 s p t m i n d 确定了进度生成机制和优先规则后 就可以确定一个调度方案 根据每次迭 代中使用优先规则的个数 基于优先规则的启发式算法可以分为单路算法 s i n g l e p a s sm e t h o d 和多路算法 m u l t i p a s sm e t h o d 单路算法在每次进行活 动选择时 调用某一种启发规则进行判断 多路算法就是多次调用调度方案 生 成多个调度 从中选择最好的调度方案 多路算法又可分为多优先规则法 正向 逆向调度法 抽样法 多优先规则法就是重复进行多次调度 每次选用一种优先规则 最后选择最 好的解作为调度计划 多优先规则法实际上是单路算法的一种扩展 和w i l l i s u 3 将正向进度生成机制 f o r w a r ds c h e d u l i n g f s 和逆向进度生 成机制 b a c k w a r ds c h e d u l i n g b s 结合起来 并形成了正向逆向调度算法 f o r w a r d b a c k w a r ds c h e d u l i n g f b s 该方法交替使用正向 逆向调度 直到 项目的总工期不再降低算法才停止 k l e i n t l 4 1 在正向逆向调度算法的基础上 提 出了双向进度生成机制 从两个方向同时进行正向和逆向调度 与适应不同调度 方向的优先规则形成了较好的匹配 k o l i s c h 等 综合比较了各种算法 发现许 多算法应用了正向逆向调度后都取得了很好的效果 抽样法从进度生成机制和优先规则中各选一种 在调度过程中不直接使用优 改进蚁群算法求解资源受限项目调度问题 先规则值 而是根据优先规则值计算各个活动被选择的概率 根据概率值选择要 安排的活动 根据概率计算方法不同 抽样法主要有随机抽样 l6 r a n d o m s a m p l i n g r s 基于偏好的随机抽样 1 8 b i a s e dr a n d o ms a m p l i n g b r s 和基于 后悔值带有偏好的随机抽样 汐2 0 r e g r e tb a s e db i a s e dr a n d o ms a m p l i n g p b r s 在随机抽样中 可行性活动集中的每个活动赋予相同的抽样概率 基于偏好的随 机抽样是根据优先规则值计算概率 基于后悔值带有偏好的随机抽样则是首先计 算活动的后悔值 然后根据后悔值计算活动被选择的概率 基于优先规则的启发式算法虽然能够较快地得到问题的解 但是无法保证解 是最优解 在这些算法中 尽管在理论上多路算法一般优于单路算法 但是由于 算法结构 变成语言 测试算例不同 目前无法对它们的优劣做出决定的判断 2 2 3元启发式算法 元启发式算法近几年来在求解r c p s p 方面得到了迅速的发展并取得了良好的 效果 元启发式算法不直接使用优先规则 而是用改进的启发式规则和搜索方式 求得r c p s p 的解 用于求解r c p s p 常用的元启发式算法有遗传算法 g e n e t i c a l g o r i t h m g a 模拟退火算法 s i m u l a t e da n n e a l i n g s a 禁忌算法 t a b u s e a r c h t s 及蚁群算法 a n tc o l o n ya l g o r i t h m a c a 遗传算法由h o l l a i l d f 2 l 于1 9 7 5 年提出 它借鉴了生物界的优胜劣汰法则 通 过一定的编码机制生成初始种群 然后在初始种群的基础上进行一系列的交叉 变异操作 生成新解 在新解生成后 适应度最高的解保留下来构成下一代 其 余的解通过选择机制被淘汰 从而使得解的质量不断提高 h a r t r n a n t 2 2 提出基于 活动列表表示法的遗传算法 采用串行进度生成机制和两个交叉算子 效果优于 基于随机键和优先规则表示法的遗传算法 a l c a r a z 和m a r o t 0 2 3 提出了一种基于 活动列表表示法和串行进度生成机制的遗传算法 该算法采用了双向调度机制 逆向调度是否进行由一个基因决定 随后 他们在2 0 0 4 年改进了上面提出的算 法 2 4 1 在原来双向调度机制上 他们采纳了h a r t i l l 锄 2 5 提出的自适应遗传算法 中决定进度生成机制选择的基因 k i m 2 6 提出了带有模糊控制机制的混合遗传算 法 加快了遗传算法的收敛速度 l i n y ut s e n g 2 7 提出了一种名为a n g e l 的混 合算法 该算法通过a c o 提供初始解和活动列表 用g a 在此基础上寻找更优 中山人学顾 t 学位论文 的解 在搜索过程中运用了局部搜索j o l n 在国内学者的研究方面 刘士新等 2 s 提出了基于精英策略的遗传算法 用于求解资源受限项目调度问题 模拟退火算法从某个初始解开始 通过对当前解的扩展来生成i 临点 如果临 点优于当前解则被接收 否则以一定的概率被接收 随着算法的进行 温度被逐 步降低以减少接收差的临点的概率 当达到规定的温度后算法终止 此时固定下 来的解为满意解 b o c t o r 2 9 l 首次尝试用模拟退火算法解决经典r c p s p 该方法基 于活动链表编码 采用串行进度生成机制 领域函数采用插入式 c h o 和k i m 3 0 采用模拟退火算法解决r c p s p 采用并行进度生成机制 改进了优先规则值的 编码机制 允许优先规则值为负 b o u l e i m e n 和l e c o c q 3 1 提出了一种平移算子的 模拟退火算法求解r c p s p 采用了串行进度生成机制 每个冷却链从不同初始 解开始搜索 初始解由基于优先规则的启发式算法求得 v a l l s 3 2 l 提出一种基于 正向逆向调度和基于偏好的随机抽样的模拟退火算法解决r c p s p 禁忌搜索从所有邻点解中选择最好的一个进行进一步的搜索 为了避免搜索 返回刚刚离开的局部最优点而形成的循环 通过建立一个禁忌列表来限制向某些 邻点的移动 b a a r 等人 3 3 提出了基于调度计划表示法和动态禁忌列表的禁忌算 法求解r c p s p 初始解通过基于优先规则的启发式算法求得 t h o m a s 和s a l h i t s 4 1 在禁忌算法中采用直接作用于调度方案的算子 通过基于三种移动方式的修复程 序将不可行的调度方案转变为可行的调度方案 a r t i g u e s 等人 3 5 将插入技术应用 于禁忌算法 把第一个被抛弃的解用基于网络流的算法计算后重新插入 蚁群算法求解r c p s p 问题的研究现状 将在3 5 节中详细介绍 关于求解r c p s p 的元启发式算法 从学者们所给的测试结果可以大致得到 如下结论 元启发式算法总体上好于基于优先规则的启发式算法 而在元启发式 算法 s a g a a c 算法的性能较好 从目前的研究来看 g a 2 3 1 算法的整体性 能比s a 3 1 好 自适应g a 2 7 比g a 2 3 好 1 3 中山人学硕 学位论文 第3 章蚁群算法求解r c p s p 本章主要内容包括蚁群算法的发展历史以及蚁群算法求解经典r c p s p 的流 程图 3 1 节介绍了蚁群算法的产生和发展 3 2 节介绍了蚁群算法的数学模型和 流程图 3 3 节对几种成功的改进的蚁群算法进行了简单的介绍 3 4 节给出了蚁 群算法求解r c p s p 的流程图 3 5 节概述了蚁群算法求解r c p s p 的研究现状以及 存在的问题 3 1蚁群算法的产生与发展 3 1 1双桥实验 昆虫学家发现 自然界的蚂蚁虽然视觉不发达 但是它可以在没有任何提示 的情况下找到巢穴到食物源的最短路径 并且能够在环境发生变化后 自适应地 搜索新的最佳路径 为了研究蚂蚁群体觅食行为的特征 d e n e u b o u r g 掣3 6 1 设计了一种双桥实验 双桥的首尾分别连接了蚁穴和食物源 他们在实验中测试了长度相同的双桥和长 度不同的双桥 分别称为对称双桥实验和非对称双桥实验 得到了十分重要的 结论 a 图3 1 对称双桥实验及实验结果 b 改进蚁群算法求解资源受限项日调度问题 在对称双桥实验中 两个桥的长度是一样的 实验如图3 1 b 所示 蚂蚁 群体只有很小的概率会均匀选择两桥 大多数情况下 蚂蚁群体会逐渐选择其中 某一桥 而两桥被选择的概率几乎是相等的 造成这种现象的原因是 在觅食的 最初期 蚂蚁们随机选择一座桥 并在经过的路径上留下信息素 随着时间的增 长 出现随机波动 其中一座桥会拥有更多的信息素 于是蚂蚁群体更加倾向于 走这一路径 并留下更多的信息素 如果时间足够长 所有蚂蚁最终都选择某一 条路径 这种自身催化 a u t o c a t a l y t i c 或者正反馈 p o s i t i v ef e e d b a c k 的过程 实际就是蚂蚁群体实现自组织行为的一个例子 a b 图3 2 非对称双桥实验及实验结果 在非对称双桥实验中 两个桥的长度是不同的 长桥与短桥之间的比例设定 为2 1 实验的结果如图3 2 b 所示 经过一定的时间以后 大部分的蚂蚁会选 择较短的一桥进行觅食 小部分的蚂蚁会选择较长的一桥进行觅食 其原因可以 解释为 在觅食的最初期 蚂蚁随机选择觅食路径 然而随着时间的增长 蚂蚁 在短桥上出现的频率比长桥上的高 从而在短桥上留下浓度很高的信息素 强化 了蚁群的正反馈行为 与对称双桥实验相比 非对称双桥实验觅食初期随机波动 的影响大大减小 起作用的主要是差异路径长度 d i f f e r e n t i a lp a t hl e n g t h 值 得注意的是 虽然较长路径远长于较短路径 但仍然有一部分蚂蚁会选择较长路 径 蚂蚁这种不依据信息素浓度进行路径选择的行为称为路径探索 p a t h e x p l o r a t i o n 在双桥实验后 d e n e u b o u r g t 3 6 等给出了上述实验的简单随机模型 形成了蚂 中山大学硕十学位论文 蚁系统的雏形 首先 假设桥上残留的信息素量和过去一段时间经过该桥的蚂蚁 数成正比 也就是说不考虑信息素挥发的情况 其次 某一时刻蚂蚁按照桥上信 息素量的多少来选择某支桥 即蚂蚁选择某支桥的概率与经过该桥的蚂蚁数成正 比 当有m 只蚂蚁都经过两支桥以后 设彳 和曰 分别为经 i 幽桥和b 桥的蚂蚁数 a 雪 m 则第m 1 只蚂蚁选择a 桥的概率为 h n 聊 喾l 3 1 么 后 曰 后 而选择b 桥的概率是 p 占 加 1 一尸一 1 3 2 从以上两个公式可以看出 以往走分妇的蚂蚁越多 选择分如的概率就越 大 在模型中 信息素浓度是通过蚂蚁数量表示的 信息素浓度的影响又是通过 参数h 和睐控制的 表示公式的非线性程度 五值越大 信息素浓度差别的影响 就越大 磙示进行随机选择的程度 艚越大 蚂蚁越忽略信息素对自己选择的 作用 当雅相对于蚂蚁数量达到无限大时 所有蚂蚁都以1 2 的概率选择两条分 支 l i u f 3 7 1 采用蒙特卡罗 m o n t ec a r l o 方法对此系统进行了模拟 证实了模型 对实验描述的有效性 3 1 2人工蚂蚁 双桥实验向人们展示了蚂蚁种群的搜寻最短路径的能力 于是人们尝试去设 计一种人工蚂蚁 使之在类似双桥系统的图上移动并寻找最短路径 然而人们发 现 仅仅对自然界中的蚂蚁进行模仿存在很大的缺陷 主要缺陷介绍如下 1 由于蚂蚁对路径的长短没有直观预见 因此在搜索初期 蚂蚁会较均 匀的分布在路径上搜索 在短时间内不会形成正反馈作用 最终增加了蚂蚁寻找 最优路径的时问 而且 在蚂蚁一次搜索结束后 对得到的解的质量没有判断能 力 不能根据解的情况分配信息素 因此也会增加寻找最优解的时间 2 即使蚂蚁对搜索过得路径具有记忆能力 蚂蚁在所搜过程中仍然不能 避免过早收敛现象 原因是一旦蚂蚁找到了较好的路径 蚂蚁的正反馈作用就会 使得更多蚂蚁集中这条路径上来 如果蚂蚁不能跳出正反馈的约束 在 较差 1 7 改进蚁群算法求解资源受限项日调度问题 的路径上进行搜索 则蚂蚁陷入了局部最优 人工蚂蚁除具备自然蚂蚁的优点外 针对自然蚂蚁具有的以上缺陷 人工蚂 蚁需要具备自身的特点 介绍如下 1 人工蚂蚁对走过的路径具有记忆能力 通过禁忌表记录已经走过的路 径 蚂蚁每次选择路径时 只能选择禁忌表以外的路径 这样蚂蚁搜索的路径中 不会出现环路 2 人工蚂蚁对路径的长短具有判断能力 蚂蚁在选择下一条路径时 能 够根据路径的长短和信息素浓度共同决定选择路径的概率 路径的长度被人为规 定为启发信息 当蚂蚁找到更好的解时 人工蚂蚁在该解对应的所有路径上释放 更多的信息素 3 为了尽量避免过早收敛现象 引入了现实中自然蚁群也具有的信息素 挥发现象 使得所有路径上的信息素以一