Abstract: The resource-constrained project scheduling problem is a classic combinatorial optimization problem with a wide range of engineering applications. Since the 1960s, many optimization algorithms have been used to solve this problem, but most intelligent optimization algorithms do not perform well in the whole problem space. Aiming at this challenge, a two-stage evolutionary imperialist competitive algorithm (TSE-ICA) is proposed. Firstly, based on the block extraction strategy obtained by the critical-path method, two assimilation operators are presented for diversification and convergence, respectively. The two-stage evolution framework of TSE-ICA is constructed by selecting appropriate assimilation operators in different stages. Then, the block-based improved revolution mechanism includes two neighborhood search strategies of insertion and out-of-order, and the empire competition mechanism  realizes the adaptive adjustment of parameters for each empire by collecting the convergence information of them. Lastly, the memory is used to guide the evolution of the population and improve the convergence rate. The design of experiment technique of Taguchi method is applied to determining the optimal parameter setting for TSE-ICA. In the following numerical experiment, the TSE-ICA is implemented and tested by 3 instance sets (J30, J60 and J120) from the standard instance library of PSPLIB. Moreover, the empirical statistical data of TSE-ICA are compared with 17 advanced state-of-the-art algorithms based on two evaluation criteria. Experimental results show that the TSE-ICA has well optimization performance and convergence efficiency, which proves the effectiveness of the proposed improved mechanism and the problem applicability of the TSE-ICA preliminarily.

Key words: resource-constrained project scheduling problem, imperialist competitive algorithm, two-stage evolution framework, assimilation;critical-path method, Taguchi method, block, memory

摘要： 资源约束项目调度问题是一类经典的组合优化难题，有着广泛的工程应用背景。自20世纪60年代起，该问题的优化方法层出不穷，但大多数智能优化算法在该问题空间中搜索表现一般。针对这一挑战，提出了一种二阶段演化帝国竞争算法（TSE-ICA）。首先，基于由关键路径法得到的组块提取策略，提出两种分别用于种群多样性开发和高效收敛的同化算子，通过在不同阶段选择合适的同化算子实现二阶段演化框架的构建。其次，基于组块的改进革命机制包含插入和乱序两种邻域搜索策略，帝国竞争机制则通过收集不同帝国的收敛信息实现参数的自适应调整；最后，利用记忆库引导种群进化，提高算法的收敛速率。TSE-ICA的最佳参数设置由Taguchi法的实验设计方法确定。数值实验面向典型实例库PSPLIB中的3个实例集J30、J60和J120对TSE-ICA执行了性能测试，并基于两种评价标准与17种先进的元启发式算法进行性能对比。实验结果显示，TSE-ICA具有较好的优化性能和收敛效率，初步验证了所提改进机制的有效性和所提算法的问题适用性。

关键词: 资源约束项目调度问题, 帝国竞争算法, 二阶段演化框架, 同化, 关键路径法, Taguchi法, 组块, 记忆库