Clustering Genetic Algorithm for Multi-objective Integrated Scheduling of AGVs and Machine

doi:10.3969/j.issn.1004-132X.2022.01.011

Abstract

Abstract: Aiming at the integrated scheduling problems of AGV and processing equipment and considering the conflict-free path planning of AGV, a scheduling optimization model was established based on the maximum completion time, AGV running time, and total machine load. And a scheduling optimization model was proposed based on time window and Dijkstra's multi-objective adaptive clustering genetic algorithm. According to the characteristics of the algorithm in different iteration periods, a cross-recombination strategy including adaptive individual cross-probability was proposed. Adaptive population mutation probability was designed. An environmental selection strategy was introduced based on the number of grid divisions and the distances of the expanded grid. The simulation results verified the feasibility and superiority of the algorithm.

Key words: automated guided vehicle(AGV) multiobjective optimization, clustering, robot motion path planning, production scheduling

摘要： 针对AGV与加工设备的集成调度问题，在考虑AGV无冲突路径规划的情况下，建立了以最大完工时间、AGV运行时间及机器总负荷为优化目标的调度优化模型，提出一种基于时间窗和Dijkstra算法的多目标自适应聚类遗传算法。根据算法在不同迭代时期的特点，提出一种包含自适应个体交叉概率的交叉重组策略；设计了自适应种群变异概率；引入基于网格划分数和扩容网格距离的环境选择策略。仿真结果验证了算法的可行性和优越性。

关键词: 自动导向小车多目标优化, 聚类, 机器人运动路径规划, 生产调度

CLC Number:

TP273
TH187

ZOU Yuji, SONG Yuchuan, WANG Xinkun, WANG Yi. Clustering Genetic Algorithm for Multi-objective Integrated Scheduling of AGVs and Machine[J]. China Mechanical Engineering, 2022, 33(01): 97-108.

邹裕吉, 宋豫川, 王馨坤, 王毅. 自动导向小车与加工设备多目标集成调度的聚类遗传算法[J]. 中国机械工程, 2022, 33(01): 97-108.

References

［1］付建林,张恒志,张剑,等.自动导引车调度优化研究综述［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.［2］ULUSOY G, BILGE . Simultaneous Scheduling of Machines and Automated Guided Vehicles［J］. International Journal of Production Research, 1993, 31(12):2857-2873.
［3］SAIDIMEHRABAD M, DEHNAVIARANI S, EVAZABADIAN F, et al. An Ant Colony Algorithm(ACA) for Solving the New Integrated Model of Job Shop Scheduling and Conflict-free Routing of AGVs［J］. Computers & Industrial Engineering, 2015:2-13.
［4］LYU X, SONG Y, HE C, et al. Approach to Integrated Scheduling Problems Considering Optimal Number of Automated Guided Vehicles and Conflict-Free Routing in Flexible Manufacturing Systems［J］. IEEE Access, 2019:74909-74924.
［5］REEDYB S P, RAO C S P. A Hybrid Multi-objective GA for Simultaneous Scheduling of Machines and AGVs in FMS［J］. The International Journal of Advanced Manufacturing Technology, 2006, 31:602-613.
［6］刘二辉,姚锡凡,陶韬,等.基于改进花授粉算法的共融AGV作业车间调度［J］.计算机集成制造系统, 2019, 25(9):2219-2236.
LIU Erhui, YAO Xifan, TAO Tao, et al. Improved Flower Pollinaton Algorithm for Job Shop Scheduling Problem Integrated with AGVS［J］. Computer Integrated Manufacturing Systems,2019,25(9):2219-2236.
［7］黄学文,陈绍芬,周阗玉,等. 求解柔性作业车间调度的遗传算法综述［J/OL］. 计算机集成制造系统:1-26［2020-09-24］. http:∥kns.cnki.net/kcms/detail/11.5946.TP.20200702.1105.002.html.
HUANG Xuewen, CHEN Shaofen, ZHOU Tianyu, et al. Survey on Genetic Algorithms for Solving Flexible Job-shop Scheduling Problem［J/OL］. Computer Integrated Manufacturing Systems:1-26［2020-09-24］. http:∥kns.cnki.net/kcms/detail/11.5946.TP.20200702.1105.002.html.
［8］AMJAD M K, BUTT S I, KOUSAR R, et al. Recent Research Trends in Genetic Algorithm Based Flexible Job Shop Scheduling Problems［J］. Mathematical Problems in Engineering, 2018, 2018:1-32.
［9］蒋增强,左乐.低碳策略下的多目标柔性作业车间调度［J］.计算机集成制造系统,2015,21(4):1023-1031.
JIANG Zengqiang, ZUO Le. Multi-objective Flexible Job-shop Scheduling Based in Low-carbon Strategy［J］. Computer Integrated Manufacturing System, 2015, 21(4):1023-1031.
［10］柳丹丹,龚祝平,邱磊.改进遗传算法求解同类并行机优化调度问题［J］.机械设计与制造,2020（4）:262-265.
LIU Dandan, GONG Zhuping, QIU Lei, et al. Improved Genetic Algorithm for the Optimal Scheduling Problem of Uniform Parallel Machine［J］. Machinery Design & Manufacture,2020（4）:262-265.
［11］LI Y, LIU G, LAO S. A Genetic Algorithm for Community Detection in Complex Networks［J］. Journal of Central South University, 2013, 20:1269-1276.
［12］DENYSIUK R, COSTA L, SANTO I E, et al. Clustering-based Selection for Evolutionary Many-objective Optimization［C］∥International Conference on Parallel Problem Solving from Nature. Ljubljana, 2014:538-547.
［13］杜轩,潘志成.聚类差分进化算法求解多目标工艺规划与调度集成问题［J］.计算机集成制造系统, 2019, 25(7):1729-1738.
DU Xuan, PAN Zhicheng. Clustering and Differential Evolution Algorithm for Solving Multi-objectives IPPS Problem［J］. Computer Integrated Manufacturing System, 2019, 25(7):1729-1738.
［14］崔志华,张茂清,常宇,等. 基于平均距离聚类的NSGA-Ⅱ［J/OL］.自动化学报:1-12［2020-08-14］.https:∥doi.org/10.16383/j.aas.c180540.
CUI Zhihua, ZHANG Maoqing, CHANG Yu, et al. NSGA-Ⅱ with Average Distance Clustering［J/OL］. Acta Automatica Sinica:1-12 ［2020-08-14］. https:∥doi.org/10.16383/j.aas.c180540
［15］MIRJALILI S, LEWIS A. The Whale Optimization Algorithm［J］. Advances in Engineering Software, 2016, 95(95):51-67.
［16］MCCALLUM A, NIGAM K, UNGAR L H, et al. Efficient Clustering of High-dimensional Data Sets with Application to Reference Matching［C］∥The 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Boston, 2000:169-178.
［17］SEYED M, BOZORGI, SAMANEH Y. IWOA:an Improved Whale Optimization Algorithm for Optimization Problems［J］. Journal of Computational Design and Engineering, 2019, 6(3):243-259.
［18］CHENG J, YEN G G, ZHANG G, et al. A Grid-based Adaptive Multi-objective Differential Evolution Algorithm［J］. Information Sciences, 2016, 367/368:890-908.
［19］HYUN Chul Ju, KIM Yeongho, KIM Yeo Keun. A Genetic Algorithm for Multiple Objective Sequencing Problems in Mixed Model Assembly Lines［J］. Computers & Operations Research, 1998, 25(7/8):675-690.
［20］ZHANG W, GEN M, JO J. Hybrid Sampling Strategy-based Multiobjective Evolutionary Algorithm for Process Planning and Scheduling Problem［J］. Journal of Intelligent Manufacturing, 2014,12:881-897.
［21］COELLO C A, PULIDO G T, LECHUGA M S, et al. Handling Multiple Objectives with Particle Swarm Optimization［J］. IEEE Transactions on Evolutionary Computation, 2004, 8(3):256-279.

[1]	LI Minbo, DONG Weiwei. Quality Prediction of Automotive Parts for Imbalanced Datasets [J]. China Mechanical Engineering, 2022, 33(01): 88-96.
[2]	SHI Hongxia, WANG Jianmin. Feature Line Extraction for Point Cloud Based on Normal Vector Region Clustering Segmentation [J]. China Mechanical Engineering, 2021, 32(21): 2552-2561.
[3]	LU Hao, CHEN Yang, WU Huaiyu, CHENG Lei, . Path Planning of Substation Inspection Robot under Road Network and Measurement Constraints [J]. China Mechanical Engineering, 2021, 32(16): 1972-1982.
[4]	ZHOU Xiaochun, LIANG Jun, CHEN Long, WANG Yafei, GONG Jinfeng. Intelligent Connected Vehicle PnP Networking Model and Decision Fusion Algorithm [J]. China Mechanical Engineering, 2021, 32(16): 1983-1993.
[5]	YI Qian, HE Shuang, NING Qing, LI Congbo, YI Shuping. An Multi-objective Optimized Production Scheduling for Automobile Prototype Workshops Considering Employee Work Ability#br# [J]. China Mechanical Engineering, 2021, 32(13): 1617-1629.
[6]	GU Yong, YUAN Yuanyi, ZHANG Lie, DUAN Jingjing. Multi-depot Half Open Vehicle Routing Problem with Time Windows [J]. China Mechanical Engineering, 2020, 31(14): 1733-1740.
[7]	LIU Zhengyu1,2;WEI Zihong1;XU Yajuan1;YANG Kun1. A Battery Dynamic Grouping Equalization Method Based on Adaptive Topology [J]. China Mechanical Engineering, 2020, 31(06): 714-721.
[8]	CHEN Yong;CHENG Ziwen;JIANG Congcong;WANG Yaliang;WANG Cheng;LI Shiyun. Robust Optimization Model and Algorithm for Polymorphic Shop Layouts Considering Layout Entropy [J]. China Mechanical Engineering, 2019, 30(15): 1837-1848.
[9]	ZHANG Chunliang;CHEN Ming. Prediction of Disassembly Costs of ELVs by Fuzzy Clustering Based on Disassembly Difficulties [J]. China Mechanical Engineering, 2019, 30(07): 840-845.
[10]	WANG Hai, ZHENG Zhengyang, CAI Yingfeng, CHEN Long. Obstacle Detection Algorithm for Driverless Vehicles Based on Four-layer Lidars [J]. China Mechanical Engineering, 2018, 29(15): 1884-1889.
[11]	LI Maolin1;LIANG Lin2;CHEN Yuanming2;XU Guanghua2;HE Kangkang2. Non-negative Matrix Factorization Based on Clustering and Its Application [J]. China Mechanical Engineering, 2018, 29(06): 720-725.
[12]	GAO Jianping1;ZHANG Leimin1;SUN Zhongbo2;XI Jianguo1. Control Strategy Optimization of Plug-in Hybrid Electric Vehicle Based on Driving Cycles [J]. China Mechanical Engineering, 2017, 28(15): 1770-1777.
[13]	WANG Youyuan1;ZHAO Lu2;ZHANG Le'en3. Knowledge Personalized Push Based on Context Constraint [J]. China Mechanical Engineering, 2017, 28(15): 1812-1819.
[14]	JIANG Wanlu, WANG Haonan, ZHU Yong, WANG Zhenwei, DONG Keyan, . Integrated VMD Denoising and KFCM Clustering Fault Identification Method of Rolling Bearings [J]. China Mechanical Engineering, 2017, 28(10): 1215-1220,1226.
[15]	Zhang Shuqing1;Li Wei1;Zhang Liguo1，2;Hu Yongtao1;Qian Lei1;Jiang Wanlu1. Bearing Fault Diagnosis Based on multi-EMD, cApEn and GG Clustering Algorithm [J]. China Mechanical Engineering, 2016, 27(24): 3362-3367.