求解柔性作业车间调度问题的两阶段参数自适应蚁群算法

摘要/Abstract

摘要：

针对柔性作业车间调度问题,提出了一种新的两阶段蚁群算法求解方案。在算法前期，采用细菌觅食趋化聚类技术判断蚁群所处的状态，自适应调整蚁群算法的参数，使算法快速收敛到全局最优解附近；在算法后期，利用混沌的随机性和遍历性特点来调整参数，有利于算法跳出局部最优。实验结果验证了该两阶段法的有效性。

关键词: 柔性作业车间调度, 蚁群算法, 细菌觅食聚类算法, 混沌

Abstract:

A new two-stage ant colony algorithm was proposed to solve the flexible job shop scheduling problem. At the early stage of the algorithm, bacterial foraging chemotaxis based clustering technology was used to determine the state of ant colony, and the parameters of ant colony algorithm were adjusted adaptively to make the algorithm rapidly convergence to the nearly global optimal solution. At the late stage, the parameters were tuned based on the randomness and ergodicity of chaos, beneficial to jump out of local optima. Experimental results verify the effectiveness of the two stage method.

Key words: flexible job shop scheduling problem, ant colony algorithm, bacterial foraging clustering algorithm, chaos

中图分类号:

TP278
TP301

凌海峰, 王西山. 求解柔性作业车间调度问题的两阶段参数自适应蚁群算法[J]. 中国机械工程, 2013, 24(24): 3380-3385.

Ling Haifeng, Wang Xishan. A Two-stage Parameter Adaptive Ant Colony Algorithm for Flexible Job Shop Scheduling Problem[J]. China Mechanical Engineering, 2013, 24(24): 3380-3385.

参考文献

[1]Song Libo, Xu Xuejun, Sun Yanming, et al. A Hybrid Genetic Algorithm for Flexible Job Shop Scheduling Problem[J]. Journal of Management Sciences in China, 2010, 13(11): 49-54.
[2]陈勇, 阮幸聪, 鲁建厦, 等. 基于元胞机和改进GA的大型零件柔性作业车间调度算法[J]. 中国机械工程, 2012, 23(2): 177-184.
Chen Yong, Ruan Xingcong, Lu Jiansha, et al. Flexible Job Shop Scheduling Algorithm of Large PartsBased on Cellular Automata and Improved GA[J]. China Mechanical Engineering, 2012, 23(2): 177-184.
[3]贾兆红, 陈华平, 孙耀晖. 混合粒子群算法在柔性工作车间调度中的应用[J]. 系统仿真学报, 2007, 19(20): 4743-4747.
Jia Zhaohong, Chen Huaping, Sun Yaohui. Hybrid Particle Swarm Optimization for Flexible Job Shop Scheduling[J]. Journal of System Simulation, 2007, 19(20): 4743-4747.
[4]Dorigo M, Maniezzo V, Colorni A. Ant System: Optimization by a Colony of Cooperating Agents[J]. IEEE Transaction on System, Man and Cybernetics, 1996, 26(1): 29-41.
[5]王万良, 赵澄, 熊婧, 等. 基于改进蚁群算法的柔性作业车间调度问题的求解方法[J]. 系统仿真学报, 2008, 20(16): 4326-4329.
Wang Wanliang, Zhao Cheng, Xiong Jing, et al. Method to Resolve Flexible Job Shop Scheduling Problem Based on Improved Ant Colony Algorithm[J]. Journal of System Simulation, 2008, 20(16): 4326-4329.
[6]Xing L N, Chen Y W, Wang P, et al. A Knowledge-based Ant Colony Optimization for Flexible Job Shop Scheduling Problems[J]. Applied Soft Computing, 2010, 10(3): 888-896.
[7]Liouane N, Saad I, Hammadi S, et al. Ant Systems & Local Search Optimization for Flexible Job Shop Scheduling Production[J]. International Journal of Computers, Communications Control, 2007, 2(2): 174-184.
[8]Dorigo M, Birattari M, Stutzle T. Ant Colony Optimization[J]. IEEE Computational Intelligence Magazine, 2006, 1(4):28-39.
[9]Favaretto D, Moretti E, Pellegrini P. On the Explorative Behavior of Max-Min Ant System[C]//Engineering Stochastic Local Search Algorithms, Designing ,Implementing and Analyzing Effective Heuristics. SLS 2009, Lecture Notes in Computer Science. Heidelberg: Springer, 2009: 115-119.
[10]鲁丽君, 何向军. 改进蚁群算法在柔性作业车间调度中的应用研究[D]. 北京: 首都经济贸易大学, 2012.
[11]焦淑娟, 张军. 蚁群算法中基于PAM聚类算法的参数调整[D]. 广州: 中山大学, 2008.
[12]Gong Y, Xu R, Zhang J, et al. A Clustering-based Adaptive Parameter Control Method for Continuous Ant Colony Optimization[C]//Proc. of the Systems, Man and Cybernetics. San Antonio, 2009: 1827-1832.
[13]Wan M, Li L, Xiao J, et al. Data Clustering Using Bacterial Foraging Optimization[J]. Journal of Intelligent Information Systems, 2012, 38(2): 321-341.
[14]凌海峰, 王浩. 细菌觅食算法与K-means结合的Web用户会话聚类[J]. 计算机工程与应用, 2012, 48(36): 121-124.
[15]余琦玮, 赵亮, 潘双夏. 基于遗传算法的柔性作业车间调度优化[J]. 组合机床与自动化加工技术, 2004(4): 32-34.
Yu Qiwei, Zhao Liang, Pan Shuangxia. A Scheduling Optimization of Flexible Job Shop Using Genetic Algorithm[J]. Modular Machine Tool Automatic Manufacturing Technique, 2004, 46(4): 32-34.
[16]亓凌, 杨建栋, 李保, 等. 基于自适应蚁群算法的柔性作业车间调度问题[J]. 机电工程, 2010, 27(2): 46-49.
Qi Ling, Yang Jiandong, Li Bao, et al. Flexible Job Shop Scheduling Problem Based on Adaptive Ant Colony Algorithm[J]. Journal of Mechanica Electrical Engineering, 2010, 27(2): 46-49.
[17]Kacem I, Hammadi S, Borne P. Approach by Localization and Multiobjective Evolutionary Optimization for Flexible Job-shop Scheduling Problems[J]. IEEE Transactions on Systems, Man and Cybernetics, 2002, 32(1): 1-13.
[18]张国辉, 高亮, 李培根, 等. 改进遗传算法求解柔性作业车间调度问题[J]. 机械工程学报, 2009, 45(7): 145-151.
Zhang Guohui, Gao Liang, Li Peigen, et al. Improved Genetic Algorithm for the Flexible Job Shop Scheduling Problem[J]. Journal of Mechanical Engineering, 2009, 45(7): 145-151.