Abstract: Based on the characteristics of Flexible Job Shop Scheduling Problem(FJSP),a hybrid algorithm combining Chemical Reaction Optimization Algorithm and Tabu Search (CROTS) was proposed.In this algorithm,an elitist selection scheme was used to reserve the better solutions.Besides,operation-based representation and machine-based representation were adopted to construct encoding form.To improve the global search performance of the algorithm,four operations were designed to ensure the diversity of population.Meanwhile,tabu search was added for enhancing the local search performance of the algorithm.The contrast experiments were conducted and the results showed the effectiveness of the proposed hybrid algorithm.

Key words: flexible job shop scheduling problem, chemical-reaction optimization, tabu search, elitist selection scheme, hybrid algorithm

摘要： 针对柔性作业车间调度问题自身的特点,提出一种将化学反应算法和禁忌搜索相结合的混合算法。该混合算法使用精英保留策略将较优个体保留到子代中,并采用基于工序和基于机器的编码方法。为提高化学反应,优化算法的全局搜索能力,设计了4种基本操作来保证种群的多样性。同时混合算法中引入禁忌搜索,使混合算法具有较好的局部搜索能力。最后,进行了算法性能对比试验,结果验证了该混合算法的有效性。

关键词: 柔性作业车间调度, 化学反应优化, 禁忌搜索, 精英保留策略, 混合算法