2.845

2023影响因子

(CJCR)

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

留言板

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

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

求解差异机器平行批调度的双目标协同蚁群算法

贾兆红 王燕 张以文

贾兆红, 王燕, 张以文. 求解差异机器平行批调度的双目标协同蚁群算法. 自动化学报, 2020, 46(6): 1121−1135 doi: 10.16383/j.aas.c180834
引用本文: 贾兆红, 王燕, 张以文. 求解差异机器平行批调度的双目标协同蚁群算法. 自动化学报, 2020, 46(6): 1121−1135 doi: 10.16383/j.aas.c180834
Jia Zhao-Hong, Wang Yan, Zhang Yi-Wen. A bi-objective synergy optimization algorithm of ant colony for scheduling on non-identical parallel batch machines. Acta Automatica Sinica, 2020, 46(6): 1121−1135 doi: 10.16383/j.aas.c180834
Citation: Jia Zhao-Hong, Wang Yan, Zhang Yi-Wen. A bi-objective synergy optimization algorithm of ant colony for scheduling on non-identical parallel batch machines. Acta Automatica Sinica, 2020, 46(6): 1121−1135 doi: 10.16383/j.aas.c180834

求解差异机器平行批调度的双目标协同蚁群算法

doi: 10.16383/j.aas.c180834
基金项目: 国家自然科学基金(71601001, 71671168), 中国教育部人文社会科学青年基金会(15YJC630041), 安徽省科学基金(1608085MG154), 安徽省教育厅自然科学基金(KJ2015A062)资助
详细信息
    作者简介:

    贾兆红:安徽大学计算机科学与技术学院教授. 2008年获得中国科技大学博士学位. 主要研究方向为计算智能, 多目标优化, 决策支持. 本文通信作者. E-mail: jiazhaohong001@163.com

    王燕:安徽大学硕士研究生. 主要研究方向为多目标优化, 进化计算. E-mail: yanwang0501@outlook.com

    张以文:安徽大学计算机科学与技术学院教授. 主要研究方向为服务计算, 云计算, 电子商务. E-mail: zhangyiwen@ahu.edu.cn

A Bi-objective Synergy Optimization Algorithm of Ant Colony for Scheduling on Non-identical Parallel Batch Machines

Funds: Supported by National Natural Science Foundation of China (71601001, 71671168), Humanity and Social Science Youth Founda-tion of Ministry of Education of China (15YJC630041), Natural Science Foundation of Anhui Province (1608085MG154), and Natural Science Foundation of Anhui Provincial Department of Education (KJ2015A062)
  • 摘要: 利用用户的偏好信息, 提出一种基于蚁群的双目标协同优化算法(Bi-objective synergy ant colony optimization algorithm based on Pareto domination, PDACO)并用于求解平行批处理机调度问题. 考虑在一组差异容量并带有不同加工功率的平行批处理机器上, 加工带有不同到达时间、尺寸和加工时间的一组工件, 以同时最小化最大完工时间和总能耗. 偏好向量的引入虽然可以提高算法的收敛性, 但会降低解的多样性. 为了弥补这一缺陷, 在本文所提算法中, 利用两个子蚁群分别沿着不同方向, 迭代地进行独立和联合搜索. 最后, 通过大量的仿真实验验证了本文提出算法的有效性.
  • 图  1  $ {\sigma _{{\rm{0}}}} $ 甘特图

    Fig.  1  The Gantt chart of $ \sigma_{{\rm{0}}} $

    图  2  $ {\sigma _{{\rm{1}}}} $ 甘特图

    Fig.  2  The Gantt chart of $ \sigma_{{\rm{1}}} $

    图  3  PDACO算法总流程图

    Fig.  3  The flowchart of algorithm PDACO

    图  4  ($ N_1 $, $ N_2 $), $ K $, $ \rho $, $ Q $不同取值获得的$ H $

    Fig.  4  The values of $ H $ under different values of ($ N_1 $, $ N_2 $), $ K $, $ \rho $ and $ Q $

    图  5  $ ({\alpha _{{\rm{1}}}},{\beta _1}) $, $ ({\alpha _{{\rm{2}}}},{\beta _2}) $不同取值获得的$ H $

    Fig.  5  The values of $ H $ under different values of $ ({\alpha _{{\rm{1}}}},{\beta _1}) $, $ ({\alpha _{{\rm{2}}}},{\beta _2}) $

    图  6  采用不同策略时获得的$ H $

    Fig.  6  The values of $ H $ using different strategies

    图  7  4组不同工件数测试实例目标函数

    Fig.  7  Solution distribution on four instances with different number of jobs

    图  8  90个工件实例调度甘特图

    Fig.  8  The Gantt chart of the example with 90 jobs

    表  1  编码实例

    Table  1  An example of a solution encoding

    Jj b i
    J1 2 3
    J2 1 4
    J3 3 2
    J4 5 4
    J5 4 1
    J6 2 3
    J7 3 2
    J8 5 5
    J9 1 4
    下载: 导出CSV

    表  2  实例参数

    Table  2  The example of the problem

    Bbi Rbi PTbi
    B11 3 7
    B21 125
    B12 54
    B22 25
    B32 3 4
    下载: 导出CSV

    表  3  实验参数设置

    Table  3  Experimental parameter settings

    参数 符号 取值
    工件数 n $n \in ${90, 108, 126, 144, 162, 180, 216,
    252, 306, 360, 432}
    工件尺寸 $s_j$ ${s_j}\sim $P$({\lambda_i}),{\lambda _1} = 5,{\lambda _2} = 12.5, $
    ${\lambda _3} = 32.5 $
    工件到达时间 rj U [1, R]
    工件加工时间 pj U [8, 48]
    机器数 $m_i$ m1 = 5, m2 = 3, m3 = 2
    机器容量 $S^i$ S 1 = 10, S 2 = 25, S 3 = 65
    机器功率 $l^i$ l 1 = 10, l 2 = 35, l 3 = 85
    下载: 导出CSV

    表  4  比较算法的参数设置

    Table  4  The parameter settings of comparative algorithms

    PDACO PACO NSGA-II SPEA2 SMPSO
    $N_1: 50$ $N:100$ $N:100$ $N:100$ $N: 100$
    $N_2: 50$ $Q_a: 100$ $Q_a: 100$ $r_1 \in [0,1], r_2 \in[0,1]$
    交叉概率: 1.0 交叉概率: 1.0 交叉概率: 0.9
    变异概率: 0.01 变异概率: 0.01 变异概率: 1/L
    $T_{\max}=200$ $T_{\max}=200$ $T_{\max}=200$ $T_{\max}=200$ $T_{\max}=200$
    下载: 导出CSV

    表  5  NPS指标值比较结果

    Table  5  Comparison of the five algorithms using the NPS metric

    工件数 PDACO PACO NSGA-II SPEA2 SMPSO
    MAX MIN AVG MAX MIN AVG MAX MIN AVG MAX MIN AVG MAX MIN AVG
    90 11.10 3.20 6.80 10.40 2.65 6.30 7.75 1.00 2.74 4.25 1.00 1.22 8.4 1.2 4.26
    108 11.45 3.00 7.00 10.05 2.75 6.36 7.85 1.00 2.92 5.65 1.00 1.51 7.95 1.4 4.07
    126 11.40 3.80 7.24 10.50 2.75 6.28 7.75 1.05 2.84 6.95 1.00 1.73 8.2 1.3 3.99
    144 12.85 3.65 7.62 19.15 7.40 13.04 8.80 1.00 3.02 8.05 1.00 1.92 7.9 1.35 4
    162 11.50 3.60 7.39 10.50 3.30 6.63 9.70 1.00 3.05 6.95 1.00 1.73 7.35 1.25 3.93
    180 12.35 3.45 7.40 11.40 2.55 6.64 8.95 1.00 2.95 7.70 1.00 2.11 8.35 1.25 4.15
    216 12.40 3.90 7.75 11.40 3.20 7.04 8.55 1.00 2.71 8.20 1.00 2.11 7.95 1.2 4.03
    252 12.45 3.75 7.87 11.35 3.55 7.16 9.25 1.00 2.71 8.60 1.00 2.01 7.6 1.4 4.02
    306 12.35 3.60 7.72 11.30 3.20 7.00 8.45 1.00 2.55 8.50 1.00 2.00 8.1 1.3 4.11
    360 12.75 3.60 7.79 11.85 3.35 7.40 7.75 1.00 2.42 9.05 1.00 2.06 8.15 1.3 4.21
    432 13.15 4.00 8.10 12.15 3.25 7.61 8.05 1.00 2.39 7.65 1.00 1.76 8.2 1.25 4.04
    下载: 导出CSV

    表  6  覆盖率$(C) $比较结果

    Table  6  Comparison of the five algorithms using the C metric

    工件数 C (PDACO,
    PACO)
    C (PACO,
    PDACO)
    C (PDACO,
    NSGA-II)
    C (NSGA-II,
    PDACO)
    C (PDACO,
    SPEA2)
    C (SPEA2,
    PDACO)
    C (PDACO,
    SMPSO)
    C (SMPSO,
    PDACO)
    90 0.988 0.001 0.801 0.001 0.757 0 0.833 0.021
    108 0.971 0.003 0.608 0.001 0.564 0.001 0.743 0.004
    126 0.986 0.002 0.656 0 0.599 0 0.647 0
    144 0.994 0 0.504 0 0.476 0 0.561 0
    162 0.997 0 0.421 0 0.677 0 0.587 0
    180 0.999 0 0.554 0 0.533 0 0.533 0
    216 0.995 0 0.470 0 0.577 0 0.516 0
    252 0.997 0 0.421 0 0.426 0 0.452 0
    306 0.997 0 0.529 0 0.645 0 0.513 0
    360 0.989 0 0.606 0 0.553 0 0.459 0
    432 0.997 0 0.501 0 0.439 0 0.466 0
    下载: 导出CSV

    表  7  超体$(H) $指标比较结果

    Table  7  Comparison of the five algorithms using the H metric

    工件数 PDACO PACO NSGA-II SPEA2 SMPSO
    90 469 603 277 319 110 110 111 396 121 352
    108 650 187 403 180 146 403 148 960 147 856
    126 933 105 539 363 256 380 236 164 271 332
    144 1 232 318 690 126 275 805 303 290 288 495
    162 1 472 585 793 386 318 719 358 388 341 864
    180 1 814 061 1 000 950 413 532 465 956 428 793
    216 2 577 210 1 385 263 560 037 671 642 635 549
    252 3 489 851 1 874 024 749 649 888 686 815 992
    306 4 969 991 2 614 455 1 079 066 1 314 258 1 179 523
    360 6 638 616 3 478 054 1 555 105 1 878 950 1 638 628
    432 8 805 782 4 469 622 2 106 786 2 439 180 2 266 835
    下载: 导出CSV

    表  8  多样性(DVR)、Spacing(SPC)和时间(T)指标比较结果

    Table  8  Comparison of the five algorithms using the DVR, SPC and T metrics

    工件数 PDACO PACO NSGA-II SPEA2 SMPSO
    DVR SPC T DVR SPC T DVR SPC T DVR SPC T DVR SPC T
    90 137 262 0.89 0.86 89 010 0.82 0.83 17 167 0.26 1.87 4 121 0.04 2.17 21 362 0.36 1.14
    108 164 060 0.89 1.08 110 360 0.84 1.13 20 772 0.29 2.39 17 299 0.11 2.96 26 815 0.33 1.28
    126 219 865 0.92 1.44 141 594 0.86 1.49 46 860 1.01 2.88 28 803 0.13 3.93 52 619 0.52 1.5
    144 256 752 0.91 1.80 166 727 0.84 1.65 24 153 0.29 3.61 59 443 0.22 4.65 39 526 0.23 1.7
    162 294 754 0.88 2.30 197 631 0.86 2.53 24 276 0.28 4.43 54 872 0.14 5.62 43 511 0.22 1.83
    180 328 732 0.92 2.67 213 904 0.83 3.17 27 072 0.26 5.07 102 915 0.27 6.59 27 342 0.24 2.28
    216 435 913 0.94 3.83 290 015 0.90 4.40 21 623 0.25 17.00 133 770 0.27 9.01 25 113 0.24 2.29
    252 520 652 0.93 5.05 370 128 0.90 5.94 23 940 0.22 9.43 179 343 0.23 12.87 34 619 0.25 2.57
    306 664 941 0.94 7.36 451 475 0.89 8.53 24 801 0.24 20.53 293 842 0.27 21.12 33 428 0.24 3.07
    360 800 856 0.91 10.33 535 670 0.93 12.33 23 838 0.19 27.58 431 781 0.28 27.80 49 734 0.26 3.46
    432 1 010 000 0.96 14.77 789 834 0.94 17.54 23 959 0.17 36.70 374 310 0.19 40.10 66 253 0.21 4.03
    下载: 导出CSV
  • [1] Ahmadi J H, Ahmadi R H, Dasu S, Tang C S. Batching and scheduling jobs on batch and discrete processors. Operations research, 1992, 40(4): 750−763 doi: 10.1287/opre.40.4.750
    [2] 原豪男, 郭戈. 交通信息物理系统中的车辆协同运行优化调度. 自动化学报, 2019, 45(1): 143−152

    Yuan Hao-Nan, Guo Ge. Vehicle cooperative optimization scheduilng intransportation cyber physical systems. Acta Automatica Sinica, 2019, 45(1): 143−152
    [3] Uzsoy R. Scheduling a single batch processing machine with non-identical job sizes. International Journal of Production Research, 1994, 32(7): 1615−1635 doi: 10.1080/00207549408957026
    [4] Ikura Y, Gimple M. Efficient scheduling algorithms for a single batch processing machine. Operations Research Letters, 1986, 5(2): 61−65 doi: 10.1016/0167-6377(86)90104-5
    [5] 赵玉芳, 唐立新. 极小化最大完工时间的单机连续型批调度问题. 自动化学报, 2006, 32(5): 730−737

    Zhao Yu-Fang, Tang Li-Xin. Scheduling a single continuous batch processing machine to minimize makespan. Acta Acta Automatica Sinica, 2006, 32(5): 730−737
    [6] Zhou H M, Pang J H, Chen P K, Chou F D. A modified particle swarm optimization algorithm for a batch-processing machine scheduling problem with arbitrary release times and non-identical job sizes. Computers and Industrial Engineering, 2018, 123: 67−81
    [7] Chang P Y, Damodaran P, Melouk S. Minimizing makespan on parallel batch processing machines. International Journal of Production Research, 2004, 42(19): 4211−4220 doi: 10.1080/00207540410001711863
    [8] Jia Z H, Wang Y, Wu C, Yang Y, Zhang X Y, Chen H P. Multi-objective energy-aware batch scheduling using ant colony optimization algorithm. Computer and Industrial Engineering, 2019, 131: 41−56
    [9] Shi Z S, Huang Z W, Shi L Y. Customer order scheduling on batch processing machines with incompatible job families. International Journal of Production Research, 2018, 56(1-2): 795−808 doi: 10.1080/00207543.2017.1401247
    [10] Zhou S C, Xie J H, Du N, Pang Y. A random-keys genetic algorithm for scheduling unrelated parallel batch processing machines with different capcities and arbitrary job sizes. Applied Mathematics and Computation, 2018, 334: 254−268 doi: 10.1016/j.amc.2018.04.024
    [11] Arroyo J E C, Leung J Y T. Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times. Computers and Operations Research, 2017, 78: 117−128
    [12] 陆志强, 刘欣仪. 考虑资源转移时间的资源受限项目调度问题的算法. 自动化学报, 2018, 44(6): 1028−1036

    Lu Zhi-Qiang, Liu Xin-Yi. Algorithm for resource-constrained project scheduling problem with resource transfer time. Acta Automatica Sinica, 2018, 44(6): 1028−1036
    [13] Zhou S C, Li X L, Du N, Pang Y, Chen H P. A multi-objective differential evolution algorithm for parallel batch processing machine scheduling considering electricity consumption cost. Computers and Operations Research, 2018, 96: 55−68
    [14] Du B, Chen H P, Huang G Q, Yang H D. Preference vector ant colony system for minimising make-span and energy consumption in a hybrid flow shop. Multi-objective Evolutionary Optimisation for Product Design and Manufacturing. Springer-London, 2011. 279–304
    [15] Jia Z H, Zhang Y L, Leung J Y T, Li K. Bi-criteria ant colony optimization algorithm for minimizing makespan and energy consumption on parallel batch machines. Applied Soft Computing, 2017, 55: 226−237 doi: 10.1016/j.asoc.2017.01.044
    [16] 汪恭书, 刘静宜, 唐立新. 连铸–轧制混流生产模式下轧批调度问题的分支–定价算法. 自动化学报, 2017, 43(7): 1178−1189

    Wang Gong-Shu, Liu Jing-Yi, Tang Li-Xin. Branch-and-price algorithm for rolling batch scheduling problem in continuous-casting and rolling processes with hybrid production mode. Acta Automatica Sinica, 2017, 43(7): 1178−1189
    [17] 郎劲, 唐立新. 考虑爬坡约束的油井间抽批调度问题. 自动化学报, 2019, 45(2): 388−397

    Lang Jin, Tang Li-Xin. Batch scheduling problem of oil well considering ramping constraints in oilfield production. Acta Automatica Sinica, 2019, 45(2): 388−397
    [18] Zhao B X, Gao J M, Chen K, Guo K. Two-generation Pareto ant colony algorithm for multi-objective job shop scheduling problem with alternative process plans and unrelated parallel machines. Journal of Intelligent Manufacturing, 2018, 29(1): 93−108 doi: 10.1007/s10845-015-1091-z
    [19] Wu Y, Gong M G, Ma W P, Wang S F. High-order graph matching based on ant colony optimization. Neurocomputing, 2019, 328: 97−104 doi: 10.1016/j.neucom.2018.02.104
    [20] Eskandari L, Jafarian A, Rahimloo P, Baleanu D. A modified and enhanced ant colony optimization algorithm for traveling salesman problem. Mathematical Methods in Engineering. Springer-Cham, 2019. 257–265
    [21] Stützle T, Hoos H H. MAX-MIN ant system. Future Generation Computer Systems, 2000, 16(8): 889−914 doi: 10.1016/S0167-739X(00)00043-1
    [22] Jia Z H, Leung J Y T. A meta-heuristic to minimize makespan for parallel batch machines with arbitrary job sizes. European Journal of Operational Research, 2015, 240(3): 649−665 doi: 10.1016/j.ejor.2014.07.039
    [23] Deb K, Agrawal S, Pratap A, Meyarivan T. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In: Proceedings of the 2000 International Conference on Parallel Problem Solving from Nature. Berlin, Heidelberg: Springer, 2000. 849–858
    [24] Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength Pareto evolutionary algorithm. TIK-Report, 2001, 103
    [25] Nebro A J, Durillo J J, Garcia-Nieto J, Coello C C A, Luna F, Alba E. SMPSO: A new PSO-based metaheuristic for multi-objective optimization. In: Proceedings of the 2009 IEEE Symposium on Computational Intelligence in Multi-Criteria Decision-Making. IEEE, 2009. 66–73
    [26] Wang J Q, Leung J Y T. Scheduling jobs with equal-processing-time on parallel machines with non-identical capacities to minimize makespan. International Journal of Production Economics, 2014, 156: 325−331 doi: 10.1016/j.ijpe.2014.06.019
    [27] Jia Z H, Li X H, Leung J Y T. Minimizing makespan for arbitrary size jobs with release times on P-batch machines with arbitrary capacities. Future Generation Computer Systems, 2017, 67: 22−34
  • 加载中
图(8) / 表(8)
计量
  • 文章访问数:  1769
  • HTML全文浏览量:  82
  • PDF下载量:  185
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-12-17
  • 录用日期:  2019-08-08
  • 网络出版日期:  2020-07-10
  • 刊出日期:  2020-07-10

目录

    /

    返回文章
    返回