一类解决Job Shop问题的禁忌搜索算法

针对Job shop问题，设计了一种改进的禁忌搜索算法（MTS算法）。MTS算法从多个初始解开始，将传统禁忌搜索算法由串行搜索结构变为并行搜索结构；采用互换和交叉两种邻域搜索函数，既有利于新邻域的探索又有利于交换信息；基于目标值的禁忌表保证了群体的多样性。实验表明，MTS算法克服了传统禁忌搜索算法的缺陷，具有较高的求解质量和鲁棒性。

A Modified Tabu Search Algorithm for Job Shop Scheduling

As a class of the hardest combinatorial optimization problems, job shop scheduling problem has been a major target for many researchers, for which an enhanced tabu search algorithm was proposed. The algorithm started from a group of initial solutions and the classic serial structure was replaced by parallel structure, so the robustness of the algorithm was improved. Pairwise interchange and crossover operation were adopted in the neighborhood structure, which enhanced both the global exploitation and local exploration. Tabu list that the characteristis were makespan ensured the diversity of the solutions. Simulation results demonstrate the effectiveness of the proposed procedure, whose optimization performance is superior to the algorithm reported in the literatures.