留言板

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

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

求解多目标双资源柔性车间调度问题的改进NSGA-Ⅱ算法

张守京 杜昊天 侯天天

张守京, 杜昊天, 侯天天. 求解多目标双资源柔性车间调度问题的改进NSGA-Ⅱ算法[J]. 机械科学与技术, 2022, 41(5): 771-778. doi: 10.13433/j.cnki.1003-8728.20200375
引用本文: 张守京, 杜昊天, 侯天天. 求解多目标双资源柔性车间调度问题的改进NSGA-Ⅱ算法[J]. 机械科学与技术, 2022, 41(5): 771-778. doi: 10.13433/j.cnki.1003-8728.20200375
ZHANG Shoujing, DU Haotian, HOU Tiantian. An Improved NSGA-Ⅱ Algorithm for Solving Multi-objective Dual Resource Constrained Flexible Job Shop Scheduling Problem[J]. Mechanical Science and Technology for Aerospace Engineering, 2022, 41(5): 771-778. doi: 10.13433/j.cnki.1003-8728.20200375
Citation: ZHANG Shoujing, DU Haotian, HOU Tiantian. An Improved NSGA-Ⅱ Algorithm for Solving Multi-objective Dual Resource Constrained Flexible Job Shop Scheduling Problem[J]. Mechanical Science and Technology for Aerospace Engineering, 2022, 41(5): 771-778. doi: 10.13433/j.cnki.1003-8728.20200375

求解多目标双资源柔性车间调度问题的改进NSGA-Ⅱ算法

doi: 10.13433/j.cnki.1003-8728.20200375
基金项目: 

国家重点研发计划项目 2019YFB1707205

西安市现代智能纺织装备重点实验室 2019220614SYS021CG043

陕西省教育厅科研计划项目 17JK0321

详细信息
    作者简介:

    张守京(1976-), 副教授, 硕士生导师, 研究方向为智能制造技术及系统, zhangshoujing@xpu.edu.cn

  • 中图分类号: TH165

An Improved NSGA-Ⅱ Algorithm for Solving Multi-objective Dual Resource Constrained Flexible Job Shop Scheduling Problem

  • 摘要: 针对操作工人之间存在效率差异的多目标双资源柔性车间调度的问题, 构建了以生产时间最小化、生产成本最小化和绿色制造评价系数最小化为目标的柔性车间调度优化模型, 并设计了一种改进的NSGA-Ⅱ算法对其求解。首先, 采用量子编码对工序进行编码, 随后利用小生境技术初始化种群、重复个体控制策略和熵权法选择策略来提升算法效率, 避免算法早熟收敛, 并选出最优解。最后通过算例和改进前的NSGA-Ⅱ进行对比测试, 验证了改进后的NSGA-Ⅱ可以很好的解决上述的柔性车间调度问题。
  • 图  1  改进NSGA-Ⅱ算法流程图

    图  2  Pareto前沿图

    图  3  拟合Pareto前沿面

    图  4  生产时间迭代图

    图  5  绿色制造评价系数迭代图

    图  6  生产成本迭代图

    图  7  最优解的调度甘特图

    表  1  生产时间属性表

    属性 说明
    Ti i个工件的完工时间
    Tij 工件i的第j道工序完工时间
    Pijkr 工人r在机器k上加工工序Oij所需要实际时间
    Pijkrs 工人r在机器k上加工工序Oij所需要标准时间
    ωkr r个工人操作机器k的效率, 且0≤ωkr≤1
    Xijkr 若工人r在机器k上加工工序Oij为1, 否则为0
    下载: 导出CSV

    表  2  绿色制造评价系数属性表

    属性 说明
    gijkr 工人r在机器k上加工Oij的绿色制造评价系数
    Eijkr 工人r在机器k上加工Oij的能耗归一化结果
    Nijkr 工人r在机器k上加工Oij的噪音归一化结果
    Rijkr 工人r在机器k加工Oij的切屑回收归一化结果
    下载: 导出CSV

    表  3  生产成本属性表

    属性 说明
    MC 机器加工所需要的材料成本
    PC 机器加工所需要的加工成本
    PCM 加工过程中的机器成本
    PCH 加工过程中的员工成本
    mci i个工件的原材料成本
    Yijk 若在机器k上加工工序Oij为1, 否则为0
    PCkM 工件在机器k上运作单位时间的成本
    Zijr 若工人r加工工序Oij为1, 否则为0
    PCrH 工件由工人r进行加工单位时间的成本
    下载: 导出CSV

    表  4  工序标准时间表

    工件 工序 M1 M2 M3 M4 M5 M6
    J1 O11 6 4 5 3 4 -
    O12 10 - 8 7 7 9
    O13 - 9 - 6 7 6
    J2 O21 5 6 5 8 9 -
    O22 - 8 6 5 5 7
    O23 - 10 - 6 8 5
    O24 10 8 9 7 5 7
    J3 O31 10 - - 8 7 7
    O32 - 10 6 5 8 10
    O33 2 4 6 7 - 8
    J4 O41 4 2 5 6 8 7
    O42 10 8 4 7 8 6
    O43 8 7 8 4 2 3
    J5 O51 4 2 6 5 8 -
    O52 12 - 10 6 8 11
    O53 - 6 5 8 10 4
    O54 7 8 - 6 4 3
    J6 O61 8 9 5 6 6 7
    O62 11 - 9 10 8 8
    O63 10 7 8 12 11 -
    下载: 导出CSV

    表  5  工人可操控机器及操控效率

    机器 1 2 3 4 5 6
    1 1 0.8 - - 1 -
    2 - 1 0.9 - 0.85 1
    3 0.9 - - 0.9 0.9 -
    4 - 0.85 1 0.8 - -
    5 0.85 - 0.8 - 0.8 0.85
    6 - 0.9 - 1 - 0.8
    下载: 导出CSV

    表  6  工人单位时间成本

    工人 W1 W2 W3 W4 W5 W6
    单位成本 18 19 16 12 14 15
    下载: 导出CSV

    表  7  机器单位时间成本

    机器 M1 M2 M3 M4 M5 M6
    单位成本 52 58 57 63 61 57
    下载: 导出CSV

    表  8  最终的得到的31组解集

    序号 生产时间T 绿色制造评价系数G 生产成本C
    1 27.35 14.00 8 283.95
    2 27.35 14.17 8 271.95
    3 24.78 15.10 8 036.86
    4 25.59 14.83 8 287.44
    5 24.00 15.95 7 661.86
    6 24.56 15.79 7 660.75
    7 33.00 15.79 7 660.75
    8 27.78 13.99 8 634.78
    9 27.53 14.68 8 251.36
    10 32.33 14.29 8 102.36
    11 27.29 14.42 8 689.25
    12 28.00 13.74 8 237.10
    13 30.53 13.48 8 625.58
    14 26.78 13.44 8 919.52
    15 31.78 13.15 8 441.10
    16 31.00 13.35 8 932.58
    17 29.78 13.38 9 026.69
    18 28.29 13.69 8 752.92
    19 30.53 13.46 8 722.58
    20 31.78 13.45 8 423.92
    21 28.29 13.42 9 003.50
    22 32.33 14.44 8 021.36
    23 25.29 14.47 8 334.36
    24 28.67 13.58 8 554.58
    25 31.78 14.03 8 157.69
    26 26.31 14.72 8 200.58
    27 27.88 13.93 8 851.10
    28 30.78 14.33 8 157.69
    29 26.44 13.78 8 932.58
    30 26.44 14.31 8 854.58
    31 25.00 14.89 7 894.30
    下载: 导出CSV
  • [1] 栾飞, 蔡宗琰, 吴书强, 等. 求解低碳车间调度问题的改进鲸鱼算法[J]. 机械科学与技术, 2020, 39(5): 721-728 doi: 10.13433/j.cnki.1003-8728.20190198

    LUAN F, CAI Z Y, WU S Q, et al. Improved whale optimization algorithm of scheduling problem for low carbon workshop[J]. Mechanical Science and Technology for Aerospace Engineering, 2020, 39(5): 721-728 (in Chinese) doi: 10.13433/j.cnki.1003-8728.20190198
    [2] 黄伟, 阎春平, 王星荣, 等. 面向复杂工程项目型产品作业车间调度问题[J]. 机械科学与技术, 2020, 39(3): 400-410 doi: 10.13433/j.cnki.1003-8728.20190126

    HUANG W, YAN C P, WANG X R, et al. Job shop scheduling problem for complex engineering project products[J]. Mechanical Science and Technology for Aerospace Engineering, 2020, 39(3): 400-410 (in Chinese) doi: 10.13433/j.cnki.1003-8728.20190126
    [3] 栾飞, 吴书强, 李富康, 等. 一种求解柔性作业车间调度问题的鲸鱼群优化算法[J]. 机械科学与技术, 2020, 39(2): 241-246 doi: 10.13433/j.cnki.1003-8728.20190114

    LUAN F, WU S Q, LI F K, et al. A whale swarm optimization algorithm for solving flexible job shop scheduling problem[J]. Mechanical Science and Technology for Aerospace Engineering, 2020, 39(2): 241-246 (in Chinese) doi: 10.13433/j.cnki.1003-8728.20190114
    [4] 黄曙东, 张力, 戴立操. 复杂人机系统人误分析技术研究[J]. 工业工程与管理, 2007, 12(4): 70-74 doi: 10.3969/j.issn.1007-5429.2007.04.016

    HUANG S D, ZHANG L, DAI L C. The method of human error analysis for complicated man-machine system[J]. Industrial Engineering and Management, 2007, 12(4): 70-74 (in Chinese) doi: 10.3969/j.issn.1007-5429.2007.04.016
    [5] CAO X Z, YANG Z H. An improved genetic algorithm for dual-resource constrained flexible job shop scheduling[C]//International Conference on Intelligent Computation Technology and Automation. Shenzhen: IEEE, 2011: 42-45
    [6] LI J Y, HUANG Y, NIU X W, et al. A branch population genetic algorithm for dual-resource constrained job shop scheduling problem[J]. Computers & Industrial Engineering, 2016, 102: 113-131
    [7] GONG G L, DENG Q W, GONG X R, et al. A new double flexible job-shop scheduling problem integrating processing time, green production, and human factor indicators[J]. Journal of Cleaner Production, 2018, 174: 560-576 doi: 10.1016/j.jclepro.2017.10.188
    [8] ZHANG J, WANG W L, XU X L, et al. A multi-objective particle swarm optimization for dual-resource constrained shop scheduling with resource flexibility[C]//2013 IEEE Symposium on Computational Intelligence for Engineering Solutions (CIES). Singaporel: IEEE, 2013: 29-34
    [9] ZHANG J, JIE J, WANG W L, et al. A hybrid particle swarm optimisation for multi-objective flexible job-shop scheduling problem with dual-resources constrained[J]. International Journal of Computing Science and Mathematics, 2017, 8(6): 526-532 doi: 10.1504/IJCSM.2017.088956
    [10] LI J Y, SUN S D, HUANG Y. Adaptive hybrid ant colony optimization for solving dual resource constrained job shop scheduling problem[J]. Journal of Software, 2011, 6(4): 584-594
    [11] ZHENG X L, WANG L. A knowledge-guided fruit fly optimization algorithm for dual resource constrained flexible job-shop scheduling problem[J]. International Journal of Production Research, 2016, 54(18): 5554-5566 doi: 10.1080/00207543.2016.1170226
    [12] 陈呈频, 赵丹青, 董巧英. 基于改进智能水滴算法的双资源约束车间调度[J]. 浙江工业大学学报, 2016, 44(5): 559-563 doi: 10.3969/j.issn.1006-4303.2016.05.018

    CHEN C P, ZHAO D Q, DONG Q Y. Dual resource constrained scheduling of job shop based on improved intelligent water drop algorithm[J]. Journal of Zhejiang University of Technology, 2016, 44(5): 559-563 (in Chinese) doi: 10.3969/j.issn.1006-4303.2016.05.018
    [13] 陈少, 吉卫喜, 仇永涛, 等. 基于改进鸟群算法的双资源约束离散智能车间调度问题研究[J]. 现代制造工程, 2019(4): 20-26 https://www.cnki.com.cn/Article/CJFDTOTAL-XXGY201904004.htm

    CHEN S, JI W X, QIU Y T, et al. Improved bird swarm algorithm for dual resource constrained discrete intelligent job shop scheduling problem[J]. Modern Manufacturing Engineering, 2019(4): 20-26 (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XXGY201904004.htm
    [14] 张雷, 张北鲲, 鲍宏. 面向低碳低噪的螺纹车削工艺参数优化[J]. 计算机集成制造系统, 2018, 24(3): 639-648 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJJ201803011.htm

    ZHANG L, ZHANG B K, BAO H. Cutting parameters optimization of thread turning oriented to low carbon and low noise[J]. Computer Integrated Manufacturing Systems, 2018, 24(3): 639-648 (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JSJJ201803011.htm
    [15] 吴秀丽, 崔琪. 考虑可再生能源的多目标柔性流水车间调度问题[J]. 计算机集成制造系统, 2018, 24(11): 2792-2807 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJJ201811014.htm

    WU X L, CUI Q. Multi-objective flexible flow shop scheduling problem with renewable energy[J]. Computer Integrated Manufacturing Systems, 2018, 24(11): 2792-2807 (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JSJJ201811014.htm
    [16] 李伟平, 王世东, 周兵, 等. 基于响应面法和NSGA-Ⅱ算法的麦弗逊悬架优化[J]. 湖南大学学报(自然科学版), 2011, 38(6): 27-32 https://www.cnki.com.cn/Article/CJFDTOTAL-HNDX201106006.htm

    LI W P, WANG S D, ZHOU B, et al. Macpherson suspension parameter optimization based on response surface method and NSGA-Ⅱ algorithm[J]. Journal of Hunan University (Natural Sciences), 2011, 38(6): 27-32 (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-HNDX201106006.htm
    [17] 刘润恺, 于龙, 陈德明. 基于AHP-熵权法的高铁接触网可信性评价研究[J]. 铁道科学与工程学报, 2019, 16(8): 1882-1889 https://www.cnki.com.cn/Article/CJFDTOTAL-CSTD201908003.htm

    LIU R K, YU L, CHEN D M. Research on dependability evaluation of high-speed railway catenary based on AHP-entropy method[J]. Journal of Railway Science and Engineering, 2019, 16(8): 1882-1889 (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-CSTD201908003.htm
    [18] 刘伟. 双柔性多目标作业车间调度方法研究及原型系统开发[D]. 长沙: 湖南大学, 2018

    LIU W. Research on Multi-Objective Job Shop Scheduling with Double Flexibility and Prototype System Development[D]. Changsha: Hunan University, 2018 (in Chinese)
  • 加载中
图(7) / 表(8)
计量
  • 文章访问数:  133
  • HTML全文浏览量:  72
  • PDF下载量:  26
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-10-14
  • 刊出日期:  2022-05-01

目录

    /

    返回文章
    返回