改进麻雀搜索算法求解作业车间调度问题

针对最小化完工时间的作业车间调度问题(JSP),提出改进麻雀搜索算法(ISSA).首先设计有效的编码转换方式,形成JSP离散决策空间与麻雀搜索算法(SSA)连续搜索空间的对应关系.然后,针对SSA在求解后期易陷入局部最优,利用量子计算、正余弦搜索和警戒者数量递减策略对SSA进行改进,同时引入多邻域搜索和高斯扰动策略以弥补SSA在求解离散问题时深度发掘能力不足的弊端.最后,进行FT、LA系列10个测试问题、6种算法和2个应用实例的对比实验.结果表明,ISSA在求解JSP时,能获得更好的最小值、平均值和寻优成功率,验证了ISSA求解JSP的有效性.

Improved sparrow search algorithm for solving Job-Shop scheduling problem

This paper proposed an improved sparrow search algorithm(ISSA) to minimize makespan of Job-Shop scheduling problem(JSP). Firstly, it formed the corresponding relationship between the discrete decision space of JSP and the continuous search space of sparrow search algorithm(SSA) by designing an effective code conversion mode. Then, since the SSA is easy to fall into local optimum, this paper improved SSA based on the idea of quantum computation, sine cosine search and decreasing vigilance strategy. Meanwhile, to make up for the lack of depth mining ability of SSA in solving discrete problems, it introduced multi-neighbor search and Gaussian disturbance strategy. Finally, this paper provided comparative experiments of 10 test questions of FT and LA series, 6 algorithms and 2 application examples. The results show that ISSA can obtain better minimum value, average value and optimization success rate when solving JSP, which verifies the effectiveness of ISSA in solving JSP.