2.793

2018影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

混合离散教与学算法求解复杂并行机调度问题

何雨洁 钱斌 胡蓉

何雨洁, 钱斌, 胡蓉. 混合离散教与学算法求解复杂并行机调度问题. 自动化学报, 2020, 46(4): 805-819. doi: 10.16383/j.aas.c180321
引用本文: 何雨洁, 钱斌, 胡蓉. 混合离散教与学算法求解复杂并行机调度问题. 自动化学报, 2020, 46(4): 805-819. doi: 10.16383/j.aas.c180321
HE Yu-Jie, QIAN Bin, HU Rong. Hybrid Discrete Teaching-learning-based Optimization Algorithm for Solving Complex Parallel Machine Scheduling Problem. ACTA AUTOMATICA SINICA, 2020, 46(4): 805-819. doi: 10.16383/j.aas.c180321
Citation: HE Yu-Jie, QIAN Bin, HU Rong. Hybrid Discrete Teaching-learning-based Optimization Algorithm for Solving Complex Parallel Machine Scheduling Problem. ACTA AUTOMATICA SINICA, 2020, 46(4): 805-819. doi: 10.16383/j.aas.c180321

混合离散教与学算法求解复杂并行机调度问题


DOI: 10.16383/j.aas.c180321
详细信息
    作者简介:

    何雨洁  昆明理工大学信息工程与自动化学院硕士研究生. 2016年获得昆明理工大学信息工程与自动化学院自动化系学士学位.主要研究方向为调度与智能优化算法. E-mail: Hyujie_one@163.com

    胡蓉  昆明理工大学信息工程与自动化学院副教授. 2004年获得清华大学自动化系硕士学位.主要研究方向为优化方法和决策支持系统.E-mail: ronghu@vip.163.com

    通讯作者: 钱斌  昆明理工大学信息工程与自动化学院教授. 2009年获得清华大学自动化系博士学位.主要研究方向为调度与优化.本文通信作者.E-mail: bin.qian@vip.163.com
  • 本文责任编委 阳春华
  • 基金项目:

    国家自然科学基金 51665025

    国家自然科学基金 61963022

    云南省自然科学基金项目 2015FB136

Hybrid Discrete Teaching-learning-based Optimization Algorithm for Solving Complex Parallel Machine Scheduling Problem

More Information
    Author Bio:

    HE Yu-Jie   Master student at the School of Information Engineering and Automation, Kunming University of Science and Technology. She received her bachelor degree from Kunming University of Science and Technology in 2016. Her research interest covers scheduling and intelligent optimization algorithms

    HU Rong   Associate professor at the School of Information Engineering and Automation, Kunming University of Science and Technology. She received her master degree from Tsinghua University in 2004. Her research interest covers optimization methods and decision support systems

    Corresponding author: QIAN Bin   Professor at the School of Information Engineering and Automation, Kunming University of Science and Technology. He received his Ph. D. degree from Tsinghua University in 2009. His research interest covers scheduling and optimization. Corresponding author of this paper
  • Recommended by Associate Editor YANG Chun-Hua
  • Fund Project:

    National Natural Science Foundation of China 51665025

    National Natural Science Foundation of China 61963022

    Applied Basic Research Foundation of Yunnan Province 2015FB136

  • 摘要: 针对制造行业中广泛存在的一类复杂并行机调度问题, 即带到达时间、多工序、加工约束和序相关设置时间的并行机调度问题(Parallel machine scheduling problem with arrival time, multiple operations, process restraints and sequence-dependent setup times, PMSP_AMPS), 建立问题的排序模型并提出一种混合离散教与学优化算法进行求解, 优化目标为最小化最大完工时间.首先, 根据标准教与学算法(Teaching-learning-based optimization, TLBO)中两阶段个体更新公式的特点, 在保留每一阶段个体更新公式框架不变的前提下, 对公式中具体改变实数个体或向量的每个核心操作均用所设计的排列操作进行替换, 使其可直接在离散问题解空间中执行基于标准教与学算法机理的全局搜索, 从而明显提高了原算法的全局搜索效率.其次, 采用交换操作和插入操作构造了一种简洁有效地变邻域局部搜索, 对全局搜索发现的优质解区域进行细致搜索, 从而进一步增强了算法的性能.通过对不同测试问题的仿真实验和算法比较, 验证了所提算法可有效求解PMSP_AMPS.
    本文责任编委 阳春华
    Recommended by Associate Editor YANG Chun-Hua
  • 图  1  工序为$ \pi $ = [1 3 2 5 4 1 3 1 3 4]时的甘特图

    Fig.  1  The Gantt chart of $ \pi $ = [1 3 2 5 4 1 3 1 3 4]

    图  2  基于顺序的交叉法

    Fig.  2  The order-based crossover (OBX)

    图  3  顺序交叉法

    Fig.  3  Order crossover (OX)

    图  4  HDTLBO流程图

    Fig.  4  HDTLBO's flow chart

    图  5  各参数响应趋势

    Fig.  5  The influence trend of each parameter

    图  6  各算法在不同时间参数下的均值线及95 %置信度下Tukey$'$s HSD检验的置信区间

    Fig.  6  Means plot and 95 % Tukey$'$s HSD confidence intervals for the interaction between the algorithms and the different time factor $ \rho $

    图  7  各算法在不同时间参数下的均值线及95 %置信度下Tukey$'$s HSD检验的置信区间

    Fig.  7  Means plot and 95 % Tukey$'$s HSD confidence intervals for the interaction between the algorithms and the different time factor $ \rho $

    表  1  工序加工约束、序相关设置时间和工件到达时间表($ \pi $ = [1  3  2  5  4  1  3  1  3  4])

    Table  1  The schedule of process constraint, sequence setup time and arrival time ($ \pi $ = [1 3 2 5 4 1 3 1 3 4])

    可执行操作的设备 序相关设置时间 首次到达设备的时间
    操作1 操作2 操作3 工件1 工件2 工件3 工件4 工件5 m1 m2 m3
    工件1 m1/m2 m1/m2/m3 m1/m3 83 38 39 47 35 34 23
    工件2 m1 53 66 45 25 38 78 98
    工件3 m3 m2/m3 m2 64 57 72 46 52 23 32
    工件4 m1/m3 m1 46 67 83 55 132 131 98
    工件5 m1/m3 40 66 83 77 114 99 112
    下载: 导出CSV

    表  2  工件加工时间表($ \pi $ =  [1 3 2 5 4 1 3 1 3 4]) ($t$/s)

    Table  2  The processing time table ($ \pi $ =  [1 3 2 5 4 1 3 1 3 4]) ($t$/s)

    操作1 操作2 操作3
    m1 m2 m3 m1 m2 m3 m1 m2 m3
    工件1 62 44 78 86 26 48 87
    工件2 41
    工件3 31 58 65 42
    工件4 32 31 27
    工件5 74 36
    下载: 导出CSV

    表  3  参数水平设置表

    Table  3  Combinations of parameter values

    参数 水平
    1 2 3 4
    $ popsize $ 10 20 30 40
    $ TF $ 0 1 2 3
    $ r_{m} $ 0.1 0.4 0.7 0.9
    下载: 导出CSV

    表  4  正交表和AVG统计

    Table  4  Orthogonal array and AVG

    参数组合 水平 $ AVG $
    $ popsize $ $ TF $ $ r_{m} $
    1 1 1 1 500.65
    2 1 2 2 503.90
    3 1 3 3 497.30
    4 1 4 4 498.55
    5 2 1 2 489.35
    6 2 2 3 491.20
    7 2 3 4 485.50
    8 2 4 1 488.35
    9 3 1 3 482.55
    10 3 2 4 481.80
    11 3 3 1 482.25
    12 3 4 2 483.25
    13 4 1 4 483.35
    14 4 2 1 484.00
    15 4 3 2 483.60
    16 4 4 3 482.20
    下载: 导出CSV

    表  5  各参数响应值

    Table  5  Average response value and rank of each parameter

    水平 $ popsize $ $ TF $ $ r_{m} $
    1 500.10 488.98 488.81
    2 488.60 490.23 490.02
    3 482.46 487.16 488.31
    4 483.29 488.09 487.30
    等级 1 3 2
    下载: 导出CSV

    表  6  DTLBO与PSO、DTLBO-Ⅰ、标准TLBO和CIWO的比较($ \rho =4 $)

    Table  6  Comparisons of DTLBO, DTLBO-Ⅰ, PSO, CIWO, and standard TLBO ($ \rho =4 $)

    测试问题 PSO DTLBO-Ⅰ 标准TLBO CIWO DTLBO
    BST WST AVG BST WST AVG BST WST AVG BST WST AVG BST WST AVG
    10$ \times $5 229 235 230.15 228 231 229.45 228 233 230.05 227 246 229.95 227 244 229.3
    20$ \times $5 560 587 576.7 546 579 560.3 558 589 574.5 503 554 526.5 506 534 521.4
    30$ \times $5 682 708 694.8 638 685 662.3 675 709 697 615 665 635.5 607 638 622.4
    40$ \times $5 752 784 771.4 696 748 725.7 728 787 767.75 654 716 690.05 661 716 692.8
    50$ \times $5 1 132 1 171 1 157.45 1 093 1 140 1 114.3 1148 1 175 1 161.5 1 019 1 091 1 059.2 1 019 1 078 1 051.85
    40$ \times $10 340 357 348.2 307 336 321.3 340 360 351.15 293 326 311.9 284 317 304.3
    50$ \times $10 410 429 419.7 373 411 392.75 413 429 421.1 362 391 376.3 353 386 370.75
    60$ \times $10 523 548 538.8 497 529 516 538 552 544.3 485 516 499.95 481 516 500.6
    70$ \times $10 658 682 672 626 653 641.8 660 684 672.65 604 639 622 597 636 621.75
    80$ \times $10 596 619 612.15 567 601 585.55 597 621 612.95 553 589 571.45 553 584 569.5
    80$ \times $20 286 298 292.2 265 289 278.85 285 298 291.8 257 282 271.65 259 272 264.7
    90$ \times $20 287 299 294.65 271 289 280.55 288 301 297.4 255 284 273.1 255 279 269.05
    100$ \times $20 329 340 336 309 328 320.5 333 343 338 304 323 312.65 299 313 306.25
    150$ \times $20 479 496 489.2 460 486 472 487 499 492.9 454 476 464.95 449 477 458.45
    200$ \times $20 575 593 587.25 557 576 568.5 577 598 589.85 559 575 564.4 547 559 549.55
    Average 522.53 543.06 534.71 495.53 525.4 511.32 523.66 545.2 536.19 476.27 511.53 493.97 473.13 503.27 488.84
    下载: 导出CSV

    表  7  HDTLBO与DPSO、DTLBO-Ⅱ、GA_DR_C和CCIWO的比较($ \rho =4 $)

    Table  7  Comparisons of HDTLBO, DPSO, DTLBO-Ⅱ, GA_DR_C, and CCIWO ($ \rho =4 $)

    测试问题 DPSO DTLBO-Ⅱ GA_DR_C CCIWO HDTLBO
    BST WST AVG BST WST AVG BST WST AVG BST WST AVG BST WST AVG
    10$ \times $5 227 230 228.75 227 230 228.45 227 230 228.2 227 230 228.2 227 230 227.3
    20$ \times $5 521 547 527.15 533 554 543.1 514 551 536.15 494 536 518.1 499 540 520.95
    30$ \times $5 612 647 624.1 630 658 645.65 625 656 645.85 617 644 621.95 603 638 617.5
    40$ \times $5 652 692 686.75 695 733 710.15 695 735 715.8 657 715 686.15 645 692 681.65
    50$ \times $5 1 014 1 074 1 058.4 1 064 1 111 1 090 1 070 1107 1 094.75 1 024 1 088 1 057.05 1 006 1 055 1 035.9
    40$ \times $10 303 317 306.14 303 328 316.2 305 325 316.4 292 320 307.7 290 316 303.65
    50$ \times $10 365 387 370.95 370 395 387.95 374 400 388.2 362 390 373.85 355 382 369
    60$ \times $10 481 503 498.85 498 519 510.9 497 584 541.15 481 515 496.6 481 501 493.05
    70$ \times $10 601 639 615.4 626 656 640.15 636 716 694.55 597 639 621.7 597 635 606.75
    80$ \times $10 556 590 579 571 596 584.55 561 590 582.75 548 586 568.45 554 575 564.85
    80$ \times $20 274 285 277.41 269 285 278 273 285 279.9 275 280 269.3 262 279 273.7
    90$ \times $20 269 290 273.33 275 288 282.1 277 292 285.8 268 285 276.25 266 282 272.58
    100$ \times $20 304 323 313.7 313 327 320.85 317 328 322.85 300 323 314.6 297 323 310.65
    150$ \times $20 472 489 475.34 469 486 476.45 470 488 480.55 469 486 470.7 464 483 469.89
    200$ \times $20 553 579 566.5 564 579 573 562 587 578.1 557 583 570.05 549 579 565.2
    Average 480.27 506.13 493.45 493.8 516.33 505.83 493.53 524.93 521.73 477.87 508 492.04 473 500.67 487.51
    下载: 导出CSV

    表  8  模具各工序加工约束及首次到达时间表

    Table  8  The schedule of mold process constraint and arrival time

    模具 可执行操作的设备 模具首次到达设备时间
    操作1 操作2 操作3 m1 m2 m3 m4 m5
    1 m1/m3/m5 m3/m4 m2/m3/m4 7 4 8 4 6
    2 m1/m3/m6 m1 1 6 2 3 3
    3 m3 3 1 8 4 6
    4 m2/m3/m5 m1/m2/m3/m4/m5 m2/m3/m4 8 1 6 8 7
    5 m1/m3/m4 1 2 6 7 3
    6 m2/m5 m1/m4/m5 m1/m4/m5 5 8 3 1 5
    7 m2/m4/m5 m2/m3/m4/m5 3 8 3 3 6
    8 m1/m2/m3/m5 2 6 8 7 7
    9 m4/m5 m3 m3/m4 6 3 5 3 7
    10 m2 m2/m4 m1/m2/m3 7 4 1 4 6
    11 m1/m5 m1 6 5 1 8 4
    12 m4/m5 m1/m2/m3/m4/m5 m1/m2/m4 5 3 1 8 8
    13 m2/m4/m5 m3 m4/m5 7 1 6 6 6
    14 m3 m1/m3/m5 2 1 4 6 3
    15 m3/m4/m5 8 6 5 3 2
    16 m1/m3 m3 8 6 6 7 2
    17 m3 8 4 6 7 1
    18 m4/m5 m2/m4 m5 4 3 5 2 6
    19 m1/m2/m4/m5 3 6 2 1 3
    20 m1/m4 m3/m5 m2/m4/m5 4 7 5 7 7
    下载: 导出CSV

    表  9  各模具产品的序相关设置时间表

    Table  9  The schedule of sequence setup time between each mold

    模具 序相关设置时间
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
    1 2 3 3 4 3 3 3 3 2 1 3 1 4 4 4 2 4 2 1
    2 2 2 2 3 2 2 1 3 1 2 2 4 4 3 3 4 4 2 4
    3 2 3 4 3 3 4 2 1 2 3 3 1 4 2 1 3 3 4 3
    4 3 1 3 4 1 4 2 2 2 1 1 4 1 3 2 2 1 2 3
    5 4 4 4 2 1 1 1 4 1 1 1 3 2 1 3 2 4 3 3
    6 1 2 3 2 3 3 2 2 3 4 1 1 3 3 2 4 2 4 1
    7 3 4 4 4 1 2 1 1 4 2 2 3 2 2 2 4 1 1 2
    8 4 2 4 1 4 1 2 4 3 3 3 2 4 1 3 4 1 4 1
    9 4 2 3 3 2 4 4 1 2 2 3 2 1 2 4 2 1 4 3
    10 2 4 1 2 2 4 4 3 3 1 1 2 3 1 2 1 4 2 1
    11 3 4 3 2 2 2 1 2 2 2 2 4 3 3 2 1 2 2 2
    12 2 1 4 2 4 2 3 2 1 2 3 1 1 3 2 3 2 1 2
    13 2 1 2 4 2 1 4 2 4 2 4 3 4 4 3 4 3 4 1
    14 4 4 1 3 2 2 2 4 1 4 1 2 1 2 2 1 3 4 1
    15 3 2 2 3 1 2 3 4 3 1 2 1 3 1 2 3 1 4 4
    16 1 4 1 1 4 3 1 3 1 2 4 4 2 3 4 4 4 4 1
    17 4 3 1 1 3 2 3 1 3 4 1 1 3 2 1 1 2 1 1
    18 1 2 4 4 2 1 4 1 2 1 4 4 3 2 1 3 1 2 2
    19 2 3 2 2 2 3 4 1 1 3 2 2 2 3 3 2 4 1 2
    20 2 2 2 2 2 2 2 1 2 1 2 4 1 4 1 1 1 4 1
    下载: 导出CSV

    表  10  模具各工序的加工时间表

    Table  10  The processing time table of each mold

    模具 操作1 操作2 操作3
    m1 m2 m3 m4 m5 m1 m2 m3 m4 m5 m1 m2 m3 m4 m5
    1 27 18 29 27 17 23 29 19
    2 13 26 11 13
    3 23
    4 10 13 12 18 25 11 10 26 21 31 27
    5 9 8 16
    6 9 29 19 25 10 30 26 19
    7 19 22 28 10 28 24 27
    8 30 23 28 17
    9 31 24 9 8 28
    10 25 27 13 31 20 26
    11 25 24 12
    12 23 17 13 16 22 8 30
    13 16 19 22 28 27 23
    14 28 16 20 18 16 16 21
    15 28 29 23
    16 27 10 8
    17 26
    18 12 24 13 27 17
    19 24 19 12 14
    20 17 10 31 20 30 9 24
    下载: 导出CSV

    表  11  实例仿真结果

    Table  11  Simulation results of the instance

    运行次数 DTLBO-Ⅱ GA DPSO CCIWO HDTLBO
    1 167 166 166 163 163
    2 164 166 164 163 166
    3 168 167 167 167 167
    4 169 166 164 166 163
    5 163 163 165 163 165
    6 167 165 166 167 163
    7 167 168 163 168 166
    8 166 168 167 164 168
    9 168 167 164 163 163
    10 169 168 165 164 165
    11 168 163 164 168 166
    12 169 168 169 167 163
    13 168 167 165 166 167
    14 163 170 166 170 166
    15 167 166 168 169 163
    16 166 167 166 171 163
    17 167 170 163 168 163
    18 169 168 164 170 165
    19 165 168 163 165 168
    20 167 168 164 167 163
    Average 166.85 166.95 165.15 166.45 164.8
    下载: 导出CSV
  • [1] Pinedo M. Scheduling: theory, algorithms, and systems. Berlin Heidelberg: Springer, 2012.
    [2] Allahverdi A. Two-machine proportionate flowshop scheduling with breakdowns maximum lateness. Computers & Operations Research, 1996, 23(10): 909-916
    [3] Lan X J, Su D D. Research of a mold job shop scheduling optimization based on particle swarm optimization algorithm. Applied Mechanics & Materials, 2015, 757(2): 201-207 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=10.4028/www.scientific.net/AMM.757.201
    [4] Sang H Y, Duan P Y, Li J Q. An effective invasive weed optimization algorithm for scheduling semiconductor final testing problem. Swarm & Evolutionary Computation, 2018, 38: 42-53 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=f24ee1e67ed4add61940b0e69b5f0a53
    [5] Hu H, Ng KKH, Qin Y C. Robust parallel machine scheduling problem with uncertainties and sequence-dependent setup time. Scientific Programming, 2016: 1-13
    [6] Li C L, Cheng T C E. The parallel machine min-max weighted absolute lateness scheduling problem. Naval Research Logistics, 1994, 41(1): 33-46 doi:  10.1002/1520-6750(199402)41:1<33::AID-NAV3220410104>3.0.CO;2-S
    [7] Ranjbar M, Davari M, Leus R. Two branch-and-bound algorithms for the robust parallel machine scheduling problem. Computers & Operations Research, 2012, 39(7): 1652-1660 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=58dbb13e91377bee19b577c7d4561726
    [8] Lee W C, Wang J Y, Lin M C. A branch-and-bound algorithm for minimizing the total weighted completion time on parallel identical machines with two competing agents. Knowledge-Based Systems, 2016, 105(C): 68-82 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=90998daca3d98ce1fbd2b119fbae1b4a
    [9] Wu L, Wang S. Exact and heuristic methods to solve the parallel machine scheduling problem with multi-processor tasks. International Journal of Production Economics, 2018, 201: 26-40 doi:  10.1016/j.ijpe.2018.04.013
    [10] Chen Z L, Powell W B. A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem. European Journal of Operational Research, 1999, 116(1): 220-232 doi:  10.1016/S0377-2217(98)00136-2
    [11] Yin Y, Ye D, Zhang G. Single machine batch scheduling to minimize the sum of total flow time and batch delivery cost with an unavailability interval. Information Sciences, 2014, 274(8): 310-322 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=057211486faaa3fa789b3f4b9a751866
    [12] Li D W, Lu X W. Two-agent parallel-machine scheduling with rejection. Theoretical Computer Science, 2017, 703: 66-75 doi:  10.1016/j.tcs.2017.09.004
    [13] Yin Y, Cheng S R, Cheng T C E, et al. Just-in-time scheduling with two competing agents on unrelated parallel machines. Omega, 2016, 63: 41-47 doi:  10.1016/j.omega.2015.09.010
    [14] Woo Y B, Jung S, Kim B S. A rule-based genetic algorithm with an improvement heuristic for unrelated parallel machine scheduling problem with time-dependent deterioration and multiple rate-modifying activities. Computers & Industrial Engineering, 2017, 109: 179-190 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=f0a6c39ef977f0f9c653802880bf2420
    [15] Avalos-Rosales O, Angel-Bello F, Alvarez A. Efficient metaheuristic algorithm and re-formulations for the unrelated parallel machine scheduling problem with sequence and machine-dependent setup times. International Journal of Advanced Manufacturing Technology, 2015, 76(9-12): 1705-1718 doi:  10.1007/s00170-014-6390-6
    [16] 张嘉琦, 曹政才, 刘民.融合代理模型和差分进化算法的并行机动态调度方法.计算机集成制造系统, 2017, 23(1): 75-81 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt201701009

    Zhang Jia-Qi, Cao Zheng-Cai, Liu Min. Integrated differential evolution algorithm with surrogate model for dynamic parallel machine scheduling. Computer Integrated Manufacturing Systems, 2017, 23(1): 75-81 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt201701009
    [17] Chen C L. Iterated hybrid metaheuristic algorithms for unrelated parallel machines problem with unequal ready times and sequence-dependent setup times. International Journal of Advanced Manufacturing Technology, 2012, 60(5-8): 693-705 doi:  10.1007/s00170-011-3623-9
    [18] Damodaran P, Diyadawagamage D A, Ghrayeb O. A particle swarm optimization algorithm for minimizing makespan of nonidentical parallel batch processing machines. International Journal of Advanced Manufacturing Technology, 2012, 58(9-12): 1131-1140 doi:  10.1007/s00170-011-3442-z
    [19] Diana R O M. An immune-inspired algorithm for an unrelated parallel machines$'$ scheduling problem with sequence and machine dependent setup-times for makespan minimisation. Neurocomputing, 2015, 163(C): 94-105
    [20] Sels V, Coelho J, Dias A M, et al. Hybrid tabu search and a truncated branch-and-bound for the unrelated parallel machine scheduling problem. Computers & Operations Research, 2015, 53: 107-117 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=a7d0c31a9a95e9f1ce534a14dda1cdb2
    [21] Bitar A, Yugma C, Roussel R. A memetic algorithm to solve an unrelated parallel machine scheduling problem with auxiliary resources in semiconductor manufacturing. Journal of Scheduling, 2016, 19(4): 367-376 doi:  10.1007/s10951-014-0397-6
    [22] Joo C M, Kim B S. Hybrid genetic algorithms with dispatching rules for unrelated parallel machine scheduling with setup time and production availability. Computers & Industrial Engineering, 2015, 85(C): 102-109 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=fcb17bbd465d8682d2400ec1e2f8025a
    [23] 罗家祥, 唐立新.带释放时间的并行机调度.问题的ILS & SS算法.自动化学报, 2005, 31(6): 917-924 http://www.aas.net.cn/article/id/15921

    Luo Jia-Xiang, Tang Li-Xin. A new ILS & SS algorithm for parallel-machine scheduling problem. Acta Automatica Sinica, 2005, 31(6): 917-924 http://www.aas.net.cn/article/id/15921
    [24] Lin S W, Ying K C. ABC-based manufacturing scheduling for unrelated parallel machines with machine-dependent and job sequence-dependent setup times. Computers & Operations Research, 2014, 51(3): 172-181 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=5b16d15a9448bceeb8e453a1f542ce32
    [25] Rao R V, Savsani V J. and Vakharia D P. Teaching- learning-based optimization: a novel method for constrained mechanical design optimization problems. Computer-Aided Design, 2011, 43(3): 303-315 doi:  10.1016/j.cad.2010.12.015
    [26] Waghmare, G. Comments on "a note on teaching-learning-based optimization algorithm". Information Sciences, 2013, 229: 159-169 doi:  10.1016/j.ins.2012.11.009
    [27] Shao S W, Pi D C, Shao Z. An extended teaching-learning based optimization algorithm for solving no-wait flow shop scheduling problem. Applied Soft Computing, 2017, 61: 193-210 doi:  10.1016/j.asoc.2017.08.020
    [28] Xu Y, Wang L, Wang S Y, et al. An effective teaching--learning-based optimization algorithm for the flexible job-shop scheduling problem with fuzzy processing time. Neurocomputing, 2015, 148: 260-268 doi:  10.1016/j.neucom.2013.10.042
    [29] Shao S W, Pi D C, Shao Z. A hybrid discrete optimization algorithm based on teaching-probabilistic learning mechanism for no-wait flow shop scheduling. Knowledge-Based Systems, 2016, 107: 219-234 doi:  10.1016/j.knosys.2016.06.011
    [30] Li J Q, Pan Q K, Mao K. A discrete teaching-learning-based optimisation algorithm for realistic flowshop rescheduling problems. Engineering Applications of Artificial Intelligence, 2015, 37: 279-292 doi:  10.1016/j.engappai.2014.09.015
    [31] 马永杰, 云文霞.遗传算法研究进展.计算机应用研究, 2012, 29(4): 1201-1206 doi:  10.3969/j.issn.1001-3695.2012.04.001

    Ma Yong-Jie, Yun Wen-Xia. Research progress of genetic algorithm. Application Rehash of Computers, 2012, 29(4): 1201-1206 doi:  10.3969/j.issn.1001-3695.2012.04.001
    [32] Abdoun O, Abouchabaka J. A comparative study of adaptive crossover operators for genetic algorithms to resolve the traveling salesman problem. Computer Science, 2011, 31(11): 49-57
    [33] 王凌, 钱斌.混合差分进化与调度算法.北京:清华大学出版社, 2012.

    Wang Ling, Qian Bin. Hybrid differential evolution and scheduling algorithms. Beijing: Tsinghua University Press, 2012.
    [34] 潘全科, 王凌, 赵保华.解决零空闲流水线调度问题的离散粒子群算法.控制与决策, 2008, 23(2): 191-194 doi:  10.3321/j.issn:1001-0920.2008.02.014

    Pan Quan-Ke, Wang Ling, Zhao Bao-Hua. Discrete particle swarm optimization for no-idle flow shop problem. Control and Decision, 2008, 23(2): 191-194 doi:  10.3321/j.issn:1001-0920.2008.02.014
  • [1] 徐君, 张国良, 曾静, 孙巧, 羊帆. 具有时延和切换拓扑的高阶离散时间多智能体系统鲁棒保性能一致性[J]. 自动化学报, 2019, 45(2): 360-373. doi: 10.16383/j.aas.2017.c160758
    [2] 谢志强, 张晓欢, 辛宇, 杨静. 考虑后续工序的择时综合调度算法[J]. 自动化学报, 2018, 44(2): 344-362. doi: 10.16383/j.aas.2018.c160562
    [3] 盖彦荣, 陈阳舟, 张亚霄. 切换信息拓扑和时变时滞下离散时间线性多智能体系统一致性的平均驻留时间条件[J]. 自动化学报, 2014, 40(11): 2609-2617. doi: 10.3724/SP.J.1004.2014.02609
    [4] 王大志, 刘士新, 郭希旺. 求解总拖期时间最小化流水车间调度问题的多智能体进化算法[J]. 自动化学报, 2014, 40(3): 548-555. doi: 10.3724/SP.J.1004.2014.00548
    [5] 杨洪勇, 郭雷, 张玉玲, 姚秀明. 离散时间分数阶多自主体系统的时延一致性[J]. 自动化学报, 2014, 40(9): 2022-2028. doi: 10.3724/SP.J.1004.2014.02022
    [6] 韩敏, 许美玲, 任伟杰. 多元混沌时间序列的相关状态机预测模型研究[J]. 自动化学报, 2014, 40(5): 822-829. doi: 10.3724/SP.J.1004.2014.00822
    [7] 穆朝絮, 余星火, 孙长银. 非奇异终端滑模控制系统相轨迹和暂态分析[J]. 自动化学报, 2013, 39(6): 902-908. doi: 10.3724/SP.J.1004.2013.00902
    [8] 黄勤珍. 离散时间多智能体系统的一致性[J]. 自动化学报, 2012, 38(7): 1127-1133. doi: 10.3724/SP.J.1004.2012.01127
    [9] 谢志强, 滕宇峥, 杨静. 紧密衔接工序组联动的综合调度算法[J]. 自动化学报, 2011, 37(3): 371-379. doi: 10.3724/SP.J.1004.2011.00371
    [10] 曾莉, 胡广大. 带输入延时的连续时间系统的离散化[J]. 自动化学报, 2010, 36(10): 1426-1431. doi: 10.3724/SP.J.1004.2010.01426
    [11] 车伟伟, 杨光红. 离散时间系统量化动态输出反馈的H控制[J]. 自动化学报, 2008, 34(6): 652-658. doi: 10.3724/SP.J.1004.2008.00652
    [12] 于艾清, 顾幸生. 基于耦合瞬态混沌神经网络的同等并行机调度[J]. 自动化学报, 2008, 34(6): 697-701. doi: 10.3724/SP.J.1004.2008.00697
    [13] 赵玉芳, 唐立新. 释放时间和工期同序的单机连续型批调度问题[J]. 自动化学报, 2008, 34(8): 957-963. doi: 10.3724/SP.J.1004.2008.00957
    [14] 李俊领, 解学军. 离散时间直接型模型参考自适应控制[J]. 自动化学报, 2007, 33(10): 1048-1052. doi: 10.1360/aas-007-1048
    [15] 罗家祥, 唐立新. 带释放时间的并行机调度问题的ILS & SS算法[J]. 自动化学报, 2005, 31(6): 917-924.
    [16] 衣杨, 汪定伟. 软计算求解并行多机成组工件提前/拖期惩罚调度问题[J]. 自动化学报, 2002, 28(5): 862-864.
    [17] 翟长连, 吴智铭. 不确定离散时间系统的变结构控制设计[J]. 自动化学报, 2000, 26(2): 184-191.
    [18] 刘民, 吴澄. 解决并行多机提前/拖后调度问题的混合遗传算法方法[J]. 自动化学报, 2000, 26(2): 258-262.
    [19] 杨保民, 孙翔. 不确定离散时间系统鲁棒稳定控制[J]. 自动化学报, 1995, 21(5): 597-603.
    [20] 高为炳. 离散时间系统的变结构控制[J]. 自动化学报, 1995, 21(2): 154-161.
  • 加载中
图(7) / 表(11)
计量
  • 文章访问数:  3991
  • HTML全文浏览量:  1439
  • PDF下载量:  69
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-05-18
  • 录用日期:  2018-08-14
  • 刊出日期:  2020-04-24

混合离散教与学算法求解复杂并行机调度问题

doi: 10.16383/j.aas.c180321
    基金项目:

    国家自然科学基金 51665025

    国家自然科学基金 61963022

    云南省自然科学基金项目 2015FB136

    作者简介:

    何雨洁  昆明理工大学信息工程与自动化学院硕士研究生. 2016年获得昆明理工大学信息工程与自动化学院自动化系学士学位.主要研究方向为调度与智能优化算法. E-mail: Hyujie_one@163.com

    胡蓉  昆明理工大学信息工程与自动化学院副教授. 2004年获得清华大学自动化系硕士学位.主要研究方向为优化方法和决策支持系统.E-mail: ronghu@vip.163.com

    通讯作者: 钱斌  昆明理工大学信息工程与自动化学院教授. 2009年获得清华大学自动化系博士学位.主要研究方向为调度与优化.本文通信作者.E-mail: bin.qian@vip.163.com
  • 本文责任编委 阳春华

摘要: 针对制造行业中广泛存在的一类复杂并行机调度问题, 即带到达时间、多工序、加工约束和序相关设置时间的并行机调度问题(Parallel machine scheduling problem with arrival time, multiple operations, process restraints and sequence-dependent setup times, PMSP_AMPS), 建立问题的排序模型并提出一种混合离散教与学优化算法进行求解, 优化目标为最小化最大完工时间.首先, 根据标准教与学算法(Teaching-learning-based optimization, TLBO)中两阶段个体更新公式的特点, 在保留每一阶段个体更新公式框架不变的前提下, 对公式中具体改变实数个体或向量的每个核心操作均用所设计的排列操作进行替换, 使其可直接在离散问题解空间中执行基于标准教与学算法机理的全局搜索, 从而明显提高了原算法的全局搜索效率.其次, 采用交换操作和插入操作构造了一种简洁有效地变邻域局部搜索, 对全局搜索发现的优质解区域进行细致搜索, 从而进一步增强了算法的性能.通过对不同测试问题的仿真实验和算法比较, 验证了所提算法可有效求解PMSP_AMPS.

本文责任编委 阳春华

English Abstract

何雨洁, 钱斌, 胡蓉. 混合离散教与学算法求解复杂并行机调度问题. 自动化学报, 2020, 46(4): 805-819. doi: 10.16383/j.aas.c180321
引用本文: 何雨洁, 钱斌, 胡蓉. 混合离散教与学算法求解复杂并行机调度问题. 自动化学报, 2020, 46(4): 805-819. doi: 10.16383/j.aas.c180321
HE Yu-Jie, QIAN Bin, HU Rong. Hybrid Discrete Teaching-learning-based Optimization Algorithm for Solving Complex Parallel Machine Scheduling Problem. ACTA AUTOMATICA SINICA, 2020, 46(4): 805-819. doi: 10.16383/j.aas.c180321
Citation: HE Yu-Jie, QIAN Bin, HU Rong. Hybrid Discrete Teaching-learning-based Optimization Algorithm for Solving Complex Parallel Machine Scheduling Problem. ACTA AUTOMATICA SINICA, 2020, 46(4): 805-819. doi: 10.16383/j.aas.c180321
  • 智能制造是解决我国制造业由大变强的根本路径, 有效地生产调度优化算法是提高企业效率和竞争力的重要途径, 属于智能制造的重要研究领域.并行机调度问题(Parallel machine scheduling problem, PMSP)是制造行业中的一类典型生产调度问题.该类问题不仅需要确定每个工件的加工机器, 还需要确定每台机器上相应工件的加工顺序[1]. Allahverdi [2]将并行机分为三个类别:相同并行机, 均匀平行机和不相关并行机.在实际生产制造或加工过程中, 许多问题可抽象为带不同约束的上述三类并行机调度问题.其中, 带到达时间、多工序、加工约束和序相关设置时间的并行机调度问题(Parallel machine scheduling problem with arrival time, multiple operations, process restraints and sequence-dependent setup times, PMSP_AMPS), 是模具制造[3]、半导体芯片终端测试阶段[4]、塑料加工[5]等行业中广泛存在的一类复杂并行机调度问题, 属于带不同约束的不相关并行机调度问题.显然, 在计算复杂度上, 并行机问题已被证明为NP-Complete问题[6], 而该问题又归约为PMSP_AMPS, 故PMSP_AMPS属于NP-Complete问题. PMSP_AMPS是不相关并行机中非常复杂的一类, 很多其他并行机调度问题均可归约为该类问题.因此, 研究求解PMSP_AMPS的有效算法具有较大的工程意义和理论价值.

    并行机调度问题可建立两类问题模型.一类是0-1数学规划模型, 由目标函数和多条显式约束组成, 其对应的求解算法主要为分支定界、列生成[7-10]等运筹学算法.该算法可在几分钟至几十分钟内求解较小规模问题(工件数小于等于30), 同时经过合适设计, 也可用于求解较大规模问题(工件数大于等于100), 但往往求解时间较长.由于问题具有非凸特性, 目前尚无通用的最优解多项式时间求解算法, 故求解质量取决于具体问题的复杂度以及算法设计者对该问题结构的理解程度, 算法要在较短时间获取满意解的难度较大.另一类是排序模型, 该类模型相对数学规划模型来说则较为简单, 由几个计算各工件在不同机器上的开始加工时间的式子组成, 约束隐式包含在问题解的排序编码中, 其对应的求解算法主要为基于动态规划的近似算法[11-13]和各种智能优化算法.基于动态规划的近似算法需要所求解的问题能提出可构造状态递推方程的、确保最优解不丢失的规则方可使用.这使其应用主要集中在可行状态较少、能提出相应规则的单机、并行机等调度问题上, 优点在于可确保算法获得问题的最优解, 具有较大理论意义.但由于该算法本质上仍属于穷举法, 其计算时间复杂度大多为指数型, 难以实际应用.智能优化算法利用某种拟人、拟物的机制来引导算法执行搜索, 往往在几秒或十几秒就能获得各类调度问题的满意解.正是由于智能算法具有性能好、求解时间短、适用面广的优点, 使其近年得到广泛研究和应用.

    目前, 各种智能优化算法已被设计用于求解包括并行机在内的大量生产调度问题, 并取得良好效果.但是, 各类文献对所提算法使用少量个体(一般种群规模为20 $ {\sim} $ 100)运行少量代数(一般进化代数为100 $ {\sim} $ 500代)后, 为何都可获得问题的满意解, 基本都只从各自算法本身的机制、特点进行解释, 而忽略了该类算法所采用的排序模型对求解质量的重要影响.这导致了很多后续研究者过于追求方法和技巧上的创新.实际上, 智能优化算法为何有效, 是由所采用排序模型的解空间和解的特点, 以及智能优化算法自身机制共同决定的.

    在排序模型的解空间方面, 调度问题的目标值变化范围远远小于排序模型解空间的规模.譬如, 对于智能优化算法求解最多的优化目标为最小化最大完工时间的置换流水线调度问题, 假如有50个工件, 5台机器, 每个工件在每台机器上的加工时间为在$ [1, 100]$间均匀分布的随机数, 则其目标值变化范围在$ (1, 25 000) $之内(25 000为各工件在各机器上的加工时间之和, 实际的最大目标值小于此值), 而解空间规模为$ 50! $, 平均每一个具体目标值对应约$ 1.2\times 10^{60} $个不同排列或解, 这表明数量巨大的不同解具有相同的目标值.对于其他类型的调度问题(包括本文研究的并行机问题)同样存在上述情况.因此, 调度问题的排序模型解空间是一个"巨大"和"极为扁平"的空间.该空间规模"巨大", 内部遍布各种不同的山峰(峰顶为局部极大解)和低谷(谷底为局部极小解), 而最高峰顶(全局极大解)和最低谷底(全局极小解)之间的差值相对于整个空间的规模来说又非常小, 这使得整个空间呈现出"极为扁平"的形态, 即空间中大量不同的位置(对应不同的解)会具有相同的目标值.另外, 就排序模型的解(即排列或个体)而言, 解与解之间没有梯度, 两个相似解的目标值也可能差别较大.排序模型解空间的"极为扁平"性, 以及解与解之间"无梯度"性, 使得任何带保优的随机搜索只需用较短时间搜索解空间中极小的区域(类似足球场中1根针面积甚至更小的区域), 却可能到达较广的目标值区域.各种智能优化算法均是在带保优的随机搜索基础上, 增加了自身的寻优机制.这使此类算法不仅可短时间内搜索较广的目标值区域, 而且其内在的寻优机制可推动算法到达目标值较小的不同区域搜索, 从而获得问题的满意解.智能优化算法这种通过对排序模型解空间极小区域的搜索来实现对目标值较大、较优区域的搜索, 是其有效地本质原因, 也是现有运筹学算法和基于动态规划的近似算法这些偏遍历或部分遍历解空间的算法难以做到的.因此, 采用智能优化算法求解复杂调度问题是合理且必要的.

    对于基于排序模型的复杂并行机调度问题, 智能优化算法在过去几年中已有较多的研究. Woo等[14]针对在处理时间不断恶化下带多个机器维护阶段的并行机调度问题, 提出一种融合了改进启发式操作的基于规则的遗传算法(Genetic algorithm, GA)来求解, 以此增强解的高效性. Avalos-Rosales等[15]针对带序相关设置时间的不相关并行机调度问题, 提出了一种基于多启动和变邻域下降的元启发式算法.张嘉琦等[16]针对并行机动态调度问题, 引入问题分解思想和评价策略, 提出了一种基于差分进化算法与代理模型相结合的快速求解方法. Chen [17]针对带不相等准备时间和序相关设置时间的不相关并行机问题, 提出了几种迭代混合元启发式算法进行求解. Damodaran等[18]提出一种微粒群优化算法(Particle swarm optimization, PSO)求解不相关并行批处理机问题, 测试结果表明该算法在求解大规模问题时, 能在较短时间内找到优质解. Diana [19]提出了一种基于变邻域下降的混合免疫算法求解带序相关设置时间的不相关并行机调度问题. Sels等[20]针对不相关并行机调度问题, 提出了融合禁忌搜索、遗传算法和截断分支定界法的混合算法, 通过标准测试问题表明了所提算法的有效性. Bitar等[21]针对半导体制造中的不相关并行机调度问题, 提出了一种文化基因算法, 在合理的测试时间内求得了较好的解. Joo等[22]提出了三种分配规则的混合遗传算法, 求解带序相关设置时间和产品约束的不相关并行机调度问题, 通过对比实验验证了算法的高效性和鲁棒性.罗家祥等[23]提出一种基于变深度环交邻域结构的迭代搜索算法, 用于求解不相关并行机调度问题, 仿真实验验证了算法计算结果十分接近问题的下界. Lin等[24]提出了一种混合人工蜂群算法求解带序相关设置时间的不相关并行机调度问题.由文献调研可知, 尚无智能优化算法求解PMSP_AMPS的相关研究.

    对于PMSP_AMPS这一类复杂并行机调度问题, 无论是运筹学方法还是基于动态规划的近似算法均难以在较短时间内有效求解, 故有必要设计相应的智能优化算法.教与学算法(Teaching-learning-based optimization, TLBO)是一种基于群体智能的连续随机优化算法, 最早由Rao等[25]于2011年提出.它模拟了教师给学员的教学过程和学员的学习过程, 目的是通过教师的"教"和学员之间的相互"学"来提高学员的学习成绩. TLBO参数少、算法简单、易理解、搜索能力较强[26].对于制造过程调度问题(即一类典型的离散优化问题), 现有的TLBO求解算法分为两类: 1)以标准的连续TLBO为基础, 通过一定的编码和解码方式实现离散问题解空间到连续空间的映射, 在"教"、"学"阶段, 对个体的更新仍采用传统的连续运算准则; 2)利用TLBO的基本思想, 重新定义"教"、"学"阶段中个体的离散更新方式, 使算法可直接用于离散解空间的搜索, 这类算法称为离散TLBO (Discrete TLBO, DTLBO).近年TLBO和DTLBO在生产调度领域均已有初步研究, 在TLBO方面, Shao等[27]针对零等待流水车间调度问题, 提出了一种基于高斯分布的扩展教与学算法, 建立反向学习机制和高斯概率模型实现对个体的更新, 并加入基于模拟退火和插入操作的局部搜索, 通过对标准测试问题的仿真实验验证了所提算法的有效性. Xu等[28]针对带模糊加工时间的柔性作业车间调度问题, 提出了一种有效地TLBO算法, 通过加入交叉操作和局部搜索以增强算法的性能.在DTLBO方面, Shao等[29]提出了一种混合离散优化算法求解零等待流水车间调度问题, 采用前向、后向插入操作模拟教学阶段, 同时将学习阶段用2维分布估计算法替换, 并使用基于3种邻域结构的局部搜索来增强算法的搜索能力, 仿真实验验证了其算法的鲁棒性和有效性. Li等[30]针对流水线重调度问题, 提出离散教与学算法进行求解, 在"教"、"学"阶段分别定义了2种较复杂的离散操作, 并在每个阶段都采用同一种迭代贪心局部搜索来提高算法性能, 所提算法在与5有效算法的对比中优势明显.文献调研表明, DTLBO求解并行机调度问题的研究处于空白状态.

    已有的TLBO和DTLBO与大多数文献中的连续域智能调度算法一样(包括前一段中求解并行机问题的连续域智能算法), 均过于强调原有机制的完整保留, 要么采用一定的编码和解码方式实现原算法从连续空间搜索到离散空间搜索的映射(譬如文献[27-28]), 要么在离散化时不够彻底和直接(譬如文献[27-28]), 从而导致全局搜索的实际效率并不高.因此, 本文设计一种离散化更为彻底的DTLBO, 直接用大部分智能调度算法实际执行搜索的排序操作(即交叉、插入、交换等)来对TLBO进行离散化, 以实现对解空间更有效率的搜索.具体来说, 本文提出一种混合离散教与学优化算法(Hybrid discrete teaching-learning-based optimization, HDTLBO), 求解以最小化最大完工时间为目标的PMSP_AMPS. HDTLBO设计了针对问题解的多种排序操作, 在保持标准教与学算法更新机理的前提下实现算法的离散化.首先, 在算法初始化阶段, 将工件排序(即问题的解)作为种群中的个体, 随机初始化种群, 这样有利于确保算法初期搜索的分散性; 其次, 设计了不同的排序操作以实现对标准TLBO两阶段更新公式的离散化, 使算法能直接在离散解空间中进行基于TLBO机理的有效全局搜索, 明显增强了算法的全局搜索效率; 最后, 采用InterchangeInsert邻域操作设计了一种有效地变邻域局部搜索, 进一步增强了算法的局部搜索能力.通过对不同测试问题的仿真实验和算法比较验证了HDTLBO的有效性和鲁棒性.

    • 第1.1节建立PMSP_AMPS的排序模型, 第1.2节给出该模型的一个示例.

    • PMSP_AMPS可描述如下: $ n $个产品或工件在$ m $台设备上进行加工.每种产品需要$ s_{j} $, $ j\in (1, 2$, $ \cdots, l) $道加工工序, $ S_{t} = [s_{1}, s_{2}$, $\cdots, s_{l}] $表示所有产品的工序数所构成的集合, 同种产品的不同工序需要按先后顺序加工; 所有工序只能由满足加工约束的设备进行加工; 产品的加工时间与加工设备有关, 任何设备同一时刻只能加工一种产品; 不同产品间带序相关设置时间, 其依赖于加工顺序, 同种产品间的设置时间为0.

      令$ TS $为所有产品的总工序数, $ \pi = [\pi _{1}, \pi _{2}$, $ \cdots, \pi _{TS}] $ $, \pi _{j} \in (1, 2, \cdots, n) $为待加工的$ n $个工件基于工序的排列(该排列中的工件从左往右根据一定的规则及并行加工约束分配到相应的机器上加工), 也是问题的决策变量, $ T_{i} $为第$ i $台设备上加工的工序总数, $ \pi ^{T(i)} = [\pi _{1}^{T(i)}, \pi _{2}^{T(i)}, \cdots, \pi _{T_{i} }^{T(i)}], (\pi _{k}^{T(i)} \in (1, 2, \cdots, n), k=1, 2, \cdots, T_{i}) $为第$ i $台设备上所加工工件基于工序的排列; $ P(\pi _{k}^{T(i)}) $为$ \pi _{k}^{T(i)} $的加工时间$ (k=0, 1, \cdots, T_{i}; P(\pi _{0}^{T(i)})=0) $; $ St(\pi _{k}^{T(i)}) $为$ \pi _{k}^{T(i)} $的开始加工时间$ (St(\pi _{0}^{T(i)})=0) $; $ S(\pi _{k-1}^{T(i)}, \pi _{k}^{T(i)}) $为$ \pi _{k-1}^{T(i)} $与$ \pi _{k}^{T(i)} $之间的序相关设置时间$ (S(\pi _{0}^{T(i)}, \pi _{1}^{T(i)})=0 $, 当$ k>1 $且$ \pi _{k-1}^{T(i)} =\pi _{k}^{T(i)} $时$ S(\pi _{k-1}^{T(i)}, \pi _{k}^{T(i)})=0) $; $ pre\_ m(\pi _{k}^{T(i)}) $为$ \pi _{k}^{T(i)} $前一次加工所用的设备号, $ pre\_ k(\pi _{k}^{T(i)}) $为$ \pi _{k}^{T(i)} $在前一次加工设备上的排列$ \pi ^{T(pre\_ m(\pi _{k}^{T(i)}))} $中从左往右的位置, (当$ \pi _{k}^{T(i)} $是首次加工时, $ pre\_ m(\pi _{k}^{T(i)})=0, pre\_ k(\pi _{k}^{T(i)})=0 $); $ R(\pi _{k}^{T(i)}) $是工件$ k $首次到达第$ i $台设备的时间.

      根据上述定义, 建立如下排序模型, 优化目标为在所有产品排序的集合$ \Pi $中找到一个最优排序$ \pi ^{*} $, 使得最早完工时间$ C_{\max } (\pi) $最小, 即

      $$ \begin{align} C_{\max } (\pi )=\max \{ St(\pi _{T_{1} }^{T(1)} )+P(\pi _{T_{1} }^{T(1)} ), St(\pi _{T_{2} }^{T(2)} ) +\\ \qquad\qquad\quad P(\pi _{T_{2} }^{T(2)} ), \cdots, St(\pi _{T_{m} }^{T(m)} )+P(\pi _{T_{m} }^{T(m)} )\!\} \\ \end{align} $$ (1)
      $$ \begin{align} &St(\pi _{k}^{T(i)} )= \\ &\begin{cases} \max \{ St(\pi _{k-1}^{T(i)} )+P(\pi _{k-1}^{T(i)} )+S(\pi _{k-1}^{T(i)}, \pi _{k}^{T(i)} ), \\ R(\pi _{k}^{T(i)} )\}, \quad\mbox{若 } pre\_ k(\pi _{k}^{T(i)} )=0 \\ \max \{St(\pi _{k-1}^{T(i)} )+P(\pi _{k-1}^{T(i)} )+S(\pi _{k-1}^{T(i)}, \pi _{k}^{T(i)} ), \\ St(\pi _{pre\_ k(\pi _{k}^{T(i)} )}^{T(pre\_ m(\pi _{k}^{T(i)} ))} )+P(\pi _{pre\_ k(\pi _{k}^{T(i)} )}^{T(pre\_ m(\pi _{k}^{T(i)} ))} )\}, \quad\mbox{其他 } \end{cases} \end{align} $$ (2)
      $$ C_{\max } (\pi ^{*} )={\mathop{\min }\limits_{m\subset \Pi }} C_{\max } (\pi ) $$ (3)
      $$ \pi ^{*} =\arg \{ C_{\max } (\pi )\} \to \min, \quad \forall\: \pi \in \Pi $$ (4)

      其中, 式(1)和式(2)为最大完工时间$ C_{\max } (\pi) $的计算公式, 式(3)和式(4)表示在所有产品集合$ \Pi $中找到最优排序$ \pi ^{*} $, 使得$ C_{\max } (\pi) $最小.

    • 由于PMSP_AMPS中部分产品需多工序加工, 故HDTLBO采用基于操作的编码方式来表示个体或解.例如, 对于$ n=5 $, $ m=3 $, 工序集合$ S_{t} = [3, 1, 3, 2, 1] $的问题, $ \pi = [1\; 3\; 2\; 5\; 4\; 1\; 3\; 1\; 3\; 4] $可以表示该问题采用基于操作的编码方式的一个编码排列, 即第一个加工的工件为工件1, 共有3个加工工序, 第二个加工的工件是工件3, 共有3个加工工序, 以此类推.本文采用最早完工时间(Early completion time, ECT)规则进行解码.现对$ \pi = [1\; 3\; 2\; 5\; 4\; 1\; 3\; 1\; 3\; 4] $的解码操作举例说明, 排列$ \pi $中各工件的工序加工约束、序相关设置时间(s)和工件到达时间(s)如表 1所示, 其中每个工件的不同操作可在0台或多台机器上加工, 工序加工时间如表 2所示.根据表 1表 2中所给数据, 结合ECT规则可得$ T_{1} =4 $, $ T_{2} =4 $, $ T_{3} =3 $, 3 台机器分别对应的工件排序为: $ \pi ^{T(1)} = [\pi _{1}^{T(1)}, \pi _{2}^{T(1)}, \pi _{3}^{T(1)}, \pi _{4}^{T(1)} ] = [2, 4, 1, 4] $; $ \pi ^{T(2)} = [\pi _{1}^{T(2)}, \pi _{2}^{T(2)}, \pi _{3}^{T(2)}, \pi _{4}^{T(2)} ] = [1, 1, 3, 3] $; $ \pi ^{T(3)} = $ $ [\pi _{1}^{T(3)}, \pi _{2}^{T(3)} ] = [3, 5] $, 对应的甘特图如图 1所示.

      表 1  工序加工约束、序相关设置时间和工件到达时间表($ \pi $ = [1  3  2  5  4  1  3  1  3  4])

      Table 1.  The schedule of process constraint, sequence setup time and arrival time ($ \pi $ = [1 3 2 5 4 1 3 1 3 4])

      可执行操作的设备 序相关设置时间 首次到达设备的时间
      操作1 操作2 操作3 工件1 工件2 工件3 工件4 工件5 m1 m2 m3
      工件1 m1/m2 m1/m2/m3 m1/m3 83 38 39 47 35 34 23
      工件2 m1 53 66 45 25 38 78 98
      工件3 m3 m2/m3 m2 64 57 72 46 52 23 32
      工件4 m1/m3 m1 46 67 83 55 132 131 98
      工件5 m1/m3 40 66 83 77 114 99 112

      表 2  工件加工时间表($ \pi $ =  [1 3 2 5 4 1 3 1 3 4]) ($t$/s)

      Table 2.  The processing time table ($ \pi $ =  [1 3 2 5 4 1 3 1 3 4]) ($t$/s)

      操作1 操作2 操作3
      m1 m2 m3 m1 m2 m3 m1 m2 m3
      工件1 62 44 78 86 26 48 87
      工件2 41
      工件3 31 58 65 42
      工件4 32 31 27
      工件5 74 36

      图  1  工序为$ \pi $ = [1 3 2 5 4 1 3 1 3 4]时的甘特图

      Figure 1.  The Gantt chart of $ \pi $ = [1 3 2 5 4 1 3 1 3 4]

    • 本节将对HDTLBO中的关键环节, 即离散"教"、"学"阶段以及HDTLBO流程进行介绍.根据标准TLBO两阶段的个体更新机制, HDTLBO分别在离散"教"、"学"阶段设计了不同的排序操作(基于交叉、插入、交换等), 以此替换标准TLBO中对实数个体的核心更新方式, 进而实现对TLBO的离散化和对排序模型解空间的有效搜索.这使得HDTLBO能够直接用于求解PMSP_AMPS, 并且在全局搜索能力上得到明显提高.

      令$ X_{i}^{gen} $是第$ gen $代中的第$ i $个个体, $ X_{mean}^{gen} $是第$ gen $代的种群均值, $ X_{teacher}^{gen} $是第$ gen $代种群中的最优个体即"教师", $ TF $为教学因子, $ TF=round[1+rand(0, 1)] $, $ r_{i} $为学习概率, $ r_{i} =rand(0, 1) $, $ rand[0, 1] $是区间$ [0, 1] $上分布的随机数, $ f(X_{i}^{gen}) $为第$ gen $代中第$ i $个个体的评价函数值.根据上述定义我们提出以下第2.1节~第2.3节的DTLBO.

    • 本文采用随机初始化方法产生初始种群, 以保证解的多样性和分散性.

    • 本阶段学生(个体)通过自身与教师(种群中当前最优个体)之间的差异交互来获得知识, 每个个体通过最优个体(教师)的教导提升自身的水平进而提高整个种群的均值.针对调度问题解空间的特点, 设计不同的排序交叉操作实现教学活动, 使个体能直接从教师中获取优质解信息.定义种群均值为当前种群中处于中间大小的目标值所对应的个体或排序.根据上述定义, 提出如式(5)所示的个体更新公式.

      $$ \begin{align} &X_{i}^{gen+1} =\\ &\{ r_{m} \odot (X_{i}^{gen} ), TF\odot [X_{teacher}^{gen}, X_{mean}^{gen} ]^{r[a, b]} \} ^{r[c]} \end{align} $$ (5)

      显然, 式(5)中依次执行的三个核心操作分别为$ r_{m} \odot (X_{i}^{gen}) $、$ TF \odot [X_{teacher}^{gen}, X_{mean}^{gen} ]^{r[a, b]}$和$ \{ r_{m} \odot (X_{i}^{gen}), TF \odot [X_{teacher}^{gen}, X_{mean}^{gen}]^{r[a, b]} \} ^{r[c]}$, 第2.2.1节~第2.2.3节将对这三个核心操作进行具体描述.

    • $ r_{m} \odot (X_{i}^{gen}) $表示以概率$ r_{m} $对$ X_{i}^{gen} $执行变异操作, 引入变异概率$ r_{m} $, 模拟个体在"教"之前的自学习过程, 设计InterchangInsert邻域操作实现自学习.令$ Interchange(\pi, u, v) $为将解$ \pi $中的第$ u $个位置上的工件与第$ v $个位置上的工件进行交换, $ Insert(\pi, u, v) $为将解$ \pi $中的第$ u $个位置上的工件插入到第$ v $个位置上, $ u $和$ v $为随机生成的不同整数.自学习过程如式(6)所示:

      $$ \begin{align}\label{eq6} \overline{X_{i}^{gen} }=\, &r_{m} \odot (X_{i}^{gen} ) =\nonumber\\&\begin{cases} (X_{i}^{gen} ), &\mbox{若 } {rand[0, 1]<r_{m}} \\ X_{i}^{gen}, & \mbox{否则} \end{cases} \end{align} $$ (6)

      当产生的$ rand[0, 1] $小于$ r_{m} $时, 执行变异操作$ \overline{X_{i}^{gen} }{\rm =(}X_{i}^{gen}) $, 反之执行$ \overline{X_{i}^{gen} }=X_{i}^{gen} $.变异操作采用如下分阶段的方式:

      $$ \begin{equation}\label{eq7} (X_{i}^{gen} )=\begin{cases} Interchange(X_{i}^{gen}, u, v), \!&\! \mbox{若 } {gen\le 50} \\ Insert(X_{i}^{gen}, u, v), \!&\! \mbox{否则} \end{cases} \end{equation} $$ (7)

      即在算法运行的前50代执行$ Interchange(X_{i}^{gen}, u, v) $操作, 之后算法执行$ Insert(X_{i}^{gen}, u, v) $操作, 这有利于搜索问题解空间中的不同区域.执行$ r_{m} \odot (X_{i}^{gen}) $后, 式(5)变为如下所示:

      $$ \begin{align} X_{i}^{gen+1} =\{ \overline{X_{i}^{gen} }, TF\odot [X_{teacher}^{gen}, X_{mean}^{gen} ]^{r[a, b]} \} ^{r[c]} \end{align} $$ (8)
    • $$ \begin{align} &X_{mean\_ new}^{gen} =TF\odot [X_{teacher}^{gen}, X_{mean}^{gen} ]^{r[a, b]} =\nonumber\\ &\begin{cases} [X_{teacher}^{gen}, X_{mean}^{gen} ]^{r[a, b]}, & \mbox{若} {TF=2} \\ X_{mean}^{gen}, &\mbox{否则} \end{cases} \end{align} $$ (9)

      该操作为种群均值的离散化更新方式, 种群中每个个体在"教"阶段通过不断学习提高自身的评价值进而提高整个种群均值.其中, 教学因子$ TF $决定了均值的选取, $ [X_{teacher}^{gen}, X_{mean}^{gen}]^{r[a, b]}$为对$ X_{teacher}^{gen} $和$ X_{mean}^{gen} $执行基于$ r[a, b] $的交叉操作, $ r[a, b] $为随机选取整数$ a, b $ $ (1\le a\le b\le TS) $以构成区间$ [a, b] $.采用类似文献[31]中基于顺序的交叉法(Order-based crossover, OBX)实现$ TF=2 $时新的均值个体的产生, 具体交叉方法如图 2中例子所示.执行完此节操作后, 式(5)变为如下所示:

      $$ \begin{equation}\label{eq10} X_{i}^{gen+1} =\{ \overline{X_{i}^{gen} }, X_{mean\_ new}^{gen} \} ^{r[c]} \end{equation} $$ (10)

      图  2  基于顺序的交叉法

      Figure 2.  The order-based crossover (OBX)

    • 该操作为"教"阶段的最后一个操作, 根据当前学生与教师水平之间的差异对解进行更新. $ r\left[c\right] $为随机选取整数$ c (1\le c\le n) $, $ \{ \overline{X_{i}^{gen} }, X_{mean\_ new}^{gen} \} ^{r[c]}$表示对$ \overline{X_{i}^{gen} } $和$ X_{mean\_ new}^{gen} $执行基于$ r\left[c\right] $的交叉操作, 该操作可举例说明, 譬如$ \overline{X_{i}^{gen} } $ = [2 3 5 4 3 4 1 1 3 1], $ X_{mean\_ new}^{gen} $ = [5 4 1 3 3 4 2 1 3 1], $ c=3 $时, 将$ \overline{X_{i}^{gen} } $中为3的元素均置0, 可得第一个中间排列$ temp1 $ = [2 0 5 4 0 4 1 1 0 1], 然后将$ X_{mean\_ new}^{gen} $中不为3的元素均置0, 可得第二个中间排列$ temp2 $ = [0 0 0 3 3 0 0 0 3 0], 然后将$ temp1 $中不为0的元素从左至右依次替换$ temp2 $中为0的元素, 即可生成交叉后的排列$ X_{i}^{gen+1} $ = [2 5 4 3 3 4 1 1 3 1].在执行完最后一个操作后, 将所得$ X_{i}^{gen+1} $和$ X_{i}^{gen} $进行比较, 把两者中较优者保存至$ X_{i}^{gen+1} $, 从而完成了离散"教"阶段的个体更新.

    • 首先把"教"阶段的$ X_{i}^{gen+1} $赋值给本阶段的$ X_{i}^{gen} $, 然后本阶段班级中学生之间互相学习, 通过学生间的互相交流, 学生可从比自己知识多的学生(即对应目标值更小的个体)那获取新的知识.对任一学生$ X_{i}^{gen} $, 随机选取另一学习对象$ X_{j}^{gen} $, 以一定的学习概率$ r_{i} $向学员$ X_{j}^{gen} $获取新知识.本节通过不同的交叉操作实现学生之间的互相学习, 以此缩小学生之间的差异, 解的更新公式如式(11)所示.

      $$ \begin{equation}\label{eq11} X_{i}^{gen+1} =r_{i} \odot \{ X_{i}^{gen}, [X_{i}^{gen}, X_{j}^{gen} ]^{r[d, e]} \} ^{r\left[c\right]} \end{equation} $$ (11)
    • $$ \begin{align} &X_{d\_ temp}^{gen} = [X_{i}^{gen}, X_{j}^{gen} ]^{r[d, e]} =\nonumber\\ &\begin{cases} [X_{i}^{gen}, X_{j}^{gen} ]^{r[d, e]}, &\mbox{若 } {f(X_{i}^{gen} )<f(X_{j}^{gen} )} \\ [X_{j}^{gen}, X_{i}^{gen} ]^{r[d, e]}, &\mbox{否则} \end{cases} \end{align} $$ (12)

      该操作中, 种群中两个个体通过互相学习, 差的个体从较优个体获取知识实现取长补短.由于每个个体在学习时, 是在小范围的学生之间进行, 不会过早向全局最优点方向聚集, 因此能够有效保持学员的多样性特征, 从而保证算法在搜索空间的全局探索能力.利用类似文献[32]中的顺序交叉(Order crossover, OX)法实现个体之间互相学习. $ [X_{i}^{gen}, X_{j}^{gen}]^{r[d, e]} $表示对$ X_{i}^{gen} $和$ X_{j}^{gen} $执行基于$ r[d, e] $的交叉操作, $ r[d, e] $表示随机选取整数$ d, e $ $ (1\le d\le e\le TS) $以构成区间$ [d, e] $, 具体操作如图 3中例子所示.执行此节操作后, 式(11)变为如下所示:

      $$ \begin{equation}\label{eq13} X_{i}^{gen+1} =r_{i} \odot \{ X_{i}^{gen}, X_{d\_ temp}^{gen} \} ^{r\left[c\right]} \end{equation} $$ (13)

      图  3  顺序交叉法

      Figure 3.  Order crossover (OX)

    • 在学生互相学习的过程中, 学生对已获得的知识可能会存在一定程度上的误解, 如果在个体相互学习过程中对已获取的知识完全信任, 学生就会盲目信任自己已获取知识, 此时算法易陷入局部最优.因此, 引入学习概率$ r_{i} $控制解的更新方式, 避免学生相互学习中的盲目信任.具体更新方式如式(14)所示.

      $$ \begin{align}\nonumber &X_{i}^{gen+1} =r_{i} \odot \{ X_{i}^{gen}, X_{d\_ temp}^{gen} \} ^{r\left[c\right]} = \\ & \begin{cases} \{ X_{i}^{gen}, X_{d\_ temp}^{gen} \} ^{r\left[c\right]}, &\mbox{若 } {r_{i} <0.5} \\ X_{d\_ temp}^{gen}, &\mbox{否则} \end{cases} \end{align} $$ (14)

      该操作是"学"阶段的最后一个操作, 其中的$ \{ X_{i}^{gen}, X_{d\_ temp}^{gen} \} ^{r\left[c\right]}$与"教"阶段第2.2.3节的操作相似.在执行完最后一个操作后, 将$ X_{i}^{gen+1} $和$ X_{i}^{gen} $中较优者保存至$ X_{i}^{gen+1} $, 进而完成了离散"学"阶段的个体更新.至此整个DTLBO两阶段离散搜索执行完毕.

    • 为增加算法的搜索能力, 需对优质解的近邻区域进行较细致的局部搜索.在各种常用搜索操作或邻域中, 交换操作Interchange和插入操作Insert构成的问题解空间中解之间的距离是最短的[33].基于这两种邻域构造的局部搜索可引导算法在更为紧凑的解空间中进行搜索, 有利于提高算法的性能.因此, HDTLBO对全局搜索之后产生的新种群中前20个优质个体$ X_{i}^{gen+1} $执行基于这两种邻域的局部搜索.具体来说, 对每个进行局部搜索的个体$ X_{i}^{gen+1} $执行1次扰动操作$ tmp1=Interchange(X_{i}^{gen+1}, u, v) $后, 均对$ tmp1 $执行$ n $次插入操作$ tmp2=Insert(tmp1, u, v) $.每次插入操作时, 如$ tmp2 $优于$ tmp1 $则令$ tmp1=tmp2 $.执行完$ n $次插入操作后, 如$ tmp1 $优于$ X_{i}^{gen+1} $则令$ X_{i}^{gen{\rm +1}} =tmp1 $.其中, $ u, v\left(u\ne v\right) $为随机数, $ n $为工件数, 每次执行交换、插入操作时均重新生成$ u $和$ v $.

    • 令$ P\left(gen\right) $为算法第$ gen $代种群, $ popsize $为种群大小, $ gen\_ \max $为算法最大运行代数.根据第2.1节~第2.4节描述, HDTLBO的具体步骤如下:

      步骤1.初始化种群.令$ gen=1 $, 设定$ popsize $和$ gen\_ \max $, 随机生成初始种群$ P\left(0\right) $, 并计算种群中每个个体的适配值$ f $;

      步骤2.根据第2.1节~第2.3节内容生成$ P\left(gen\right) $中的每一个个体, 并进行保优更新;

      步骤3.根据第2.4节内容对种群中前20个个体执行基于InterchangeInsert的局部搜索;

      步骤4.令$ gen=gen+1 $;

      步骤5.如果$ gen\le gen\_ \max $, 转到步骤2, 否则输出当前种群中的最优个体$ X_{best}^{gen} $.

      由上述算法步骤可知, 步骤2直接负责在基于排列的问题解空间中进行全局搜索, 用于发现解空间中的优质区域, 步骤3对全局搜索找到的优质区域再进行较为细致的局部搜索, 从而增强算法的性能, 也使算法在全局和局部搜索之间达到较好的平衡, 完整算法流程图如图 4所示.由此知, HDTLBO有望成为求解PMSP_AMPS的有效算法.

      图  4  HDTLBO流程图

      Figure 4.  HDTLBO's flow chart

    • 群智能算法的计算复杂度是指算法执行加、减、乘、除的次数.对于种群规模为$ popsize $, 迭代次数为$ gen\_ \max $, 问题规模为$ n\times m $的问题, HDTLBO的计算复杂度分析如下:

      由第1 节可知, 计算个体适应度(即计算$ C_{\max } (\pi ) $) 的计算复杂度为$ {\rm O}(mn) $. 初始化种群的计算复杂度为$ {\rm O}(popsize\times mn) $. 初始化种群之后, 每一次迭代均需经过离散"教" 阶段、离散"学" 阶段和局部搜索三个步骤. 离散"教" 阶段的计算复杂度为$ {\rm O}(popsize\times mn+popsize^{2} ) ( {\rm O }(popsize^{2} ) $ 为采用冒泡排序计算种群均值时的计算复杂度), 离散"学" 阶段的计算复杂度为$ {\rm O}(popsize\times mn) $, 局部搜索的复杂度为$ {\rm O}(20\times mn^{2} +popsize^{2} ) ( {\rm O}(popsize^{2} ) $ 为采用冒泡排序计算种群前20 较优个体的计算复杂度). 由此整个算法的时间复杂度为:

      $$ \begin{align}\nonumber &{{\rm O}(popsize, gen\_ \max, n\times m)} =\\ \nonumber &\qquad{\rm O}(popsize\times mn)+gen\_ \max \times\\\nonumber &\qquad ({\rm O}(popsize\times mn+popsize^{2} )+{\rm O}(popsize\times\\\nonumber &\qquad mn)+{\rm O}(20\times mn^{2} +popsize^{2} )) =\\ \nonumber &\qquad gen\_ \max \times ({\rm O}(popsize\times mn+popsize^{2} )+ \\ &\qquad{{\rm O}(20\times mn^{2} +popsize^{2} ))} \end{align} $$ (15)

      从式(15)可以看出, HDTLBO整体计算复杂度的最高次项是问题输入规模n和种群大小popsize的平方(实际popsize是一个较小值, 本文为30), 故具有较低计算复杂度.

    • 测试问题采用随机方式生成, 工件需要加工的工序在[1,3]上随机产生, 工件第$ i $个操作的加工时间在[1,100]上随机产生, 工件间的设置时间在[1,30]上随机产生, 工件的到达时间在[1,100]上随机产生, 测试问题的规模$ n\times m $为: 10 $\times$ 5, 20 $\times$ 5, 30 $\times$ 5, 40 $\times$ 5, 50 $\times$ 5, 40 $\times$ 10, 50 $\times$ 10, 60 $\times$ 10, 70 $\times$ 10, 80 $\times$ 10, 80 $\times$ 20, 90 $\times$ 20, 100 $\times$ 20, 150 $\times$ 20和200 $\times$ 20共有15个测试问题.所有算法和测试均由Delphi 2010编程实现, 操作系统为Window 10, CPU为2.2 GHz, 内存为4 GB.每种算法对每个测试问题均在相同时间下独立运行20次, 其中, $ Fit $表示算法独立运行1次输出的最优值, 则$ AVG=\sum _{i=1}^{20}Fit_{i} /20 $表示算法独立运行20次输出结果的平均值, $ BST=\begin{array}{cc} {\min } & {\{ Fit_{i} \, |\, i=1, \cdots, 20 \} } \end{array} $表示算法独立运行20次输出结果的最优值, $ WST=\begin{array}{cc} {\max } & {\{ Fit_{i} \, |\, i=1, \cdots, 20 \} } \end{array} $表示算法独立运行20次输出结果的最差值.

    • HDTLBO的关键参数为种群规模$ popsize $、教学因子$ TF $和变异概率$ r_{m} $.本节将针对一组中等规模问题(60 $\times$ 10)采用实验设计方法DOE进行实验分析, 进而确定HDTLBO的参数设置.上述3个参数均取4个水平(见表 3), 选择规模为$ L16\left(4^{3} \right) $的正交实验, 每种参数组合下的测试问题均分别进行20次独立运行实验. HDTLBO在各个参数组合下的运行时间均为$ 100\times n $ (ms), 以AVG为评价指标进行测试实验, 参数响应值如表 5所示, 各参数的相应趋势如图 5所示.

      表 3  参数水平设置表

      Table 3.  Combinations of parameter values

      参数 水平
      1 2 3 4
      $ popsize $ 10 20 30 40
      $ TF $ 0 1 2 3
      $ r_{m} $ 0.1 0.4 0.7 0.9

      表 4  正交表和AVG统计

      Table 4.  Orthogonal array and AVG

      参数组合 水平 $ AVG $
      $ popsize $ $ TF $ $ r_{m} $
      1 1 1 1 500.65
      2 1 2 2 503.90
      3 1 3 3 497.30
      4 1 4 4 498.55
      5 2 1 2 489.35
      6 2 2 3 491.20
      7 2 3 4 485.50
      8 2 4 1 488.35
      9 3 1 3 482.55
      10 3 2 4 481.80
      11 3 3 1 482.25
      12 3 4 2 483.25
      13 4 1 4 483.35
      14 4 2 1 484.00
      15 4 3 2 483.60
      16 4 4 3 482.20

      表 5  各参数响应值

      Table 5.  Average response value and rank of each parameter

      水平 $ popsize $ $ TF $ $ r_{m} $
      1 500.10 488.98 488.81
      2 488.60 490.23 490.02
      3 482.46 487.16 488.31
      4 483.29 488.09 487.30
      等级 1 3 2

      图  5  各参数响应趋势

      Figure 5.  The influence trend of each parameter

      表 3~表 5图 5可知, $ popsize $、$ TF $和$ r_{m} $对算法的影响性能等级.说明若参数选择过大会使得算法偏离优质区域过远, 过小则会使得算法的搜索区域过窄.综合考虑, HDTLBO的参数设置为: $ popsize $ = 30, $ TF $ = 2, $ r_m $ = 0.9, 此时, 算法可表现出良好的性能.

    • 1本节表 6与下节表 7均给出了$ \rho =4 $时的各算法对比结果, $ \rho =2 $及$ \rho =6 $时的算法对比结果及实例测试问题集可在 https://pan.baidu.com/s/1Foa_Vry7xxibW9jcoVBgXQ下载, 若链接失效请联系通信作者.

      表 6  DTLBO与PSO、DTLBO-Ⅰ、标准TLBO和CIWO的比较($ \rho =4 $)

      Table 6.  Comparisons of DTLBO, DTLBO-Ⅰ, PSO, CIWO, and standard TLBO ($ \rho =4 $)

      测试问题 PSO DTLBO-Ⅰ 标准TLBO CIWO DTLBO
      BST WST AVG BST WST AVG BST WST AVG BST WST AVG BST WST AVG
      10$ \times $5 229 235 230.15 228 231 229.45 228 233 230.05 227 246 229.95 227 244 229.3
      20$ \times $5 560 587 576.7 546 579 560.3 558 589 574.5 503 554 526.5 506 534 521.4
      30$ \times $5 682 708 694.8 638 685 662.3 675 709 697 615 665 635.5 607 638 622.4
      40$ \times $5 752 784 771.4 696 748 725.7 728 787 767.75 654 716 690.05 661 716 692.8
      50$ \times $5 1 132 1 171 1 157.45 1 093 1 140 1 114.3 1148 1 175 1 161.5 1 019 1 091 1 059.2 1 019 1 078 1 051.85
      40$ \times $10 340 357 348.2 307 336 321.3 340 360 351.15 293 326 311.9 284 317 304.3
      50$ \times $10 410 429 419.7 373 411 392.75 413 429 421.1 362 391 376.3 353 386 370.75
      60$ \times $10 523 548 538.8 497 529 516 538 552 544.3 485 516 499.95 481 516 500.6
      70$ \times $10 658 682 672 626 653 641.8 660 684 672.65 604 639 622 597 636 621.75
      80$ \times $10 596 619 612.15 567 601 585.55 597 621 612.95 553 589 571.45 553 584 569.5
      80$ \times $20 286 298 292.2 265 289 278.85 285 298 291.8 257 282 271.65 259 272 264.7
      90$ \times $20 287 299 294.65 271 289 280.55 288 301 297.4 255 284 273.1 255 279 269.05
      100$ \times $20 329 340 336 309 328 320.5 333 343 338 304 323 312.65 299 313 306.25
      150$ \times $20 479 496 489.2 460 486 472 487 499 492.9 454 476 464.95 449 477 458.45
      200$ \times $20 575 593 587.25 557 576 568.5 577 598 589.85 559 575 564.4 547 559 549.55
      Average 522.53 543.06 534.71 495.53 525.4 511.32 523.66 545.2 536.19 476.27 511.53 493.97 473.13 503.27 488.84

      表 7  HDTLBO与DPSO、DTLBO-Ⅱ、GA_DR_C和CCIWO的比较($ \rho =4 $)

      Table 7.  Comparisons of HDTLBO, DPSO, DTLBO-Ⅱ, GA_DR_C, and CCIWO ($ \rho =4 $)

      测试问题 DPSO DTLBO-Ⅱ GA_DR_C CCIWO HDTLBO
      BST WST AVG BST WST AVG BST WST AVG BST WST AVG BST WST AVG
      10$ \times $5 227 230 228.75 227 230 228.45 227 230 228.2 227 230 228.2 227 230 227.3
      20$ \times $5 521 547 527.15 533 554 543.1 514 551 536.15 494 536 518.1 499 540 520.95
      30$ \times $5 612 647 624.1 630 658 645.65 625 656 645.85 617 644 621.95 603 638 617.5
      40$ \times $5 652 692 686.75 695 733 710.15 695 735 715.8 657 715 686.15 645 692 681.65
      50$ \times $5 1 014 1 074 1 058.4 1 064 1 111 1 090 1 070 1107 1 094.75 1 024 1 088 1 057.05 1 006 1 055 1 035.9
      40$ \times $10 303 317 306.14 303 328 316.2 305 325 316.4 292 320 307.7 290 316 303.65
      50$ \times $10 365 387 370.95 370 395 387.95 374 400 388.2 362 390 373.85 355 382 369
      60$ \times $10 481 503 498.85 498 519 510.9 497 584 541.15 481 515 496.6 481 501 493.05
      70$ \times $10 601 639 615.4 626 656 640.15 636 716 694.55 597 639 621.7 597 635 606.75
      80$ \times $10 556 590 579 571 596 584.55 561 590 582.75 548 586 568.45 554 575 564.85
      80$ \times $20 274 285 277.41 269 285 278 273 285 279.9 275 280 269.3 262 279 273.7
      90$ \times $20 269 290 273.33 275 288 282.1 277 292 285.8 268 285 276.25 266 282 272.58
      100$ \times $20 304 323 313.7 313 327 320.85 317 328 322.85 300 323 314.6 297 323 310.65
      150$ \times $20 472 489 475.34 469 486 476.45 470 488 480.55 469 486 470.7 464 483 469.89
      200$ \times $20 553 579 566.5 564 579 573 562 587 578.1 557 583 570.05 549 579 565.2
      Average 480.27 506.13 493.45 493.8 516.33 505.83 493.53 524.93 521.73 477.87 508 492.04 473 500.67 487.51

      为了验证DTLBO的有效性, 将DTLBO与重要国际期刊中的PSO [18]、DTLBO-Ⅰ [30]、标准TLBO [26]、CIWO [4]进行算法全局搜索性能的仿真比较, 其中PSO [18]求解的是一类不相关并行机调度问题.设定每种算法的运行时间均为$ n\times m\times \rho $毫秒, $ \rho $的取值分别为2、4、6, $ \rho =4 $时的测试结果如表 6所示.为能清楚展现每个算法的性能, 表 6中每个问题对应的最优结果用粗体表示.

      表 6可见, DTLBO通过对标准TLBO [26]的更新机制进行离散化处理后, 使算法在全局搜索能力上得以明显提高, 这验证了采用排序操作替换标准TLBO中核心操作的合理性.同时, DTLBO优于另一离散教与学优化算法DTLBO-Ⅰ [30], 这表明DTLBO中设计的排序操作更加有效.此外, DTLBO也优于具有较强全局搜索能力的PSO [18], 这说明DTLBO可搜索到更多存在优质解的区域.

      为了进一步验证DTLBO与其他算法差异性的显著与否, 根据$ \rho $在2、4、6三种取值下的算法全局对比结果, 采用Tukey$'$s HSD方法对表 6中DTLBO等5种对比算法的AVG (均值)进行方差分析(ANOVA). 图 6显示了5种算法在不同终止运行时间下的均值变化线及95 %置信度下Tukey$'$s HSD检验的置信区间.从图 6中可以看出, DTLBO在均值水平上与其他算法均有显著差异, 且随着时间的增大, DTLBO自身的均值水平并无明显的差异变化.结合算法对比实验及方差分析结果可知, DTLBO的全局搜索能力强, 能更有效地求解PMAP_AMPS.

      图  6  各算法在不同时间参数下的均值线及95 %置信度下Tukey$'$s HSD检验的置信区间

      Figure 6.  Means plot and 95 % Tukey$'$s HSD confidence intervals for the interaction between the algorithms and the different time factor $ \rho $

    • 为进一步测试HDTLBO的性能, 本节将HDTLBO和重要国内外期刊中的有效算法DPSO [34]、DTLBO-Ⅱ [30]、GA_DR_C [22]、CCIWO [4]进行比较. DPSO [34]是求解零等待流水线问题公认的有效算法, GA_DR_C [22]和CCIWO [4]是近年求解复杂并行机调度问题的有效算法.设定每种算法的运行时间均为$ n\times m\times \rho $毫秒, $ \rho $的取值分别为2、4、6, 表 7给出了$ \rho =4 $时的算法运行结果, 表中每个问题对应的最优结果用粗体表示.

      表 7中可知, HDTLBO在绝大部分问题上的测试结果都明显优于其他比较算法, 这验证了HDTLBO具有良好的性能.此外, 和表 6中各算法比较, HDTLBO也明显占优.由于表 6表 7中各算法运行时间相同, 故在DTLBO中加入局部搜索的必要性也得以验证.

      为了进一步验证各个算法组内差异, 根据$ \rho $在2、4、6三种取值下整体算法对比结果, 采用Tukey$'$s HSD分析方法对表 7中HDTLBO等5种对比算法的AVG进行方差分析(ANOVA). 图 7显示了5种算法在不同运行时间下的均值变化线及95 %置信度下Tukey$'$s HSD的置信区间, 可以看出, HDTLBO在均值水平上与其他算法有显著差异, 且随着时间参数$ \rho $的变化, HDTLBO在均值上并无显著差异, 其三个不同时间下的置信区间明显存在重叠部分.综合算法对比及方差分析结果可知, HDTLBO能更高效地求解PMAP_AMPS.

      图  7  各算法在不同时间参数下的均值线及95 %置信度下Tukey$'$s HSD检验的置信区间

      Figure 7.  Means plot and 95 % Tukey$'$s HSD confidence intervals for the interaction between the algorithms and the different time factor $ \rho $

    • 在第3.1节~第3.3节的基础上, 采用云南某模具制造公司生产过程的实例数据, 进一步对HDTLBO的性能进行验证.模具制造需要经过模架加工、模芯加工、电机加工和模具零部件加工等步骤, 其加工工艺主要铸造、切削加工、特种加工三种方法.切削加工作为最常用方法, 其加工工序主要为粗加工、半精加工、精加工3种.该企业根据不同的客户订单要求进行模具生产, 不同种模具制造过程中有不同的加工工艺路线.现有20种待生产的模具产品, 5台不同类型(即刀具、工艺不同)的加工设备用于生产该订单中所需产品.

      在对20种模具进行生产时, 考虑如下因素: 1)模具种类不同, 其加工工艺路线也不同, 即在各台设备上工艺操作不同; 2)加工时, 根据不同模具的工艺要求应选择不同的加工设备, 同种模具在进行不同工艺加工时需要选择不同的加工设备; 3)由于工序更换, 加工设备需要一定的设置时间进行更换夹具等所需动作; 4)根据客户的实时订单要求, 将模具毛坯从仓库中心运送到加工设备上需要可考虑为工件首次到达时间; 5)模具加工时间$ P_{ij} (k) $ (表示第$ i $种模具毛坯料的第$ j $个工艺操作在设备$ k $上的加工时间)取决于加工设备所处的工艺步骤.设有20种待加工的模具产品, 工序数为$ S_{t} $ = [3, 2, 1, 3, 1, 3, 2, 1, 3, 3, 2, 3, 3, 3, 1, 2, 1, 3, 1, 3], 模具加工约束、首达时间(min)如表 8所示, 不同模具产品间的设置时间(min)如表 9所示, 各工序在各台设备上的加工时间(min)如表 10所示.

      表 8  模具各工序加工约束及首次到达时间表

      Table 8.  The schedule of mold process constraint and arrival time

      模具 可执行操作的设备 模具首次到达设备时间
      操作1 操作2 操作3 m1 m2 m3 m4 m5
      1 m1/m3/m5 m3/m4 m2/m3/m4 7 4 8 4 6
      2 m1/m3/m6 m1 1 6 2 3 3
      3 m3 3 1 8 4 6
      4 m2/m3/m5 m1/m2/m3/m4/m5 m2/m3/m4 8 1 6 8 7
      5 m1/m3/m4 1 2 6 7 3
      6 m2/m5 m1/m4/m5 m1/m4/m5 5 8 3 1 5
      7 m2/m4/m5 m2/m3/m4/m5 3 8 3 3 6
      8 m1/m2/m3/m5 2 6 8 7 7
      9 m4/m5 m3 m3/m4 6 3 5 3 7
      10 m2 m2/m4 m1/m2/m3 7 4 1 4 6
      11 m1/m5 m1 6 5 1 8 4
      12 m4/m5 m1/m2/m3/m4/m5 m1/m2/m4 5 3 1 8 8
      13 m2/m4/m5 m3 m4/m5 7 1 6 6 6
      14 m3 m1/m3/m5 2 1 4 6 3
      15 m3/m4/m5 8 6 5 3 2
      16 m1/m3 m3 8 6 6 7 2
      17 m3 8 4 6 7 1
      18 m4/m5 m2/m4 m5 4 3 5 2 6
      19 m1/m2/m4/m5 3 6 2 1 3
      20 m1/m4 m3/m5 m2/m4/m5 4 7 5 7 7

      表 9  各模具产品的序相关设置时间表

      Table 9.  The schedule of sequence setup time between each mold

      模具 序相关设置时间
      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
      1 2 3 3 4 3 3 3 3 2 1 3 1 4 4 4 2 4 2 1
      2 2 2 2 3 2 2 1 3 1 2 2 4 4 3 3 4 4 2 4
      3 2 3 4 3 3 4 2 1 2 3 3 1 4 2 1 3 3 4 3
      4 3 1 3 4 1 4 2 2 2 1 1 4 1 3 2 2 1 2 3
      5 4 4 4 2 1 1 1 4 1 1 1 3 2 1 3 2 4 3 3
      6 1 2 3 2 3 3 2 2 3 4 1 1 3 3 2 4 2 4 1
      7 3 4 4 4 1 2 1 1 4 2 2 3 2 2 2 4 1 1 2
      8 4 2 4 1 4 1 2 4 3 3 3 2 4 1 3 4 1 4 1
      9 4 2 3 3 2 4 4 1 2 2 3 2 1 2 4 2 1 4 3
      10 2 4 1 2 2 4 4 3 3 1 1 2 3 1 2 1 4 2 1
      11 3 4 3 2 2 2 1 2 2 2 2 4 3 3 2 1 2 2 2
      12 2 1 4 2 4 2 3 2 1 2 3 1 1 3 2 3 2 1 2
      13 2 1 2 4 2 1 4 2 4 2 4 3 4 4 3 4 3 4 1
      14 4 4 1 3 2 2 2 4 1 4 1 2 1 2 2 1 3 4 1
      15 3 2 2 3 1 2 3 4 3 1 2 1 3 1 2 3 1 4 4
      16 1 4 1 1 4 3 1 3 1 2 4 4 2 3 4 4 4 4 1
      17 4 3 1 1 3 2 3 1 3 4 1 1 3 2 1 1 2 1 1
      18 1 2 4 4 2 1 4 1 2 1 4 4 3 2 1 3 1 2 2
      19 2 3 2 2 2 3 4 1 1 3 2 2 2 3 3 2 4 1 2
      20 2 2 2 2 2 2 2 1 2 1 2 4 1 4 1 1 1 4 1

      表 10  模具各工序的加工时间表

      Table 10.  The processing time table of each mold

      模具 操作1 操作2 操作3
      m1 m2 m3 m4 m5 m1 m2 m3 m4 m5 m1 m2 m3 m4 m5
      1 27 18 29 27 17 23 29 19
      2 13 26 11 13
      3 23
      4 10 13 12 18 25 11 10 26 21 31 27
      5 9 8 16
      6 9 29 19 25 10 30 26 19
      7 19 22 28 10 28 24 27
      8 30 23 28 17
      9 31 24 9 8 28
      10 25 27 13 31 20 26
      11 25 24 12
      12 23 17 13 16 22 8 30
      13 16 19 22 28 27 23
      14 28 16 20 18 16 16 21
      15 28 29 23
      16 27 10 8
      17 26
      18 12 24 13 27 17
      19 24 19 12 14
      20 17 10 31 20 30 9 24

      对于上述实例, 分别使用表 7中各算法(即DPSO、DTLBO-Ⅱ、GA_DR_C、CCIWO、HDTLBO)进行求解, 设定算法运行时间均为$ n\times m\times 40 $ (ms)即4秒.对于上述5种算法分别独立运行20次, 每次运行结果如表 11所示.

      表 11  实例仿真结果

      Table 11.  Simulation results of the instance

      运行次数 DTLBO-Ⅱ GA DPSO CCIWO HDTLBO
      1 167 166 166 163 163
      2 164 166 164 163 166
      3 168 167 167 167 167
      4 169 166 164 166 163
      5 163 163 165 163 165
      6 167 165 166 167 163
      7 167 168 163 168 166
      8 166 168 167 164 168
      9 168 167 164 163 163
      10 169 168 165 164 165
      11 168 163 164 168 166
      12 169 168 169 167 163
      13 168 167 165 166 167
      14 163 170 166 170 166
      15 167 166 168 169 163
      16 166 167 166 171 163
      17 167 170 163 168 163
      18 169 168 164 170 165
      19 165 168 163 165 168
      20 167 168 164 167 163
      Average 166.85 166.95 165.15 166.45 164.8

      表 11可见, HDTLBO在20次独立运行中9次找到了最大完工时间$ C_{\max } $为163的最小解, 明显大于其他4种算法找到最小解的次数, 且HDTLBO运行20次的均值Average = 164.8小于其他算法的均值, 这也再次验证了HDTLBO具有良好的搜索性能.

      综上可知, HDTLBO能十分有效地求解PMSP_AMPS.

    • 本文针对一类复杂并行机调度问题, 即带到达时间、多工序、加工约束和序相关设置时间的并行机调度问题(PMSP_AMPS), 建立了排序模型并提出一种混合离散教与学优化算法(HDTLBO)进行求解.这是首次运用基于TLBO的算法求解PMSP_AMPS.在HDTLBO的全局搜索部分, 设计了不同的排序操作, 以此替换标准教与学算法的个体更新操作, 实现了算法的离散化, 使其能直接在问题的离散解空间中执行搜索, 从而在保留TLBO更新机理的前提下提高了算法的全局搜索效率.在局部搜索部分, 构造了基于InterchangeInsert邻域操作的变邻域局部搜索, 对全局搜索得到的优质区域执行较为细致的搜索, 使算法在全局和局部搜索之间达到较好平衡, 从而增强了算法的整体搜索能力.通过不同测试问题上的仿真实验和算法比较, 验证了HDTLBO是求解PMSP_AMPS的有效算法.现有的智能调度算法, 大多基于在连续优化领域取得成功应用的智能优化算法, 并在其中加入编码规则来实现解连续空间到问题离散空间的映射, 从而可求解相关调度问题.这一方式本质上是否有效, 尚无人进行探讨和分析.本文所提HDTLBO在保留标准TLBO进化框架基础上, 直接设计各种排序操作来替换原算法的核心操作, 取得了更好的搜索性能.这对其他智能调度算法的离散化设计具有一定的借鉴意义, 也有利于理解智能调度算法为何有效的本质原因.下一步的工作将把HDTLBO拓展用于求解智能制造中的绿色生产调度问题.

参考文献 (34)

目录

    /

    返回文章
    返回