蚁群优化结合变邻域搜索求解NWFS调度问题

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (16): 216-219.

蚁群优化结合变邻域搜索求解NWFS调度问题

屈国强1，2，周永良1

1.北京科技大学经济管理学院，北京 100083
2.河南理工大学经济管理学院，河南焦作 454000

出版日期:2012-06-01 发布日期:2012-06-01

Ant colony optimization and variable neighborhood search for no-wait flow shop scheduling problem

QU Guoqiang1，2, ZHOU Yongliang1

1.School of Economics and Management, University of Science and Technology Beijing, Beijing 100083, China
2.School of Economics and Management, Henan Polytechnic University, Jiaozuo, Henan 454000, China

Online:2012-06-01 Published:2012-06-01

摘要/Abstract

摘要： 针对NP-难的最小化时间表长为目标的无等待流水车间调度问题，将此问题转化为旅行商问题。采用蚁群优化求得初始工件排序。在提出的一种新的邻域结构基础上，迭代进行集中和分散的变邻域搜索以改善解。用Rec系列及hel1和hel2共计23个Benchmark算例进行计算验证，并与RAJ算法进行了比较。结果表明所提出的方法是有效的。

关键词: 流水车间, 无等待, 时间表长, 蚁群优化, 变邻域搜索

Abstract: To solve NP-hard no-wait flow shop scheduling problem with the makespan minimization criterion, this question is first turned into a Traveling Salesman Problem（TSP）. Then Ant Colony Optimization（ACO） is used to construct an initial job sequence. Based on a new proposed neighborhood, intensification and diversification variable neighborhood search is interchangeably evolved to improve solution. The performance of the algorithm is tested on Rec, hel1 and hel2 Benchmark problems. The results are compared to the well-known RAJ heuristic. The computational results indicate the effectiveness of the proposed approach.

Key words: flowshop, no-wait, makespan, ant colony optimization, variable neighborhood search

屈国强1，2，周永良1. 蚁群优化结合变邻域搜索求解NWFS调度问题[J]. 计算机工程与应用, 2012, 48(16): 216-219.

QU Guoqiang1，2, ZHOU Yongliang1. Ant colony optimization and variable neighborhood search for no-wait flow shop scheduling problem[J]. Computer Engineering and Applications, 2012, 48(16): 216-219.

[1]	张铭，邓文瀚，林娟，钟一文. 改进蚁群优化算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(13): 85-95.
[2]	张海南，游晓明，刘升，刘中强. 交互式学习的布谷鸟搜索算法[J]. 计算机工程与应用, 2020, 56(7): 147-154.
[3]	秦琴，梁承姬. 自动化码头考虑缓冲区的设备协调调度优化[J]. 计算机工程与应用, 2020, 56(6): 262-270.
[4]	吴树景，游有鹏，罗福源. 变邻域保优遗传算法求解柔性车间调度问题[J]. 计算机工程与应用, 2020, 56(22): 236-243.
[5]	罗函明，罗天洪，吴晓东，陈科百. 求解混合流水车间调度问题的离散布谷鸟算法[J]. 计算机工程与应用, 2020, 56(22): 264-271.
[6]	蔡延光，陈厚仁，戚远航. 变邻域量子烟花算法求解CVRP[J]. 计算机工程与应用, 2019, 55(9): 230-236.
[7]	尹建津1，张贝克1，高东1，许欣2. 改进蝙蝠算法解决FFSP问题及其应用研究[J]. 计算机工程与应用, 2019, 55(9): 243-247.
[8]	薛文艳，赵江，郝崇清，刘慧贤. 基于信息素负反馈的超启发式蚁群优化算法[J]. 计算机工程与应用, 2019, 55(4): 163-172.
[9]	姜道银1，2，葛洪伟1，2. 基于信息交流策略的连续域蚁群优化算法[J]. 计算机工程与应用, 2019, 55(11): 153-159.
[10]	姜道银1，2，葛洪伟1，2，袁罗1. 一种动态划分的混合连续域蚁群优化算法[J]. 计算机工程与应用, 2018, 54(7): 144-151.
[11]	段少楠，戴胜华. 离散萤火虫算法在高速列车运行调整中的应用[J]. 计算机工程与应用, 2018, 54(15): 209-213.
[12]	孔林1，张国富1，2，苏兆品1，2，蒋建国1，2. 基于改进蚁群算法的救护车应急救援路径规划[J]. 计算机工程与应用, 2018, 54(13): 153-159.
[13]	张文鹏，王兴. 改进型蝙蝠算法在作业车间调度问题中的应用[J]. 计算机工程与应用, 2017, 53(8): 137-140.
[14]	周袅1，2，葛洪伟1，2，苏树智1. 基于信息素的自适应连续域混合蚁群算法[J]. 计算机工程与应用, 2017, 53(6): 156-161.
[15]	孙良旭1，曲殿利2，刘国莉3. 置换流水车间调度问题的两阶段分布估计算法[J]. 计算机工程与应用, 2017, 53(2): 64-71.