求解批量流水线调度问题的蜂群算法

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (21): 35-38.

求解批量流水线调度问题的蜂群算法

桑红燕1，2，潘全科2，任立群3

1.聊城大学数学科学学院，山东聊城 252059
2.聊城大学计算机学院，山东聊城 252059
3.聊城市人民医院，山东聊城 252000

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-07-21 发布日期:2011-07-21

Artificial bee colony algorithm for lot-streaming flow shop scheduling problem

SANG Hongyan1，2，PAN Quanke2，REN Liqun3

1.School of Mathematics Science，Liaocheng University，Liaocheng，Shandong 252059，China
2.School of Computer Science，Liaocheng University，Liaocheng，Shandong 252059，China
3.Liaocheng Hospital，Liaocheng，Shandong 252000，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-07-21 Published:2011-07-21

摘要/Abstract

摘要： 针对批量流水线调度问题，提出了一种改进的人工蜂群算法来优化最大完成时间。该算法运用NEH方法产生初始解，采用混沌遍历的方法生成新的邻域解。为了跳出局部最优，使用最优解的插入扰动来替换一些连续若干步不能改进的解来提高算法的全局搜索能力。采用自适应的局部搜索加强算法的局部搜索能力。仿真试验表明了所得算法的可行性和高效性。

关键词: 批量流水线调度, 最大完成时间, 人工蜂群算法, 微粒群优化, 局部搜索

Abstract: An Improved Artificial Bee Colony（IABC） algorithm is presented for solving the Lot-streaming Flow Shop Scheduling Problem（LFSP） with the objective of minimizing the maximum completion time，i.e.，makespan.In the proposed IABC algorithm，the famous NEH heuristic is used to produce an initial solution，and the chaos is employed to generate a new candidate.In order to avoid trapping into local optima，the solution not improved in a number of generations in the population is replaced by the perturbation of the best solution found so far.In addition，a self-adaptive local search is presented and imbedded in the IABC algorithm to balance the exploitation and exploration.The computational results show that the IABC algorithm is effective and efficient for the LFSP．

Key words: lot-streaming flow shop scheduling, maximum completion time, artificial bee colony algorithm, particle swarm optimization, local search

桑红燕1，2，潘全科2，任立群3. 求解批量流水线调度问题的蜂群算法[J]. 计算机工程与应用, 2011, 47(21): 35-38.

SANG Hongyan1，2，PAN Quanke2，REN Liqun3. Artificial bee colony algorithm for lot-streaming flow shop scheduling problem[J]. Computer Engineering and Applications, 2011, 47(21): 35-38.

[1]	徐辰华，骆珠光，吴冠宏，刘斌. 基于正弦因子和量子局部搜索的灰狼优化算法[J]. 计算机工程与应用, 2021, 57(24): 83-89.
[2]	郝翔，贺毅朝，朱晓斌，翟庆雷. 基于离散混合多宇宙算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(18): 103-113.
[3]	李雨鑫，李悦悦. 面向JIT采购的多目标车辆调度[J]. 计算机工程与应用, 2021, 57(12): 263-272.
[4]	李顺东，游晓明，刘升. 结合ABC算法动态分级的双蚁态蚁群算法[J]. 计算机工程与应用, 2020, 56(12): 37-46.
[5]	闫苗苗，刘三阳. 多班级交互式教学优化算法[J]. 计算机工程与应用, 2019, 55(9): 10-16.
[6]	宋晓宇，高明海，赵明. 具有自适应搜索策略的混合人工蜂群算法[J]. 计算机工程与应用, 2019, 55(22): 53-59.
[7]	浦玉学，舒鹏飞，蒋祺，陈卫中. 工业机器人时间-能量最优轨迹规划[J]. 计算机工程与应用, 2019, 55(22): 86-90.
[8]	王贞，李旭飞. 求解约束优化问题的自适应人工蜂群算法[J]. 计算机工程与应用, 2019, 55(15): 47-58.
[9]	张维存，张曼. 面向连续生产的供应链联合调度及算法[J]. 计算机工程与应用, 2019, 55(13): 246-253.
[10]	张戈，王建林. 基于混合ABC和CRO的高维特征选择方法[J]. 计算机工程与应用, 2019, 55(11): 93-101.
[11]	魏锋涛，岳明娟，郑建明. 基于多策略融合的改进人工蜂群算法[J]. 计算机工程与应用, 2018, 54(5): 111-116.
[12]	刘春苗，张惠珍. 求解无容量设施选址问题的混合蝙蝠算法[J]. 计算机工程与应用, 2018, 54(22): 28-34.
[13]	刘明辉1，李炜2. 基于knee points的改进多目标人工蜂群算法[J]. 计算机工程与应用, 2018, 54(2): 40-47.
[14]	董小帅1，2，3，毛政元1，2，3. 基于改进遗传算法的动态路径规划研究[J]. 计算机工程与应用, 2018, 54(19): 49-55.
[15]	黄亚飞，王国富，张法全，叶金才. 基于蜂群算法和带参阈值函数的图像去噪方法[J]. 计算机工程与应用, 2018, 54(17): 164-168.