混合禁忌搜索的车间调度遗传算法研究

A hybrid taboo search genetic algorithm for shop floor scheduling

针对以最小化最大完工时间为目标的作业车间调度问题,提出一种混合禁忌搜索的遗传算法。禁忌搜索是一种能有效跳出局部最优解的元启发式算法,在每次迭代过程中通过搜索当前解的邻域来获得一个新解,通过评价新解的优越性来优化求解结果;加入多种交叉方式随机选择来扩大种群多样性;同时加入局部邻域搜索来改善解的质量,加快算法收敛速度。将提出的改进算法用于求解若干基准问题,算法具有一定的改良性,能优化求解结果。

A genetic algorithm with hybrid taboo search is proposed for a job shop scheduling problem to minimize the maximum completion time.Taboo search is a meta-heuristic algorithm that can effectively jump out of the local optimal solution,and obtains a new solution by searching the neighborhood of the current solution during each iteration,and optimizes the solution result by evaluating the superiority of the new solution.A variety of crossover methods are added for random selection to expand the population diversity.Meanwhile,local neighborhood search is added to improve the quality of the solution and speed up the convergence of the algorithm.The proposed improved algorithm is used to solve several benchmark problems,and the algorithm has some improvements to optimize the solution results.