高级检索

  • ISSN 1006-3080
  • CN 31-1691/TQ

离散水波优化算法求解带批处理的混合流水车间批量流调度问题

王文艳 徐震浩 顾幸生

王文艳, 徐震浩, 顾幸生. 离散水波优化算法求解带批处理的混合流水车间批量流调度问题[J]. 华东理工大学学报(自然科学版). doi: 10.14135/j.cnki.1006-3080.20200831001
引用本文: 王文艳, 徐震浩, 顾幸生. 离散水波优化算法求解带批处理的混合流水车间批量流调度问题[J]. 华东理工大学学报(自然科学版). doi: 10.14135/j.cnki.1006-3080.20200831001
WANG Wenyan, XU Zhenhao, GU Xingsheng. Discrete Water Wave Optimization Algorithm for Hybrid Flowshop Lot-Streaming Scheduling Problem with Batch Processing[J]. Journal of East China University of Science and Technology. doi: 10.14135/j.cnki.1006-3080.20200831001
Citation: WANG Wenyan, XU Zhenhao, GU Xingsheng. Discrete Water Wave Optimization Algorithm for Hybrid Flowshop Lot-Streaming Scheduling Problem with Batch Processing[J]. Journal of East China University of Science and Technology. doi: 10.14135/j.cnki.1006-3080.20200831001

离散水波优化算法求解带批处理的混合流水车间批量流调度问题

doi: 10.14135/j.cnki.1006-3080.20200831001
基金项目: 国家自然科学基金(61573144,61673175,61603139)
详细信息
    作者简介:

    王文艳(1994—),女,江苏淮安人,硕士生,研究方向为生产调度、智能算法。E-mail:2822986775@qq.com

    通讯作者:

    徐震浩,E-mail:xuzhenhao@ecust.edu.cn

  • 中图分类号: TP301

Discrete Water Wave Optimization Algorithm for Hybrid Flowshop Lot-Streaming Scheduling Problem with Batch Processing

  • 摘要: 针对实际生产系统中生产方式复杂多样的特点,研究了带批处理的混合流水车间批量流调度问题。综合考虑批处理机容量和不相关离散机加工能力,提出了一种可变分批方法,以最小化完工时间为目标建立了调度模型,并提出了一种动态连续加工策略来优化目标函数。同时提出了一种离散水波优化(DWWO)算法求解模型。结合分批特点与优化目标,设计了4种解码方式对机器选择及工件的加工顺序进行优化;利用块最优插入、交叉操作和多邻域搜索对操作算子进行改进,增强了局部搜索能力;提出了一种替换差解的操作来提高算法的收敛能力。最后,采用实验设计的方法对算法的参数进行了标定;并设计了不同规模的算例,对算法的性能进行评估。实验结果表明DWWO算法能够有效解决带批处理的混合流水车间批量流调度问题。

     

  • 图  1  参数水平影响趋势图

    Figure  1.  Trend graphs of influence of parameters

    图  2  加工序列为$ {\pi }_{1} $时两种策略下的甘特图

    Figure  2.  Gantt charts under two strategies when the processing sequence is $ {\pi }_{1} $

    图  3  各算法求解不同规模问题的迭代曲线

    Figure  3.  Iterative curves of each algorithm for solving problems of different scales

    表  1  不同解码方案对比结果

    Table  1.   Comparison results of different decoding schemes

    nmAVG
    IIIIIIIV
    641 224.01 220.01 231.01 222.0
    71 520.41 520.01 522.01 522.0
    102 200.02 200.02 200.02 200.0
    153 025.02967.03 140.03 058.0
    1041 605.01 605.01 605.01 605.0
    72 040.82 037.02 039.22 039.4
    102 844.52 832.02 884.32 832.0
    153 688.43 652.83 714.73 712.5
    1542 280.82 278.02 277.82 277.5
    72 719.02 719.02 790.32 786.8
    103 488.83 447.03 486.03 449.0
    154 400.94 344.04 462.94 397.2
    2042 968.02 968.02 968.02 968.0
    73 378.63 378.63 378.63 378.6
    104 436.64 326.04 435.04 381.0
    155 297.25 170.05 355.45 278.4
    3545 254.05 254.05 254.05 254.0
    76 010.66 009.06 011.46 009.8
    106 874.06 847.06 937.86 861.0
    157 753.87 686.47 842.87 786.4
    5047 681.07 681.07 681.07 681.0
    78 559.98 559.68 560.08 559.6
    109 307.49 256.89 326.89 301.6
    1510 175.410 094.410 247.410 226.8
    下载: 导出CSV

    表  2  两种策略下的实验结果对比

    Table  2.   Comparison of experimental results under two strategies

    nmAVG
    With dynamic continuous processingWithout dynamic continuous processing
    641 122.01 220.0
    71 376.51 520.0
    102 021.02 200.0
    152 742.82 967.0
    1041 531.01 605.0
    71 904.02 037.0
    102 658.02 832.0
    153 337.83 652.8
    1542 192.02 278.0
    72 642.02 719.0
    103 293.03 447.0
    153 983.64 344.0
    2042 888.02 968.0
    73 308.03 378.6
    104 202.04 326.0
    154 853.05 170.0
    3545 223.05 254.0
    75 891.06 009.0
    106 715.66 847.0
    157 377.67 686.4
    5047 622.07 681.0
    78 478.28 559.6
    109 145.29 256.8
    159 787.010 094.4
    下载: 导出CSV

    表  3  DWWO,FOA,MMBO,WWO,IGA_V算法对比结果

    Table  3.   Comparison results of DWWO, FOA, MMBO, WWO and IGA_V

    MRPD$ \times {10}^{2} $SDRPD$ \times {10}^{2} $BRPD$ \times {10}^{2} $
    nmDWWOFOAMMBOWWOIGA_VDWWOFOAMMBOWWOIGA_VDWWOFOAMMBOWWOIGA_V
    64000000000000000
    70.4000000.40000000000
    10000000000000000
    150.4000000.32000000000
    104000000000000000
    700.173.711.010.3200.080.600.640.32002.570.210
    10000.4100000.810000000
    150.260.321.470.580.340.320.230.420.290.33000.660.000
    15400.240.320.320.2500.12000.22000.320.320
    7003.440.640.07000.420.450.14002.990.000
    10000.7200000.590000000
    150.043.066.224.201.830.040.460.601.070.9402.345.152.110.60
    2040.030.150.820.610.070.030.240.260.36000.070.070.070.07
    701.372.581.540.7900.460.650.410.400.391.870.910.21
    10001.930.190000.110.250001.8600
    150.413.254.595.243.310.570.920.510.131.2302.054.015.031.63
    354000000000000000
    70.100.521.101.420.810.080.1900.270.6400.251.101.020.32
    100.440.591.491.190.580.220.070.130.180.1200.551.230.970.45
    150.272.134.254.072.120.250.480.470.670.8601.373.872.890.86
    5040000.120.050000.100.0600000
    70.010.171.090.692.080.020.120.150.261.7000.040.800.260.02
    100.080.460.931.320.850.060.220.100.290.4300.140.890.890.26
    150.342.403.824.442.830.250.6600.320.6001.383.823.941.74
    下载: 导出CSV
  • [1] 郝尚刚, 陈华平, 李小林. 两阶段流水车间批处理机调度的聚类算法[J]. 计算机工程, 2012, 38(14): 272-275. doi: 10.3969/j.issn.1000-3428.2012.14.081
    [2] QIN M, WANG R S, SHI Z S, et al. A genetic programming-based scheduling approach for hybrid flow shop with a batch processor and waiting time constraint[J]. IEEE Transactions on Automation Science and Engineering, 2019, 18(1): 94-105.
    [3] 张煜, 容芷君, 马杰. 含批处理机和多工件族的混合流水车间问题[J]. 计算机集成制造系统, 2014, 20(2): 407-413.
    [4] LIU M, YANG X N, ZHANG J T, et al. Scheduling a tempered glass manufacturing system: A three-stage hybrid flow shop model[J]. International Journal of Production Research, 2017, 55(19/20): 181-190.
    [5] 王君妍, 王薛苑, 轩华. 带批处理机的多阶段柔性流水车间调度优化[J]. 郑州大学学报(工学版), 2017, 38(5): 86-90.
    [6] 轩华, 王君妍, 王薛苑. 初始阶段为串行批处理的FFSP改进遗传算法[J]. 控制工程, 2018, 25(8): 1415-1420.
    [7] ZHANG B, PAN Q K, GAO L, et al. An effective modified migrating birds optimization for hybrid flowshop scheduling problem with lot streaming[J]. Applied Soft Computing, 2017, 52: 14-27. doi: 10.1016/j.asoc.2016.12.021
    [8] QIN W, ZHUANG Z L, LIU Y, et al. A two-stage ant colony algorithm for hybrid flow shop scheduling with lot sizing and calendar constraints in printed circuit board assembly[J]. Computers & Industrial Engineering, 2019, 138: 106115.
    [9] NEJATI M, MAHDAVI I, HASSANZADEH R, et al. Multi-job lot streaming to minimize the weighted completion time in a hybrid flow shop scheduling problem with work shift constraint[J]. International Journal of Advanced Manufacturing Technology, 2014, 70(1/4): 501-514.
    [10] WANG S S, KURZ M, MASON S J, et al. Two-stage hybrid flow shop batching and lot streaming with variable sublots and sequence-dependent setups[J]. International Journal of Production Research, 2019, 57(22): 1-15.
    [11] ZHENG Y J. Water wave optimization: A new nature-inspired metaheuristic[J]. Computers and Operations Research, 2015, 55: 1-11. doi: 10.1016/j.cor.2014.10.008
    [12] ZHAO F Q, LIU H, ZHANG Y. A discrete water wave optimization algorithm for no-wait flow shop scheduling problem[J]. Expert Systems with Applications, 2018, 91: 347-363. doi: 10.1016/j.eswa.2017.09.028
    [13] LAKSHMINARASIMMAN L, SIVA M, BALAMURUGAN R. Water wave optimization algorithm for solving multi-area economic dispatch problem[J]. International Journal of Computer Applications, 2017, 167(5): 19-27. doi: 10.5120/ijca2017914247
    [14] SIVA M, BALAMURUGAN R, LAKSHMINARASIMMAN L. Water wave optimization algorithm for solving thermal unit maintenance scheduling[J]. IOSR Journal of Electrical and Electronics Engineering, 2017, 12(3): 61-70. doi: 10.9790/1676-1203026170
    [15] 任彩乐. 基于候鸟优化算法的混合流水车间调度问题研究[D]. 武汉: 华中科技大学, 2019.
    [16] 崔琪, 吴秀丽, 余建军. 变邻域改进遗传算法求解混合流水车间调度问题[J]. 计算机集成制造系统, 2017, 23(9): 1917-1927.
    [17] NAWAZ M, ENSCORE J E, HAM I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem[J]. Omega, 1983, 11(1): 91-95. doi: 10.1016/0305-0483(83)90088-9
    [18] 陈飞跃, 徐震浩, 顾幸生. 基于离散布谷鸟搜索算法的带阻塞有差速混合流水车间调度[J]. 华东理工大学学报 (自然科学版), 2017, 43(3): 425-435.
    [19] 刘欢. 水波优化算法及在车间调度问题中的应用研究[D]. 兰州: 兰州理工大学, 2018.
    [20] 杜利珍, 王震, 柯善富, 等. 混合流水车间调度问题的果蝇优化算法求解[J]. 中国机械工程, 2019, 30(12): 1480-1485. doi: 10.3969/j.issn.1004-132X.2019.12.015
    [21] ZHANG B, PAN Q K, GAO L, et al. A multi-objective migrating birds optimization algorithm for the hybrid flowshop rescheduling problem[J]. Soft Computing, 2019, 23: 8101-8129. doi: 10.1007/s00500-018-3447-8
  • 加载中
图(3) / 表(3)
计量
  • 文章访问数:  719
  • HTML全文浏览量:  391
  • PDF下载量:  4
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-08-31
  • 网络出版日期:  2020-12-16

目录

    /

    返回文章
    返回