新混合鸟群算法求解零空闲流水车间调度问题

• 作者: 闫红超 汤伟 姚斌 程雪红
• 来源期刊: 微电子学与计算机
• 学科: 工学
• 关键词: 零空闲 种群初始化 局部搜索 鸟群算法 生产调度
• 年，卷（期）: 2023,（9）
• 所属期刊栏目: 计算机工程与应用
• 页码范围: 98-106
• 页数: 8页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.19304/J.ISSN1000-7180.2022.0125

摘要

针对零空闲流水车间调度问题(NFSP)，提出了一种新混合鸟群算法(NHBSA)以最小化最大完工时间.首先，对一种FRB(Farahmand-Ruiz-Boroojerdian)启发式算法进行了改进，在初始化阶段结合改进的FRB算法和混沌映射来改善种群的质量和多样性.其次，采用SPV(Smallest-Position-Value)规则在连续的位置和离散的工件排序之间进行转换，使算法适用于求解离散的调度问题.最后，借鉴变邻域搜索和迭代贪婪算法的思想针对种群最佳工件排序提出了一种局部搜索方法，以提升算法收敛的精度和跳出局部最优的能力.基于广泛使用的Taillard标准测试集进行了仿真测试，并与多种针对NFSP的元启发式算法相比较，结果显示，所提出的算法在保证良好稳定性的前提下，得到的平均百分比相对偏差(APRD)和性能提升百分比(PIP)较对比算法分别改善了71.017%和4.653%.