面向FMS基于改进的混合PSO-GA的多AGV调度算法研究

摘要/Abstract

摘要： 在柔性制造系统(Flexible Manufacturing System,FMS)中,自动导引小车(Automated Guided Vehicle,AGV)常被用于搬运物料或产品,因此AGV的优化调度成为提高生产效率的关键。AGV的调度除了要考虑AGV的任务分配问题,还需要参考每个操作的花费时间、小车的运行时间等因素。相比于单AGV调度算法,多AGV多任务调度算法需要一个更加复杂的模型来支撑。在考虑AGV的电量状况下,以最小完成时间与调度最少AGV数量作为优化目标,提出了一种改进的混合遗传算法与粒子群算法(PSO-GA),并基于该算法给出了多AGV调度模型,在此基础上进行了仿真实验。结果表明,相较于单一的GA或PSO算法,所提算法在全局寻优收敛与运行时间上有明显的优化效果,而相比于现有的混合PSO-GA算法,其在搜索精度和收敛速度上有进一步提高。

关键词: AGV, 调度, 多目标优化, 粒子群优化, 模糊混合PSO-GA, 遗传算法

Abstract: The antomated guided vehicle(AGV) is often used to transport materials for improving prodiction efficiency in manufacturing facility or a warehouse.AGV scheduling not only needs to consider the AGV task assignment problem,but also needs to consider the time spent for each operation and the running time of the car.Compared with single-objective optimization scheduling algorithm,multi-objective optimization requires a more complex model to support.This model optimizes the two dimensions of minimizing the completion time and scheduling the minimum number of AGVs considering the power status of the AGV.This paper presented an improved hybrid particle swarm optimization and genetic algorithm (PSO-GA) to optimize the model.Compared with the GA or PSO algorithm,the proposed algorithm has significant optimization effect.Compared to PSO-GA hybrid algorithm,it is further improved in the running time.

Key words: Autimated guided vehicle, Fuzzy mixing PSO-GA, Genetic algorithm, Multi-objective opimization, Particle swarm optimization, Scheduling

中图分类号:

TP391.7

岳笑含, 许晓健, 王溪波. 面向FMS基于改进的混合PSO-GA的多AGV调度算法研究[J]. 计算机科学, 2018, 45(11A): 167-171. https://doi.org/

YUE Xiao-han, XU Xiao-jian, WANG Xi-bo. Research on Muti-AGV Sechduling Algorithm Based on Improved Hybrid PSO-GA for FMS[J]. Computer Science, 2018, 45(11A): 167-171. https://doi.org/

参考文献

[1]KOO P H,JANG J J,SUH J D.Vehicle dispatching for highfily loaded semiconductor production bottle-neck machines first [J].International Journal of Flexifible Manufacturing System,2005,17(1):23-38.
[2]樊树海,陈金龙,曹霞,等.顺序矩阵扩展研究及其在流水车间布置中的应用 [J].工业工程与管理,2008,13(6):51-54.
[3]AYDEMIR E,KORUCA H I.A new production scheduling module using priority-rule based genetic glgorithmnm[J].International Journal of Simulation Modeling,2015,14(3):450-462.
[4]李雪芹,丰伟.车辆优化调度的遗传算法求解[J].铁道运输与经济,2006,29(1):73-75.
[5]柳赛男,柯映林.自动化仓库系统 AGV 小车优化调度方法[J].组合机床与自动化加工技术,2008(6):23-25.
[6]CAI Q,TANG D,ZHENG K,et al.Multi-AGV scheduling optimization based on neuro-endocrine coordination mechanism[J].Inrternational Journal on Smart Sensing and Intelligent Systems,2014,7(4):1613-1630.
[7]杨立熙,余慧慧.考虑运输时间的柔性作业车间调度问题研究 [J].武汉理工大学学报,2017,39(1):608-613.
[8]KRISHNAN M,KARTHIKEYAN T,CHINNUSAMY T R,et al.An Evolutionary Hybrid Algorithm for Layout Planning in Flexible Manufacturing System[J].Advanced Materials Research,2014,984-985:444-451.
[9]CHANG C D J,LIU S H J.AGV Control Using PSO for ANFIS-PID Controller Parameters Tuning[C]∥International Conference on Electric Information & Control Engineering.2012:176-179.
[10]汤晏安,谷宝慧.改进PSO在AGV系统路径优化调度中的应用研究[J].计算机工程应用,2016,52(3):261-265.
[11]徐云琴,叶春明,曹磊.含有AGV的柔性车间调度优化研究[J].计算机应用研究,2017,35(11).
[12]MOUSAVI M,YAP H J,MUSA S N,et al.Multi-objective AGV scheduling in an FMS using a hybrid of genetic algorithm and particle swarm optimization[J].Plos One,2017,12(3):e0169817.
[13]REDDY B S P,RAO C S P.Flexible manufacturing system mo-delling and performance evaluation using Automod[J].International Journal of Simulation Modelling,2011,10(2):78-90.
[14]DE K,LI J,WANG W C.Research on flexible manufacturing system real-time scheduling optimization[J].Machine Tool & Hydraulics,2015(18):44-47.
[15]Egemin Automation Inc.Battery charging systems for automated guided vehicles[OL].http://www.egeminusa.com/pages/agvs/agvscharging.html.
[16]TALEIZADEH A A,NIAKI S T A,ARYANEZHAD M B,et al.A hybrid method of fuzzy simulation and genetic algorithm to optimize constrained inventory control systems with stochastic replenishments and fuzzy demand[J].Information Sciences,2013,220:425-441.
[17]TASGETIREN M F,SEVKLI M,LIANG Y C,et al.Particle swarm optimization algorithm for single machine total weighted tardiness problem[C]∥Congress on Evolutionary Computation(CEC 2004).2004:1412-1419.

相关文章 15

[1]	冷典典, 杜鹏, 陈建廷, 向阳. 面向自动化集装箱码头的AGV行驶时间估计 Automated Container Terminal Oriented Travel Time Estimation of AGV 计算机科学, 2022, 49(9): 208-214. https://doi.org/10.11896/jsjkx.210700028
[2]	赵冬梅, 吴亚星, 张红斌. 基于IPSO-BiLSTM的网络安全态势预测 Network Security Situation Prediction Based on IPSO-BiLSTM 计算机科学, 2022, 49(7): 357-362. https://doi.org/10.11896/jsjkx.210900103
[3]	杨浩雄, 高晶, 邵恩露. 考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题 Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery 计算机科学, 2022, 49(6A): 191-198. https://doi.org/10.11896/jsjkx.210400005
[4]	刘漳辉, 郑鸿强, 张建山, 陈哲毅. 多无人机使能移动边缘计算系统中的计算卸载与部署优化 Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems 计算机科学, 2022, 49(6A): 619-627. https://doi.org/10.11896/jsjkx.210600165
[5]	田真真, 蒋维, 郑炳旭, 孟利民. 基于服务器集群的负载均衡优化调度算法 Load Balancing Optimization Scheduling Algorithm Based on Server Cluster 计算机科学, 2022, 49(6A): 639-644. https://doi.org/10.11896/jsjkx.210800071
[6]	孙刚, 伍江江, 陈浩, 李军, 徐仕远. 一种基于切比雪夫距离的隐式偏好多目标进化算法 Hidden Preference-based Multi-objective Evolutionary Algorithm Based on Chebyshev Distance 计算机科学, 2022, 49(6): 297-304. https://doi.org/10.11896/jsjkx.210500095
[7]	张捷, 唐强, 刘朔晗, 曹越, 赵维, 刘韬, 谢士明. 智能电网中基于优先级的预约式电动汽车充电管理研究 Priority Based EV Charging Management Under Service Reservation in Smart Grid 计算机科学, 2022, 49(6): 55-65. https://doi.org/10.11896/jsjkx.220200013
[8]	李浩东, 胡洁, 范勤勤. 基于并行分区搜索的多模态多目标优化及其应用 Multimodal Multi-objective Optimization Based on Parallel Zoning Search and Its Application 计算机科学, 2022, 49(5): 212-220. https://doi.org/10.11896/jsjkx.210300019
[9]	柳鹏, 刘波, 周娜琴, 彭心怡, 林伟伟. 混合云工作流调度综述 Survey of Hybrid Cloud Workflow Scheduling 计算机科学, 2022, 49(5): 235-243. https://doi.org/10.11896/jsjkx.210300303
[10]	彭冬阳, 王睿, 胡谷雨, 祖家琛, 王田丰. 视频缓存策略中QoE和能量效率的公平联合优化 Fair Joint Optimization of QoE and Energy Efficiency in Caching Strategy for Videos 计算机科学, 2022, 49(4): 312-320. https://doi.org/10.11896/jsjkx.210800027
[11]	田冰川, 田臣, 周宇航, 陈贵海, 窦万春. 减少Hadoop集群中网络队头阻塞的调度算法 Reducing Head-of-Line Blocking on Network in Hadoop Clusters 计算机科学, 2022, 49(3): 11-22. https://doi.org/10.11896/jsjkx.210900117
[12]	林潮伟, 林兵, 陈星. 边缘环境下基于模糊理论的科学工作流调度研究 Study on Scientific Workflow Scheduling Based on Fuzzy Theory Under Edge Environment 计算机科学, 2022, 49(2): 312-320. https://doi.org/10.11896/jsjkx.201000102
[13]	谭双杰, 林宝军, 刘迎春, 赵帅. 基于机器学习的分布式星载RTs系统负载调度算法 Load Scheduling Algorithm for Distributed On-board RTs System Based on Machine Learning 计算机科学, 2022, 49(2): 336-341. https://doi.org/10.11896/jsjkx.201200126
[14]	沈彪, 沈立炜, 李弋. 空间众包任务的路径动态调度方法 Dynamic Task Scheduling Method for Space Crowdsourcing 计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249
[15]	屈立成, 吕娇, 屈艺华, 王海飞. 基于模糊神经网络的运动目标智能分配定位算法 Intelligent Assignment and Positioning Algorithm of Moving Target Based on Fuzzy Neural Network 计算机科学, 2021, 48(8): 246-252. https://doi.org/10.11896/jsjkx.200600050

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed