Heuristic optimal method of flexible manufacturing based on Petri nets and artificial potential field

被引：0
|
作者：
Yi S.-J. [1 ,2 ]
Luo J.-L. [1 ,2 ]
Li X.-H. [1 ,2 ]
Li J. [1 ,2 ]
Zhang H.-B. [1 ,2 ]
机构：
[1] College of Information Science and Engineering, Huaqiao University, Xiamen
[2] Fujian Engineering Research Center of Motor Control and System Optimal Schedule, Xiamen
来源：
Kongzhi yu Juece/Control and Decision | 2024年 / 39卷 / 06期
关键词：
A* algorithm; artificial potential field; flexible manufacturing system; optimal scheduling; Petri net;
D O I：
10.13195/j.kzyjc.2022.0667
中图分类号：
学科分类号：
摘要：
The optimal scheduling of manufacturing systems is a NP-hard combinatorial optimization problem, and the tight coupling between the automated guided vehicle (AGV) path planing and task allocation intensifies its complexity. To address this issue, a heuristic optimization method based on Petri nets and artificial potential fields is proposed. First, the processes of a manufacturing system and the AGV system are described as a task Petri net and a path one respectively, which are then combined. Second, the potential energy parameters of the net nodes are designed using the topology of Petri nets, thereby assigning an artificial potential field to the Petri net. Third, two heuristic functions are designed using artificial potential fields, including a maximum-potential-difference heuristic function and a total-potential-difference one, and the corresponding A* algorithm is constructed. Experimental results show that the maximum-potential-difference heuristic function is admissible. Finally, two sets of numerical experiments are performed to show that the maximum-potential-difference A* algorithm can obtain the optimal solution, and the average computing efficiency is 57 % higher than that of the Dijkstra algorithm, but it cannot meet the requirements of large task quantity scheduling, while the total-potential-difference heuristic A* algorithm is at least one order of magnitude more efficient on average than the former algorithm that can solve the joint problem of AGV task allocation and path planning in a limited time. © 2024 Northeast University. All rights reserved.
引用
收藏
页码：1977 / 1985
页数：8
相关论文
共 19 条
  • [1] Luo J L, Zhang Q., Collision prevention and deadlock formal control method for automated guided vehicle system, Control and Decision, 32, 9, pp. 1628-1634, (2017)
  • [2] Zhou J Z, Luo J L, Zhan Y K., Optimal scheduling and control of batch chemical processes with Petri nets, Control Theory & Applications, 33, 6, pp. 809-815, (2016)
  • [3] Li D C, Luo J L, Sun S S, Et al., The integrated method of scheduling and control for manufacturing systems based on parallel Petri nets, Acta Automatica Sinica, 49, 4, pp. 845-856, (2023)
  • [4] Luo J C, Xing K Y, Zhou M C, Et al., Deadlock-free scheduling of automated manufacturing systems using Petri nets and hybrid heuristic search, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 45, 3, pp. 530-541, (2015)
  • [5] Lee T E, Kim H J, Roh D H, Et al., Characterizing token delays of timed event graphs for k-cyclic schedules, IEEE Transactions on Automatic Control, 62, 2, pp. 961-966, (2017)
  • [6] Declerck P., Extremum cycle times in time interval models, IEEE Transactions on Automatic Control, 63, 6, pp. 1821-1827, (2018)
  • [7] Karoui O, Chen Y F, Li Z W, Et al., On hierarchical construction of the state space of an automated manufacturing system modeled with Petri nets, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 50, 10, pp. 3613-3627, (2020)
  • [8] Zhu Q H, Zhou M C, Qiao Y, Et al., Petri net modeling and scheduling of a close-down process for time-constrained single-arm cluster tools, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 48, 3, pp. 389-400, (2018)
  • [9] Xiong W Q, Pan C R, Qiao Y, Et al., Reducing wafer delay time by robot idle time regulation for single-arm cluster tools, IEEE Transactions on Automation Science and Engineering, 18, 4, pp. 1653-1667, (2021)
  • [10] Baruwa O T, Piera M A., Identifying FMS repetitive patterns for efficient search-based scheduling algorithm: A colored Petri net approach, Journal of Manufacturing Systems, 35, pp. 120-135, (2015)
12