基于离散型鲸鱼优化算法的AGV与机器集成调度方法
作者:
基金项目:

国家自然科学基金资助项目(51205429);重庆市科技局重庆市技术创新与应用示范专项项目(cstc2018jszx-cyzdX0150)。


AGV and machine integrated scheduling method based on discrete whale optimization algorithm
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [30]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    针对制造系统中考虑路径冲突的AGV (automated guided vehicles)与机器集成调度问题,提出一种基于时间窗和Dijkstra算法的离散型鲸鱼优化算法。首先,以最小化最大完工时间为目标,建立AGV与机器集成调度的数学模型,并采用一种三段式编码实现AGV和机器的集成编码,建立连续空间与离散空间之间的映射关系;然后,为了保证初始种群的质量和多样性,设计一种结合混沌映射和对立学习的扩展型GLR (global,local,random)种群初始化方法;运用Levy飞行算子和阈值重启操作进一步提高算法的全局搜索能力;最后,为了提高算法的局部搜索能力,引入结合问题特点的变邻域搜索算法。标准算例仿真实验和柔性仿真实验证明了该算法解决AGV和机器集成调度问题的可行性和优越性。

    Abstract:

    In order to address the integrated scheduling problem of AGVs (automated guided vehicles) and machines with considering path conlict in manufacturing system, an improved discrete whale optimization algorithm based on time window and Dijkstra algorithm was proposed. First, with the goal of minimizing the maximum completion time, a mathematical model of AGV-and-machine integrated scheduling was established. Then, a three-stage coding was used to realize the integrated coding of AGVs and machine, and a continuous space and discrete space were established. Second, in order to ensure the quality and diversity of the initial population, an extended GLR population initialization method combining chaotic mapping and opposition learning was designed. Then, the Levy flight operator and threshold restart operation were used to further improve the algorithm's global search capability. Finally, in order to improve the local search ability of the algorithm, a variable neighborhood search algorithm combined with the features of the problem was introduced. Standard simulation experiments and flexible simulation experiments have proved the feasibility and superiority of the proposed algorithm to solve the problem of AGV-and-machine integrated scheduling.

    参考文献
    [1] 付建林,张恒志,张剑,等.自动导引车调度优化研究综述[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.(in Chinese)
    [2] Ulusoy G, Bilge V. Simultaneous scheduling of machines and automated guided vehicles[J]. International Journal of Production Research, 1993, 31(12):2857-2873.
    [3] Ulusoy G, Sivrikaya-Serifo?lu F, Bilge V. A genetic algorithm approach to the simultaneous scheduling of machines and automated guided vehicles[J]. Computers&Operations Research, 1997, 24(4):335-351.
    [4] Bilge V, 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.
    [5] Abdelmaguid T F, Nassef A O, Kamal B A, et al. A hybrid GA/heuristic approach to the simultaneous scheduling of machines and automated guided vehicles[J]. International Journal of Production Research, 2004, 42(2):267-281.
    [6] Zheng Y, Xiao Y J, Seo Y. A tabu search algorithm for simultaneous machine/AGV scheduling problem[J]. International Journal of Production Research, 2014, 52(19):5748-5763.
    [7] Deroussi L, Gourgand M, Tchernev N. A simple metaheuristic approach to the simultaneous scheduling of machines and automated guided vehicles[J]. International Journal of Production Research, 2008, 46(8):2143-2164.
    [8] 刘二辉,姚锡凡,陶韬,等.基于改进花授粉算法的共融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.(in Chinese)
    [9] Saidi-Mehrabad M, Dehnavi-Arani 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, 86:2-13.
    [10] Shi Y J, Wang X C, Sun X Y, et al. A two-phase strategy with micro genetic algorithm for scheduling Multiple AGVs[C]//2016 IEEE International Conference on Systems, Man, and Cybernetics. October 9-12, 2016, Budapest, Hungary. IEEE, 2016:3101-3106.
    [11] 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-74924.
    [12] Mirjalili S, Lewis A. The whale optimization algorithm[J]. Advances in Engineering Software, 2016, 95:51-67.
    [13] 吴坤,谭劭昌.基于改进鲸鱼优化算法的无人机航路规划[J].航空学报, 2020, 41(S2):724286.Wu K, Tan S C. Path planning of UAVs based on improved whale optimization algorithm[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(S2):724286.(in Chinese)
    [14] 李伯棠,王智利,周海英,等.港口拖轮调度模糊规划优化模型及算法[J].计算机集成制造系统, 2021, 27(5):1518-1530.Li B T, Wang Z L, Zhou H Y, et al. Fuzzy programming model and algorithm of port tugboat scheduling[J]. Computer Integrated Manufacturing Systems, 2021, 27(5):1518-1530.(in Chinese)
    [15] Zhang H, Tang L, Yang C, et al. Locating electric vehicle charging stations with service capacity using the improved whale optimization algorithm[J]. Advanced Engineering Informatics, 2019, 41:100901.
    [16] Yuan Y, Xu H. An integrated search heuristic for large-scale flexible job shop scheduling problems[J]. Computers&Operations Research, 2013, 40(12):2864-2877.
    [17] Yuan Y, Xu H. Flexible job shop scheduling using hybrid differential evolution algorithms[J]. Computers&Industrial Engineering, 2013, 65(2):246-260.
    [18] Haupt R L, Haupt S E. Practical genetic algorithms[M]. New York:Wiley, 2003.
    [19] 高亮,张国辉,王晓娟.柔性作业车间调度智能算法及其应用[M].武汉:华中科技大学出版社, 2012:35-38.Gao L, Zhang G H, Wang X J. Intelligent algorithm for flexible job shop scheduling and its application[M]. Wuhan:Huazhong University of Science and Technology Press, 2012:35-38.(in Chinese)
    [20] Ewees A A, El Aziz M A, Hassanien A E. Chaotic multi-verse optimizer-based feature selection[J]. Neural Computing and Applications, 2019, 31(4): 991-1006. DOI:10.1007/s00521-017-3131-4
    [21] Shen L Y, Xu L H, Wei R H, et al. Multi-swarm optimization with chaotic mapping for dynamic optimization problems[C]//2015 8th International Symposium on Computational Intelligence and Design (ISCID). December 12-13, 2015, Hangzhou, China. IEEE, 2015: 132-137.
    [22] Alamri H S, Alsariera Y A, Zamli K Z. Opposition-based whale optimization algorithm[J]. Advanced Science Letters, 2018, 24(10):7461-7464.
    [23] Elaziz M A, Mirjalili S. A hyper-heuristic for improving the initial population of whale optimization algorithm[J]. Knowledge-Based Systems, 2019, 172:42-63.
    [24] 王学武,严益鑫,顾幸生.基于莱维飞行粒子群算法的焊接机器人路径规划[J].控制与决策, 2017, 32(2):373-377.Wang X W, Yan Y X, Gu X S. Welding robot path planning based on Levy-PSO[J]. Control and Decision, 2017, 32(2):373-377.(in Chinese)
    [25] 徐坤,陈志军,闫学勤.基于莱维飞行的改进蚁群算法求解TSP问题[J].计算机工程与设计, 2019, 40(1):245-249.Xu K, Chen Z J, Yan X Q. Improved ant colony algorithm based on Levy flight to solve TSP problem[J]. Computer Engineering and Design, 2019, 40(1):245-249.(in Chinese)
    [26] Liu M, Yao X F, Li Y X. Hybrid whale optimization algorithm enhanced with Lévy flight and differential evolution for job shop scheduling problems[J]. Applied Soft Computing, 2020, 87:105954.
    [27] Mladenovi[KG-1.0mm]c[DD (-2.5mm] [KG0.5mm] [HT5"SS]'[HT5" SS] N, Hansen P. Variable neighborhood search[J]. Computers&Operations Research, 1997, 24(11):1097-1100.
    [28] 贺丽娜,楼佩煌,钱晓明,等.基于时间窗的自动导引车无碰撞路径规划[J].计算机集成制造系统, 2010, 16(12):2630-2634.He L N, Lou P H, Qian X M, et al. Conflict-free automated guided vehicles routing based on time window[J]. Computer Integrated Manufacturing Systems, 2010, 16(12):2630-2634.(in Chinese)
    [29] 赵诗奎,方水良.基于工序编码和邻域搜索策略的遗传算法优化作业车间调度[J].机械工程学报, 2013, 49(16):160-169.Zhao S K, Fang S L. Operation-based encoding and neighborhood search genetic algorithm for job shop scheduling optimization[J]. Journal of Mechanical Engineering, 2013, 49(16):160-169.(in Chinese)
    [30] Alfredo Tang Montané F, Galv?o R D. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service[J]. Computers & Operations Research, 2006, 33(3): 595-619. DOI:10.1016/j.cor.2004.07.009
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

邹裕吉,宋豫川,王毅,王馨坤.基于离散型鲸鱼优化算法的AGV与机器集成调度方法[J].重庆大学学报,2022,45(6):55-74.

复制
分享
文章指标
  • 点击次数:403
  • 下载次数: 793
  • HTML阅读次数: 907
  • 引用次数: 0
历史
  • 收稿日期:2020-11-25
  • 最后修改日期:2021-04-02
  • 在线发布日期: 2022-06-18
文章二维码