高级检索

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

基于离散正弦优化算法的多目标混合零空闲置换流水车间调度

赵芮 郎峻 顾幸生

赵芮, 郎峻, 顾幸生. 基于离散正弦优化算法的多目标混合零空闲置换流水车间调度[J]. 华东理工大学学报(自然科学版). doi: 10.14135/j.cnki.1006-3080.20201201005
引用本文: 赵芮, 郎峻, 顾幸生. 基于离散正弦优化算法的多目标混合零空闲置换流水车间调度[J]. 华东理工大学学报(自然科学版). doi: 10.14135/j.cnki.1006-3080.20201201005
ZHAO Rui, LANG Jun, GU Xingsheng. Mixed No-idle Permutation Flow Shop Scheduling Problem Based on Multi-objective Discrete Sine Optimization Algorithm[J]. Journal of East China University of Science and Technology. doi: 10.14135/j.cnki.1006-3080.20201201005
Citation: ZHAO Rui, LANG Jun, GU Xingsheng. Mixed No-idle Permutation Flow Shop Scheduling Problem Based on Multi-objective Discrete Sine Optimization Algorithm[J]. Journal of East China University of Science and Technology. doi: 10.14135/j.cnki.1006-3080.20201201005

基于离散正弦优化算法的多目标混合零空闲置换流水车间调度

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

    赵芮:赵 芮(1994-),女,重庆永川人,硕士生,研究方向为生产调度。E-mail:Y30200968@mail.ecust.edu.cn

    通讯作者:

    顾幸生,E-mail:xsgu@ecust.edu.cn

  • 中图分类号: TB497

Mixed No-idle Permutation Flow Shop Scheduling Problem Based on Multi-objective Discrete Sine Optimization Algorithm

  • 摘要: 针对以最小化最大完工时间(makespan)和最小化最大拖期(maximum tardiness)为目标的多目标混合零空闲置换流水车间调度问题(Mixed No-idle Permutation Flow Shop Scheduling Problem, MNPFSP),提出了一种多目标离散正弦优化算法(Multi-objective Discrete Sine Optimization Algorithm, MDSOA)。首先,建立外部档案集(AS)存储Pareto解,并在每次迭代后对AS进行更新;其次,在正弦优化算法(Sine Optimization Algorithm,SOA)的基础上,引入迭代贪婪(IG)算法的破坏重构机制,重新定义了一种适用于离散调度问题的位置更新策略;最后,引入快速非支配排序和拥挤距离对种群进行筛选,在保留精英解的同时保证了解的多样性和分布性。选取Taillard Benchmark中11个不同规模的算例进行仿真实验,并将仿真结果与NSGA-II和NSGA-III算法进行比较,验证了MDSOA求解MNPFSP的有效性。

     

  • 图  1  基于FNDS和拥挤距离的选择策略

    Figure  1.  Selection strategy based on fast non-dominated sorting and crowding distance

    图  2  MDSOA算法流程图

    Figure  2.  Flowchart of the MDSOA

    图  3  MDSOA、NSGA-II和NSGA-III获得的Pareto前沿

    Figure  3.  Pareto front obtained by MDSOA, NSGA-II and NSGA-III algorithms

    表  1  正交设计因子水平表

    Table  1.   Factors and levels for orthogonal design

    FactorLevel 1Level 2Level 3
    ${\rm{MaxGen}}$100150300
    ${P_{{\rm{size}}}}$203050
    $\;\beta$0.10.30.5
    $K$304050
    下载: 导出CSV

    表  2  算例Ta051的正交试验结果

    Table  2.   Orthogonal test results for the instance of Ta051

    TestFactor levelsRV/%
    ${\rm{MaxGen}}$${P_{{\rm{size}}}}$$\;\beta$$K$
    1100(1)20(1)0.1(1)30(1)0.339
    2100(1)30(2)0.3(2)40(2)0.508
    3100(1)50(3)0.5(3)50(3)0.485
    4150(2)20(1)0.3(2)50(3)0.271
    5150(2)30(2)0.5(3)30(1)0.485
    6150(2)50(3)0.1(1)40(2)0.610
    7300(3)20(1)0.5(3)40(2)0.746
    8300(3)30(2)0.1(1)50(3)0.576
    9300(3)50(3)0.3(2)30(1)0.898
    k10.4350.4520.5080.565
    k20.4460.5140.5590.621
    k30.7400.6550.5540.435
    Range0.3050.2030.0510.186
    Level1243
    下载: 导出CSV

    表  3  NSGA-II和NSGA-III的参数设置

    Table  3.   Parameter settings of NSGA-II and NSGA-III algorithms

    Algorithm${\rm{MaxGen}}$${P_{{\rm{size}}}}$${P_{\rm c}}$${P_{\rm m}}$
    NSGA-II300500.70.4
    NSGA-III300500.50.5
    下载: 导出CSV

    表  4  ${N_{{\rm{NDS}}}}$的计算结果

    Table  4.   Computational results of${N_{{\rm{NDS}}}}$

    ProblemMsetn×mNSGA-IINSGA-IIIMDSOA
    AvgSDAvgSDAvgSD
    Ta001220×515.105.4913.604.2240.000.00
    Ta011520×1012.003.699.602.8438.602.37
    Ta0211120×209.603.448.402.1515.506.05
    Ta031350×531.902.4730.204.8139.301.19
    Ta041850×1011.502.8711.503.1137.806.60
    Ta0511550×2010.703.2610.301.7913.506.68
    Ta0614100×521.006.1331.105.1940.000.00
    Ta0717100×1014.104.7217.807.3640.000.00
    Ta08110100×2011.102.6611.503.8015.406.65
    Ta0913200×1018.804.1213.106.8839.800.40
    Ta1016200×2013.903.5310.102.3417.109.47
    Average15.433.8515.204.0430.643.58
    下载: 导出CSV

    表  5  SM的计算结果

    Table  5.   Computational results of SM

    ProblemMsetn×mNSGA-IINSGA-IIIMDSOA
    AvgSDAvgSDAvgSD
    Ta001220×525.1911.3318.7212.498.494.82
    Ta011520×1044.4828.6772.5893.8211.792.96
    Ta0211120×20108.61135.99133.4289.0533.5827.49
    Ta031350×514.956.3823.3911.3218.387.04
    Ta041850×1040.7427.1969.3451.3918.9710.81
    Ta0511550×20195.52186.81108.1978.2132.3324.06
    Ta0614100×513.629.3411.247.8714.764.47
    Ta0717100×1099.05123.54126.3274.9341.1736.82
    Ta08110100×2054.8739.26114.82117.7730.5620.46
    Ta0913200×1034.8917.1970.5772.9340.3646.85
    Ta1016200×2050.6850.3587.1497.1258.7236.16
    Average62.0557.8275.9864.2628.1020.18
    下载: 导出CSV

    表  6  ${\rm{DI}_{\rm{R}}}$的计算结果

    Table  6.   Computational results of ${\rm{DI}_{\rm{R}}}$

    ProblemMsetn×mNSGA-IINSGA-IIIMDSOA
    AvgSDAvgSDAvgSD
    Ta001220×50.230.060.210.070.050.05
    Ta011520×100.300.090.430.090.060.03
    Ta0211120×200.430.120.490.150.040.02
    Ta031350×50.130.030.140.030.010.01
    Ta041850×100.900.081.170.160.100.10
    Ta0511550×200.980.161.350.170.080.06
    Ta0614100×50.270.120.440.230.010.01
    Ta0717100×101.890.652.530.590.040.07
    Ta08110100×201.540.242.020.270.080.05
    Ta0913200×102.200.442.990.590.020.03
    Ta1016200×203.530.454.470.470.230.12
    Average1.130.221.480.260.070.05
    下载: 导出CSV

    表  7  IGD的计算结果

    Table  7.   Computational results of IGD

    ProblemMsetn×mNSGA-IINSGA-IIIMDSOA
    AvgSDAvgSDAvgSD
    Ta001220×50.4212.840.4112.660.1813.39
    Ta011520×100.6115.240.9123.030.1810.05
    Ta0211120×201.2626.821.4837.630.438.17
    Ta031350×50.4912.290.7412.990.3127.76
    Ta041850×102.2624.622.8525.800.5716.28
    Ta0511550×204.3884.315.9493.221.4648.85
    Ta0614100×51.3578.951.92106.120.0710.90
    Ta0717100×103.0157.944.4652.410.6251.69
    Ta08110100×207.65110.929.74107.001.5739.99
    Ta0913200×105.3872.217.07144.190.3043.67
    Ta1016200×2012.22123.8315.38156.131.1047.91
    Average3.5556.364.6370.110.6228.97
    下载: 导出CSV
  • [1] 刘翱, 冯骁毅, 邓旭东, 等. 求解零空闲置换流水车间调度问题的离散烟花算法[J]. 系统工程理论与实践, 2018, 38(11): 2874-2884.
    [2] PAN Q K, WANG L. No-idle permutation flow shop scheduling based on a hybrid discrete particle swarm optimization algorithm[J]. International Journal of Advanced Manufacturing Technology, 2008, 39(7/8): 796-807.
    [3] PAN Q K, RUIZ R. An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem[J]. Omega, 2014, 44(2): 41-50.
    [4] 张晓霞, 吕云虹. 一种求解混合零空闲置换流水车间调度禁忌分布估计算法[J]. 计算机应用与软件, 2017, 34(1): 270-274, 292.
    [5] CHENG C Y, YING K C, CHEN H H, et al. Minimising makespan in distributed mixed no-idle flowshops[J]. International Journal of Production Research, 2019, 57(1): 48-60. doi: 10.1080/00207543.2018.1457812
    [6] ROSSI F L, NAGANO M S. Heuristics for the mixed no-idle flowshop with sequence-dependent setup times and total flowtime criterion[J]. Expert Systems with Applications, 2019, 125(1): 40-54.
    [7] SANTOSA B, SISWANTO N. Discrete particle swarm optimization to solve multi-objective limited-wait hybrid flow shop scheduling problem[J]. IOP Conference Series: Materials Science and Engineering, 2018, 337(1): 012006.
    [8] PAN Q K, WANG L, QIAN B. A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems[J]. Computers & Operations Research, 2009, 36(8): 2498-2511.
    [9] LEI D M, ZHENG Y L. Hybrid flow shop scheduling with assembly operations and key objectives: A novel neighborhood search[J]. Applied Soft Computing, 2017, 61: 122-128. doi: 10.1016/j.asoc.2017.07.058
    [10] MURILO Z, APARECIDO C A, JOSU C. A decomposition-based kernel of Mallows models algorithm for bi- and tri-objective permutationflowshop scheduling problem[J]. Applied Soft Computing Journal, 2018, 71: 526-537. doi: 10.1016/j.asoc.2018.07.011
    [11] MESHKAT M, PARHIZGAR M. Sine optimization algorithm (SOA): A novel optimization algorithm by change update position strategy of search agent in sine cosine algorithm[C]//2017 3rd Iranian Conference on Intelligent Systems and Signal Processing (ICSPIS)[C]. Shahrood, Iran: IEEE, 2017: 11-16.
    [12] MIRJALILI S. SCA: A Sine Cosine Algorithm for solving optimization problems[J]. Knowledge-Based Systems, 2016, 96: 120-133. doi: 10.1016/j.knosys.2015.12.022
    [13] FERNANDEZ-VIAGAS V, FRAMINAN J M. A beam-search-based constructive heuristic for the PFSP to minimise total flowtime[J]. Computers and Operations Research, 2017, 81: 167-177. doi: 10.1016/j.cor.2016.12.020
    [14] JOLAI F, ASEFI H, RABIEE M, et al. Bi-objective simulated annealing approaches for no-wait two-stage flexible flow shop scheduling problem[J]. Scientia Iranica, 2013, 20(3): 861-872.
    [15] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. doi: 10.1109/4235.996017
    [16] MIRJALILI S, LEWIS A. Novel performance metrics for robust multi-objective optimization algorithms[J]. Swarm and Evolutionary Computation, 2015, 21: 1-23. doi: 10.1016/j.swevo.2014.10.005
    [17] DEB K, AGARWAL S, PRATAP A, et al. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II[C]//International Conference on Parallel Problem Solving from Nature. Berlin, Heidelberg: Springer, 2000: 849-858.
    [18] TAILLARD E. Benchmarks for basic scheduling problems[J]. European Journal of Operational Research, 1993, 64(2): 278-285. doi: 10.1016/0377-2217(93)90182-M
    [19] DEB K, JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach: Part I. Solving problems with box constraints[J]. IEEE transactions on evolutionary computation, 2014, 18(4): 577-601. doi: 10.1109/TEVC.2013.2281535
    [20] MINELLA G, RUIZ R, CIAVOTTA M. Restarted iterated Pareto greedy algorithm for multi-objective flowshop scheduling problems[J]. Computers & Operations Research, 2011, 38(11): 1521-1533.
    [21] RIQUELME N, LÜCKEN C V, BARAN B. Performance metrics in multi-objective optimization[C]//Latin American Computing Conference (CLEI). Arequipa, Peru: IEEE, 2015: 286-296.
    [22] QIAN B, WANG L, HUANG D X, et al. An effective hybrid DE-based algorithm for flow shop scheduling with limited buffers[J]. Computers & Operations Research, 2009, 33(10): 2960-2971.
  • 加载中
图(3) / 表(7)
计量
  • 文章访问数:  212
  • HTML全文浏览量:  167
  • PDF下载量:  3
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-12-01
  • 网络出版日期:  2021-03-24

目录

    /

    返回文章
    返回