带有充电约束的多AGV柔性作业车间调度

doi:10.19678/j.issn.1000-3428.0068991

摘要/Abstract

摘要：

在制造单元不再唯一且加工时间不确定的柔性作业车间调度中, 多自动导向小车(AGV)发挥着重要作用。然而当AGV执行任务时间过长、消耗电量较多时, 充电事件成为必须考虑的因素。该研究旨在解决考虑电池约束条件下的多AGV的柔性车间作业调度问题。综合考虑制造单元加工时间、AGV小车搬运时间以及AGV小车充电情况等约束条件, 以优化最大完工时间为目标。针对此问题建立数学模型, 将文化基因算法和自适应变邻域搜索算法相结合提出一种混合文化基因算法。该算法采用文化基因算法作为框架, 并引入基于析取图的关键路径方法, 以解决制造单元和AGV小车滞空率高的问题。同时, 为了提高算法的寻优能力, 避免陷入局部最优解, 利用自适应变邻域搜索对当前迭代中的最优解进行改进。针对模型特点, 设计多种打破重组的邻域结构, 以实现算法求解最优值的目标。仿真实验结果表明, 该算法具有寻找最优解的能力且整体性能优于所对比的算法, 验证了该算法的有效性。

关键词: 柔性作业车间调度, 自动导向小车, 充电, 基因算法, 自适应变邻域搜索算法

Abstract:

In flexible job shop scheduling, where manufacturing cells are no longer the only option and processing time is uncertain, multiple Automated Guided Vehicles (AGVs) play an important role. However, charging becomes a crucial factor when an AGV consumes excessive power or takes too long to complete its tasks. This study aims to solve the Flexible Job Shop Scheduling Problem (FJSP) involving multiple AGVs while considering battery constraints. This study comprehensively considers constraints such as manufacturing unit processing time, AGV transportation time, and AGV charging status with the goal of optimizing the maximum completion time. A mathematical model is established for this problem, and a hybrid Memetic Algorithm (MA) combining MA with an adaptive variable neighborhood search algorithm is proposed. The algorithm utilizes a cultural genetic algorithm as a framework and introduces a critical path method based on a disjunctive graph to solve the problem of high idle rates of manufacturing units and AGVs. Additionally, to improve the algorithm's search capability and avoid becoming trapped in local optimal solutions, an adaptive variable neighborhood search is used to enhance the best solution of the current iteration. Multiple neighborhood structures that break recombination are designed to find the optimal value. The simulation results show that the algorithm can find the optimal solution and has a better overall performance than other algorithms, verifying its effectiveness.

Key words: flexible job shop scheduling, Automated Guided Vehicle(AGV), charging, Memetic Algorithm(MA), adaptive variable neighborhood search algorithm

李晓辉, 资湖海, 徐坷鑫, 牛樱清, 赵毅, 董媛. 带有充电约束的多AGV柔性作业车间调度[J]. 计算机工程, 2025, 51(4): 314-326.

LI Xiaohui, ZI Huhai, XU Kexin, NIU Yingqing, ZHAO Yi, DONG Yuan. Multi-AGV Flexible Job Shop Scheduling with Charging Constraints[J]. Computer Engineering, 2025, 51(4): 314-326.

https://www.ecice06.com/CN/Y2025/V51/I4/314

图/表 13

图1 MAFJSP-BC示意图

Fig.1 Schematic diagram of MAFJSP-BC

图2 搬运机器搬运过程

Fig.2 Handling process of the handling machine

图3 充电过程

Fig.3 Charging process

图4 工件加工时间点

Fig.4 Workpiece processing time point

图5 编码方式

Fig.5 Coding mode

图6 POX交叉算法示例

Fig.6 Example of the POX cross algorithm

图7 案例甘特图

Fig.7 Case Gantt chart

图8 关键路径示意图

Fig.8 Critical path Schematic drawing

图9 基于关键路径的变异操作甘特图

Fig.9 Mutated operation Gantt chart based on critical path

图10 混合文化基因算法流程

Fig.10 Procedure of hybrid memetic algorithm

图11 多AGV制造单元调度方案甘特图

Fig.11 Multi-AGV manufacturing unit scheduling scheme Gantt chart

参考文献 26

1	赵宁, 李开典, 田青, 等. 考虑运输时间柔性作业车间调度问题的快速寻优方法. 计算机集成制造系统, 2015, 21 (3): 724- 732.
	ZHAO N , LI K D , TIAN Q , et al. Fast optimization approach of flexible job shop scheduling with transport time consideration. Computer Integrated Manufacturing Systems, 2015, 21 (3): 724- 732.
2	张国辉, 党世杰. 考虑工件移动时间的柔性作业车间调度问题研究. 计算机应用研究, 2017, 34 (8): 2329- 2331. doi: 10.3969/j.issn.1001-3695.2017.08.021
	ZHANG G H , DANG S J . Research on flexible Job-Shop scheduling problem considering job movement time. Application Research of Computers, 2017, 34 (8): 2329- 2331. doi: 10.3969/j.issn.1001-3695.2017.08.021
3	李峥峰, 赵长春, 张国辉, 等. 考虑多种时间因素的作业车间调度优化. 重庆大学学报, 2020, 43 (1): 12- 18.
	LI Z F , ZHAO C C , ZHANG G H , et al. Optimism of job shop scheduling with multi-times. Journal of Chongqing University, 2020, 43 (1): 12- 18.
4	李西兴, 杨道明, 李鑫, 等. 基于混合遗传鲸鱼优化算法的柔性作业车间自动导引车融合调度方法. 中国机械工程, 2021, 32 (8): 938-950, 986. doi: 10.3969/j.issn.1004-132X.2021.08.008
	LI X X , YANG D M , LI X , et al. Flexible job shop AGV fusion scheduling method based on HGWOA. China Mechanical Engineering, 2021, 32 (8): 938-950, 986. doi: 10.3969/j.issn.1004-132X.2021.08.008
5	ALI UMAR U , ARIFFIN M K A , ISMAIL N , et al. Hybrid multiobjective genetic algorithms for integrated dynamic scheduling and routing of jobs and automated-guided vehicle in flexible manufacturing systems environment. The International Journal of Advanced Manufacturing Technology, 2015, 81 (9): 2123- 2141.
6	LIU Y , FAN Y S , LIU B J . A workshop scheduling and optimization method based on multi-process workflow simulation. IFAC Proceedings Volumes, 2013, 46 (9): 1738- 1743. doi: 10.3182/20130619-3-RU-3018.00039
7	LI L P, WU W J, HU Y. Research on flexible job scheduling based on genetic prohibited search algorithm[C]//Proceedings of the 11th International Conference of Information and Communication Technology. Washington D. C., USA: IEE Press, 2022: 457-468.
8	ZHANG F F, MEI Y, NGUYEN S, et al. A preliminary approach to evolutionary multitasking for dynamic flexible job shop scheduling via genetic programming[C]//Proceedings of 2020 Genetic and Evolutionary Computation Conference Companion. New York, USA: ACM Press, 2020: 107-108.
9	YE J R, WANG A M, GE Y, et al. An improved grey wolf optimizer for flexible job-shop scheduling problem[C]//Proceedings of the 11th IEEE International Conference on Mechanical and Intelligent Manufacturing Technologies. Washington D. C., USA: IEE Press, 2020: 1140-1149.
10	邓希, 胡晓兵, 江代渝, 等. 基于混合遗传算法的柔性作业车间机器和AGV规划. 四川大学学报(自然科学版), 2021, 58 (2): 73- 82.
	DENG X , HU X B , JIANG D Y , et al. A hybrid GA approach to the scheduling of machines and automated guided vehicles in flexible job shops. Journal of Sichuan University (Natural Science Edition), 2021, 58 (2): 73- 82.
11	LACOMME P , LARABI M , TCHERNEV N . Job-shop based framework for simultaneous scheduling of machines and automated guided vehicles. International Journal of Production Economics, 2013, 143 (1): 24- 34. doi: 10.1016/j.ijpe.2010.07.012
12	ZOU W Q , PAN Q K , MENG T , et al. An effective discrete artificial bee colony algorithm for multi-AGVs dispatching problem in a matrix manufacturing workshop. Expert Systems with Applications, 2020, 161, 113675. doi: 10.1016/j.eswa.2020.113675
13	DE RYCK M , VERSTEYHE M , DEBROUWERE F . Automated guided vehicle systems, state-of-the-art control algorithms and techniques. Journal of Manufacturing Systems, 2020, 54, 152- 173. doi: 10.1016/j.jmsy.2019.12.002
14	SINGH N , DANG Q V , AKCAY A , et al. A matheuristic for AGV scheduling with battery constraints. European Journal of Operational Research, 2022, 298 (3): 855- 873. doi: 10.1016/j.ejor.2021.08.008
15	DANG Q V , SINGH N , ADAN I , et al. Scheduling heterogeneous multi-load AGVs with battery constraints. Computers & Operations Research, 2021, 136, 105517.
16	MO J F , CHANG D F , WANG S , et al. Analysis of influence of AGV quantity configuration based on plant simulation on dockside operation efficiency. International Journal of Intelligent Information, 2020, 9 (5): 268- 278.
17	李峥峰, 刘阳阳. 考虑充电的多AGV的作业车间调度问题. 计算机集成制造系统, 2021, 27 (10): 2872- 2879.
	LI Z F , LIU Y Y . Job shop scheduling considering multiple AGVs with charging. Computer Integrated Manufacturing Systems, 2021, 27 (10): 2872- 2879.
18	GAREY M R , JOHNSON D S , SETHI R . The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1976, 1 (2): 117- 129. doi: 10.1287/moor.1.2.117
19	张超勇, 饶运清, 刘向军, 等. 基于POX交叉的遗传算法求解Job-Shop调度问题. 中国机械工程, 2004, 15 (23): 2149- 2153. doi: 10.3321/j.issn:1004-132X.2004.23.020
	ZHANG C Y , RAO Y Q , LIU X J , et al. An improved genetic algorithm for the Job-Shop scheduling problem. China Mechanical Engineering, 2004, 15 (23): 2149- 2153. doi: 10.3321/j.issn:1004-132X.2004.23.020
20	ZHANG C Y , LI P G , GUAN Z L , et al. A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem. Computers & Operations Research, 2007, 34 (11): 3229- 3242.
21	REDDY B S P , RAO C S P . A hybrid multi-objective GA for simultaneous scheduling of machines and AGVs in FMS. The International Journal of Advanced Manufacturing Technology, 2006, 31 (5): 602- 613.
22	ABDELMAGUID T F , NASSEF A O , KAMAL B A , et al. A hybrid GA/heuristic approach to the simultaneous scheduling of machines and automated guided vehicles. International Journal of Production Research, 2004, 42 (2): 267- 281. doi: 10.1080/0020754032000123579
23	GNANAVEL BABU A , JERALD J , NOORUL HAQ A , et al. Scheduling of machines and automated guided vehicles in FMS using differential evolution. International Journal of Production Research, 2010, 48 (16): 4683- 4699. doi: 10.1080/00207540903049407
24	NOURI H E , BELKAHLA DRISS O , GHÉDIRA K . Simultaneous scheduling of machines and transport robots in flexible job shop environment using hybrid metaheuristics based on clustered holonic multiagent model. Computers & Industrial Engineering, 2016, 102, 488- 501.
25	BILGE Ü , ULUSOY G . A time window approach to simultaneous scheduling of machines and material handling system in an FMS. Operations Research, 1995, 43 (6): 1058- 1070. doi: 10.1287/opre.43.6.1058
26	DEROUSSI L, NORRE S. Simultaneous scheduling of machines and vehicles for the flexible job shop problem[EB/OL]. [2023-11-01]. https://www.researchgate.net/publication/265801340.

[1]	郑锦灿, 邵立珍, 雷雪梅. 基于改进MOEA/D的模糊柔性作业车间调度算法[J]. 计算机工程, 2024, 50(6): 336-345.
[2]	赵文薇, 林兵, 卢宇, 王明芬. 面向汽车充电预约的光储充电站能量调度策略[J]. 计算机工程, 2023, 49(12): 262-273, 281.
[3]	谈玲. 一种智能电网中基于优先充电机制的节能汇聚路由方案[J]. 计算机工程, 2018, 44(8): 285-290.
[4]	王志方,郑霖,李晓记. 无线可充电传感器网络中充电器的部署优化[J]. 计算机工程, 2018, 44(5): 83-87,93.
[5]	田建伟,漆文辉,黎曦,刘潇潇,肖德贵. 充电设施监控系统中的数据并发控制研究[J]. 计算机工程, 2015, 41(6): 280-286,293.
[6]	董文洪, 易波, 栗飞. 无人布雷机航路规划仿真系统设计与实现[J]. 计算机工程, 2012, 38(06): 250-252.
[7]	卜海祥, 杨华秋, 段欣, 陈利光, 来金梅, 鲍丽春. 基因算法加速器与芯片级进化研究[J]. 计算机工程, 2011, 37(7): 258-261.
[8]	任海英, 商晓坤. 柔性作业车间调度的多Agent协商策略[J]. 计算机工程, 2011, 37(2): 269-271.
[9]	陈亮;王世进;周炳海. 柔性作业车间调度问题的集成启发式算法[J]. 计算机工程, 2008, 34(1): 256-258.
[10]	李文，唐志敏. 一种减少内存访问延时的方法[J]. 计算机工程, 2006, 32(3): 242-244.

选择文件类型/文献管理软件名称

选择包含的内容