高级检索

  • ISSN 1006-3080
  • CN 31-1691/TQ
引用本文:
Citation:

基于改进生物地理学优化算法的分布式装配置换流水车间调度问题

    作者简介: 黄佳琳(1996—),女,江苏海门人,硕士生,主要研究方向为生产调度与智能优化。E-mail:Y30180649@mail.ecust.edu.cn;
    通讯作者: 顾幸生, xsgu@ecust.edu.cn
  • 中图分类号: TB497; TP18

Distributed Assembly Permutation Flow Shop Scheduling Problem Based on Modified Biogeography-Based Optimization Algorithm

    Corresponding author: Xingsheng GU, xsgu@ecust.edu.cn
  • CLC number: TB497; TP18

  • 摘要: 提出了一种改进的生物地理学优化(MBBO)算法,以最小化最大完工时间为目标,求解分布式装配置换流水车间调度问题。MBBO算法在初始化阶段利用加工时间最短(SPT)规则和NR2规则对生成的可行解进行初步优化;然后在变异阶段采用基于工厂完工时间的工件插入启发式方法调整工件的工厂分配及加工顺序;最后结合模拟退火算法,跳出局部最优解,增强算法的全局搜索能力。对900个小型实例和540个大型实例进行仿真计算,并与现有的12种启发式算法以及基本生物地理学优化(BBO)算法进行比较,证明了MBBO算法的优越性,同时更新了70个实例的最新已知最优方案。
  • 图 1  分布式装配置换流水车间调度问题

    Figure 1.  Distributed assembly permutation flowshop scheduling problem

    图 2  迁入率、迁出率与物种数量的关系图

    Figure 2.  Relationship between immigration rate, emigration rate and species quantity

    图 3  规则解的工件排序图

    Figure 3.  Job sequence of rule solution

    图 4  规则解的具体形式

    Figure 4.  Specific form of rule solution

    图 5  某随机解的具体形式

    Figure 5.  Specific form of random solution

    图 6  MBBO算法求解DAPFSP问题的流程图

    Figure 6.  Flow chart of MBBO for solving DAPFSP

    图 7  参数趋势图

    Figure 7.  Parameter trend chart

    表 1  不同参数值的组合

    Table 1.  Combination of different parameters

    Group P mmax MaxIterations α
    1 30 0.05 50 0.5
    2 50 0.10 100 0.6
    3 100 0.15 200 0.8
    4 200 0.20 500 0.9
    下载: 导出CSV

    表 2  不同组合的平均最大完工时间

    Table 2.  Average maximum completion time for different combinations

    NumberPmmaxMaxIterationsαAM
    1300.05500.51 716.10
    2300.11000.61 704.50
    3300.152000.81 700.90
    4300.25000.91 695.50
    5500.051000.81 713.40
    6500.1500.91 706.30
    7500.155000.51 697.20
    8500.22000.61 697.60
    91000.052000.91 697.60
    101000.15000.81 696.90
    111000.15500.61 708.00
    121000.21000.51 703.60
    132000.055000.61 698.11
    142000.12000.51 695.11
    152000.151000.91 697.40
    162000.2500.81 703.30
    下载: 导出CSV

    表 3  MBBO算法的小型实例运算结果

    Table 3.  Statistical results of various algorithms on small-sized instances

    F×nARPD
    MBBO(without SA)MBBO
    2×80.0720.027
    2×120.2300.182
    2×160.2660.193
    2×20−0.07−0.203
    2×24−0.162−0.256
    3×80.0060.006
    3×120.1810.173
    3×160.1510.110
    3×200.1710.118
    3×240.1450.038
    4×800
    4×120.0540.041
    4×160.1680.123
    4×200.1790.128
    4×240.1130.043
    Average0.1000.051
    下载: 导出CSV

    表 4  小型实例平均ARPD值的结果对比

    Table 4.  Comparison of average ARPD values of small instances

    F×n ARPD
    H11 H12 H21 H22 H31 H32 VNDH11 VNDH12 VNDH21 VNDH22 VNDH31 VNDH32 BBO MBBO
    2×8 14.62 13.61 6.91 5.99 13.55 12.17 1.00 0.76 1.00 0.76 1.02 0.78 0.020 0.027
    2×12 13.70 12.78 5.74 5.17 11.58 11.05 0.93 0.87 0.93 0.87 0.93 0.87 0.177 0.182
    2×16 12.52 11.40 5.77 5.10 10.00 9.16 0.73 0.55 0.72 0.53 1.09 0.53 0.24 0.193
    2×20 10.23 9.59 4.55 3.78 8.96 8.46 0.53 0.36 0.51 0.37 0.57 0.37 0.226 -0.202
    2×24 8.71 8.34 5.00 4.74 7.54 7.15 0.54 0.21 0.54 0.21 0.54 0.21 0.194 -0.256
    3×8 11.35 9.96 4.57 3.15 8.92 7.79 1.09 0.70 1.15 0.76 1.15 0.76 0.022 0.006
    3×12 9.96 9.13 3.03 2.55 8.72 7.50 0.44 0.28 0.44 0.28 0.44 0.28 0.185 0.173
    3×16 10.10 9.16 3.77 3.14 9.59 8.73 0.86 0.56 0.91 0.56 0.91 0.56 0.218 0.11
    3×20 9.86 8.93 2.72 2.19 8.53 7.84 0.43 0.43 0.43 0.43 0.43 0.43 0.421 0.118
    3×24 7.77 6.48 3.11 2.52 7.24 6.32 0.64 0.33 0.64 0.33 0.64 0.33 0.38 0.038
    4×8 9.03 8.01 2.16 1.25 6.41 5.25 1.08 0.63 0.99 0.63 0.99 0.63 0 0
    4×12 5.63 4.53 1.82 1.38 4.58 3.58 0.74 0.47 0.74 0.47 0.74 0.56 0.17 0.041
    4×16 7.21 6.34 2.86 2.27 6.14 5.18 0.59 0.28 0.59 0.28 0.59 0.28 0.284 0.123
    4×20 6.80 6.00 2.96 2.61 5.66 5.04 1.10 0.63 1.10 0.63 1.10 0.63 0.269 0.128
    4×24 5.14 4.43 2.02 1.60 4.87 4.19 0.57 0.26 0.57 0.26 0.57 0.26 0.358 0.043
    Average 9.51 8.58 3.80 3.16 8.15 7.29 0.75 0.49 0.75 0.49 0.78 0.50 0.211 0.051
    下载: 导出CSV

    表 5  大型实例平均ARPD值的结果对比

    Table 5.  Comparison of average ARPD values of large instances

    n ARPD
    H11 H12 H21 H22 H31 H31 H31 VNDH12 VNDH12 VNDH22 VNDH31 VNDH32 BBO MBBO
    100 6.30 5.61 0.17 0.08 2.02 2.02 2.02 0.02 0.02 0.01 0.03 0.01 0.274 0.015
    200 3.76 3.28 0.15 0.07 1.92 1.92 1.92 0.01 0.01 0.00 0.02 0.00 1.485 0.238
    Average 5.03 4.45 0.16 0.08 1.97 1.97 1.97 0.02 0.02 0.01 0.03 0.01 0.880 0.127
    下载: 导出CSV

    表 6  MBBO算法更新的最佳方案

    Table 6.  Best solutions updated by MBBO

    InstanceBest knownMBBOARPDInstanceBest knownMBBOARPD
    I_16_3_2_3_11 0411 039−0.175I_24_3_2_2_51 6851 679−0.356
    I_16_4_2_2_31 1461 143−0.262I_24_3_2_3_11 0771 075−0.186
    I_16_5_2_4_4836832−0.478I_24_3_2_3_21 4171 404−0.917
    I_20_2_2_2_2859857−0.234I_24_3_2_4_11 3231 320−0.227
    I_20_2_2_2_31 4621 460−0.137I_24_3_2_4_2755739−2.119
    I_20_2_2_3_21 2061 199−0.58I_24_3_3_2_21 2321 230−0.162
    I_20_2_2_4_31 2071 205−0.166I_24_3_3_2_4584578−1.027
    I_20_2_3_2_21 6271 626−0.061I_24_3_3_2_5856854−0.234
    I_20_3_2_2_1968961−0.723I_24_3_3_4_1918917−0.109
    I_20_3_2_2_3997982−1.505I_24_3_3_4_31 7381 734−0.23
    I_20_3_2_2_41 7221 718−0.232I_24_3_4_2_31 7531 748−0.285
    I_20_3_2_3_21 1211 111−0.892I_24_4_2_2_11 3501 338−0.889
    I_20_3_2_3_41 4821 4800.135I_24_4_2_2_21 3651 358−0.513
    I_20_4_2_2_11 2291 220−0.732I_24_4_2_2_5999975−2.402
    I_20_4_2_2_2862858−0.464I_24_4_2_3_31 7111 675−2.104
    I_20_4_2_2_41 6751 673−0.119I_24_4_3_2_21 6941 688−0.354
    I_20_4_2_2_51 3941 381−0.933I_24_4_3_2_32 4582 455−0.122
    I_20_4_2_3_2858826−3.73I_24_4_3_2_41 8441 839−0.271
    I_20_4_2_3_41 7251 716−0.522I_24_4_4_2_51 3561 355−0.074
    I_20_4_3_3_51 1371 129−0.703I_24_5_2_2_11 6251 615−0.615
    I_20_5_2_2_11 4781 474−0.271I_24_5_2_2_32 0492 024−0.244
    I_20_5_2_2_21 2581 253−0.397I_24_5_2_2_41 7641 758−0.34
    I_20_5_2_2_31 5001 479−1.4I_24_5_2_3_31 3401 333−0.522
    I_20_5_2_2_51 5891 587−0.063I_24_5_2_3_5914912−0.219
    I_20_5_2_3_21 1811 176−0.423I_24_5_2_4_21 0541 020−3.226
    I_20_5_2_3_31 4991 494−0.334I_24_5_2_4_31 6911 687−0.237
    I_24_2_2_2_2947944−0.317I_24_5_3_2_21 5181 489−1.91
    I_24_2_2_3_21 5141 491−1.519I_24_5_3_2_31 8901 886−0.212
    I_24_2_2_3_31 4951 492−0.2I_24_5_3_2_42 2872 279−0.35
    I_24_2_2_3_51 8611 856−0.269I_24_5_3_3_31 7611 759−0.114
    I_24_2_3_2_41 7061 705−0.059I_24_5_4_2_51 7921 777−0.837
    I_24_2_3_2_51 0841 082−0.185I_100_5_4_30_65 6645 659−0.088
    I_24_2_4_2_5563554−1.599I_100_10_4_30_56 2966 248−0.191
    I_24_3_2_2_11 7051 695−0.587I_100_20_4_40_15 5635 562−0.018
    I_24_3_2_2_3879876−0.341I_100_20_4_40_85 3935 365−0.519
    下载: 导出CSV
  • [1] GAO J, CHEN R, DENG W. An efficient tabu search algorithm for the distributed permutation flowshop scheduling problem[J]. International Journal of Production Research, 2013, 51(3): 641-651. doi: 10.1080/00207543.2011.644819
    [2] CHAN F T S, CHUNG S H, CHAN P L Y. An adaptive genetic algorithm with dominated genes for distributed scheduling problems[J]. Expert Systems with Applications, 2005, 29(2): 364-371. doi: 10.1016/j.eswa.2005.04.009
    [3] 李子辉, 钱斌, 方德斌, 等. 求解一类柔性装配流水车间调度问题的混合分布估计算法[J]. 管理工程学报, 2017, 31(4): 200-208.
    [4] HATAMI S, RUIZ R, Andres-ROMANO C. Heuristics and metaheuristics for the distributed assembly permutation flowshop scheduling problem with sequence dependent setup times[J]. International Journal of Production Economics, 2015, 169: 76-88. doi: 10.1016/j.ijpe.2015.07.027
    [5] HATAMI S, RUIZ R, Andrés-ROMANO C. The distributed assembly permutation flowshop scheduling problem[J]. International Journal of Production Research, 2013, 51(17): 5292-5308. doi: 10.1080/00207543.2013.807955
    [6] WANG S Y, WANG L. An estimation of distribution algorithm-based memetic algorithm for the distributed assembly permutation flow-shop scheduling problem[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2016, 46(1): 139-149. doi: 10.1109/TSMC.2015.2416127
    [7] LIN J, WANG Z J, LI X D. A backtracking search hyper-heuristic for the distributed assembly flow-shop scheduling problem[J]. Swarm and Evolutionary Computation, 2017, 36: 124-135. doi: 10.1016/j.swevo.2017.04.007
    [8] PAN Q K, GAO L, LI X Y, et al. Effective constructive heuristics and meta-heuristics for the distributed assembly permutation flowshop scheduling problem[J]. Applied Soft Computing, 2019, 81: 105492. doi: 10.1016/j.asoc.2019.105492
    [9] 马萍, 刘思含, 孙根云, 等. 基于邻域引力学习的生物地理学优化算法[J]. 计算机工程与应用, 2018, 54(22): 35-41. doi: 10.3778/j.issn.1002-8331.1710-0115
    [10] 杨蒙蒙, 王水花, 陈燚, 等. 生物地理学优化算法与应用综述[J]. 南京师范大学学报(工程技术版), 2018, 18(28): 50-55.
    [11] LIN J, XU L, ZHANG H Y. Hybrid biogeography based optimization for constrained optimal spot color matching[J]. Color Research and Application, 2014, 39(6): 607-615. doi: 10.1002/col.21836
    [12] LIN J. A hybrid biogeography-based optimization for the fuzzy flexible job-shop scheduling problem[J]. Knowledge-Based System, 2015, 78(1): 59-74.
    [13] LIN J, ZHANG S. An effective hybrid biogeography-based optimization algorithm for the distributed assembly permutation flow-shop scheduling problem[J]. Computers & Industrial Engineering, 2016, 97: 128-136.
    [14] 陈飞跃, 徐震浩, 顾幸生. 基于离散布谷鸟搜索算法的带阻塞有差速混合流水车间调度[J]. 华东理工大学学报(自然科学版), 2017, 43(3): 425-435.
    [15] WANG X H, DUAN H B. A hybrid biogeography-based optimization algorithm for job shop scheduling problem[J]. Computers & Industrial Engineering, 2014, 73: 96-144.
    [16] WANG X H, DUAN H B. Hybrid biogeography-based optimization for integer programming[J]. The Scientific World Journal, 2014, 12(6): 1-7.
    [17] 李知聪, 顾幸生. 改进的生物地理学优化算法在混合流水车间调度中的应用[J]. 化工学报, 2016, 67(3): 751-757.
    [18] BOUSSAÏD I, CHATTERJEE A, SIARRY P, et al. Biogeography-based optimization for constrained optimization problems[J]. Computers & Operations Research, 2012, 39(12): 3293-3304.
    [19] MA H P, SIMON D, SIARRY P, et al. Biogeography-based optimization: A 10-year review[J]. IEEE Transactions on Emerging Topics in Computational Intelligence, 2017, 1(5): 391-407. doi: 10.1109/TETCI.2017.2739124
  • [1] 赵倩倩赵均徐祖华陈曦邵之江秦海中 . 空分装置群的设备启停及变负荷调度策略. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20181015005
    [2] 陈兰萍牛玉刚 . 基于多代理的微电网分区分布式最优潮流分析. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190523004
    [3] 马晓东袁伟娜凌小峰 . 一种基于机会参考源的分布式ADS-B无源定位防欺骗方法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20181115001
    [4] 叶贞成王鑫梅华 . 基于改进差分进化算法的裂解反应动力学系数辨识. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190910002
    [5] 徐震浩周畅张凌波顾幸生 . 柔性作业车间的成套订单调度问题. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20181109001
    [6] 齐莉莉刘济 . 基于改进CKF算法的一类有色噪声污染的线性观测系统的状态估计. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180427002
    [7] 高天阳虞慧群范贵生 . 基于模拟退火遗传算法的云资源调度方法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180416001
    [8] 赖兆林冯翔虞慧群 . 基于逆向学习行为粒子群算法的云计算大规模任务调度. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190218001
    [9] 张丹杨敏博冯霄 . 循环流化床甲醇制芳烃分离工艺的模拟与改进. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180911004
    [10] 叶贞成倪泽雨程辉 . 一种改进的分隔壁精馏塔简捷计算方法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20191010001
    [11] 张星崔向伟李宗霖李志敏 . 基于能量循环再生系统酶法生产谷胱甘肽. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190806001
    [12] 曹雅茜黄海燕 . 基于代价敏感大间隔分布机的不平衡数据分类算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180515001
    [13] 曹移林余炜 . 平行三阶段流水作业问题的近似算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180206001
    [14] 盛建为钱夕元 . 零膨胀对数级数分布的参数估计. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180419003
    [15] 魏江平林家骏陈宁 . 多特征非接触式测谎技术. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190619002
    [16] 王学武闵永顾幸生 . 基于密度聚类的多目标粒子群优化算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180321005
    [17] 陈鹏罗娜 . 基于竞争机制差分进化算法的无分流换热网络优化. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20181015004
    [18] 潘傲谢明辉夏建业庄英萍 . 基于均龄理论模拟搅拌式反应器的混合时间. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180716001
    [19] 潘斌翁涛杨家鹏安琦 . 汽车发动机皮带系统臂式张紧轮力学性能研究. 华东理工大学学报(自然科学版), doi: 10.14135/j.cmki.1006-3080.20190114006
    [20] 粟爽格安琦 . 内外圈装配过盈量对圆柱滚子轴承力学性能的影响. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190121002
  • 加载中
图(7)表(6)
计量
  • 文章访问数:  1346
  • HTML全文浏览量:  227
  • PDF下载量:  5
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-08-28
  • 网络出版日期:  2019-12-25

基于改进生物地理学优化算法的分布式装配置换流水车间调度问题

    作者简介:黄佳琳(1996—),女,江苏海门人,硕士生,主要研究方向为生产调度与智能优化。E-mail:Y30180649@mail.ecust.edu.cn
    通讯作者: 顾幸生, xsgu@ecust.edu.cn
  • 华东理工大学化工过程先进控制和优化技术教育部重点实验室,上海 200237

摘要: 提出了一种改进的生物地理学优化(MBBO)算法,以最小化最大完工时间为目标,求解分布式装配置换流水车间调度问题。MBBO算法在初始化阶段利用加工时间最短(SPT)规则和NR2规则对生成的可行解进行初步优化;然后在变异阶段采用基于工厂完工时间的工件插入启发式方法调整工件的工厂分配及加工顺序;最后结合模拟退火算法,跳出局部最优解,增强算法的全局搜索能力。对900个小型实例和540个大型实例进行仿真计算,并与现有的12种启发式算法以及基本生物地理学优化(BBO)算法进行比较,证明了MBBO算法的优越性,同时更新了70个实例的最新已知最优方案。

English Abstract

  • 置换流水车间调度问题(Permutation Flowshop Scheduling Problem, PFSP)是制造系统和工业过程中广泛研究的组合优化问题[1],通常假设所有的工件都在一个工厂中进行加工,即单一工厂生产模式。现如今,在全球化的背景下,分布式制造以低成本、低风险、高质量的优势取代了单一工厂生产模式,成为工业生产过程中的主流形式。比起单一工厂调度问题,分布式制造的调度问题更为复杂。它不仅需要考虑工件在机器上的加工顺序,还必须考虑如何将工件合理地分配到相应的工厂进行加工。不同工厂的不同工件分配会形成不同的调度方案,从而影响供应链的绩效[2]

    装配流水车间调度问题(Assembly Flowshop Scheduling Problem, AFSP)广泛存在于生产制造系统中,用于生产由不同工件装配而成的多种产品[3]。考虑到装配系统在工业过程中的实际应用,装配流水车间调度问题也是生产调度领域的重点问题。装配流水车间是一个混合生产系统,其中各个生产操作都是独立并且同时执行的,以便将工件运输到装配线,及时进行产品的组装。在组装过程中,可以由给定数量的不同工件根据装配程序制造各种各样的最终产品,装配程序代表了由不同供应商提供的不同工件之间的组装关系[4]

    分布式装配置换流水车间调度问题(Distributed Assembly Permutation Flowshop Scheduling Problem, DAPFSP)是分布式置换流水车间调度问题和装配流水车间调度问题的结合,最早由Hatami等[5]提出,以最小化装配工厂完工时间为目标,提出了基于不同结构的启发式和可变邻域下降(VND)算法等12种启发式方法。在此基础上,越来越多的优化算法被应用于求解DAPFSP问题。2016年,Wang等[6]提出了基于分布估计算法的模因算法(EDAMA)来求解DAPFSP问题,通过与文献[5]的12种启发式算法比较,验证了EDAMA算法的优越性。2017年,Lin等[7]采用回溯搜索超启发式(BS-HH)算法,同样与12种启发式算法以及EDAMA等智能优化算法进行比较,突出了BS-HH算法的有效性。2019年,Pan等[8]针对求解DAPFSP问题的不同的CPU时间和解决方案质量的需求,提出了一个混合整数线性模型,还列出了3种不同结构的启发式算法、两种可变邻域搜索方法以及迭代贪婪算法,最后在算法性能和运算时间两方面与其他16个已有算法进行对比,表明所提算法能够高效地解决DAPFSP问题。

    生物地理学优化算法(Biogeography-Based Optimization, BBO) [9]自提出以来,因对问题依赖度小、算法参数少、易于实现等优点备受青睐。Rahmati等采用BBO算法求解包含3个目标函数的柔性作业车间调度问题,并且对遗传算法和BBO算法进行比较,利用基准测试数据(Brandimart数据)以及Barnes和Chamber数据的运算,凸显了BBO算法的优势[10]。Lin等[11]采用和声搜索算法和基于对立的学习方法改进BBO算法来求解专色印刷的专色匹配问题,通过与粒子群算法的比较,验证了BBO算法的有效性。然而,BBO算法存在收敛速度缓慢、易陷入局部最优解以及在规定迭代次数中难以获得最优解等缺点[12]。考虑到分布式装配置换流水车间的加工特点,本文设计了3种改进策略:首先,使用加工时间最短优先(Shortest Processing Time,SPT)规则和NR2规则改善初始可行解的结构;其次,在变异过程中加入基于工厂完工时间的工件插入启发式方法,优化工件的工厂分配策略及其在各工厂内的加工顺序;最后结合模拟退火算法,跳出局部最优,提高算法寻优的质量。仿真结果证明了改进的BBO算法求解分布式装配置换流水车间调度问题的有效性。

    • 分布式装配置换流水车间调度问题包括两个阶段:生产阶段和装配阶段,并且可以概括为3个子问题:工件调度、产品调度和工厂分配,如图1所示。

      图  1  分布式装配置换流水车间调度问题

      Figure 1.  Distributed assembly permutation flowshop scheduling problem

      分布式装配置换流水车间调度问题的描述如下[13]:在生产阶段,一共有n个工件$\left\{ {{J_1},{J_2}, \cdots ,{J_n}} \right\}$分配给F个相同的工厂进行加工。每个工件只能在一个工厂进行加工,并且所有的工厂都能处理所有的工件。每个工厂都有m台机器$\left\{ {{M_1},{M_2}, \cdots ,{M_m}} \right\}$,任一工件${J_i}$都以$\left\{ {{O_{i1}},{O_{i2}}, \cdots ,{O_{im}}} \right\}$的加工顺序依次在m台机器上进行加工。每台机器同一时刻只允许加工一个工件,而每个工件同一时刻也只能够在一台机器上进行加工[14]。工件一旦开始进行加工,操作就不能中断,直至加工完毕。在装配阶段只有一个装配工厂,所有的工件在生产阶段加工完毕后都会运输到装配工厂进行产品的组装。装配工厂里有一台装配机器${M_{\rm{A}}}$,使用定义的组装程序来组装工件,然后制造出H个不同的最终产品$\left\{ {{P_1},{P_2}, \cdots ,{P_H}} \right\}$。每个最终产品${P_h}$都由${N_h}$个工件组成,并且这些工件都必须在组装最终产品${P_h}$前加工完毕,由此可知$\mathop \sum \limits_{h = 1}^H {N_h} = n$。由分布式装配置换流水车间调度问题的定义可知:所有工件在零时刻都可用且不允许抢占;每个工件都由m+1个操作组成,前m个操作在生产阶段的m台机器上执行,而最后一个操作在装配阶段的组装机器上执行;从生产阶段到装配阶段收集和运输所有工件的时间可以忽略不计。

    • 对于分布式装配置换流水车间调度问题,通常选择最小化最大完工时间(makespan)作为优化目标。假设${\gamma ^f} = \left[ {{\gamma ^f}\left( 1 \right),{\gamma ^f}\left( 2 \right), \cdots ,{\gamma ^f}\left( {{n^f}} \right)} \right]$表示分配给工厂f的工件加工顺序,${n^f}$表示分配给工厂f的工件总数,${p_{i,j}}$${C_{i,j}}$分别表示在生产阶段第i个工件在第j台机器上的加工时间和第i个工件在第j台机器上的完工时间。由此可得出生产阶段的计算过程:

      工件在生产阶段加工完毕后,进入装配阶段进行产品的组装。假设${\gamma _h} = \left[ {{\gamma _h}\left( 1 \right),{\gamma _h}\left( 2 \right), \cdots ,{\gamma _h}\left( {{n_h}} \right)} \right]$表示产品h的工件组装顺序,${n_h}$表示隶属于产品h的工件总数,${Q_h}$${C_{{M_{\rm{A}}},h}}$分别表示产品h在装配机器上的装配时间及其在装配阶段的完工时间,则可得出装配阶段的计算过程:

      $\varLambda $是一个可行的调度方案,最终最大完工时间表示为

      所以,解决分布式装配置换流水车间调度问题的关键就是找到一个最优调度方案${\Lambda _{{\rm{best}}}}$,使得最大完工时间${C_{\max }}\left( {{\Lambda _{{\rm{best}}}}} \right)$取得最小值。由于DAPFSP问题是NP难问题,无法在多项式时间内找到最优解,因此,求解DAPFSP问题的目标退化为在有限时间内,找到一个较为满意的调度方案,使得最大完工时间最小化。

    • BBO算法是一类基于种群和生物启发的群智能优化算法,其核心是栖息地间种群的迁移和变异过程,同时这两个过程也是算法实现优化操作的主要步骤。

    • 生物种群分布于不同的栖息地,各栖息地都可用对应的适宜度指数(Habitat Suitability Index, HSI)来表示。与HSI相关的特征包括栖息地的降雨量、植被的多样性和气候等因素,构成了一个描述栖息地适宜度的向量SIV(Suitable Index Vector)[15]。应用BBO算法求解优化问题时,一个栖息地对应优化问题的一个可行解,通过计算各栖息地的适宜度值来评价这些解的优劣程度。根据不同栖息地之间物种的迁移操作和栖息地内物种的变异操作,使适应度值较差的栖息地获得更多适应度值较好的栖息地的信息,实现栖息地的不断进化[16]

    • BBO算法通过迁移算子实现栖息地之间的信息交互,从而达到进化的目的。栖息地的适应度值越高,其所能容纳的物种数量越多,反之则越少,这就需要建立一个表征物种数量与栖息地适应度关系的映射函数[17]。BBO算法根据各个栖息地的适应度值,从大到小进行排序,设栖息地数量为P,最大物种数为Nmax,则栖息地n的物种数量N(n)=Nmax-nn=1,2,…,Pn是各栖息地经过排序后的序号)。物种在栖息地之间的迁移操作根据迁出率µ(n)和迁入率λ(n)进行,各栖息地的µ(n)和λ(n)的计算公式如式(8)、式(9)所示。

      其中:$\mu \left( n \right)$表示栖息地n的迁出率;$E$表示最大迁出概率,${E \in \left( {0,1} \right]}$$\lambda \left( n \right)$表示栖息地n的迁入率;$I$表示最大迁入概率,${I \in \left( {0,1} \right]}$。可以看出栖息地的迁出率与该栖息地的物种数量呈正比,而迁入率与其物种数量呈反比[18]图2示出了迁入率、迁出率和物种数量的关系。

      图  2  迁入率、迁出率与物种数量的关系图

      Figure 2.  Relationship between immigration rate, emigration rate and species quantity

    • 突发的灾难性事件能够完全改变一个栖息地的生态环境,导致栖息地的适宜度值产生巨变,生物地理学中通过变异来模拟这一情况[19]。BBO算法根据变异概率随机地修改栖息地的特征向量,变异概率主要取决于栖息地的物种数量概率,也可以说和栖息地的物种数量息息相关。物种数量为N(n)的栖息地发生变异的概率${m_n}$如式(10)所示:

      其中:mmax为自定义的最大变异概率;Pmax为指栖息地的物种数概率的最大值;Pn为物种数量为N(n)的栖息地的物种数概率。在t时刻,栖息地n的物种数量为N(n)的概率如下:

    • 应用MBBO算法求解分布式装配置换流水车间调度问题时,在初始化阶段将采用两种不同的编码方式生成初始可行解,分别被称为规则解和随机解。

      规则解主要是根据SPT规则生成。将每个产品中的工件按SPT规则进行排列,确定每个产品的工件加工顺序。在此基础上,计算每个产品的装配开始时间,并规定最早开始装配的产品排在前面,由此产生产品序列。两者结合即一个完整的工件加工序列,这样产生的规则解是唯一的。最后采用NR2规则进行解码。NR2规则定义为[13]:将工件j分配给包含工件j之后最大完工时间最小的工厂,由此生成新的调度方案。

      随机解引入了“虚拟工件”的概念,其包含了工件和工厂两种因素。首先,将所有工件进行随机排列,生成一个工件加工序列;然后,将工厂作为“虚拟工件”,插入到已有的工件加工序列中,“虚拟工件”的个数同工厂的数量一致,并且,“虚拟工件”用数字“0”表示。需要注意的是,每个随机解的第1列必须是“虚拟工件”,即必须为“0”,否则将存在不能在任何工厂加工的工件,这样的随机解就变成了不可行解。除此之外,若随机解存在两个“虚拟工件”相邻的情况,就表示存在某个工厂处于闲置状态,不加工任何工件。这样的解虽然属于可行解,但根据实际生产过程可以判断,此类解的适应度值一般比较低。为了提高初始可行解的质量,MBBO算法以将工件均匀分配给各个工厂的方式生成新的初始解,取代存在工厂闲置情况的初始解。随机解的解码即根据最大完工时间的计算公式进行。

      以8个工件、2台机器、2个工厂、2个产品的分布式装配置换流水车间调度问题为例,隶属于2个产品的工件分别为:产品1={1,2,4,8},产品2={3,5,6,7}。对于规则解,所有工件按SPT规则排列后,每个产品的工件加工顺序如下:产品1={8,1,2,4},产品2={7,5,3,6},此时,两个产品的开始装配时间分别为:产品1=127,产品2=133,则规则解的工件排序如图3所示。最后根据NR2规则解码,得出规则解的具体形式及最大完工时间${C_{\max }}\left( {{\Lambda _{{\rm{rule}}}}} \right){\rm{ = }}501$,规则解的具体形式如图4所示。

      图  3  规则解的工件排序图

      Figure 3.  Job sequence of rule solution

      图  4  规则解的具体形式

      Figure 4.  Specific form of rule solution

      针对这个例子,随机解就是利用randperm函数对1~9进行随机排序,并把大于8的数置零,最后在首位插入一个“0”。随机解的数量很多,从中挑出一个,其具体形式如图5所示。

      图  5  某随机解的具体形式

      Figure 5.  Specific form of random solution

    • 在执行精英保留策略、迁移操作和变异操作之前,需要计算各个栖息地即各个初始可行解的适应度值,并按照从大到小的顺序进行降序排序,最优解排在第一位。

    • BBO算法在迭代过程中有可能生成适应度值更高的解,若不对这些优良解采取保护措施[17],放任它们参与迁移操作和变异操作,很容易破坏优良解的结构,丧失获取更优可行解的机会,导致算法的搜索能力下降。MBBO算法加入了精英保留策略,即在每次执行迁移和变异操作之前,取初始可行解数量的10%作为精英解,不作任何改变,而是保留到下一步迭代过程再进行相应操作。

    • BBO算法通过迁移操作,用较优解中的元素来取代较差解中的元素,以此实现栖息地之间的信息交互。MBBO算法的迁移操作和BBO算法的迁移操作大同小异。对每个解,在执行迁移操作时,改进前后的算法同样都是按位进行循环,根据迁入率判断该位是否发生迁入,若发生迁入,再根据轮盘赌法选择迁出的位,进行相应位的交换操作。MBBO算法有两个特别之处:第一,对于规则解,规定其不参与迁移操作。因为规则解的特色就在于它是产品序列和各产品工件序列的结合,每个产品的工件不能分开,否则将会影响产品的装配开始时间,进而影响解的结构,致使该解失去作为规则解的优势。第二,对于随机解,在按位循环判断是否发生迁入或是根据轮盘赌选择迁出位的时候,都必须跳过每个解的第一位(第一位都是“0”,即“虚拟工件”),否则将会生成不可行解。基于工厂完工时间的工件插入启发式方法的伪代码如下:

        For m=1:P %每个解按解集循环

      If ms > rand %根据变异概率判断该解是否发生变异

        For n=1:length(fCmax) %选出该解中完工时间最大的工厂的工件

         For l=0: length(fCmin) %列出该解中完工时间最小的工厂的工件序列的可插入位

          Insert the job fCmax(n) into the position l of factory fCmin; %将完工时间最大的工厂的工件依次插入到完工时间最小的工厂的工件序列中;

         End

        End

        If value(fCmax) is strictly improved %找到最佳的插入位置并且插入后新解的最大工厂完工时间小于旧解,则接受新解

         Update solution;

        End

       End

      End

    • BBO算法利用变异操作来保证解的多样性,抑制算法的早熟现象。BBO算法的变异过程是根据变异概率判断解(栖息地)的某个特征分量是否发生突变,具体操作与迁移过程相似。首先按位进行循环,根据变异概率判断该位置元素是否发生变异,若发生变异,则随机选择变异的位,进行合法交换即可。然而,BBO算法的变异过程随机性较大,很有可能大幅破坏之前的优势解,因此MBBO算法对此进行了改进,加入了基于工厂完工时间的工件插入启发式方法。在MBBO算法的变异过程中,利用变异概率判断某个解而不是解的某个特征分量是否进行突变,若确定该解发生突变,则依次将该解中完工时间最大的工厂的每个工件插入到该解中完工时间最小的工厂的工件序列中,并找到最佳的插入位置。插入最佳位置后,比较新解和旧解的工厂最大完工时间,若新解的工厂最大完工时间小于旧解的最大完工时间,则接受新解,反之,则返回旧解。

    • 为了提高解的质量,MBBO算法还结合了模拟退火算法,有助于跳出局部最优解,增强算法的搜索能力。

      考虑到MBBO算法的效率问题,在算法迭代过程中,记录每次的最优值,若在最后20次的迭代过程中,最优值都保持不变,则对得到的最优解采用模拟退火算法进行进一步寻优。模拟退火算法的伪代码如下:

        设置初始温度T0和最终温度Tf;

      π=bestsolution; % π为当前最优解

      While T0 > Tf

        通过工件交换或工件反转产生一个新解π’;

        If ∆T=Cmax(π’)-Cmax(π)<0

          π=π’;

        Elseif rand<exp(-∆T/T)

          π=π’;

        End

        T0=αT0; % α为退火率

      End

      If Cmax(π)<=Cmax(bestsolution)

        bestsolution=π %若新解的适应度值小于旧解,则仍返回旧解

      End

    • MBBO算法求解DAPFSP问题的过程中,可行解表示栖息地,每个可行解都由一个行矩阵表示,而栖息地中的物种由矩阵中的元素及它的位置信息共同表示。适应度值对应着于目标函数值的倒数,目标函数值即式(7)计算出的值。MBBO算法求解DAPFSP问题的具体流程如图6所示。

      图  6  MBBO算法求解DAPFSP问题的流程图

      Figure 6.  Flow chart of MBBO for solving DAPFSP

    • 为了验证改进的生物地理学优化算法求解分布式装配置换流水车间调度问题的有效性,对两组基准数据(http://soa.iti.es)进行仿真计算。每组数据由4个变量组成:n(工件数)、m(机器数)、F(工厂数)、H(产品数)。第1组由900个小型实例组成,其中,n={8,12,16,20,24},m={2,3,4,5},F={2,3,4},H={2,3,4}。第2组由540个大型实例组成,其中,n={100,200},m={5,10,20},F={4,6,8},H={30,40,50}。对于小型实例,每个组合都有5个例子;对于大型实例,每个组合有10个例子[6]

      采用平均相对百分比偏差(ARPD)来评估算法的性能[7],计算公式如下:

      其中:Cbest为所有实例已知的最佳解决方案的最优值;Ci为算法每次运行后得到的最大完工时间的最小值,即算法的最优值,一共运行R次。如果ARPD<0,则表明产生了新的最佳解决方案。所有实例的已知最优解都可在http://soa.iti.es上获得。

    • MBBO算法有4个关键参数:栖息地数量P(初始化产生的可行解的数量)、最大突变率mmax、最大迭代次数MaxIterations以及退火率α。为了研究这4个参数对MBBO算法性能的影响,采用正交试验的方法对实例I_24_3_2_2_1进行仿真计算。其中的“24”表示工件总数为24,“3”表示每个工厂都有3台机器,第1个“2”表示一共有两个工厂,第2个“2”表示最终装配出两个产品,末尾的1表示这个实例是这个组合的第1个例子。表1列出了影响算法性能的关键参数的不同组合。

      Group P mmax MaxIterations α
      1 30 0.05 50 0.5
      2 50 0.10 100 0.6
      3 100 0.15 200 0.8
      4 200 0.20 500 0.9

      表 1  不同参数值的组合

      Table 1.  Combination of different parameters

      所有的参数组合都采用MBBO算法运行10次,计算平均最大完工时间(AM),所得结果列于表2,由此观察不同参数对算法性能的影响,最终找出效果最令人满意的参数组合。

      NumberPmmaxMaxIterationsαAM
      1300.05500.51 716.10
      2300.11000.61 704.50
      3300.152000.81 700.90
      4300.25000.91 695.50
      5500.051000.81 713.40
      6500.1500.91 706.30
      7500.155000.51 697.20
      8500.22000.61 697.60
      91000.052000.91 697.60
      101000.15000.81 696.90
      111000.15500.61 708.00
      121000.21000.51 703.60
      132000.055000.61 698.11
      142000.12000.51 695.11
      152000.151000.91 697.40
      162000.2500.81 703.30

      表 2  不同组合的平均最大完工时间

      Table 2.  Average maximum completion time for different combinations

      对于每个参数,将平均最大完工时间作为关键指标,判断每个参数的趋势,结果如图7所示。

      图  7  参数趋势图

      Figure 7.  Parameter trend chart

      图7可以看出,栖息地数量和最大迭代次数越大,算法的性能越好,但同时计算成本会增加,时间明显变慢。综合考虑算法的性能效果以及耗费的时间成本,选取MBBO算法参数如下:P=50,mmax=0.10,MaxIterations=100,α=0.9。此外,最大迁出率I和最大迁入率E均设为1,取栖息地数量P的10%作为保留的精英解。

    • 为了验证模拟退火算法对改进生物地理学优化算法的有效性,对所有小型实例进行仿真,比较了使用和不使用模拟退火算法的MBBO算法的实例运算结果。两个算法都具有相同的参数设置(除了SA算法的部分)和停止条件,并且独立运行5次。表3列出了Fn分的15个组合的平均ARPD值,每个组合包含60个小型实例。

      F×nARPD
      MBBO(without SA)MBBO
      2×80.0720.027
      2×120.2300.182
      2×160.2660.193
      2×20−0.07−0.203
      2×24−0.162−0.256
      3×80.0060.006
      3×120.1810.173
      3×160.1510.110
      3×200.1710.118
      3×240.1450.038
      4×800
      4×120.0540.041
      4×160.1680.123
      4×200.1790.128
      4×240.1130.043
      Average0.1000.051

      表 3  MBBO算法的小型实例运算结果

      Table 3.  Statistical results of various algorithms on small-sized instances

      模拟退火算法具有很强的全局搜索能力,能够使算法跳出局部最优而趋向于全局最优。从表3可以看出,在大多数组合中,融合了模拟退火算法的MBBO算法可以利用模拟退火算法的优势来获得较低的ARPD值。不仅如此,MBBO算法在有和没有模拟退火算法的情况下获得的ARPD平均值分别为0.051和0.100,前者的算法性能明显高于后者。由此可见,混合入模拟退火算法可以有效地改善所提出的MBBO算法的性能。

    • 运用MBBO算法求解分布式装配置换流水车间调度问题的900个小型实例,每个实例都独立运行5次,记录每次得到的算法最优值,利用ARPD值评估算法的性能。表4列出了Fn的15种不同组合分组的统计结果,每个组合都包含60个实例。取60个实例的平均ARPD值作为最终结果,并与H11、H12、H21、H22、H31、H32${{\rm{VND}}_{{{\rm{H}}_{11}}}}$${{\rm{VND}}_{{{\rm{H}}_{12}}}}$${{\rm{VND}}_{{{\rm{H}}_{21}}}}$${{\rm{VND}}_{{{\rm{H}}_{22}}}}$${{\rm{VND}}_{{{\rm{H}}_{31}}}}$${{\rm{VND}}_{{{\rm{H}}_{32}}}}$算法进行比较。这12个启发式算法都是用来解决DAPFSP问题的有效方法,各算法的结果直接从文献中获得[5]

      F×n ARPD
      H11 H12 H21 H22 H31 H32 VNDH11 VNDH12 VNDH21 VNDH22 VNDH31 VNDH32 BBO MBBO
      2×8 14.62 13.61 6.91 5.99 13.55 12.17 1.00 0.76 1.00 0.76 1.02 0.78 0.020 0.027
      2×12 13.70 12.78 5.74 5.17 11.58 11.05 0.93 0.87 0.93 0.87 0.93 0.87 0.177 0.182
      2×16 12.52 11.40 5.77 5.10 10.00 9.16 0.73 0.55 0.72 0.53 1.09 0.53 0.24 0.193
      2×20 10.23 9.59 4.55 3.78 8.96 8.46 0.53 0.36 0.51 0.37 0.57 0.37 0.226 -0.202
      2×24 8.71 8.34 5.00 4.74 7.54 7.15 0.54 0.21 0.54 0.21 0.54 0.21 0.194 -0.256
      3×8 11.35 9.96 4.57 3.15 8.92 7.79 1.09 0.70 1.15 0.76 1.15 0.76 0.022 0.006
      3×12 9.96 9.13 3.03 2.55 8.72 7.50 0.44 0.28 0.44 0.28 0.44 0.28 0.185 0.173
      3×16 10.10 9.16 3.77 3.14 9.59 8.73 0.86 0.56 0.91 0.56 0.91 0.56 0.218 0.11
      3×20 9.86 8.93 2.72 2.19 8.53 7.84 0.43 0.43 0.43 0.43 0.43 0.43 0.421 0.118
      3×24 7.77 6.48 3.11 2.52 7.24 6.32 0.64 0.33 0.64 0.33 0.64 0.33 0.38 0.038
      4×8 9.03 8.01 2.16 1.25 6.41 5.25 1.08 0.63 0.99 0.63 0.99 0.63 0 0
      4×12 5.63 4.53 1.82 1.38 4.58 3.58 0.74 0.47 0.74 0.47 0.74 0.56 0.17 0.041
      4×16 7.21 6.34 2.86 2.27 6.14 5.18 0.59 0.28 0.59 0.28 0.59 0.28 0.284 0.123
      4×20 6.80 6.00 2.96 2.61 5.66 5.04 1.10 0.63 1.10 0.63 1.10 0.63 0.269 0.128
      4×24 5.14 4.43 2.02 1.60 4.87 4.19 0.57 0.26 0.57 0.26 0.57 0.26 0.358 0.043
      Average 9.51 8.58 3.80 3.16 8.15 7.29 0.75 0.49 0.75 0.49 0.78 0.50 0.211 0.051

      表 4  小型实例平均ARPD值的结果对比

      Table 4.  Comparison of average ARPD values of small instances

      表4可以看出,对于所有的小型实例,MBBO算法获得的结果明显优于12个启发式算法,每个组合的平均ARPD值均远远小于12个启发式算法,且MBBO算法的平均值也远优于其他12个启发式算法。不仅如此,MBBO算法还更新了一些已知最佳方案,例如组合2×20和2×24的60个实例的ARPD平均值小于零。

      本文还将MBBO算法与BBO算法的运算结果进行了比较。由于BBO算法较为简单,运算速度快,因此对BBO算法的参数进行如下调整:P=100,mmax=0.1,MaxIterations=200,I=E=1,取P的10%作为保留的精英解。由表4可知,MBBO算法求解DAPFSP问题的效率明显高于BBO算法。在工厂数和工件数均较小的情况下(如2×8和2×12),BBO算法以初始栖息地和迭代次数多的优势,比MBBO算法略胜一筹,但差别并不大。而当工厂数和工件数增大之后,BBO算法便显出颓势,所得结果大不如MBBO算法。所以,针对DAPFSP问题,引入本文的3种策略能有效地改善基本BBO算法的性能,提高所得最优解的质量。

    • 针对分布式装配置换流水车间调度问题的540个大型实例,同样运用MBBO算法,将每个实例独立运行5次,记录每次得到的算法最优值,利用ARPD值评估算法的性能。表5列出了工件数n=100和n=200时的统计结果,每组都包含270个实例,最终结果为每组所有实例的ARPD平均值,然后与12个启发式算法以及BBO算法的结果进行比较。

      n ARPD
      H11 H12 H21 H22 H31 H31 H31 VNDH12 VNDH12 VNDH22 VNDH31 VNDH32 BBO MBBO
      100 6.30 5.61 0.17 0.08 2.02 2.02 2.02 0.02 0.02 0.01 0.03 0.01 0.274 0.015
      200 3.76 3.28 0.15 0.07 1.92 1.92 1.92 0.01 0.01 0.00 0.02 0.00 1.485 0.238
      Average 5.03 4.45 0.16 0.08 1.97 1.97 1.97 0.02 0.02 0.01 0.03 0.01 0.880 0.127

      表 5  大型实例平均ARPD值的结果对比

      Table 5.  Comparison of average ARPD values of large instances

      表5可以看出,当n=100时,MBBO算法有较大的优越性,其获得的大型实例的ARPD平均值要远小于H11、H12、H21、H22、H31、H32${{\rm{VND}}_{{{\rm{H}}_{11}}}}$${{\rm{VND}}_{{{\rm{H}}_{12}}}}$${{\rm{VND}}_{{{\rm{H}}_{21}}}}$${{\rm{VND}}_{{{\rm{H}}_{31}}}}$这10种启发式算法的结果。当工件个数上升到n=200时,MBBO算法获得的大型实例的ARPD平均值均优于H11、H12、H31、H32这4种启发式算法的结果,而比另外几种启发式算法稍显不足。在大规模的实例中,与BBO算法相比,MBBO算法显然更为合理、高效,两个算法结果的平均值相差0.753,MBBO算法优势显著。

      综上所述,利用MBBO算法求解DAPFSP问题时,针对ARPD平均值这个指标,在多数规模的实例上均效果良好,在某些实例上还找到了比已知方案更佳的结果。表6列出了小型实例和大型实例中MBBO算法更新的最佳方案。MBBO算法在初始化阶段利用SPT规则、NR2规则和“虚拟工件”改良初始解,缩小算法搜索解空间的范围,提高搜索效率。在变异阶段,根据各工厂完工时间的信息,采用基于工厂完工时间的工件插入启发式方法,优化工件的工厂分配及加工顺序。同时,结合模拟退火算法,跳出局部最优,提高了算法的搜索能力。MBBO算法是求解DAPFSP问题的一种有效算法。

      InstanceBest knownMBBOARPDInstanceBest knownMBBOARPD
      I_16_3_2_3_11 0411 039−0.175I_24_3_2_2_51 6851 679−0.356
      I_16_4_2_2_31 1461 143−0.262I_24_3_2_3_11 0771 075−0.186
      I_16_5_2_4_4836832−0.478I_24_3_2_3_21 4171 404−0.917
      I_20_2_2_2_2859857−0.234I_24_3_2_4_11 3231 320−0.227
      I_20_2_2_2_31 4621 460−0.137I_24_3_2_4_2755739−2.119
      I_20_2_2_3_21 2061 199−0.58I_24_3_3_2_21 2321 230−0.162
      I_20_2_2_4_31 2071 205−0.166I_24_3_3_2_4584578−1.027
      I_20_2_3_2_21 6271 626−0.061I_24_3_3_2_5856854−0.234
      I_20_3_2_2_1968961−0.723I_24_3_3_4_1918917−0.109
      I_20_3_2_2_3997982−1.505I_24_3_3_4_31 7381 734−0.23
      I_20_3_2_2_41 7221 718−0.232I_24_3_4_2_31 7531 748−0.285
      I_20_3_2_3_21 1211 111−0.892I_24_4_2_2_11 3501 338−0.889
      I_20_3_2_3_41 4821 4800.135I_24_4_2_2_21 3651 358−0.513
      I_20_4_2_2_11 2291 220−0.732I_24_4_2_2_5999975−2.402
      I_20_4_2_2_2862858−0.464I_24_4_2_3_31 7111 675−2.104
      I_20_4_2_2_41 6751 673−0.119I_24_4_3_2_21 6941 688−0.354
      I_20_4_2_2_51 3941 381−0.933I_24_4_3_2_32 4582 455−0.122
      I_20_4_2_3_2858826−3.73I_24_4_3_2_41 8441 839−0.271
      I_20_4_2_3_41 7251 716−0.522I_24_4_4_2_51 3561 355−0.074
      I_20_4_3_3_51 1371 129−0.703I_24_5_2_2_11 6251 615−0.615
      I_20_5_2_2_11 4781 474−0.271I_24_5_2_2_32 0492 024−0.244
      I_20_5_2_2_21 2581 253−0.397I_24_5_2_2_41 7641 758−0.34
      I_20_5_2_2_31 5001 479−1.4I_24_5_2_3_31 3401 333−0.522
      I_20_5_2_2_51 5891 587−0.063I_24_5_2_3_5914912−0.219
      I_20_5_2_3_21 1811 176−0.423I_24_5_2_4_21 0541 020−3.226
      I_20_5_2_3_31 4991 494−0.334I_24_5_2_4_31 6911 687−0.237
      I_24_2_2_2_2947944−0.317I_24_5_3_2_21 5181 489−1.91
      I_24_2_2_3_21 5141 491−1.519I_24_5_3_2_31 8901 886−0.212
      I_24_2_2_3_31 4951 492−0.2I_24_5_3_2_42 2872 279−0.35
      I_24_2_2_3_51 8611 856−0.269I_24_5_3_3_31 7611 759−0.114
      I_24_2_3_2_41 7061 705−0.059I_24_5_4_2_51 7921 777−0.837
      I_24_2_3_2_51 0841 082−0.185I_100_5_4_30_65 6645 659−0.088
      I_24_2_4_2_5563554−1.599I_100_10_4_30_56 2966 248−0.191
      I_24_3_2_2_11 7051 695−0.587I_100_20_4_40_15 5635 562−0.018
      I_24_3_2_2_3879876−0.341I_100_20_4_40_85 3935 365−0.519

      表 6  MBBO算法更新的最佳方案

      Table 6.  Best solutions updated by MBBO

    • 本文提出了一种改进的生物地理学优化算法及其应用于分布式装配置换流水车间调度问题的基本步骤。针对基本BBO算法的缺点,提出了3种改进策略:使用SPT规则和NR2规则初始化栖息地;在变异过程中加入基于工厂完工时间的工件插入启发式方法;加入模拟退火算法跳出局部最优。这3种改进策略提高了算法的搜索能力,改善了算法的寻优效果。通过900小型实例和540个大型实例的仿真计算,并与12个启发式算法以及BBO算法进行比较,验证了MBBO算法求解DAPFSP问题的有效性。

      本文针对分布式装配置换流水车间调度问题,采用改进的生物地理学优化算法进行求解,取得了较好的优化效果。今后可以从以下几个方面做进一步的研究。

      (1) 在迁移和变异操作过程中,MBBO算法只是针对迁移和变异的方式进行改进,没有对其根本的迁入率、迁出率和变异概率进行优化。可以考虑对迁移概率和变异概率的计算公式做出相应的改进,以提高算法的搜索能力。

      (2) 目前,利用启发式方法和智能优化算法求解分布式装配置换流水车间调度问题已经有了初步进展。可以考虑在DAPFSP问题的基础上进行拓展,进一步加深问题的复杂度,例如研究具有顺序相关准备时间的分布式装配置换流水车间调度问题等。

(7)  表(6) 参考文献 (19) 相关文章 (20)

目录

    /

    返回文章