应用混合蚁群算法求解模糊作业车间调度问题

• 论文 •

应用混合蚁群算法求解模糊作业车间调度问题

宋晓宇，朱云龙，尹朝万，李富明,

1.中国科学院沈阳自动化研究所，辽宁沈阳110016；2.中国科学院研究生院，北京100039

出版日期:2007-01-15 发布日期:2007-01-25

Hybrid ant colony algorithm for fuzzy Job Shop scheduling

SONG Xiao-yu, ZHU Yun-long，YIN Chao-wan，LI Fu-ming

1.Shenyang Inst. of Automation, Chinese Academy of Sciences, Shenyang110016, China; 2.Graduate Sch. of Chinese Academy of Sciences, Beijing100039, China

Online:2007-01-15 Published:2007-01-25

摘要/Abstract

摘要： 为解决蚁群算法求解时间过长和易陷入局部最优的问题，提出了一种求解模糊作业车间调度问题的混合算法，该算法将蚁群算法用于全局搜索。为了提高搜索效率，根据作业车间调度问题解的特征，提出一种基于关键工序的邻域搜索方法，并使用此邻域搜索方法的禁忌搜索算法嵌入蚁群算法。利用禁忌搜索算法较强的局部搜索能力，提高了蚁群算法的优化能力，改善了作业车间调度问题解的质量。实验结果验证了该混合搜索算法的有效性，其优化效果优于并行遗传算法和禁忌搜索算法。

关键词: 蚁群算法, 禁忌搜索, 混合算法, 模糊加工时间

Abstract: Due to the low efficiency of ant colony algorithms and easily plunged into local optimal, a hybrid ant colony algorithm for fuzzy Job Shop scheduling was proposed. In this method, the ant colony algorithm was served as a global search algorithm. According to the characteristics of Job Shop scheduling, a new TS algorithm based on the critical operation was presented, which was used as the local search algorithm in the hybrid ant colony algorithm. Because of the stronger local search ability of TS algorithm, this hybrid algorithm could improve the solutions′ quality. Experimental results verified the effectiveness of the proposed hybrid algorithm by comparing with TS algorithm and parallel genetic algorithms.

Key words: ant colony algorithm, taboo search, hybrid algorithm, fuzzy processing time

中图分类号:

TP278

宋晓宇，，朱云龙，尹朝万，李富明,. 应用混合蚁群算法求解模糊作业车间调度问题[J]. .

SONG Xiao-yu,, ZHU Yun-long，YIN Chao-wan，LI Fu-ming,. Hybrid ant colony algorithm for fuzzy Job Shop scheduling[J]. .

[1]	李国明,李军华. 带软时间窗随机需求车辆路径问题的算法研究[J]. 计算机集成制造系统, 2021, 27(8): 2270-2281.
[2]	杨艳华,姚立纲. 基于时间递推建模及交叉熵算法求解柔性作业车间调度问题[J]. 计算机集成制造系统, 2021, 27(6): 1703-1713.
[3]	张昊鹏,郭宇,汤鹏洲,黄少华,刘道元,李晗. 基于图像匹配的增强现实装配系统跟踪注册方法[J]. 计算机集成制造系统, 2021, 27(5): 1281-1291.
[4]	葛显龙,冉小芬. 基于时间窗指派的污染路径问题[J]. 计算机集成制造系统, 2021, 27(4): 1178-1187.
[5]	夏扬坤,邓永东,庞燕,王忠伟,高亮. 带客户分级和需求可拆分的生鲜车辆路径问题[J]. 计算机集成制造系统, 2021, 27(4): 1238-1248.
[6]	连裕翔,张超勇,孟磊磊,薛燕社,詹欣隆,吕畅. 基于改进Jaya算法的柔性作业车间调度问题[J]. 计算机集成制造系统, 2021, 27(11): 3172-3184.
[7]	王沙沙,张则强,刘俊琦,陈凤. 双向环形过道布置问题建模及混合鲸鱼算法求解[J]. 计算机集成制造系统, 2021, 27(10): 2908-2920.
[8]	徐兴,钱誉钦,赵芸,张云,陈小依,吕晓姝. 基于改进蚁群算法的立体仓库三维空间路径优化[J]. 计算机集成制造系统, 2021, 27(1): 207-214.
[9]	张玉茹,王晨旸. 引入变异算子的改进贪心和蚁群混合算法[J]. 计算机集成制造系统, 2020, 26(第3): 860-870.
[10]	张景玲,刘金龙,赵燕伟,王宏伟,冷龙龙,冯勤炳. 时间依赖型同时取送货VRP及超启发式算法[J]. 计算机集成制造系统, 2020, 26(7): 1905-1917.
[11]	庞燕,罗华丽,夏扬坤. 基于禁忌搜索算法的废弃家具回收车辆路径优化[J]. 计算机集成制造系统, 2020, 26(5期): 1425-1433.
[12]	吕畅,张超勇,张道德,任亚平,孟磊磊. 基于双层禁忌搜索算法的共享单车再平衡问题[J]. 计算机集成制造系统, 2020, 26(12): 3216-3228.
[13]	徐小斐,陈婧,饶运清,孟荣华,袁博,罗强. 迁移蚁群强化学习算法及其在矩形排样中的应用[J]. 计算机集成制造系统, 2020, 26(12): 3236-3247.
[14]	周翔,许茂增,吕奇光,李丹. 基于客户点行政地址的自提点选址—路径优化[J]. 计算机集成制造系统, 2019, 25(第8): 2069-2078.
[15]	白建龙,陈瀚宁,胡亚宝,何茂伟,梁晓丹,PARK Dongwon. 基于负反馈机制的蚁群算法及其在机器人路径规划中的应用[J]. 计算机集成制造系统, 2019, 25(第7): 1767-1774.