一种基于GA-SA-TS算法的车间调度方法的研究

运用现代优化算法来解决车间调度这类NP完全问题是现在普遍使用的方法。本文将模拟退火算法和禁忌搜索算法的思想与遗传算法相结合,改善了传统遗传算法中单一的交叉和变异机制,提出了模拟退火-交叉机制和禁忌搜索-变异机制,最终形成了一种适用于解决车间调度方面问题的GA-SA-TS混合遗传算法。三种算法取长补短,避免了遗传算法局部搜索能力差和易早熟的缺点。同时运用GA-SA-TS算法,针对实际车间调度问题进行了仿真。通过该仿真结果可以看出,GA-SA-TS混合遗传算法对于解决车间调度问题是可行的,且在解的质量方面有所提高。

Study on job-shop scheduling problem based on GA-SA-TS algorithm

It is one common method to solve the NP-Complete problem such as job-shop scheduling problem(JSSP) with modern optimization algorithm.In this paper,the separate cross and variation mechanism of the traditional genetic algorithm was improved by integrating the ideas of both simulated annealing and tabu Search,putting up with simulated annealing-cross mechanism and tabu search-variation mechanism and forming one new hybrid genetic algorithm called GA-SA-TS,which applies to JSSP.These three algorithms,compensating each other,avoid the genetic algorithm’s shortcomings of poor local search capability and precocious convergence.With this new hybrid genetic algorithm,one simulation on actual JSSP was carried out.And the results indicate that GA-SA-TS hybrid genetic algorithm is indeed feasible for solving the JSSP,and the quality is improved.