第  卷第  期  年  月 计 算 机 应 用 研 究 ;#1 # 661".-# 9++.)"0 #:#$6(-+) 6) 生物地理学算法求解柔性作业车间调度问题 !郑州航空工业管理学院 管理科学与工程学院 郑州  !上海第二工业大学 机电工程学院 上海  !郑州市科学技术局 郑州  张国辉  聂黎  毛学港 摘要 针对柔性作业车间调度问题对生物地理学优化算法中的迁移操作和突变操作进行改进提出一种改 进的生物地理学优化算法 在算法初始阶段采用混合初始化的方法提高初始种群质量对迁移操作和突变操 作采用不同选择方法提高算法全局搜索能力加快收敛速度 通过编程仿真对柔性作业车间调度问题标准测 试算例进行运算并与其他文献中的计算结果进行比较验证了该算法是可行和有效的也可用于其他车间调度 问题中 关键词 生物地理学优化算法 柔性作业车间调度问题 智能优化算法 迁移操作 中图分类号 %&文献标志码 文章编号  '#! !!!!! #1*,1+D1+#0#6 "0+'(1,6)#1+$ .+' # #,+#,).60.+' #6-$3.-# .1,#)-0$    2(#0(  57  4C(+,.,  &&&   $(&+$%     &&& &&  &+ %&&"#$%     (+$  &&-&%      <#)-0+1+D1+#0#6 "0+'(1,6)#1+$  <&  -06.6+)6)#6#+' -0+$6)#*+' #,+#,).60.+' #6- $3.-# .1,#)-0$  884  $#'+' -0+$,).-# #6+).-#).' $(-.-# #6+).-#)!5 -0+-.1-.,+#-0+.1,#)-0$ -. '#6-+' 0)' -.13.-# .66)#."0 -#$6)#*+-0+(.1-#-0+-.13.-# 6#6(1.-#!%0+ -(+' '+)+-$+-0#'# $,).-# #6+).-#).' $(-.-# #6+).-#)-#$6)#*+-0+.1-#,1#.1+.)"0 .' -#.""+1+).-+-0+"#*+),+"+6++'!8 6)#,).$$,.' $(1.-# -##1*+-0++"0$.)/ 6)#1+$#<& -"#$6.)+' )+(1--0 -0+#-0+))+(1- -0+1-+). -()+!:#$6(-.-#.1)+(1-0#-0.--0+6)#6#+' 884.1,#)-0$. ++"-*+.' +"+-.66)#."0 .' ". .1#+(+' #)#-0+)0#6 "0+'(1,6)#1+$!   #,+#,).60.+' #6-$3.-#  884 .1,#)-0$ 1+D1+#0#6 "0+'(1,6)#1+$ <&  -+11,+"+ #6-$3.-# .1,#)-0$ $,).-# #6+).-#) 引言  柔性作业车间调度问题  <& 是传统作业车间调度问 题  #0#6 "0+'(1,6)#1+$ & 的 扩 展   在 传 统 的 作业车间调度问题中 每个工件的加工工序是确定的 每一 道工序的加工机器和加工时间也是确定的  而在柔性作业 车间调度问题中  每 个 工 件 的 每 一 道 工 序 可 以 在 多 个 可 选 择的加工机器上 进 行 加 工  并 且 不 同 的 加 工 机 器 所 需 要 的 复杂是比 &更加复杂的 &0.)' 问题 目前求解 <&的 常用方法有人工蜂群 .)-".1++"#1# 8: 算法  禁忌 搜索  -.( +.)"0 %  算 法   遗 传 算 法  ,++-".1,#)-0$  差分进化  '+)+-.1+*#1(-# 7 算法  以及它们  之间的混合方法等 虽然在求解结果上取得了一定的效果研 究学者仍在寻求新的方法求解 <& 生物地理学优化 #,+#,).60.+' #6-$3.-# 884 算 法是 $#  受生物地理学理论的启发通过模拟生物种群间 的迁移规律构造出的一种新型全局智能优化算法 884算法 加工时间是不同的 增加了调度的灵活性 比较符合生产的 具有参数少收敛速度快搜索精度高等特点 884算法在经 实际情况 济不匹配问题  函数优化  多目标优化  等连续优化方面 与传统的作业车间调度问题相比柔性作业车间调度问题 已得到应用取得了很好的效果而在离散优化方面如车间调 减少了机器约束增加了加工机器的不确定性 求解柔性作业 度问题等 极 少 应 用 本 文 利 用 生 物 地 理 学 优 化 算 法 针 对 车间调度问题时不仅要对工序进行排序而且还面临对可选 <&的特点改进和设计更加适用的更加有效的 884算法来 机器选择的问题扩大了可行解的搜索范围使调度问题更加 解决 <& 收稿日期   修回日期 基金项目 国家自然科学基金资助项目   国家教育部人文社会科学研究青年 基金资助项目 :  作者简介张国辉  男河南新乡人副教授博士主要研究方向为车间调度智能优化算法  3,0 33.!+'(!"  聂黎   女 讲师博士主要研究方向为车间调度毛学港  男高级工程师硕士主要研究方向为车间调度机械工程! 

   计 算 机 应 用 研 究  第  卷 柔性作业车间调度问题描述  柔性作业车间调度问题比传统作业车间调度问题更加接 近实际调度情况也更加复杂其可以用数学模型描述为 个 工件!  " 在 台机器!       " 上加工            每个工件  包含 个工序! 6  6   6 " 每个工序可以     在多台机器上加工 调度目标是为每个工件的每道工序选择 最合适的加工机器确定每台加工机器上各个工件工序的最佳 加工顺序以及开工时间使整个系统的某些性能指标达到最 优 其中每个工件中工序的加工顺序已知且在每台加工机 器上的加工时间确定 其他约束条件如下 . 同一台机器同一时刻只能加工一个工件  每道工序一旦开始加工不能中断 " 不同工件之间或机器之间具有相同的优先级 ' 不同工件的工序之间没有先后约束同一工件的工序 之间有先后约束  所有工件在零时刻都可以被加工 , 所有机器在零时刻都可以开始加工 求解柔性作业车间调度问题时包括机器选择和工序排序 两个子问题 也就是说每个工序需要先在各自的可选加工机 器集中确定加工机器然后对确定的所有加工机器上的工序进 行排序 根据工序的可选加工机器集中机器数目的不同可以 分为完全柔性 <&和部分柔性 <& 当所有工序中每一道 工序的可选加工机器集都为所有的机器时是完全柔性 <& 降雨量植被多样性地貌特征土地面积和温度等将其称为 适宜指数变量 (-.1-'+D*.).1+ 5;  25是影响栖 息地物种分布物种迁入和物种迁出的重要因素之一 具有较 高 25的栖息地有较多的物种种类物种数量逐渐趋于饱和 栖息地的迁入率降低迁出率增加相反25较低的栖息地仅 能供养较少的物种种群的迁入率提高 栖息地的 25与该栖 息地物种种类多样性成正比 25高的栖息地表示好的个体 25低的栖息地表示差的个体 如图    所示该模型为单个栖息地的物种迁徙模型横 坐标为栖息地种群数量 纵坐标为迁移比率  $ 和   $    分别为种群数量的迁入率和迁出率 当种群数量为  时种群 的迁出率  $ 为  种群的迁入率  $ 最大当种群数量达到   时种群的迁入率  $ 为  种群迁出率  $ 达到最大当    $.D 种群数量为  时迁出率和迁入率相等此时达到动态平衡  状态 其中种群数据 迁移比率  $ 迁入率  $ 迁出率迁入率    函数最大值 迁出率函数最大值 平衡点 栖息地种群最大容量  3 图 生物地理学迁移模型 相反如果只要存在一个工序的可选加工机器集不是所有的机  &&'  算法求解柔性作业车间调度问题 器就为部分柔性 <& 如表  所示为表示  个工件  台机器 的 <&实例依据上文所述此问题为完全柔性 <& 编码与解码    表   柔性作业车间调度问题实例 编码和解码是指栖息地个体与调度方案之间的相互转换 工件 工序           是利用群体智能优化算法求解问题的首要问题 有效的编码 6        6        6  6             6        是要在不产生非可行解的情况下也能够非常容易地表达和操 作完全柔性 <&和部分柔性 <& 如前文所述柔性作业车 间调度问题由两个子问题组成本文在设计编码时由两部分组 成即机器选择  $."0++1+"-#  和工序排序  #6+).-# +(+"+ 4 如图  所示 每部分的长度都为所有工件的 6  6  6  6  6  6  6           工序数之和                               注 表示工件  6 表示工件  的第  道工序   生物地理学优化算法  884是以生物地理模型为基础的一种全局群体智能优化 算法主要描述了物种如何产生灭绝以及迁移的过程 884 就像遗传算法或粒子群算法一样是以种群为基础的算法利 用种群中被选取的每个个体来解决全局优化的问题 遗传算 图 栖息地个体编码方式 法中每个染色体会解码成对应的适应度值进行比较然后通   机器选择每个位置用整数表示依次按照工件及每 过交叉变异进行迭代优化 在 884中是以栖息地作为个体 个工件中工序的顺序进行排列每个整数表示当前工序选择的 进行操作如图   . 所示 每个栖息地  0.-.- 用栖息适宜 加工机器在可选加工机器集中的序号而不是对应的机器号 指数 0.-.-(-.1-'+D 25 表示与 25相关的因素有 这样编码能够保证后续迁徙突变操作中产生的解仍然是可行 

第  期 张国辉等生物地理学算法求解柔性作业车间调度问题   解防止冗余信息的产生 如图  所示 部分中工件  第 部分进行 如图  所示 部分中随机选择一个工序工件    二道工序 6 的位置为  表示选择加工机器集 !       的工序 6 的可选加工机器中最短的加工时间为  对应的机         " 中第二个机器进行加工即机器   器为  和  对应序号为  和  那么发生突变后为   4        工序排序每个位置用工件的工件号直接表示从左 部分随机选择两个工序进行互换 到右依此对同一个工件号进行统计工件号出现的顺序表示该 工件工序间的加工先后顺序 工件号出现的次数等于工件的 工序数 如此编码柔性很高可满足调度规模变化工件工序 数不定等各种复杂情况 如图  所示工序排序部分              第  个  表示工件  的第一道工序 6 当再次   出现  时表示工件  的第二道工序 6 以此类推可以转成   工序的形式为 6 6 6 6 6 6 6 6 6 6 6              迁移操作    884算法利用迁移操作使各栖息地之间的信息进行有 效交换进而能够使优良个体进行保留也进一步扩大解空间 的搜索范围 迁移操作的流程是. 计算每个栖息地的栖息适宜指数 25并且进行降序排序 根据迁入率  $ 选择需要迁入的  图 栖息地个体突变操作   求解 流程   &&'  综上所述基于生物地理学优化算法求解柔性作业车间调 栖息地再根据迁出率  $ 选择需要与其交换的相邻栖息地  度问题的具体流程如图  所示 " 从相邻栖息地中随机选取 5;替代该栖息地中的 5;' 计 算每个栖息地的 25 迁入率  $ 迁出率  $ 分别定义为   {   $   > 1  $.D   $   1 $.D    在利用 884算 法 求 解 <&时 为 适 应 <&的 特 点 式 图 884求解 <&流程    中的  和  表示栖息地个体的栖息适宜指数 25也就 $.D 是说 为每个个体的栖息适宜指数即优化目标最大完工时 间 表示当前所有栖息地中栖息适宜指数的最大值 为简 $.D . 参数设置 设定栖息地数量 )最大迁入率 最大迁出 率 最大突变率  最大迭代代数   $.D $.D  栖息地个体初始化采用文献   中混合方法进行种群 单起见假设有 则    $   $   的初始化 突变操作    当外部自然界发生了疾病或自然灾害等意外事件时栖息 地的生态环境发生变化栖息地的栖息适宜指数 25会发生突 然的变化导致该栖息地脱离平衡点 在 884算法中将这种 突然改变的操作称之为突变 $(-.-# 操作 突变操作在进化算法中是一个核心操作突变增加种群的 " 计算栖息地的栖息适宜指数 25 ' 执行迁移操作 根据迁入率  $ 和迁出率  $ 对栖   息地进行迁移操作从而改变栖息地的适宜特征 + 根据  $ 执行突变操作  判断迭代次数是否达到最大迭代次数  若未达到 $.D 转到 " 若达到输出最优解或近似最优解 多样性提供更多的搜索目标 在 884算法中如何根据种群 实例仿真与结果分析  数量给出相应的突变率是非常重要的 在求解 <&时对突 变率进行了改进 突变率的变化根据迭代次数和栖息地的栖 息适宜指数进行改变  $  "()-+6   25 >2525    $.D $.D  其中 为最大突变率栖息地数量为 )"()-+6 为当前迭代 $.D 为了验证比较算法性能使用与文献   相同的数据集进 行测试数据集包括  个柔性作业车间调度问题实例  个 问题由工件数  = 机器数  = 进行组合每组问题的加 工工序 数  = 个 每 个 问 题 中 每 道 工 序 平 均 加 工 机 器 数 次数 为最大迭代次数25 表示栖息地 的适应指数25 $.D   =  表示所有栖息地适宜指数的平均值 在式   中第一部分是最大突变率保证迭代一开始就 会发生突变第二部分与迭代次数有关随着迭代次数增加发 生突变概率增加第三部分与个体 25有关适宜指数较高或 较低的个体发生突变概率提高防止个体陷入局部最优 突变 操作的流程步骤为 #) -#'# ).'     之间随机小数小于 $  -0+ 突变操作 +'  +' #) 改进的遗传算法采用 ;(.1:编程程序在环境为 5 -+1:#)+ :&A主频  23内存为  8的个人电脑上 运行 运行参数为栖息地数量 ) 最大迭代次数  $.D     最大突变概率   连续运行  次 $.D 表  中给出了  个柔性作业车间调度问题实例的计算结 果和其他文献中的计算结果 在表  中第一栏是问题第二 栏  分别表示工件数和机器数- 表示工序总数<1+D!表  示每个工序平均加工机器数 8 A8 分别表示问题的最优 解的下界和上界 表示最大完工时间的最优值;   $.D $.D 表示最大完工时间的平均值 从表  可以看出对于  个测试实例884算法取得了较 栖息地个体的突变操作分别对机器选择部分和工序排序 好的测试结果 884算法与 L  相比较有  个问题取得 

   计 算 机 应 用 研 究  第  卷 了相同的最优结果与   相比较有  个问题取得更好或相 较稳定而在规模较大的 <&上虽然能够取得最优解但是 同的结果 从 884算法计算结果与其他算法比较显示了提 从平均解上看还不是很稳定 这其中主要原因还在于当规模 出的 884算法求解 <&的有效性 变大时染色体的规模也相应变大在迁移操作和突变操作过 在  个测试实例中884算法对于总工序数较小的小规 程中优良信息难以稳定地共享与传递 图  给出了 $/ 问 模的 <&上都能够取得最优解而且从平均解上看运行也比 题的最优解   的甘特图 $.D 表 计算结果比较 问题   <1+D!  8A8  -   L  884  ;     ;   $.D $.D $.D $.D $.D $/    !     !        $/    !     !  !     $/    !     !        $/    !     !  !     $/    !     !       $/    !     !   !   $/    !     !       $/    !   !        $/    !     !  !     $/    !     !  !     图 $/ 甘特图 结束语  ( +.)"0 .1,#)-0$ -0 . +"+-+,0#)0##' -)("-()+#)-0+ 1+D1+#0#6 "0+'(1,6)#1+$   ! !"# 本文提出了一种基于生物地理学优化算法求解柔性作业 !$%&#$#!   ,    车间调度问题 生物地理学优化算法是通过模拟生物种群间 ! 的迁移规律构造出的一种新型智能优化算法 本文结合柔性 作业车间调度问题特点对迁移操作和突变操作进行了改进 提高了算法全局搜索能力 通过对柔性作业车间调度问题标 准算例进行运算并与其他文献中的计算结果进行了比较结 果表明该算法对于大部分问题能够找到最优解验证了该算法    2(#0( 4., 25.,! ++"-*+,++-".1,# )-0$#)-0+1+D1+#0#6 "0+'(1,6)#1+$  !4+  5%!   .    !   蔡霞李枚毅王康等!基于浮点型编码策略的差分多目标柔性 车间调度优化  !计算机应用研究   (   !    54 !8#,+#,).60.+' #6-$3.-#   !    的可行性和有效性 884算法仍有许多改进之处在今后的 进一步研究中不断寻求 884算法的最佳性能可将 884算法 &!# '#   -    !    蔡之华 龚文引 5:C!基于进化规划的新型生物地理学优 化算法研究 !系统工程理论与实践  (  ! 与其他智能优化算法进行结合用于解决其他实际优化问题和    徐志丹 莫宏伟!生物地理信息优化算法中迁移算子的改进 复杂的工程问题 参考文献   !模式识别与人工智能   ,    !    8959%7&!9#(-,.' "0+'(1, .1+D1+#0#6     张国辉 高亮 李培根 等!改进遗传算法求解柔性作业车间调 -.( +.)"0   !%! $9 *   -    度问题   !机械工程学报   ,    ! !    %9455 897 !7+"-*++,0#)0##'    , 24A., CA+ ! ++"-*+.)-".1++ ("-##)-0+1+D1+#0#6 6)#1+$  !"#!$+# "#1#.1,#)-0$ #)-0+1+D1+#0#6 "0+'(1,6)#1+$   ! !       !  !"#!$%&#$#!    :272 524  72:!,++-".1,#)-0$#)1+D1+    (    ! #0#6 "0+'(1, : &)#"#57775-+).-#.1:#+)+"+#    5(, &@(./+ A%2& !0)' -. 9##-".' (-#$.-#!  !