多AGV和机器集成的多目标柔性作业车间调度研究

doi:10.3778/j.issn.1002-8331.2106-0403

摘要/Abstract

摘要： 为解决智能制造环境中具有多时间和多AGV约束的柔性作业车间调度问题，构建了以最小化最大完工时间、最小化总延期、最小化设备总负荷为目标的机器/AGV双约束多目标调度模型，模型中综合考虑加工时间、工件到达时间、交货期等多时间因素，进行了多AGV和机器集成调度。为求解该模型，设计了新的AGV调度规则和改进的NSGA-Ⅱ算法，算法中提出了基于工序的扩展染色体编码方式和基于AGV分配的贪婪式解码策略，同时设计了不同参数控制的多种群二元锦标赛选择和分段交叉变异策略以及基于Pareto级的去重精英保留策略，以促进个体协同优化搜索。通过实例实验，分析了不同AGV数量任务分配方案下的模型有效性，对4个案例的仿真测试和同类算法比较解也验证了改进NSGA-Ⅱ算法求解该模型的有效性。

关键词: 柔性作业车间调度, 多时间因素, 自动导引小车, 多目标优化, NSGA-Ⅱ算法

Abstract: In order to solve the flexible job shop scheduling problem with multi-time and multi-AGV constraints in the intelligent manufacturing environment, a machine AGV dual-constraint multi-objective scheduling with the goal of minimizing the maximum completion time, minimizing the total delay, and minimizing the total equipment load is constructed. In the model, multi-time factors such as processing time, workpiece arrival time, and delivery date are comprehensively considered in the model, and multi-AGV and machine integrated scheduling are carried out. In order to solve this model, a new AGV scheduling rule and an improved NSGA-Ⅱ algorithm are designed. In the algorithm, a process-based extended chromosome encoding method and a greedy decoding strategy based on AGV allocation are proposed. At the same time, a variety of group binary tournament selection and segmented cross mutation strategies controlled by different parameters and a Pareto-based deduplication elite retention strategy are designed to promote individual collaborative optimization search. Through example experiments, the model validity of different AGV quantities task allocation schemes is analyzed. The simulation test and similar algorithm of four cases have also verified the effectiveness of the improved NSGA-II algorithm to solve the model.

Key words: flexible job shop scheduling, multiple time factors, automatic guided vehicle, multi-objective optimization, NSGA-Ⅱ algorithm

马千慧, 梁晓磊, 刘星雨, 张孟镝, 黄凯. 多AGV和机器集成的多目标柔性作业车间调度研究[J]. 计算机工程与应用, 2023, 59(1): 278-290.

MA Qianhui, LIANG Xiaolei, LIU Xingyu, ZHANG Mengdi, HUANG Kai. Research on Multi-Objective Flexible Job Shop Scheduling with Multiple AGVs and Machines Integration[J]. Computer Engineering and Applications, 2023, 59(1): 278-290.

参考文献

[1] 李雅琼，李强，阳小兰.考虑非确定加工时间的柔性作业车间调度问题研究[J].计算机应用研究，2018，35（10）：3016-3019.
LI Y Q，LI Q，YANG X L.Research on flexible Job-Shop scheduling problem considering uncertain processing time[J].Application Research of Computers，2018，35（10）：3016-3019.
[2] 杨帆，方成刚，吴伟伟.基于遗传-粒子群混合算法的柔性作业车间多资源调度问题[J].制造技术与机床，2020（2）：138-142.
YANG F，FANG C G，WU W W.Multi-resource flexible job shop scheduling problem based on hybrid genetic-particle swarm optimization algorithm[J].Management and Informalization，2020（2）：138-142.
[3] 王玉芳，马铭阳，葛嘉荣，等.基于改进人工蜂群算法的柔性作业车间调度[J].组合机床与自动化加工技术，2021（3）：159-163.
WANG Y F，MA M Y，GE J R，et al.Flexible job shop scheduling based on improved artificial bee colony algorithm[J].Modular Machine Tool ＆ Automatic Manufacturing Technique，2021（3）：159-163.
[4] AZZOUZ A，ENNIGROU M，BEN SAID L.A hybrid algorithm for flexible job-shop scheduling problem with setup times[J].International Journal of Production Management and Engineering，2017，5（1）：23-30.
[5] 谢锐强，张惠珍.求解柔性作业车间调度问题的两段式狼群算法[J].计算机工程与应用，2021，57（7）：251-256.
XIE R Q，ZHANG H Z.Two-vector wolf pack algorithm for flexible job shop scheduling problem[J].Computer Engineering and Applications，2021，57（7）：251-256.
[6] 石小秋，李炎炎，邓丁山.基于自适应变级别遗传杂草算法的FJSP研究[J].机械工程学报，2019，55（6）：223-232.
SHI X Q，LI Y Y，DENG D S.Research on FJSP based on adaptive variable grade genetic weed algorithm[J].Journal of Mechanical Engineering，2019，55（6）：223-232.
[7] 杨立熙，余慧慧.考虑运输时间的柔性作业车间调度问题研究[J].武汉理工大学学报（信息与管理工程版），2017，39（1）：608-613.
YANG L X，YU H H.Research on flexible job-shop scheduling problem with transport time consideration[J].Journal of WUT（Information & Management Engineering），2017，39（1）：608-613.
[8] 张国辉，党世杰.考虑工件移动时间的柔性作业车间调度问题研究[J].计算机应用研究，2017，34（8）：2329-2331.
ZHANG G H，DANG S J.Research on flexible Job-Shop scheduling problem considering job movement time[J].Application Research of Computers，2017，34（8）：2329-2331.
[9] 贺长征，宋豫川，雷琦，等.柔性作业车间多自动导引小车和机器的集成调度[J].中国机械工程，2019，30（4）：438-447.
HE C Z，SONG Y C，LEI Q，et al.Integrateg scheduling of multiple AGVs and machine in flexible job shops[J].China Mechanical Engineering，2019，30（4）：438-447.
[10] ZHENG Y，XIAO Y J，SEO Y.A Tabu search algorithm for simulta-neous machine/AGV scheduling problem[J].International Journal of Production Research，2014，52（19）：5748-5763.
[11] LU C，GAO L，LI X.Energy-efficient 14 ermutetion flow shop scheduling problem using a hybrid multiobjective backtracking search algorithm[J].Journal of Cleaner Production，2017，144：228-238.
[12] LIU Z，GUO S，WANG L.Integrated green scheduling optimization of flexible job shop and crane transportation considering comprehensive energy consumption[J].Journal of Cleaner Production，2019，211：765-786.
[13] 刘二辉，姚锡凡，陶韬，等.基于改进花授粉算法的共融AGV作业车间调度[J].计算机集成制造系统，2019，25（9）：2219-2236.
LIU E H，YAO X F，TAO T，et al.Improved flower pollinaton algorithm for job shop scheduling problems integrated with AGVs[J].Computer Integrated Manufacturing Systems，2019，25（9）：2219-2236.
[14] 鞠录岩，杨建军，张建兵，等.改进NSGA算法求解多目标柔性车间作业调度问题[J].计算机工程与应用，2019，55（13）：260-265.
JU L Y，YANG J J，ZHANG J B，et al.Improved NSGA for multi-objective flexible job-shop scheduling problem[J].Computer Engineering and Applications，2019，55（13）：260-265.
[15] 景志强，王兆辉，高琦.混合NSGA-Ⅱ算法求解多目标柔性作业车间调度问题[J].组合机床与自动化加工技术，2019（7）：138-140.
JING Z Q，WANG Z H，GAO Q.Hybrid NSGA-II algorithm for solving multi-objective flexible job-shop scheduling problem[J].Modular Machine Tool & Automatic Manufacturing Technique，2019（7）：138-140.
[16] 董海，徐晓鹏，谢谢.多目标优化算法求解多柔性作业车间调度问题[J].计算机科学，2020，47（12）：239-244.
DONG H，XU X P，XIE X.Solving multi-flexible job-shop scheduling by multi-objective algorithm[J].Computer Science，2020，47（12）：239-244.
[17] SINGH M R，SINGH M，MAHAPATRA S S，et al.Particle swarm optimization algorithm embedded with maximum deviation theory for solving multi-objective flexible job shop scheduling problem[J].The International Journal of Advanced Manufacturing Technology，2016，85（9/12）：2353-2366.
[18] ZHANG R，SONG S，WU C.A hybrid differential evolution algorithm for job shop scheduling problems with expected total tardiness criterion[J].Applied Soft Computing，2013，13（3）：1448-1458.
[19] 朱伟，赵水晶.考虑工件移动和成本的多目标柔性作业车间调度问题优化研究[J].现代制造工程，2019（7）：104-110.
ZHU W，ZHAO S J.Research on multi-objective flexible job-shop scheduling problem considering workpiece movement and operation cost[J].Modern Manufacturing Engineering，2019（7）：104-110.
[20] 张超勇，董星，王晓娟，等.基于改进非支配排序遗传算法的多目标柔性作业车间调度[J].机械工程学报，2010，46（11）：156-164.
ZHANG C Y，DONG X，WANG X J，et al.Improved NSGA-Ⅱ for the multi-objective flexible job-shop scheduling problem[J].Journal of Mechanical Engineering，2010，46（11）：156-164.
[21] 田旻，张光军，刘人境.粒子群遗传混合算法求解考虑传输时间的FJSP[J].运筹与管理，2019，28（4）：78-88.
TIAN M，ZHANG G J，LIU R J.Solve FJSP considering transport time via particle swarm genetic hybrid algorithm[J].Operations Research and Management Science，2019，28（4）：78-88.