基于遗传算法的多模式资源约束项目调度问题研究

收稿日期：!""#$"%$&’；修返日期：!""#$&&$!’ 基金项目：国家“%() * +,-.”资助项目（!""#//’&&"’"） 基于遗传算法的多模式资源约束项目调度问题研究! 王为新，李0 原，张开富 （西北工业大学 现代设计与集成制造技术教育部重点实验室，陕西 西安 1&""1!） 摘0 要：为解决多模式资源约束项目调度问题，提出了一种混合遗传算法的求解方法。该算法采用二维编码方 法来示问题的解，基因的值表示任务的优先权和执行模式，每条染色体对应一个满足逻辑关系约束的可行任 务排序，根据染色体所对应的任务调度顺序和执行模式序列可以获得一个满足资源约束的项目调度方案。应用 该编码方法进行选择、交叉和变异等遗传操作，能够使搜索范围遍及整个问题解空间。实际应用表明，该算法能 快速求得问题的最优解或近似最优解。 关键词：多模式；资源约束；项目调度；遗传算法 中图法分类号：23)4&0 0 0 文献标识码：/0 0 0 文章编号：&""&$)(4#（!""1）"&$""1!$") 567689:; <= ->?@A$-9:6$+?ACE 398C，OP/KI Q8A$=> （!"#"$ %$& ’#()*#")*& )+ ,)-"$./)*#*& 0$123- 4 5-"$3*#"$6 7#-8+#9"8*2-3 :$9;-)<)3& +)* 72-21"*& )+ =689#"2)-，>)*";?$1"$*- @)<&"$9;-29#< A-2B$*12"&，C2’#- !;#-D2 1&""1!，,;2-#） !"#$%&’$：2;A7 R8R69 B6S6??@A$-9:6$+?ACE 39:; @;8@ 8?? :98@A76B AC @;6 8?E<9A@;GU X8:; E6C6 96R9676C@7 @;6 R9A<9A@T 8CB 6L6:>@A:@ 8 7:;6B>?ACE G66@ACE 967<>9:6 :@A?ACE7 @;9<>E; E6C6@A: @8@A?@7 7;@A?@A$-9:6$+?ACE；I6C6@A: /?E<9A@;G 0 0 资源约束项目调度问题（5+3.3）指的是一类在满足项目 资源约束和任务前后约束的条件下合理安排工程各作业的开 始时间，以最小化项目总工期的调度问题。在传统的 5+3.3 中，每项任务的工期和资源需求量都是固定的，称为单模式资 源约束项目调度问题（.5+3.3）。多模式资源约束项目调度问 题（-5+3.3）是 .5+3.3 的扩展，每项任务在执行时有多种工 期和资源需求量的组合形式可供选择，与 .5+3.3相比 -5+3$ .3更接近工程实际。 -5+3.3与 .5+3.3一样也属于 K3$;89B 问题，近年来该 问题吸引着越来越多的学者对其进行研究，并提出了各种各样 的优化方法，概括起来可分为以下三类：以分支定界法为代表 的精确类算法［&，!］；基于优先

规则

编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf

的启发式算法［)，’］；以遗传算 法和模拟退火算法为代表的智能优化算法［# Z 1］。精确算法能 求得小规模问题的最优解，但对大规模问题无能为力；启发式 算法和智能优化算法不能保证求得问题的最优解，但在解决大 规模问题时能在求解质量和求解效率上获得一种较好的平衡。 本文针对 -5+3.3提出了一种混合遗传算法的解决策略。 !0 问题描述 在进行问题描述之前，先作如下假设：!任务一旦开始必 须进行到完工，中途不得中断，不得改变执行模式；"资源均 为可更新资源，即资源能力在项目工期范围内为均匀分布；# 每项任务所需资源量均小于资源的最大供应量。 设项目工期为 :；项目共包含 -个任务，E [｛&，!，⋯，-｝为 项目的任务集，E中第 & 个和第 -个任务是为了描述问题方便 而增设的虚拟任务，其作用是标记项目开始时间和结束时间， 只有一种模式，持续时间和资源消耗量均为 "；任务 F 共有 7F 种模式，.F 是任务 F所采用的模式，在该模式下对第 G 种资源 的消耗量为 *F.FG，持续时间为 6F.F；任务 F的开始时间为 1F；E" 为 时刻 "正在进行的任务集合；@F 为任务 F 的紧前任务集合；HG 是资源 G的总量；%是不同资源类型的数量，则问题可以用数 学语言描述如下： GAC0 : [ 1- \ 1& （&） 7U @U 0 12 ] 62.2$1F，42,@F （!） ’ 2,E" *2.2G$HG，G [ &，!，⋯，% （)） 式（&）定义的是目标函数，即最小化项目工期；式（!）定义 的是紧前约束关系，表示任务 F必须在其所有紧前任务均已完 工的情况下才能开始进行；式（)）定义的是资源约束关系，即 在时刻 "进行的所有任务对资源 G 的消耗量不能超过其限制 的数量。 "0 染色体编码和解码 任务之间存在着紧前约束关系，任意的排序可能产生不可 ·!1· 计算机应用研究 !""1 年 万方数据 行的进行次序，如何有效地产生能够处理前后约束的编码是遗 传算法解决该问题的关键。本文提出一种基于优先权的编码 方案来解决该问题。 定义! 设有任务链表 ! "（ "#，"$，⋯，"#），链表中的元素为 各任务的编号，元素的下标为元素所对应任务在链表中的位 置，如果 !中各任务的排列顺序满足紧前约束关系，即如果 ", $%，任务 "在 !中的位置处于任务 %的前面，则称 !为紧前关系 相容链表。 在算法中采用二维编码方法来表示 %&’()( 的解，该编 码方法如图 # 所示。染色体表示的二维结构由任务优先权和 任务执行模式两行组成：第一行中 &" 的值用来表示任务 "的优 先权，是区间［*，#］内的一个实数，数值越大则优先权越高；第 二行中 ’" 是区间［#，("］内的一个整数，用来表示任务 " 的执 行模式。 &# ’# &$ ’$ ⋯ ⋯ &" ’" ⋯ ⋯ &# ’# 图 #! 解的编码方法 采用基于优先权的编码方法可以表示给定项目的所有可 能紧前关系相容链表，并且任何染色体总是对应着一个紧前关 系相容链表。染色体的解码过程分为两步： （#）根据染色体所表达的任务优先权和执行模式信息生 成紧前关系相容链表和执行模式序列。该过程按照一次通过 方式进行：从左到右一次确定一项任务在紧前关系相容链表中 的位置以及该任务的执行模式。该过程每一次迭代中的所有 任务均处于下列三种状态之一： !已排序任务。已经放入紧前关系相容链表中的任务。 "合格任务。紧前任务都是已排序任务的任务。 #自由任务。所有其他任务。 令 !% "［ "#，"$，⋯，"%］（ %$#）表示包含前 %个任务的部分紧 前关系相容链表；(% "［’"#，’"$，⋯，’"%］（ %$#）表示与部分紧 前关系相容链表 !% 相对应的部分执行模式序列。生成紧前关 系相容链表以及执行模式序列的过程步骤如下： !"#8#，%8#，转入#。 "当 %$#时，转入#；否则，转入$。 #检查所有未排序任务，将紧前任务全部位于 !% 中的任 务放入合格任务集 )，转入%。 %将合格任务集 )中具有最高优先权的任务放入部分紧 前关系相容链表 !% 的 "% 之后形成新的部分紧前关系相容链表 !% + #，并将该任务的执行模式放入部分执行模式序列 (% 的 ’"% 之后，形成新的部分执行模式序列 (% + #，%8% + #，转入"。 $返回完整的紧前关系相容链表和执行模式序列，结束。 （$）根据步骤（#）所生成的紧前关系相容链表和执行模式 序列，按照串行调度方案生成一可行计划。令 &*+表示项目的 开始时间，) "（ *"#，*"$，⋯，*"#）表示步骤（#）所得到的紧前关系 相容链表中相应任务的开始时间，所对应的串行调度方案的调 度过程步骤如下： !*"#8&*+，%8$，转入"。 "当 %$#时，转入#；否则，转入&。 #*"% " ,-.｛*% + ,%’%｝（ %,$"%），转入%。 %判断活动 "% 按其执行模式 ’"%进行期间是否存在资源冲 突，如果存在资源冲突则转入$；否则 %8% + #，转入"。 $*"%8*"% + #，转入%。 &返回所有任务的最早开始时间，结束。 #! 适应度函数 对染色体进行解码得到各任务的开始时间，利用式（#）可 得到项目持续时间，即目标函数值。由于 %&’()( 的目标是 最小化项目工期，因此必须将原始目标函数转换为适应度函 数，以确保优秀个体具有大的适应度值。 设 -. 是当前种群的第 . 个染色体，/（ -.）是适应度函数， 0. 是目标函数值，即项目持续时间，0,-.是当前种群中的最大 目标函数值。转换方法如下： /（-.）" 0,-. / 0（-.）+ ! （0） 其中 !是一正整数，使用 !的目的是使选择行为从适应度比例 选择调整到纯随机选择。当染色体间适应度值的差距相对较 大时，为比例选择；当区别相对较小时，则选择趋向于纯随机选 择。 $! 遗传操作 $1 !! 种群的初始化 按照任务 23对项目任务进行升序排列，根据生成的排列 顺序随机地为各任务指定一执行模式，并生成区间［*，#］内的 一随机实数序列作为各任务的优先权，从而构成一条染色体。 按照该方法生成指定数目的个体构成初始种群。 $1 "! 选择操作 采用常用的比例选择策略，其基本原理是根据染色体的适 应度值来确定个体选择概率，各个体被选中的概率与其适应度 值的大小成正比。设种群规模为 1，个体 -. 的适应度值为 /（-.），则个体 -. 被选择的概率 $（-.）为 $（-.）" /（-.） ’ 1 " " # /（-"） （4） 这种选择策略可以采用如下方法实现：先生成一个［*，#］ 内的随机数 2，若 $（-#）+ $（-$）+⋯ + $（-. / #）5 2$$（-#）+ $ （-$）+⋯ + $（-.）则选择个体 -.。 由于选择、交叉和变异等遗传操作的随机性，它们有可能 破坏掉当前种群中适应度最好的个体，从而影响算法的收敛 性。为了保证每一代的优良个体不被破坏，采用最优个体保留 策略［6］。 $1 #! 交叉操作 采用单点交叉算子来完成交叉操作。记参与交叉的两个 父代个体为 3和 4，随机生成一整数 5，# 5 5 5 #，由 3和 4在 5 点进行交叉产生的两个子代个体为 36和 46。子代个体 36的前 5个任务的优先权和执行模式继承于 3，即 &36" " &3" ，’36" " ’3" ，" " #，$，⋯，5 36在 " " 5 + #，5 + $，⋯，#位置上的任务优先权和执行模式 来自于 4，即 &36" " &4" ，’36" " ’4" ，" " 5 + #，5 + $，⋯，# 子代个体 46的形成过程与 36相似，即 &46" " &4" ! " " #，$，⋯，5 &3" ! " " 5 + #，5 + $，⋯，{ #! ! ’46" " ’ 4 " ! " " #，$，⋯，5 ’3" ! " " 5 + #，5 + $，⋯，{ # ·78·第 # 期 王为新等：基于遗传算法的多模式资源约束项目调度问题研究 ! ! ! 万方数据 $! $" 变异操作 采用单重均匀变异算子来完成对染色体的变异操作，变异 算子依变异概率 !" 对染色体 # 中的每个分量进行变异操作， 得到子代个体 #$。设染色体 #的第 %个基因发生变异，则子代 个体 #$各基因所表示的优先权和执行模式分别为 !#$& # ’( " & # % !#& " &#{ %" " " " "#$& # ’) " & # %"#& " &#{ % 其中 ’( 为区间［$，%］内的随机实数，’) 为区间［%，*%］内的随机 整数。 &" 实例计算

分析

定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析

为了证明本算法的有效性，设计了一项目实例，该项目的 网络计划图如图 & 所示，图中共有 &$ 项任务，其中首尾节点是 为了描述问题方便而增设的虚拟任务。该项目需要对两种可 更新资源 +% 和 +& 进行约束优化，资源 +% 和 +& 的限量分别为 ’( 和 %)。除起始任务和终止任务只有一种模式之外，其余各 项任务均有两种模式。该项目的具体参数如表 % 所示。 表 %" 项目实例参数 任务编号模式编号 持续时间 （天） 资源强度任务编号模式编号 持续时间 （天） 资源强度 % & ’ * ) ( + , - %$ % $ $，$ % - ’，’ & ( )，* % ( &，) & ) $，( % ( ’，* & * )，) % ( %&，’ & * %,，’ % %$ %$，* & , %&，) % + %(，( & ) %,，+ % ) %*，* & * %*，( % , +，$ & ) &，& % ( -，) & ) %)，$ %% %& %’ %* %) %( %+ %, %- &$ % ) $，, & * *，( % %$ %&，& & ( %,，* % , %$，* & ) %(，( % ) (，$ & ’ $，, % - %)，$ & ( %)，) % %$ %&，) & , %)，( % %$ &，) & + $，, % * %+，’ & ’ &$，) % ’ $，’ & & ,，& % $ $，$ " " 在利用遗传算法求解问题时，算法参数对算法性能影响非 常大。在本实例中，取种群规模为 )$，用不同的交叉和变异概 率进行了反复实验，交叉概率分别取为 $. %，$. &，$. ’，⋯，$! -； 变异概率取为 $. $%，$. $&，⋯，$. $-，共 ,% 种组合，每种组合实 验 )$ 次。实验结果表明，当交叉概率为 $. * / $. (、变异概率 为 $. $’ / $. $) 时，利用遗传算法进行求解可获得较好的算法 性能。 " " 如果项目中的所有任务只采用第一种模式或第二种模式， 该 012343转换为 412343。同样在资源 +% 和 +& 的限量分别 为 ’( 和 %) 的约束条件下，所有任务只采用第一种模式时，项 目的原始工期为 *(，利用分支定界法求得其最优解为 )%；所有 任务只采用第二种模式时，项目的原始工期为 ’)，利用分支定 界法求得其最优解为 *%。由于该项目中除起止节点以外每个 任务有两种执行模式，相当于 &%,个单模式项目，用分支定界法 难以求出该 012343的最优解。利用本文所设计的遗传算法 能求得的问题最优解为 ’,，相对于只采用一种模式时的最优 解 )% 和 *% 来说有了较大的改善。当取得最优解 ’, 时各任务 的执行模式以及开始时间如表 & 所示。 表 &" 优化后的项目任务开始时间和执行模式 任务编号 % & ’ * ) ( + , - %$ 执行模式 % & % & & & & & & & 开始时间 $ $ $ $ , %& ( * %& %% 任务编号 %% %& %’ %* %) %( %+ %, %- &$ 执行模式 & & & & % & & & & % 开始时间 %( &’ &$ &$ &’ &) &- ’’ ’( ’, *" 结论 本文针对多模式资源约束项目调度问题，采用了一种混合 遗传算法，设计了一种二维编码方案，染色体的值对应着各任 务在进行调度时的优先权和执行模式。根据任务的优先权进 行解码操作能获得满足任务之间逻辑关系约束的紧前关系相 容链，能够彻底避免不可行调度解的产生。实例计算表明该混 合遗传算法能快速有效地解决 012343 问题，是一种较好的 搜索方法。 参考文献： ［%］ 45678976 :，;<6=> GE6 36EH78= 4897IJBF?D KF=9 0JB=F5B7 0EI7L［ M］. N1 457O=6J>，%--+，%-（’）： %-)P&$’. ［&］ ;<6=>5<6FLE? EG CA<8= :BDE6F=9>L［ M］. Q7=KE6OL，%--,，’&（*）：&,’P &-+. ［’］ RE8=E6 S S. ;7J6FL=F8L GE6 4897IJBF?D 36EH78=L KF=9 17LEJ687 17L=6F8P =FE?L KF=9 X7?7=F8 :BDE6F=9>L［ M］. MEJ6?7? Z，[78E8\ ;. : Q7K CGGF8F7?= 4F>JB<=7I :??7 GE6 =97 17LEJ687P2E?L=6