基于蚁群算法的多加工路线柔性车间调度问题  

ACO integrated approach for solving flexible job-shop scheduling with multiple process plans

作　　者：黄学文 张晓彤 艾亚晴 HUANG Xuewen, ZHANG Xiaotong , AI gaqing(Faculty of Management and Economics, Daiian University of Technology, Dalian 116024, Chin)

机构地区：[1]大连理工大学管理与经济学部,辽宁大连116024

出　　处：《计算机集成制造系统》2018年第3期558-569,共12页Computer Integrated Manufacturing Systems

基　　金：国家科技支撑计划资助项目(2015BAF09B01)~~

摘　　要：针对具有工艺路径柔性和机器柔性的多加工路线柔性车间调度问题(FJSP-MPP),基于OR子图,提出一种新的四元组数学描述方法来描述工艺路径柔性和机器柔性;以最小化最大完工时间为优化目标,构建了FJSP-MPP的数学模型。在不需要预先建立析取图模型的前提下,通过设计OR子图和工件的Allowed列表和Tabu列表的相关操作算法,构造了面向FJSP-MPP的蚂蚁路径;通过引入额外的节点信息素,改进信息素更新策略和状态转移规则,实现了蚁群算法求解FJSP-MPP。不同规模数据实验结果表明,该算法具有良好的优化性能。For Flexible Job-shop Scheduling Problem with Multiple Process Plans（FJSP-MPP）,a Four-Tuple based Mathematical Scheme（FTMS）was proposed for describing processing flexibility and operation flexibility.With the optimization objective of minimizing the makespan,a mathematical model on FJSP-MPP was constructed.Without establishing upfront the disjunctive graph model for FJSP-MPP,the ant path oriented to this problem was generated based on related algorithms of Allowed and Tabu lists for OR-subgraph and job.By introducing an extra pheromone on node,and modifying the pheromone update strategy and transition probability rule,an integrated scheduling algorithm for FJSP-MPP based on ant colony optimization was developed.The comparison and analysis of four different scale scheduling problems showed that the proposed algorithm had a good optimization performance.

关 键 词：柔性车间调度 工艺路径柔性 机器柔性 蚁群算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]