一种求解Job-shop调度问题的遗传局部搜索算法

利用遗传局部搜索算法求解了作业车间调度问题，遗传算法中的染色体编码采用基于工序的编码，并用插入式贪婪解码机制将染色体解码至主动调度。为了克服传统遗传算法易于早熟收敛的缺点，设计了一种改进的优先操作交叉IPOX操作和子代产生模式的遗传算法。对于遗传算法每个染色体个体，使用基于N6邻域结构的局部搜索进一步使它们得到改善。利用所提出的混合遗传算法求解基准问题，验证了算法的有效性。

A Genetic Local Search Algorithm for Solving Job-shop Scheduling Problems

This paper presented a genetic local search algorithm for job-shop scheduling problem.The chromosome representation of the problem was based on the operation-based representation.In order to reduce the search space,schedules
were constructed using a procedure that generated active schedules.After a schedule was obtained,a local search heuristic based on N6 neighborhood structure was applied to improve the solution.In order to avoid premature convergence of the conventional GA,an improved precedence operation crossover(IPOX) and approach of the generation alteration model were proposed for the GA.The approach was tested on a set of standard instances taken from the literature.The computation results validate the effectiveness of the proposed algorithm.