Recent Advances in Scheduling Optimization of Automated Guided Vehicles in Manufacturing Workshops

doi:10.3778/j.issn.1002-8331.2103-0390

Abstract

Abstract:

With the development of production automation in manufacturing enterprises, Automatic Guided Vehicle（AGV） has become the significant role in transportation and handling. In recent years, the key step of scheduling optimization of AGV in manufacturing workshops is to establish the optimization model of double-objective or multi-objective function, which is solved by intelligent optimization methods, in which genetic algorithm has become the most popular algorithm framework because of its exploration ability. In addition, hybrid methods are also widely used, because of these methods make the advantages of various algorithms and operators together and aim to achieve better optimization performance. The models of the latest AGV scheduling optimization in manufacturing workshops and the mainstream optimization results are summarized in this paper. The research methods presented to solve the optimization model are divided into three categories：algorithms based on the framework of genetic algorithm, other intelligent optimization methods and other optimization methods. In each category, important keywords and interdisciplinary vocabularies are extracted and summarized. Furthermore, the two disadvantages in the current research on AGV scheduling and many suggestions for the future research direction combined with the current hot spots（big data, artificial intelligence, et al.） are also given at the end of this article.

Key words: manufacturing workshops, automated guided vehicle, scheduling, intelligent optimization, genetic algorithm, hybrid method

摘要：

随着制造企业生产自动化程度加深，自动导引车（AGV）成为运输和搬运环节的主角。近年来，制造车间AGV调度主要是建立双目标或多目标函数的优化模型，采用智能优化方法进行求解，其中遗传算法以广度搜索能力强的优势成为当今最常用的算法框架。另外，当今主流的还有混合算法，它使各种算法和算子的优势集中在一起，以得到更好的优化表现。就最新的制造车间AGV调度优化所研究的问题模型进行了归纳和总结，给出了主流的优化结果表现形式，并将求解优化模型主要采用的研究方法分为基于遗传算法框架的算法、其他智能优化方法和其他优化方法三大类进行讨论，在每一大类中提取重要的关键字以及交叉学科词汇进行汇总。在此基础之上总结出当今AGV调度研究中的两点不足之处，并结合当今的热点（大数据、人工智能等）对未来的研究方向提出了几条建议。

关键词: 制造车间, 自动导引车, 调度, 智能优化, 遗传算法, 混合算法

CAO Lijia, LIU Yang. Recent Advances in Scheduling Optimization of Automated Guided Vehicles in Manufacturing Workshops[J]. Computer Engineering and Applications, 2021, 57(21): 59-67.

曹立佳，刘洋. 制造车间自动导引车调度新进展[J]. 计算机工程与应用, 2021, 57(21): 59-67.

References

[1] 刘家桐.自动物料转运小车调度系统的研制[D].成都：电子科技大学，2019.
LIU J T.Development of automatic material transfer trolley dispatching system[D].Chengdu：University of Electronic Science and Technology of China，2019.
[2] 付建林，张恒志，张剑，等.自动导引车调度优化研究综述[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.
[3] MOUSAVI M，YAP H J，MUSA S N，et al.A fuzzy hybrid GA-PSO algorithm for multi-objective AGV scheduling in FMS[J].International Journal of Simulation Modelling，2017，16（1）：58-71.
[4] 岳笑含，许晓健，王溪波.面向FMS基于改进的混合PSO-GA的多AGV调度算法研究[J].计算机科学，2018，45（S2）：167-171.
YUE X H，XU X J，WANG X B.Research on multi-AGV sechduling algorithm based on improved hybrid PSO-GA for FMS[J].Computer Science，2018，45（S2）：167-171.
[5] 贺长征，宋豫川，雷琦，等.柔性作业车间多自动导引小车和机器的集成调度[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.
[6] XIAO H N，WU X，ZENG Y，et al.A CEGA-based optimization approach for integrated designing of a unidirectional guide-path network and scheduling of AGVs[J].Mathematical Problems in Engineering，2020，2020：3961409.
[7] LYU X F，SONG Y C，HE C Z，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.
[8] UMAR U A，ARIFFIN M K A，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）：2123-2141.
[9] 熊晔，毛剑琳，郭宁，等.面向缓冲区容量有限的AGV系统调度研究[J].软件导刊，2018，17（1）：152-156.
XIONG Y，MAO J L，GUO N，et al.Research on scheduling of AGV system with limited buffer capacity[J].Software Guide，2018，17（1）：152-156.
[10] RAHMAN H F，JANARDHANAN M N，NIELSEN P.An integrated approach for line balancing and AGV scheduling towards smart assembly systems[J].Assembly Automation，2020，40（2）：219-234.
[11] 李西兴，杨道明，李鑫，等.基于混合遗传鲸鱼算法的柔性作业车间自动导引车融合调度方法[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 hybrid genetic whale optimization algorithm[J].China Mechanical Engineering，2021，32（8）：938-950.
[12] NABOVATI H，HALEH H，VAHDANI B.Fuzzy multi-objective optimization algorithms for solving multi-mode automated guided vehicles by considering machine break time and artificial neural network[J].Neural Network World，2018，28（3）：255-283.
[13] WANG F L，ZHANG Y，SU Z Q.A novel scheduling method for automated guided vehicles in workshop environments[J].International Journal of Advanced Robotic Systems，2019，16（3）：1737001528.
[14] CHEN C，TIONG L K，CHEN I.Using a genetic algorithm to schedule the space-constrained AGV-based prefabricated bathroom units manufacturing system[J].International Journal of Production Research，2019，57（10）：3003-3019.
[15] ZHANG L X，HU Y G，GUAN Y.Research on hybrid-load AGV dispatching problem for mixed-model automobile assembly line[J].Procedia CIRP，2019，81：1059-1064.
[16] RAHMAN H F，NIELSEN I.Scheduling automated transport vehicles for material distribution systems[J].Applied Soft Computing，2019，82：105552.
[17] LU S，HU Y G，QU S.Joint optimization of tow-trains dispatch and conflict-free route planning in mixed-model assembly lines[J].Procedia CIRP，2021，97：253-259.
[18] 李峥峰，刘阳阳.考虑充电的多AGV的作业车间调度问题[J/OL].计算机集成制造系统，2021：1-14.https：//kns.cnki.net/kcms/detail/11.5946.TP.20210329.1053.002.html.
LI Z F，LIU Y Y.Research on job shop scheduling with multiple AGVs considering charging[J/OL].Computer Integrated Manufacturing Systems，2021：1-14.https：//kns.cnki.net/kcms/detail/11.5946.TP.20210329.1053.002.html.
[19] 李广博，于东，胡毅.基于变邻域遗传算法的离散制造物料配送调度优化[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（Modular Machine Tool & Automatic Manufacturing Technique，2019（11）：152-155.
[20] QU S，HU Y G，ZHANG L X，et al.An improved optimization method for materials distribution based on spatiotemporal clustering in automobile assembly lines[J].Procedia CIRP，2021，97：241-246.
[21] LIU Y B，JI S W，SU Z R，et al.Multi-objective AGV scheduling in an automatic sorting system of an unmanned（intelligent） warehouse by using two adaptive genetic algorithms and a multi-adaptive genetic algorithm[J].PLoS One，2019，14（12）：e226161.
[22] 王体春，徐本领.基于排队论的仓储AGV配置和调度分析[J].机械设计与制造，2020（4）：266-269.
WANG T C，XU B L.AGV configuration and scheduling analysis based on queuing theory[J].Machinery Design & Manufacture，2020（4）：266-269.
[23] LEE C W，WONG W P，IGNATIUS J，et al.Winner determination problem in multiple automated guided vehicle considering cost and flexibility[J].Computers & Industrial Engineering，2020，142：106337.
[24] 詹逸鹏.多AGV系统的任务调度研究[D].武汉：湖北工业大学，2020.
ZHAN Y P.Research on task scheduling of multi-AGV system[D].Wuhan：Hubei University of Technology，2020.
[25] 杨智飞，苏春，胡祥涛，等.面向智能生产车间的多AGV系统多目标调度优化[J].东南大学学报（自然科学版），2019，49（6）：1033-1040.
YANG Z F，SU C，HU X T，et al.Multi-objective scheduling optimization for multi-AGV systems of intelligent jobshop[J].Journal of Southeast University（Natural Science Edition），2019，49（6）：1033-1040.
[26] GOLI A，TIRKOLAEE E B，AYDIN N S.Fuzzy integrated cell formation and production scheduling considering automated guided vehicles and human factors[J].IEEE Transactions on Fuzzy Systems，2021（99）：1.
[27] 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）：1329-1352.
[28] XU W X，GUO S S，LI X X，et al.A dynamic scheduling method for logistics tasks oriented to intelligent manufacturing workshop[J].Mathematical Problems in Engineering，2019，2019：7237459.
[29] YAO F，ALKAN B，AHMAD B，et al.Improving just-in-time delivery performance of IoT-enabled flexible manufacturing systems with AGV based material transportation[J].Sensors，2020，20（21）：6366.
[30] BARAK S，MOGHDANI R，MAGHSOUDLOU H.Energy-efficient multi-objective flexible manufacturing scheduling[J].Journal of Cleaner Production，2021，283：124610.
[31] ZOU W Q，PAN Q K，TASGETIREN M F.An effective iterated greedy algorithm for solving a multi-compartment AGV scheduling problem in a matrix manufacturing workshop[J].Applied Soft Computing，2021，99：106945.
[32] 徐云琴，叶春明，曹磊.具有行为效应的含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.
[33] 邹裕吉，宋豫川，王毅，等.基于离散型鲸鱼优化算法的AGV与机器集成调度方法[J/OL].重庆大学学报，2021：1-23[2021-03-22].https：//kns.cnki.net/kcms/detail/50.1044. N.20210402.1614.002.html.
ZOU Y J，SONG Y C，WANG Y，et al.AGV and machine integrated scheduling method based on discrete whale optimization algorithm[J/OL].Journal of Chongqing University，2021：1-23.[2021-03-22].https：//kns.cnki.net/kcms/detail/50.1044.N.20210402.1614.002.html
[34] 魏永来，龙伟，李炎炎，等.基于混合禁忌蝙蝠算法的AGV物料配送调度研究[J].组合机床与自动化加工技术，2018（11）：145-149.
WEI Y L，LONG W，LI Y Y，et al.Research on AGV material delivery scheduling problem based on hybrid tabu bat algorithm[J].Modular Machine Tool ＆ Automatic Manufacturing Technique，2018（11）：145-149.
[35] 伍乐，宋豫川，吕向飞，等.基于差分进化算法的FMS中机器与AGV同时调度方法[J/OL].重庆大学学报，2020：1-16[2021-03-22].http：//kns.cnki.net/kcms/detail/50.1044N.
20200907.1407.002.html.
WU Y，SONG Y C，LYU X F，et al.A differential evolution algorithm for simultaneous scheduling of machines and AGVs in an FMS[J/OL].Journal of Chongqing University，2020：1-16[2021-03-22].http：//kns.cnki.net/kcms/detail/50.1044N.20200907.1407.002.html.
[36] 刘二辉，姚锡凡，陶韬，等.基于改进花授粉算法的共融AGV作业车间调度[J].计算机集成制造系统，2019，25（9）：2219-2236.
LIU E H，YAO X F，TAO T，et al.Improved flower pollinaton algorithm for job shop scheduling problems integrated with AGVs[J].Computer Integrated Manufacturing Systems，2019，25（9）：2219-2236.
[37] NABOVATI H，HALEH H，VAHDANI B.Multi-objective invasive weeds optimisation algorithm for solving simultaneous scheduling of machines and multi-mode automated guided vehicles[J].European Journal of Industrial Engineering，2020，14（2）：165-188.
[38] LI G M，LI X Y，GAO L，et al.Tasks assigning and sequencing of multiple AGVs based on an improved harmony search algorithm[J].Journal of Ambient Intelligence and Humanized Computing，2019，10（11）：4533-4546.
[39] LI G M，ZENG B，LIAO W，et al.A new AGV scheduling algorithm based on harmony search for material transfer in a real-world manufacturing system[J].Advances in Mechanical Engineering，2018，10（3）：754380040.
[40] ZOU W Q，PAN Q K，TASGETIREN M F.An effective discrete artificial bee colony algorithm for scheduling an Automatic-Guided-Vehicle in a linear manufacturing workshop[J].IEEE Access，2020，8：35063-35076.
[41] 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[J].Expert Systems with Applications，2020，161：113675.
[42] ZOU W Q，PAN Q K，WANG L.An effective multi-objective evolutionary algorithm for solving the AGV scheduling problem with pickup and delivery[J].Knowledge-Based Systems，2021，218：106881.
[43] 陈敏，黎展滔，陈庆新，等.考虑有限物流运输能力的智能车间AGV调度算法研究[J].工业工程，2019，22（4）：49-57.
CHEN M，LI Z T，CHEN Q X，et al.AGV scheduling algorithm of intelligent workshop considering limited logistics transportation capacity[J].Industrial Engineering Journal，2019，22（4）：49-57.
[44] ZHAO X F，LIU H Z，LIN S X，et al.Design and implementation of a multiple AGV scheduling algorithm for a job-shop[J].International Journal of Simulation Modelling，2020，19（1）：134-145.
[45] FONTES D B M M，HOMAYOUNI S M.Joint production and transportation scheduling in flexible manufacturing systems[J].Journal of Global Optimization，2019，74（4）：879-908.
[46] GYULAI D，BERGMANN J，VáNCZA J.Adaptive network analytics for managing complex shop-floor logistics systems[J].CIRP Annals，2020，69（1）：393-396.
[47] FAZLOLLAHTABAR H，SAIDI-MEHRABAD M，BALAKRISHNAN J.Mathematical optimization for earliness/tardiness minimization in a multiple automated guided vehicle manufacturing system via integrated heuristic algorithms[J].Robotics and Autonomous Systems，2015，72：131-138.
[48] 李红.多AGV的多任务分配与路径规划研究[D].南京：南京邮电大学，2019.
LI H.Research on multi-task assignment and path planning of AGVs[D].Nanjing：Nanjing University of Posts and Telecommunications，2019.
[49] 戴敏，张玉伟，曾励.绿色作业车间机器与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.
[50] FAZLOLLAHTABAR H.Lagrangian relaxation method for optimizing delay of multiple autonomous guided vehicles[J].Transportation Letters，2018，10（6）：354-360.
[51] ZENG C K，TANG J F，FAN Z P.Auction-based cooperation mechanism for cell part scheduling with transportation capacity constraint[J].International Journal of Production Research，2019，57（12SI）：3831-3846.
[52] 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.
[53] GUTJAHR M，KELLERER H，PARRAGH S N.Heuristic approaches for scheduling jobs and vehicles in a cyclic flexible manufacturing system[J].Procedia Computer Science，2021，180：825-832.
[54] GAO Y H，LOU W D，LU H L.A novel scheduling algorithm for common rail dual automatic guided vehicles particle filtering algorithm for industrial process control[J].Mathematical Problems in Engineering，2021（2）：1-14.
[55] CHAWLA V K，CHANDA A K，ANGRA S，et al.Effect of nature-inspired algorithms and hybrid dispatching rules on the performance of automatic guided vehicles in the flexible manufacturing system[J].Journal of the Brazilian Society of Mechanical Sciences and Engineering，2019，41（10）：391-407.
[56] 孙阳君，赵宁.基于数字孪生的多AGV系统集中式调度方法[J/OL].计算机集成制造系统，2021：1-25[2021-03-22].https：//kns.cnki.net/kcms/detail/11.5946.TP.20210119.
1113.004.html.
SUN Y J，ZHAO N.Centralized scheduling approach for multi-AGV system based on digital twin[J/OL].Computer Integrated Manufacturing Systems，2021：1-25[2021?03?22].https：//kns.cnki.net/kcms/detail/11.5946.TP.
20210119.1113.004.html.
[57] FAROOQ B，BAO J S，MA Q W.Flow-shop predictive modeling for multi-automated guided vehicles scheduling in smart spinning cyber-physical production systems[J].Electronics，2020，9（5）：799.