基于分层蚁群遗传算法的多目标柔性作业车间调度方法

摘要/Abstract

摘要：

针对离散制造柔性作业车间实际工况，提出了一种基于分层蚁群遗传算法的柔性作业车间资源驱动的多目标调度方法，其基本特征是：基于连续生产中不同调度周期剩余或空闲资源等调度相关实时信息；基于完工时间和机床负荷等多目标；采用分层蚁群-遗传混合算法进行决策，通过逐步筛选，获得优化解。该方法特别适用于车间资源变化、任务执行情况变化、急件任务必须插入等情况下的动态调度。应用标准案例并设计相关组合案例进行了测试，与MOGV混合算法相比，25%的案例计算结果优于MOGV算法，最大完工时间减少5%~7%，62.5%的案例计算结果等同MOGV算法。因此，该智能调度方法不仅可以有效地取得对指定优先目标的最佳优化效果，且可自动获得多目标综合的最优解，智能调度效果显著。

关键词: 柔性作业车间, 智能调度, 多目标, 调度资源信息

Abstract:

A hierarchical ant-genetic algorithm-based multi-objective intelligent scheduling algorithm was proposed for flexible job shop problem. Its basic features were: (1) the approach was based on the real-time resource information of different scheduling periods; (2) its targets were completion time and machine load etc.; (3) the multi-objective optimization strategy and method were used in an ant-genetic hybrid algorithm to obtain the optimal solution. This method could be used in the periodical normal scheduling, the dynamic scheduling scenario and the situation of urgent jobs inserting. Some tests were done on the standard cases and a combined case. Compared to MOGV hybrid algorithm, the proposed approach outperformed in 25% of the test cases with a 5%~7% decrease in completion time. As for rests 75% of test cases, the above two algorithms show the same results. Therefore, with the ability of optimizing results based on the priorities of objectives and the comprehensive performance of all objective automatically, the effectiveness of the method proposed in this paper was verified.

Key words: flexible job shop, intelligent scheduling, multi-objective, real-time resource information

中图分类号:

TP278

邹攀, 李蓓智, 杨建国, 施烁, 梁越昇, . 基于分层蚁群遗传算法的多目标柔性作业车间调度方法[J]. 中国机械工程, 2015, 26(21): 2873-2879,2884.

Zou Pan, Li Beizhi, Yang Jianguo, Shi Shuo, Steven Y. Liang, . Hierarchical Ant-Genetic Algorithm-based Multi-objective Intelligent Approach for Flexible Job Shop Scheduling[J]. China Mechanical Engineering, 2015, 26(21): 2873-2879,2884.

参考文献

[1]安玉伟,严洪森. 一类两阶段生产系统生产计划与调度的集成优化[J]. 计算机集成制造系统,2012,18(4):796-806.
An Yuwei, Yan Hongsen.Integrated Optimization for Production Planning and Scheduling in a Two-stage Production System[J]. Computer Integrated Manufacturing Systems,2012,18(4):796-806.
[2]潘君. 整数规划的分支定界法及其MATLAB实现[J]. 科技信息,2008(7):167-168.
Pan Jun. A Branch and Bound Method for Integer Programming and Its Development in MATLAB[J]. Science and Technology Information, 2008(7):167-168.
[3]谢金慧,陈峰. 面向节能无关联平行机调度模型及分支定界法[J]. 工业工程与管理,2012,17(2):45-50.
Xie Jinhui, Chen Feng. Model and Branch-and-bound Algorithm for Energy Saving Production Scheduling Problem[J]. Industrial Engineering and Management,2012,17(2):45-50.
[4]Lee Sanghyup, Moon Ilkyeong, Bae Hyerim,et al.Flexible Job-shop Scheduling Problems with ‘AND’/‘OR’ Precedence Constraints[J]. International Journal of Production Research,2012,50(7):1979-2001.
[5]Montazeri M, van Wassenhove L N. Analysis of Scheduling Rules for an FMS[J]. International Journal of Production Research,1990,28(4):785-802.
[6]Chen H, Ihlow J, Lehmann C.A Genetic Algorithm for Flexible Job-Shop Scheduling[C]//IEEE International Conference on Robotics and Automation.Detroit,1999:1120-1125.
[7]张超勇,董星,王晓娟,等. 基于改进非支配排序遗传算法的多目标柔性作业车间调度[J]. 机械工程学报,2010,46(11):156-164.
Zhang Chaoyong, Dong Xing, Wang Xiaojuan, et al. Improved NSGA-Ⅱ for the Multi-objective Flexible Job-shop Scheduling Problem[J]. Journal of Mechanical Engineering,2010,46(11):156-164.
[8]张超勇,饶运清,李培根, 等. 柔性作业车间调度问题的两级遗传算法[J]. 机械工程学报,2007,43(4):119-124.
Zhang Chaoyong, Rao Yunqing, Li Peigen, et al. Bilevel Genetic Algorithm for the Flexible Job-shop Scheduling Problem[J].Chinese Journal of Mechanical Engineering,2007,43(4):119-124.
[9]谷峰,陈华平,卢冰原. 基于遗传算法的多目标柔性工作车间调度问题求解[J]. 运筹与管理,2006,15(1):134-139.
Gu Feng, Chen Huaping, Lu Bingyuan. The Solution for Multi-objective Flexible Job-shop Scheduling Based on Genetic Algorithm[J]. Operations Research and Management Science,2006,15(1):134-139.
[10]王伟玲,李俊芳,王晶. 求解多目标作业车间调度问题的双种群遗传算法[J]. 计算机集成制造系统,2011,17(4):808-815.
Wang Weiling, Li Junfang, Wang Jing. Double-population Genetic Algorithm for Multi-objective Job Shop Scheduling Problem[J]. Computer Integrated Manufacturing Systems,2011,17(4):808-815.
[11]刘爱军,杨育,邢青松,等. 多目标模糊柔性车间调度中的多种群遗传算法[J]. 计算机集成制造系统,2011,17(9):1954-1961.
Liu Aijun, Yang Yu, Xing Qingsong, et al. Multi-population Genetic Algorithm in Multi-objective Fuzzy and Flexible Job Shop Scheduling[J]. Computer Integrated Manufacturing Systems, 2011,17(9):1954-1961.
[12]汪双喜,张超勇,刘琼,等. 不同再调度周期下柔性作业车间动态调度研究[J]. 计算机集成制造系统, 2014,20(10):2470-2478.
Wang Shuangxi, Zhang Chaoyong, Liu Qiong, et al. Flexible Job Shop Dynamic Scheduling under Different Reschedule Periods[J].Computer Integrated Manufacturing Systems, 2014,20(10):2470-2478.
[13]宋晓宇,朱云龙,尹朝万,等. 应用混合蚁群算法求解模糊作业车间调度问题[J]. 计算机集成制造系统,2007,13(1):105-109.
Song Xiaoyu, Zhu Yunlong, Yin Chaowan, et al. Hybrid Ant Colony Algorithm for Fuzzy Job Shop Scheduling[J].Computer Integrated Manufacturing Systems, 2007,13(1):105-109.
[14]张洁,张朋,刘国宝. 基于两阶段蚁群算法的带非等效并行机的作业车间调度[J]. 机械工程学报,2013,49(6):136-144.
Zhang Jie, Zhang Peng, Liu Guobao. Two-stage Ant Colony Algorithm Based Job Shop Scheduling with Unrelated Parallel Machines[J]. Chinese Journal of Mechanical Engineering, 2013,49(6):136-144.
[15]刘志勇,吕文阁,谢庆华,等. 应用改进蚁群算法求解柔性作业车间调度问题[J]. 工业工程与管理,2010,15(3):115-119.
Liu Zhiyong, Lü Wenge, Xie Qinghua, et al. Solving Flexible Job-shop Scheduling Problem Based on an Improved Ant Colony Optimization Algorithm[J]. Industrial Engieering and Management,2010,15(3):115-119.
[16]王万良,赵澄,熊婧,等. 基于改进蚁群算法的柔性作业车间调度问题的求解方法[J]. 系统仿真学报,2008,20(16):4326-4329.
Wang Wanliang, Zhao Cheng, Xiong Jing, et al. Method to Resolve Flexible Job-shop Scheduling Problem Based on Ant Colony Algorithm[J]. Journal of System Simulation,2008,20(16):4326-4329.
[17]吴秀丽,李苏剑,杜彦华.柔性作业车间多品种小批量调度算法研究[J].中国机械工程,2010,21(4):425-429.
Wu Xiuli, Li Sujian, Du Yanhua. Research on Batch Scheduling Problem in a Flexible Job Shop[J].China Mechanical Engineering, 2010, 21(4):425-429.
[18]袁坤,朱剑英.一种求解多目标柔性Job Shop调度的改进遗传算法[J].中国机械工程,2007,18(2):156-160.
Yuan Kun, Zhu Jianying. Improved Genetic Algorithm for the Flexible Job-shop Scheduling with Multi-objective[J].China Mechanical Engineering,2007,18(2):156-160.
[19]Steger-Jensen K, Hvolby H-H, Nielsen P,et al. Advanced Planning and Scheduling Technology[J]. Production Planning & Control, 2011, 22(8):800-808.
[20]陈成,邢立宁. 求解柔性作业车间调度问题的遗传-蚁群算法[J]. 计算机集成制造系统,2011,17(3):615-621.
Chen Cheng, Xing Lining. GA-ACO for Solving Flexible Job Shop Scheduling Problem[J]. Computer Integrated Manufacturing Systems, 2011,17(3):615-621.
[21]Wang K, Choi S H. A Decomposition-based Approach to Flexible Flow Shop Scheduling under Machine Breakdown[J]. International Journal of Production Research,2012,50(1):215-234.
[22]宋代立,张洁. 蚁群算法求解混合流水车间分批调度问题[J]. 计算机集成制造系统,2013,19(7):1640-1647.
Song Daili, Zhang Jie. Batch Scheduling Problem of Hybrid Flow Shop Based on Ant Colony Algorithm[J].Computer Integrated Manufacturing Systems, 2013,19(7):1640-1647.
[23]Zwaan S V D,Marques C. Ant Colony Optimization for Job Shop Scheduling[C]//Proceedings of the ‘99workshop on Genetic Algorithms and Artificial Life(GAAL’99).Lisbon,1999：158-160.
[24]史峰,王辉,郁磊,等.MATLAB智能算法30个案例分析[M].北京：北京航空航天大学出版社,2011.
[25]Zhou R, Nee A Y C, Lee H P. Performance of an Ant Colony Optimization Algorithm in Dynamic Job Shop Scheduling Problems[J]. International Journal of Production Research,2009,47(11):2903-2920.
[26]高亮,张国辉,王晓娟.柔性作业车间调度智能算法及其应用[M]. 武汉：华中科技大学出版社,2012.
[27]张维存,郑丕谔,吴晓丹. 蚁群遗传算法求解能力约束的柔性作业车间调度问题[J]. 计算机集成制造系统,2007,13(2):333-337.
Zhang Weicun, Zhang Pi’e, Wu Xiaodan. Solution to Flexible Job Shop Scheduling Problems with Capacitated Constraints Based on Ant Colony and Genetic Algorithms[J]. Computer Integrated Manufacturing Systems, 2007,13(2):333-337.