摘要
为了减少算法求解作业车间调度问题(Job Shop Scheduling Problem,JSP)时的无效重复搜索,以提高算法性能,提出一种邻域单次搜索人工蜂群算法(Single Neighborhood Search Artificial Bee Colony Algorithm,SNSABC).在工序加工优先级的编码方式上结合JSP本身的特性设计邻域搜索策略,该策略采用了交换算子和路径重连算子配合搜索的方式.每次交换算子选择未被搜索过的位置搜索,在交换过程中跳过不能改变最大完工时间和已经做过的工序交换.若没有搜索到更优解,将搜索的位置标为已搜索.若搜索到更优解,将更优解进行路径重连.根据邻域搜索策略改进侦查蜂阶段,淘汰所有关键工序位置搜索完毕的解,用淘汰的解和种群中剩余的解分别交叉寻找更优解.在人工蜂群算法中加入所提策略,算法搜索效率和求解质量得到明显提升,能够快速搜索到可接受解,在大部分算例可以收敛到已知最优解.相比于对比算法,邻域单次搜索人工蜂群算法求得的最优解和均值具有更短的完工时间.实验结果表明所提策略有效提高了算法的性能.
基金项目
国家自然科学基金(62206313)
国家自然科学基金(12161043)
国家自然科学基金(61703183)
国家自然科学基金(61573157)
浙江省公益技术应用研究计划(LGG19F030010)
NETL
NSTL
万方数据