Research Status of AGV and Machine Integrated Scheduling

doi:10.3778/j.issn.1002-8331.2207-0427

Abstract

Abstract: With the wide application of automated guided vehicles（AGV）, the cooperation between machines and AGVs in flexible manufacturing system（FMS） is paid more and more attention. The research of AGV and machine integrated scheduling mainly includes machine allocation, process sequencing, AGV allocation of transport tasks and AGV path planning. This problem is a very complex combinatorial optimization problem, which has important academic significance and application value for its research. Based on the characteristics of the problem, the latest research literatures at home and abroad are reviewed from two aspects of model and algorithm. The constraints and optimization objectives of the existing models are classified in detail, and the representative results of the existing algorithms are summarized from five aspects：genetic algorithm, hybrid optimization algorithm and simulation optimization algorithm and so on. On this basis, the shortcomings of existing research are pointed out, and the content and direction of future research are put forward.

Key words: flexible manufacturing shop, automated guided vehicles, integrated scheduling, intelligent optimization, hybrid algorithm

摘要： 随着自动导引车（automated guided vehicles，AGV）的广泛应用，柔性制造车间中机器设备与AGV之间的协同配合日益受到重视。AGV与机器的集成调度主要研究机器分配、工序排序、搬运任务的AGV分配以及AGV路径规划。该问题是极为复杂的组合优化问题，对其研究具有重要的学术意义和应用价值。围绕问题特征，从模型与算法两个方面，对国内外最新的研究文献进行了梳理。对现有模型中的约束条件和优化目标进行了详细分类，从遗传算法、混合优化算法、仿真优化算法等五个方面综述了现有算法研究中的代表性成果。在此基础上，指出了现有研究中的不足，提出了未来的研究内容和方向。

关键词: 柔性制造车间, 自动导引车, 集成调度, 智能优化, 混合算法

WU Bin, DING Yuchao, ABLA Basri. Research Status of AGV and Machine Integrated Scheduling[J]. Computer Engineering and Applications, 2023, 59(6): 1-12.

吴斌, 丁钰超, ABLA Basri. 自动导引车与机器集成调度问题研究现状[J]. 计算机工程与应用, 2023, 59(6): 1-12.

References

[1] ZHANG X J，SANG H Y，LI J Q，et al.An effective multi-AGVs dispatching method applied to matrix manufacturing workshop[J].Computers & Industrial Engineering，2022，163：107791.
[2] DERYCK M，VERSTRYHE M，DEBROUWERE F.Automated guided vehicle systems，state-of-the-art control algorithms and techniques[J].Journal of Manufacturing Systems，2020，54：152-173.
[3] 梁军，韩冬冬，盘朝奉，等.基于移动机器人的智能车库关键技术综述[J].机械工程学报，2022，58（3）：1-20.
LIANG J，HAN D D，PAN C F，et al.Review on critical technologies of robot-based intelligent garages[J].Journal of Mechanical Engineering，2022，58（3）：1-20.
[4] 付建林，张恒志，张剑，等.自动导引车调度优化研究综述[J].系统仿真学报，2020，32（9）：1664-1675.
FU J L，ZHANG H Z，ZHANG J，et al.Review on AGV scheduling optimization[J].Journal of System Simulation，2020，32（9）：1664-1675.
[5] 曹立佳，刘洋.制造车间自动导引车调度新进展[J].计算机工程与应用，2021，57（21）：59-67.
CAO L J，LIU Y.Recent advances in scheduling optimization of automated guided vehicles in manufacturing workshops[J].Computer Engineering and Applications，2021，57（21）：59-67.
[6] ULUSOY G，BILGE ü.Simultaneous scheduling of machines and automated guided vehicles[J].International Journal of Production Research，1993，31（12）：2857-2873.
[7] LEE D Y，DICESARE F.Integrated models for scheduling flexible manufacturing systems[C]//Proceedings IEEE International Conference on Robotics and Automation.Atlanta：IEEE，1993：827-832.
[8] LEE D Y，DICESARE F.Integrated scheduling of flexible manufacturing systems employing automated guided vehicles[J].IEEE Transactions on Industrial Electronics，1994，41（6）：602-610.
[9] SANKAR S S，PONNAMBALAM S G.An intelligent integrated scheduling model for flexible manufacturing system[C]//IEEE Conference on Robotics，Automation and Mechatronics.Singapore：IEEE，2004：1095-1100.
[10] SANKAR S S，RAJKUMAR R，PONNAMBALAM S G，et al.Integrated scheduling of material handling and manufacturing activities in flexible manufacturing system[C]//2004 IEEE International Conference on Systems，Man and Cybernetics.The Hague：IEEE，2004：4254-4259.
[11] TAN W Y，PONNAMBALAM S G，YOGESWARAN M.Multi-objective ACO for integrated scheduling of machines and material handling equipment in flexible manufacturing systems[C]//2009 IEEE International Conference on Automation Science and Engineering.Bangalore：IEEE，2009：304-309.
[12] 李岩，吴智铭，甘泉.柔性加工环境中机器和AGV的集成调度[J].中国机械工程，2001（4）：88-91.
LI Y，WU Z M，GAN Q.Integrated scheduling of machines and AGVs in flexible manufacturing environment[J].China Mechanical Engineering，2001（4）：88-91.
[13] 柳赛男，柯映林.一种解决有AGV小车约束的车间智能调度问题的算法[J].中国机械工程，2007（15）：1810-1813.
LIU S N，KE Y L.An algorithm for job shop scheduling in dual resource constrained with AGV[J].China Mechanical Engineering，2007（15）：1810-1813.
[14] 胡晓阳，姚锡凡，黄鹏，等.改进迭代局部搜索算法求解多AGV柔性作业车间调度问题[J].计算机集成制造系统，2022，28（7）：2198-2212.
HU X Y，YAO X F，HUANG P，et al.Improved iterative local search algorithm for solving multi-AGV flexible job shop scheduling problem[J].Computer Integrated Manufacturing Systems，2022，28（7）：2198-2212.
[15] 贺长征，宋豫川，雷琦，等.柔性作业车间多自动导引小车和机器的集成调度[J].中国机械工程，2019，30（4）：438-447.
HE C Z，SONG Y C，LEI Q，et al.Integrated scheduling of multiple AGVs and machines in flexible job shops[J].China Mechanical Engineering，2019，30（4）：438-447.
[16] 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，7：74909-74924.
[17] 邹裕吉，宋豫川，王馨坤，等.多目标自适应聚类遗传算法求解无路径冲突的AGV与加工设备集成调度问题[J/OL].中国机械工程：1-14[2022-01-11].http：//kns.cnki.net/kcms/detail/42.1294.TH.20210428.1022.002.html.
ZOU Y J，SONG Y C，WANG X K，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：1-14[2022-01-11].http：//kns.cnki.net/kcms/detail/42.1294.TH.20210428.
1022.002.html.
[18] 邓希，胡晓兵，江代渝，等.基于混合遗传算法的柔性作业车间机器和AGV规划[J].四川大学学报（自然科学版），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 automatic guided vehicles in flexible job shops[J].Journal of Sichuan University（Natural Science Edition），2021，58（2）：73-82.
[19] 李西兴，杨道明，李鑫，等.基于混合遗传鲸鱼优化算法的柔性作业车间自动导引车融合调度方法[J].中国机械工程，2021，32（8）：938-950.
LI X X，YANG D M，LI X，et al.Flexible job shop AGV fusion scheduling method based on HGWOA[J].China Mechanical Engineering，2021，32（8）：938-950.
[20] 李峥峰，刘阳阳.考虑充电的多AGV的作业车间调度问题[J].计算机集成制造系统，2021，27（10）：2872-2879.
LI Z F，LIU Y Y.Research on job shop scheduling with multiple AGVs considering charging[J].Computer Integrated Manufacturing Systems，2021，27（10）：2872-2879.
[21] 刘畅，张承瑞，孙玉玺.改进自适应遗传算法在多载AGV调度的应用研究[J].小型微型计算机系统，2021，42（11）：2241-2245.
LIU C，ZHANG C R，SUN Y X.Research on application of improved adaptive genetic algorithm in multi-load AGV scheduling[J].Journal of Chinese Computer Systems，2021，42（11）：2241-2245.
[22] 葛艳红，李书珍，李文锋.个性化定制车间生产与物流协同调度研究[J].南京理工大学学报，2021，45（6）：692-699.
GE Y H，LI S Z，LI W F.Collaborative scheduling of production and logistics in personalized customization workshop[J].Journal of Nanjing University of Science and Technology，2021，45（6）：692-699.
[23] 武星，翟晶晶，楼佩煌，等.考虑任务行程时间的多载量自动导引车系统防死锁任务调度[J].中国机械工程，2021，32（23）：2840-2849.
WU X，ZHAI J J，LOU P H，et al.Deadlock-free task scheduling with task travel time for a multi-load AGV system[J].China Mechanical Engineering，2021，32（23）：2840-2849.
[24] XIONG H G，SHI S Y，REN D N，et al.A survey of job shop scheduling problem：the types and models[J].Computers & Operations Research，2022，142：105731.
[25] UMAR U A，ARIFFIN M，ISMAIL N，et al.Hybrid multiobjective genetic algorithms for integrated dynamic scheduling and routing of jobs and automated-guided vehicle（AGV） in flexible manufacturing systems（FMS） environment[J].International Journal of Advanced Manufacturing Technology，2015，81（9/12）：2123-2141.
[26] HEGER J，VOSS T.Dynamic priority based dispatching of AGVs in flexible job shops[J].Procedia CIRP，2019，79：445-449.
[27] HE L J，CHIONG R，LI W F，et al.A multiobjective evolutionary algorithm for achieving energy efficiency in production environments integrated with multiple automated guided vehicles[J].Knowledge-Based Systems，2022，243：108315.
[28] 马千慧，梁晓磊，刘星雨，等.多AGV和机器集成的多目标柔性作业车间调度研究[J].计算机工程与应用，2023，59（1）：278-290.
MA Q H，LIANG X L，LIU X Y，et al.Research on multi-objective flexible job shop scheduling with multiple AGVs and machines integration[J].Computer Engineering and Applications，2023，59（1）：278-290.
[29] NAGESWARARAO M，NARAYANARAO K，RANAGAJANARDHANA G.Simultaneous scheduling of machines and AGVs in flexible manufacturing system with minimization of tardiness criterion[J].Procedia Materials Science，2014，5：1492-1501.
[30] LI M，LEI D M.An imperialist competitive algorithm with feedback for energy-efficient flexible job shop scheduling with transportation and sequence-dependent setup times[J].Engineering Applications of Artificial Intelligence，2021，103：104307.
[31] 邹裕吉，宋豫川，王馨坤，等.自动导向小车与加工设备多目标集成调度的聚类遗传算法[J].中国机械工程，2022，33（1）：97-108.
ZOU Y J，SONG Y C，WANG X K，et al.Clustering genetic algorithm for multi-objective integrated scheduling of AGVs and machine[J].China Mechanical Engineering，2022，33（1）：97-108.
[32] HEGER J，VOSS T.Reducing mean tardiness in a flexible job shop containing AGVs with optimized combinations of sequencing and routing rules[J].Procedia CIRP，2019，81：1136-1141.
[33] 郭沛佩，付建林，江海凡，等.基于规则的柔性作业车间机床与AGV联合调度优化[J].制造技术与机床，2021（9）：107-113.
GUO P P，FU J L，JIANG H F，et al.Rule-based optimization of joint scheduling of machine and AGV in flexible job shop[J].Manufacturing Technology & Machine Tool，2021（9）：107-113.
[34] 刘二辉，姚锡凡，陶韬，等.基于改进花授粉算法的共融AGV作业车间调度[J].计算机集成制造系统，2019，25（9）：2219-2236.
LIU E H，YAO X F，TAO T，et al.Improved flower pollination algorithm for job shop scheduling problem integrated with AGVs[J].Computer Integrated Manufacturing Systems，2019，25（9）：2219-2236.
[35] XU W X，GUO S S.A multi-objective and multi-dimensional optimization scheduling method using a hybrid evolutionary algorithms with a sectional encoding mode[J].Sustainability，2019，11（5）：1-24.
[36] BARAK S，MOGHDANI R，MAGHSOUDLOU H.Energy-efficient multi-objective flexible manufacturing scheduling[J].Journal of Cleaner Production，2021，283：124610.
[37] 肖海宁，楼佩煌，严伟国，等.柔性作业车间中机床与自动导引车在线调度方法[J].农业机械学报，2013，44（4）：280-286.
XIAO H N，LOU P H，YAN W G，et al.On-line scheduling method for simultaneous scheduling of machines and automated guided vehicles in flexible job shop[J].Transactions of the Chinese Society for Agricultural Machinery，2013，44（4）：280-286.
[38] DAI M，TANG D B，GIRET A，et al.Multi-objective optimization for energy-efficient flexible job shop scheduling problem with transportation constraints[J].Robotics and Computer-Integrated Manufacturing，2019，59：143-157.
[39] 耿凯峰，叶春明.带工序跳跃的绿色混合流水车间机器与AGV联合调度研究[J].控制与决策，2022，37（23）：2723-2732.
GENG K F，YE C M.Joint scheduling of machines and AGVs in green hybrid flow shop with missing operations[J].Control and Decision，2022，37（23）：2723-2732.
[40] 戴敏，张玉伟，曾励.考虑运输时间的绿色作业车间调度问题研究[J].工业工程，2020，23（2）：41-48.
DAI M，ZHANG Y W，ZENG L.A research on green job shop scheduling considering transportation time[J].Industrial Engineering Journal，2020，23（2）：41-48.
[41] 戴敏，张玉伟，曾励.绿色作业车间机器与AGV的集成调度研究[J].南京航空航天大学学报，2020，52（3）：468-477.
DAI M，ZHANG Y W，ZENG L.Integrated scheduling of machines and AGVs in green job shop[J].Journal of Nanjing University of Aeronautics & Astronautics，2020，52（3）：468-477.
[42] TAN W H，YUAN X F，HUANG G M，et al.Low-carbon joint scheduling in flexible open-shop environment with constrained automatic guided vehicle by multi-objective particle swarm optimization[J].Applied Soft Computing，2021，111：107695.
[43] FONTES D B M，HOMAYOUNI S M.Joint production and transportation scheduling in flexible manufacturing systems[J].Journal of Global Optimization，2019，74：879-908.
[44] HAM A.Transfer-robot task scheduling in job shop[J].International Journal of Production Research，2020（19）：1-11.
[45] BABU A G，JERALD J，HAQ A N，et al.Scheduling of machines and automated guided vehicles in FMS using differential evolution[J].International Journal of Production Research，2010，48（16）：4683-4699.
[46] CHAUDHRY I A，MAHMOOD S，SHAMI M.Simultaneous scheduling of machines and automated guided vehicles in FMS using GAs[J].Journal of Central South University，2011，18（5）：1473-1486.
[47] KUMAR M，JANARDHANA R，RAO C.Simultaneous scheduling of machines and vehicles in an FMS environment with alternative routing[J].International Journal of Advanced Manufacturing Technology，2011，53（1/4）：339-351.
[48] EROL R，SAHIN C，BAYKASOGLU A，et al.A multi-agent based approach to dynamic scheduling of machines and automated guided vehicles in manufacturing systems[J].Applied Soft Computing，2012，12（6）：1720-1732.
[49] LACOMME P，LARABI M，TCHERNEV N.Job-shop based framework for simultaneous scheduling of machines and automated guided vehicles[J].International Journal of Production Economics，2013，143（1）：24-34.
[50] ZHENG Y，XIAO Y，SEO Y.A tabu search algorithm for simultaneous machine/AGV scheduling problem[J].International Journal of Production Research，2014，52（19/20）：5748-5763.
[51] NOURI H E，DRISS O B，GHEDIRA K.Simultaneous scheduling of machines and transport robots in flexible job shop environment using hybrid metaheuristics based on clustered holonic multiagent model[J].Computers & Industrial Engineering，2016，102（12）：488-501.
[52] LIN J T，CHIU C C，CHANG Y H.Simulation-based optimization approach for simultaneous scheduling of vehicles and machines with processing time uncertainty in FMS[J].Flexible Services and Manufacturing Journal，2019（31）：104-141.
[53] ZHU Z，HE Y.An improved genetic algorithm for production scheduling on FMS with simultaneous use of machines and AGVs[C]//2019 11th International Conference on Intelligent Human-Machine Systems and Cybernetics（IHMSC），2019：245-249.
[54] REDDY N S，RAMAMURTHY D V，RAO K P，et al.Integrated scheduling of machines，AGVs and tools in multi-machine FMS using crow search algorithm[J].International Journal of Computer Integrated Manufacturing，2019，32（11）：1117-1133.
[55] REDDY N S，RAMAMURTHY D V，LALITHA M P，et al.Minimizing the total completion time on a multi-machine FMS using flower pollination algorithm[J].Soft Computing，2022，26：1437-1458.
[56] HOMAYOUNI S M，FONTES D，GONALVES J F.A multistart biased random key genetic algorithm for the flexible job shop scheduling problem with transportation[J].International Transactions in Operational Research，2020，30（3）：1-29.
[57] YUAN M H，LI Y D，PEI F Q，et al.Dual-resource integrated scheduling method of AGV and machine in intelligent manufacturing job shop[J].Journal of Central South University，2021，28（8）：2423-2435.
[58] HOMAYOUNI S M，FONTES D B M M.Production and transport scheduling in flexible job shop manufacturing systems[J].Journal of Global Optimization，2021，79：463-502.
[59] QU S，HU Y G，REN W B，et al.Coordinative scheduling of the mobile robots and machines based on hybrid GA in flexible manufacturing systems[J].Procedia CIRP，2021，104：1005-1010.
[60] YAN J，LIU Z F，ZHANG C X，et al.Research on flexible job shop scheduling under finite transportation conditions for digital twin workshop[J].Robotics and Computer-Integrated Manufacturing，2021，72：102198.
[61] 龙传泽，杨煜俊.基于遗传算法的柔性机器人制造单元调度问题研究[J].组合机床与自动化加工技术，2015（11）：141-144.
LONG C Z，YANG Y J.Research of flexible robotic manufacturing cell scheduling problem based on hybrid genetic algorithm[J].Modular Machine Tool & Automatic Manufacturing Technique，2015（11）：141-144.
[62] 王雷，蔡劲草，唐敦兵，等.基于改进遗传算法的柔性作业车间调度[J].南京航空航天大学学报，2017，49（6）：779-785.
WANG L，CAI J C，TANG D B，et al.Flexible job shop scheduling problem based on improved genetic algorithm[J].Journal of Nanjing University of Aeronautics & Astronautics，2017，49（6）：779-785.
[63] 杨煜俊，陈业.求解柔性机器人车间调度问题的混合蚁群算法[J].计算机工程与应用，2018，54（13）：160-167.
YANG Y J，CHEN Y.Hybrid ant colony optimization for flexible robotic manufacturing cell scheduling problem[J].Computer Engineering and Applications，2018，54（13）：160-167.
[64] 徐云琴，叶春明，曹磊.含有AGV的柔性车间调度优化研究[J].计算机应用研究，2018，35（11）：3271-3275.
XU Y Q，YE C M，CAO L.Research on flexible job-shop scheduling problem with AGV constraints[J].Application Research of Computers，2018，35（11）：3271-3275.
[65] 徐云琴，叶春明，曹磊.具有行为效应的含AGV柔性车间调度研究[J].计算机应用研究，2019，36（10）：3033-3038.
XU Y Q，YE C M，CAO L.Research on flexible job-shop scheduling problem with AGV constraints and behavioral effects[J].Application Research of Computers，2019，36（10）：3033-3038.
[66] 陆远，冯睽睽，胡莹.单个AGV小车多个搬运请求的调度算法研究[J].组合机床与自动化加工技术，2019（2）：157-160.
LU Y，FENG K K，HU Y.An automated guided vehicle deals with scheduling algorithm for multiple transport requests[J].Modular Machine Tool & Automatic Manufacturing Technique，2019（2）：157-160.
[67] 李广博，于东，胡毅.基于变邻域遗传算法的离散制造物料配送调度优化[J].组合机床与自动化加工技术，2019（11）：152-155.
LI G B，YU D，HU Y.Distribution scheduling optimization of discrete manufacturing materials based on variable neighborhood genetic algorithms[J].Modular Machine Tool & Automatic Manufacturing Technique，2019（11）：152-155.
[68] 陈魁，毕利，王文雅.柔性作业车间AGV与机器双资源集成调度研究[J].系统仿真学报，2022，34（3）：461-469.
CHEN K，BI L，WANG W Y.Research on integrated scheduling of AGV and machine in flexible job shop[J].Journal of System Simulation，2022，34（3）：461-469.
[69] 徐逸凡，张利平，唐秋华，等.求解带AGV柔性作业车间调度问题的改进灰狼算法[J].工业工程，2021，24（6）：25-33.
XU Y F，ZHANG L P，TANG Q H，et al.An improved grey wolf optimization for solving scheduling problem of flexible job shop with AGV[J].Industrial Engineering Journal，2021，24（6）：25-33.
[70] 伍乐，宋豫川，吕向飞，等.基于差分进化算法的FMS中机器与AGV同时调度方法[J].重庆大学学报，2021，44（12）：116-129.
WU Y，SONG Y C，LV X F，et al.An improved differential evolution algorithm for simultaneous scheduling of machines and AGVs in an FMS[J].Journal of Chongqing University，2021，44（12）：116-129.
[71] 苑明海，张理志，周开俊，等.基于混合遗传算法的柔性车间调度问题研究[J].工业工程与管理，2021，26（6）：95-103.
YUAN M H，ZHANG L Z，ZHOU K J，et al.Research on flexible shop scheduling based on improved hybrid genetic[J].Industrial Engineering and Management，2021，26（6）：95-103.
[72] BILGE ü，ULUSOY G.A time window approach to simultaneous scheduling of machines and material handling system in an FMS[J].Operations Research，1995，43（6）：1058-1070.
[73] ULUSOY G，ERIFOLU F S，BILGE U.A genetic algorithm approach to the simultaneous scheduling of machines and automated guided vehicles[J].Computers and Operations Research，1997，24：335-351.