多目标遗传算法求解模糊柔性作业车间调度问题

楚雄师范学院学报 ›› 2023, Vol. 38 ›› Issue (3): 76-82.

多目标遗传算法求解模糊柔性作业车间调度问题

庄小叶¹, 李轲²

1.潍坊工程职业学院信息工程学院,山东青州 262500;
2.火箭军士官学校作战保障系,山东青州 262500

收稿日期:2022-12-12 出版日期:2023-05-20 发布日期:2023-08-07
作者简介:庄小叶（1983–）,女,副教授,研究方向为计算机网络、网络安全、计算机科学与技术。E-mail：50872285@qq.com,Tel：13780813656

Multi-objective Genetic Algorithm to Solve Fuzzy Flexible Job Shop Scheduling Problem

ZHUANG Xiaoye¹, LI Ke²

1. Department of Information Engineering, Weifang Engineering Vocational College, Qingzhou, Shandong Province 262500;
2. Department of Operational Support, Rocket Sergeant Academy, Qingzhou, Shandong Province 262500

Received:2022-12-12 Online:2023-05-20 Published:2023-08-07

摘要/Abstract

摘要： 建立了模糊数表示工件加工时间和交货期,以最大化平均客户满意度和最小化模糊完工时间为优化目标的多目标模糊柔性作业车间调度问题（Multi-objective fuzzy flexible job shop scheduling problem, MOFFJSP）模型,提出一种改进的多目标遗传算法（Multi-objective genetic algorithm,MOGA）。使用基于工序的编码方式表示调度解,并采用活动化解码方法改进解的质量。采用基于免疫和熵原理设计的交叉和变异算子来构造新解,并利用非支配排序和改进的精英保留策略来提升帕累托解集的多样性。通过仿真实验证明,改进的MOGA能够有效求解MOFFJSP问题模型。

关键词: 模糊柔性作业车间, 多目标遗传算法, 帕累托最优, 免疫和熵原理

Abstract: A multi-objective fuzzy flexible job shop scheduling problem (MOFFJSP) is established that uses fuzzy numbers to represent workpiece processing time and delivery date, and the optimization goal is to maximize average customer satisfaction and minimize fuzzy completion time. Process-based encoding is used to represent scheduling solutions, and active decoding methods to improve the quality of the solutions. The algorithm uses crossover and mutation operators designed based on the principles of immunity and entropy to construct new solutions, and uses non-dominated sorting and improved elite retention Strategies to improve the diversity of Pareto solution sets. Simulation experiments prove that the proposed MOGA can effectively solve the problem model.

Key words: fuzzy flexible job shop, multi-objective genetic algorithm, Pareto optimal, immune and entropy principle

中图分类号:

TP278

庄小叶, 李轲. 多目标遗传算法求解模糊柔性作业车间调度问题[J]. 楚雄师范学院学报, 2023, 38(3): 76-82.

ZHUANG Xiaoye, LI Ke. Multi-objective Genetic Algorithm to Solve Fuzzy Flexible Job Shop Scheduling Problem[J]. Journal of Chuxiong Normal University, 2023, 38(3): 76-82.

参考文献

[1] 庞新富,姜迎春,俞胜平,等.人机协同的柔性作业车间炼钢—连铸重调度方法[J].计算机集成制造系统,2018, 24(10):43-55.
PANG X F, JIANG Y C, YU S P, et al. Flexible job shop rescheduling method of steelmaking-continuous casting base on human-computer cooperation[J].computer Integrated Manufacturing Systems, 2018, 24(10):43-55.
[2] 吴秀丽. 多目标柔性作业车间调度技术研究[D].西安:西北工业大学(博士学位论文),2006.
WU X L.Research on multi-objective flexible job shop scheduling problem [D]. Xi'an: Northwestern Polytechnical University (Doctoral Dissertation), 2006.
[3] 李琳,霍佳震.钢管生产计划中的多目标柔性Job-shop调度问题[J].系统工程理论与实践,2009,29(8):117-126.
LI L, HUO J Z.Multi-objective flexible Job-shop scheduling problem in steel tubes production[J]. Systems Engineering-Theory & Practice, 2009, 29(8):117-126.
[4] De-Ming Lei, Ming Li, Ling Wang.A two-phase meta-heuristic for multiobjective flexible job shop scheduling problem with total energy consumption threshold[J]. IEEE Transactions on Cybernetics, 2018, 49(3): 1097-1109.
[5] Lvjiang Yin, Xinyu Li, Liang Gao, et al. A novel mathematical model and multi-objective method for the low-carbon flexible job shop scheduling problem[J]. Sustainable Computing: Informatics and Systems, 2017, 13: 15-30.
[6] Joe Cing Tay, NB Ho.Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems[J].computers & Industrial Engineering, 2008, 54(3):453-473.
[7] Jie Gao, Mitsuo Gen, Linyan Sun, Xiaohui Zhao.A hybrid of genetic algorithm and bottleneck shifting for multi-objective flexible job shop scheduling problems[J].computers & Industrial Engineering, 2007, 53(1): 149-162.
[8] Deming Lei.Pareto archive particle swarm optimization for multi-objective fuzzy job shop scheduling problems[J]. The International Journal of Advanced Manufacturing Technology, 2008, 37(1): 157-165.
[9] Saravanan M, Haq A N.Evaluation of meta-heuristic approaches for scheduling optimisation of flexible manufacturing systems[J]. International Journal of Computer Applications in Technology, 2011, 42(2-3): 150-158.
[10] 李尚函,胡蓉,钱斌,等.超启发式遗传算法求解模糊柔性作业车间调度[J].控制理论与应用,2020,37(2):316-330.
LI S H, HU R, QIAN B, et al. Hyper-heuristic genetic algorithm for solving fuzzy flexible job shop scheduling problem[J]. Control Theory & Applications, 2020, 37(2):316-330.
[11] 张长泽,李引珍,尹胜男,等.多目标模糊柔性作业车间调度问题优化[J].科学技术与工程,2020,20(3):8.
ZHANG C Z, LI Y Z, YIN S N, et al. Optimization of multi-objective fuzzy flexible job shop scheduling problem[J]. Science Technology and Engineering, 2020, 20(3):8.
[12] Xin-She Yang.Bat algorithm for multi-objective optimization[J]. International Journal of Bio-Inspired Computation, 2011, 3(5): 267-274.