An Improved NSGA-Ⅱ Algorithm for Solving Multi-objective Dual Resource Constrained Flexible Job Shop Scheduling Problem
-
摘要: 针对操作工人之间存在效率差异的多目标双资源柔性车间调度的问题, 构建了以生产时间最小化、生产成本最小化和绿色制造评价系数最小化为目标的柔性车间调度优化模型, 并设计了一种改进的NSGA-Ⅱ算法对其求解。首先, 采用量子编码对工序进行编码, 随后利用小生境技术初始化种群、重复个体控制策略和熵权法选择策略来提升算法效率, 避免算法早熟收敛, 并选出最优解。最后通过算例和改进前的NSGA-Ⅱ进行对比测试, 验证了改进后的NSGA-Ⅱ可以很好的解决上述的柔性车间调度问题。Abstract: Because the multi-objective dual resource constrained flexible job shop scheduling has efficiency differences among operators, a flexible workshop scheduling optimization model is established to minimize production time, production cost and green manufacturing evaluation coefficient, and then an improved NSGA-Ⅱ algorithm is proposed. Firstly, the scheduling process is coded through quantum coding, and the niche technology is used to initialize the population and repeated individual control strategy and the entropy weight method selection strategy to improve the quality of the improved NSGA-Ⅱ algorithm. Finally, the comparison of the test results between the NSGA-Ⅱ algorithm and the improved NSGA-Ⅱ algorithm verifies that the improved NSGA-Ⅱ algorithm can solve the above-mentioned flexible job shop scheduling problem.
-
表 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 表 2 绿色制造评价系数属性表
属性 说明 gijkr 工人r在机器k上加工Oij的绿色制造评价系数 E′ijkr 工人r在机器k上加工Oij的能耗归一化结果 N′ijkr 工人r在机器k上加工Oij的噪音归一化结果 R′ijkr 工人r在机器k加工Oij的切屑回收归一化结果 表 3 生产成本属性表
属性 说明 MC 机器加工所需要的材料成本 PC 机器加工所需要的加工成本 PCM 加工过程中的机器成本 PCH 加工过程中的员工成本 mci 第i个工件的原材料成本 Yijk 若在机器k上加工工序Oij为1, 否则为0 PCkM 工件在机器k上运作单位时间的成本 Zijr 若工人r加工工序Oij为1, 否则为0 PCrH 工件由工人r进行加工单位时间的成本 表 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 - 表 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 表 6 工人单位时间成本
工人 W1 W2 W3 W4 W5 W6 单位成本 18 19 16 12 14 15 表 7 机器单位时间成本
机器 M1 M2 M3 M4 M5 M6 单位成本 52 58 57 63 61 57 表 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 -
[1] 栾飞, 蔡宗琰, 吴书强, 等. 求解低碳车间调度问题的改进鲸鱼算法[J]. 机械科学与技术, 2020, 39(5): 721-728 doi: 10.13433/j.cnki.1003-8728.20190198LUAN 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.20190126HUANG 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.20190114LUAN 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.016HUANG 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.018CHEN 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.htmCHEN 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.htmZHANG 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.htmWU 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.htmLI 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.htmLIU 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]. 长沙: 湖南大学, 2018LIU W. Research on Multi-Objective Job Shop Scheduling with Double Flexibility and Prototype System Development[D]. Changsha: Hunan University, 2018 (in Chinese)