In order to solve the problems of task scheduling and buffer deadlock for a multi-load AGV system,a deadlock-free task scheduling scheme with task traveling time was proposed.Firstly,the task scheduling model was established with the objective of minimizing the delay rate and the imbalance degree of traffic loads.Secondly,the practical constraints in task scheduling were analyzed,and a prediction model was developed under the constraint of task traveling time.Thirdly,a multi-objective deadlock-free task scheduling method was proposed based on the AI-GWO algorithm for the task scheduling model.Deadlock prevention rules were used to prohibit tasks that would cause the buffer deadlock of workstations, and the AI-GWO algorithm was combined to perform the multi-objective optimization for the operation sequence of tasks.Finally,the tasks were assigned to different AGVs according to the balance degree of AGV loads.The simulation results show that the task-traveling time prediction model achieves high accuracy,and the task scheduling model and the deadlock-free scheduling method have the satisfactory optimization performance and computation efficiency.Therefore,the task punctuality rate of the material handling systems and the traffic-load balance degree of the path network are improved significantly.
WU Xing, ZHAI Jingjing, LOU Peihuang, HU Ya, XIAO Haining
. Deadlock-free Task Scheduling with Task Traveling Time for a Multi-load AGV System[J]. China Mechanical Engineering, 2021
, 32(23)
: 2840
-2849
.
DOI: 10.3969/j.issn.1004-132X.2021.23.008
[1]GIUSEPPE F, REN K, FABIO S, et al. Planning and Control of Autonomous Mobile Robots for Intralogistics:Literature Review and Research Agenda[J]. European Journal of Operational Research, 2021, 294(2):405-426.
[2]MOUSAVI M, YAP H J, MUAS S N. et al. A Fuzzy Hybrid GA-PSO Algorithm for Multi-objective AGV Scheduling in FMS[J]. International Journal of Simulation Modeling, 2017, 16(1):58-71.
[3]KABIR Q S, SUZUKI Y. Increasing Manufacturing Flexibility through Battery Management of Automated Guided Vehicles[J]. Computers & Industrial Engineering, 2018, 117:225-236.
[4]李西兴, 杨道明, 李鑫, 等. 基于混合遗传鲸鱼优化算法的柔性作业车间自动导引车融合调度方法[J]. 中国机械工程, 2021, 32(8):938-950.
LI Xixing, YANG Daoming, LI Xin, et al. Flexible Job Shop AGV Fusion Scheduling Method Based on HGWOA[J]. China Mechanical Engineering, 2021, 32(8):938-950.
[5]邹裕吉, 宋豫川, 王馨坤, 等. 多目标自适应聚类遗传算法求解无路径冲突的AGV与加工设备集成调度问题[J/OL]. 中国机械工程. [2021-08-12]. http:∥kns. cnki. net/kcms/detail/42. 1294. TH. 20210428. 1022. 002. html.
ZOU Yuji, SONG Yuchuan, WANG Xinkun, et al. Multi-objective Adaptive Clustering Genetic Algorithm to Solve the AGVs and Machine Integrated Scheduling Problem without Path Conflict[J/OL]. China Mechanical Engineering. [2021-08-12]. http:∥kns. cnki. net/kcms/detail/42. 1294. TH. 20210428. 1022. 002. html.
[6]ZAJC J, MAOPOLSKI W. Structural On-line Control Policy for Collision and Deadlock Resolution in Multi-AGV Systems[J]. Journal of Manufacturing Systems, 2021, 60:80-92.
[7]付建林, 张恒志, 张剑, 等. 自动导引车调度优化研究综述[J]. 系统仿真学报, 2020, 32(9):1664-1675.
FU Jianlin, ZHANG Hengzhi, ZHANG Jian, et al. Review on AGV Scheduling Optimization[J]. Journal of System Simulation, 2020, 32(9):1664-1675.
[8]LI Q, POGROMSKY A, ADRIAANSEN T, et al. A Control of Collision and Deadlock Avoidance for Automated Guided Vehicles with a Fault-tolerance Capability[J]. International Journal of Advanced Robotic Systems, 2016, 13:64-74.
[9]VIVALDINI K C T, ROCHA L F, BECKER M, et al. Comprehensive Review of the Dispatching, Scheduling and Routing of AGVs[C]∥Proceedings of the 11th Portuguese Conference on Automatic Control. Porto, 2015:505-514.
[10]HO Y C, LIU H C. A Simulation Study on the Performance of Pickup-dispatching Rules for Multiple-load AGVs[J]. Computers & Industrial Engineering, 2006, 51(3):445-463.
[11]HO Y C, CHIEN S H. A Simulation Study on the Performance of Task-determination Rules and Delivery-dispatching Rules for Multiple-load AGVs[J]. International Journal of Production Research, 2006, 44(20):4193-4222.
[12]HO Y C, CHIEN S H. A Simulation Study on the Performance of Delivery Dispatching Rules for Multiple-load AGVs[C]∥Proceedings of the Fifth Asia Pacific Industrial Engineering and Management Systems Conference. Brisbane, 2004:1-15.
[13]HO Y C, LIU H C, YIH Y. A Multiple-attribute Method for Concurrently Solving the Pickup-dispatching Problem and the Load-selection Problem of Multiple-load AGVs[J]. Journal of Manufacturing Systems, 2012, 31(3):288-300.
[14]HO Y C, LIU H C. The Performance of Load-selection Rules and Pickup-dispatching Rules for Multiple-load AGVs[J]. Journal of Manufacturing Systems, 2009, 28(1):1-10.
[15]AZIMI P, HALEH H, ALIDOOST M. The Selection of the Best Control Rule for a Multiple-load AGV System Using Simulation and Fuzzy MADM in a Flexible Manufacturing System[J]. Modelling and Simulation in Engineering, 2010, 7:1-11.
[16]AZIMI P, ALIDOOST M. A Heuristic Approach for Optimizing a Multiple-load Automated Guided Vehicle System in an Integrated Flexible Manufacturing System[J]. Economic Computation and Economic Cybernetics Studies and Research, 2011, 2(2):157-176.
[17]AZIMI P, GHANBARI M R, YARMOHAMMADI S. Optimization a Multi-objective and Multiple-load AGV System Using Optimization via Simulation Approach[J]. International Bulletin of Business Administration, 2012, 13:97-108.
[18]LEE J, SRISAWAT T. Effect of Manufacturing System Constructs on Pick-up and Drop-off Strategies of Multiple-load AGVs[J]. International Journal of Production Research, 2006, 44(4):653-673.
[19]RAMANAIAH D V, ASHOK B. Performance of Multiple-load AGV System under Different Guide Path Configurations[J]. International Journal of Technology and Engineering Sciences, 2013, 1(1):22-31.
[20]GUAN X P, DAI X Z. Deadlock-free Multi-attri-bute Dispatching Method for AGV Systems[J]. International Journal of Advanced Manufacturing Technology, 2009, 45(5/6):603-615.
[21]ZHOU Q, ZHOU B H. An Impending Deadlock-free Scheduling Method in the Case of Unified Automated Material Handling Systems in 300 mm Wafer Fabrications[J]. Journal of Intelligent Manufacturing, 2018, 29(1):1-10.
[22]LIU F H, HUNG P C. Control Strategy for Dispatching Multi-load Automated Guided Vehicles in a Deadlock-free Environment[J]. Journal of Mathematical Modelling and Algorithms, 2002, 1(2):117-134.
[23]XIAO H N, WU X, ZOU T, et al. A Deadlock-avoidance Dispatching Method for Multiple-load AGVs Based Transportation System[J]. Transactions of Nanjing University of Aeronautics and Astronautics, 2021, 38(1):181-192.
[24]KALINOVCIC L, PETROVIC T, BOGDAN S, et al. Modified Banker’s Algorithm for Scheduling in Multi-AGV Systems[C]∥ IEEE Conference on Automation Science and Engineering. Trieste, 2011:351-356.
[25]ZHAO Y, LIU X, WANG G, et al. Dynamic Resource Reservation Based Collision and Deadlock Prevention for Multi-AGVs[J]. IEEE Access, 2020, 8:82120-82130.
[26]XIAO H N, WU X, QIN D F, et al. A Collision and Deadlock Prevention Method with Traffic Sequence Optimization Strategy for UGN Based AGVS[J]. IEEE Access, 2020, 8:209452-209470.
[27]武星, 翟晶晶, 肖海宁, 等. 多载量AGV系统防死锁路口通行顺序优化及避碰[J/OL]. 计算机集成制造系统. [2021-08-12]. http:∥kns. cnki. net/kcms /detail/11. 5946. TP. 20201130. 1726. 002. html.
WU Xing, ZHAI Jingjing, XIAO Haining, et al. Deadlock-free Intersection-access Sequence Optimization and Collision Avoidance for a Multi-load AGV System[J/OL]. Computer Integrated Manufacturing Systems. [2021-08-12]. http:∥kns. cnki. net/kcms/detail/11. 5946. TP. 20201130. 1726. 002. html.
[28]武星, 楼佩煌, 胡亚, 等. 多载量自动导引车防死锁的任务调度方法:CN111353706A[P]. 2020-06-30.
WU Xing, LOU Peihuang, HU Ya, et al. Deadlock-free Task Scheduling Method for Multi-load AGVs:CN111353706A[P]. 2020-06-30.
[29]周涓. 基于最大最小距离法的多中心聚类算法研究[D]. 重庆:重庆大学, 2016.
ZHOU Juan. Study on Muliseed Clustering Algorithm Based on Max-min Distance Algorithm[D]. Chongqing:Chongqing University, 2016.
[30]卢超. 加工时间可控的多目标车间调度问题研究[D]. 武汉:华中科技大学, 2017.
LU Chao. Study on Theory and Method of Multi-objective Scheduling Problems with Controllable Processing Times[D]. Wuhan:Huazhong University of Science and Technology, 2017.