基于差分进化算法的FMS中机器与AGV同时调度方法
作者:
中图分类号:

TP273

基金项目:

国家自然科学基金资助项目(51205429);工信部"船用柴油机关重件行业数字化车间集成标准研究与试验验证"项目(CSICXX002)。


An improved differential evolution algorithm for simultaneous scheduling of machines and AGVs in an FMS
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [19]
  • |
  • 相似文献
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    针对柔性制造系统中机器与AGV(automated guided vehicle)同时调度问题,提出一种混合变邻域搜索的改进离散差分进化算法。以最大完工时间最小为优化目标,考虑机器与AGV双资源约束,建立相应的数学模型。为了同时调度机器与AGV,采用基于工序、机器、AGV的3层编码结构。通过改进差分进化(differential evolution,DE)算法的变异、交叉算子产生新个体以提高算法的全局搜索能力,并引入模拟退火算法中解的接受准则选择下一代。同时,为了增强算法的局部搜索能力,对算法每次迭代的最优个体进行变邻域搜索。通过算例计算和对比,证明了提出的改进DE算法的有效性、稳定性和优越性。

    Abstract:

    An improved discrete differential evolution algorithm with variable neighborhood search was proposed for solving simultaneous scheduling of machines and AGVs in flexible manufacturing systems. With the optimization goal of making the maximum completion time minimum, considering the dual resource constraints of machines and AGVs, the corresponding mathematical model was established. The three-layer coding structure of operation,machine and AGV was employed to schedule machines and AGVs simultaneously. In order to improve the global search capability, the differential evolution algorithm generated new individuals by improved mutation and crossover operators, and introduced the acceptance criterion of solution in simulated annealing algorithm to select next generation. Furthermore, a variable neighborhood search was performed on the optimal individual in each iteration of the algorithm in order to enhance the local search capability. Finally, the effectiveness, stability and superiority of the improved differential evolution algorithm were proved by calculation and comparison of examples.

    参考文献
    [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] 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.
    [3] 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.
    [4] 龙传泽, 杨煜俊. 基于遗传算法的柔性机器人制造单元调度问题研究[J]. 组合机床与自动化加工技术, 2015(11):141-144,148. 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,148.(in Chinese)
    [5] 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]. The International Journal of Advanced Manufacturing Technology, 2015, 81(9/10/11/12):2123-2141.
    [6] Nouri H E, BelkahlaDriss O, Ghédira K. Simultaneous scheduling of machines and transport robots in flexible job shop environment using hybrid metaheuristics based on clustered holonicmultiagent model[J]. Computers & Industrial Engineering, 2016, 102:488-501.
    [7] 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(1):104-141.
    [8] 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.
    [9] Kumar M V S, Janardhana R, Rao C S P. Simultaneous scheduling of machines and vehicles in an FMS environment with alternative routing[J]. The International Journal of Advanced Manufacturing Technology, 2011, 53(1/2/3/4):339-351.
    [10] Zhang F Q, Li J J. An improved particle swarm optimization algorithm for integrated scheduling model in AGV-served manufacturing systems[J]. Journal of Advanced Manufacturing Systems, 2018, 17(3):375-390.
    [11] 徐云琴, 叶春明, 曹磊. 含有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.(in Chinese)
    [12] 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.
    [13] 刘二辉, 姚锡凡, 陶韬, 等. 基于改进花授粉算法的共融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)
    [14] Pan Q K, Wang L, Qian B. A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems[J]. Computers & Operations Research, 2009, 36(8):2498-2511.
    [15] 杨锋英, 刘会超. AGV作业调度模型及改进的DE算法研究[J]. 计算机工程与应用, 2014, 50(9):225-230. Yang F Y, Liu H C. Research on AGV job scheduling model and improved differential evolution algorithm[J]. Computer Engineering and Applications, 2014, 50(9):225-230.(in Chinese)
    [16] 吴秀丽, 刘夏晶. 差分进化算法求解分布式柔性作业车间调度问题[J]. 计算机集成制造系统, 2019, 25(10):2539-2558. Wu X L, Liu X J. Differential evolution algorithm for solving distributed flexible job shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2019, 25(10):2539-2558.(in Chinese)
    [17] 崔琪, 吴秀丽, 余建军. 变邻域改进遗传算法求解混合流水车间调度问题[J]. 计算机集成制造系统, 2017, 23(9):1917-1927. Cui Q, Wu X L, Yu J J. Improved genetic algorithm variable neighborhood search for solving hybrid flow shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2017, 23(9):1917-1927.(in Chinese)
    [18] 张超勇, 董星, 王晓娟, 等. 基于改进非支配排序遗传算法的多目标柔性作业车间调度[J]. 机械工程学报, 2010, 46(11):156-164. Zhang C Y, Dong X, Wang X J, et al. Improved NSGA-Ⅱ for the multi-objective flexible job-shop scheduling problem[J]. Journal of Mechanical Engineering, 2010, 46(11):156-164.(in Chinese)
    [19] Sahin C, Demirtas M, Erol R, et al. A multi-agent based approach to dynamic scheduling with flexible processing capabilities[J]. Journal of Intelligent Manufacturing, 2017, 28(8):1827-1845.
    相似文献
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

伍乐,宋豫川,吕向飞,雷琦.基于差分进化算法的FMS中机器与AGV同时调度方法[J].重庆大学学报,2021,44(12):116-129.

复制
分享
文章指标
  • 点击次数:388
  • 下载次数: 905
  • HTML阅读次数: 748
  • 引用次数: 0
历史
  • 收稿日期:2020-07-17
  • 在线发布日期: 2021-12-16
文章二维码