求解作业车间调度问题的混合帝国主义竞争算法

针对最小化最大完工时间的作业车间调度问题（JSP），提出一种结合帝国主义竞争算法（ICA）和禁忌搜索（TS）算法的混合算法。混合算法以帝国主义竞争算法为基础，在同化操作中融入遗传算法中的杂交算子和变异算子，使算法全局搜索能力更强。为了克服帝国主义竞争算法局部搜索能力弱的缺点，引入禁忌搜索算法进一步优化同化操作后的后代。禁忌搜索算法采用混合邻域结构和新型选择策略，使得算法能够更有效地搜索邻域解。混合算法兼具全局搜索能力和局部搜索能力，通过对13个经典的Benchmark调度问题进行仿真测试，并与近年4种新型混合算法进行对比分析，实验结果表明了所提算法求解Job Shop调度问题的有效性和稳定性。

Hybrid imperialist competitive algorithm for solving job-shop scheduling problem

For the Job-shop Scheduling Problem (JSP) with the objective of minimizing the makespan, a hybrid algorithm combining with Imperialist Competitive Algorithm (ICA) and Tabu Search (TS) was proposed. Based on imperialist competitive algorithm, crossover operator and mutation operator of Genetic Algorithm (GA) were applied in the hybrid algorithm as assimilation to strengthen its global search ability. To overcome the weakness of imperialist competitive algorithm in local search, TS algorithm was used to improve the offspring of assimilation. The hybrid neighborhood structure and a novel selection strategy were used by TS to make the search more efficient. By combining with the ability of global search and local search, testing on the 13 classic benchmark scheduling problems and comparing with other four hybrid algorithms in recent years, the experimental results show that the proposed hybrid algorithm is effective and stable.