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

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