关键词: 资源受限, 项目调度, 多次抢占, 遗传算法, 禁忌搜索, 参数调试

Abstract: A multiple preemptive resource constrained project scheduling problem is investigated where preemptive point can be any time and the number of preemptions are unlimited, the linear integer programming model is formulated for the multiple preemptive situation. An improved genetic algorithm（Genetic-Tabu Search Algorithm, GTSA） is proposed to solve the model. To overcome the weakness of Genetic Algorithm（GA） in local search, Tabu Search（TS） algorithm is used to avoid local optima trap. The encoding strategy based on activity priority and serial scheduling generation mechanism are designed to allow multiple preemption in the GTSA. Through the experiments on a test case set, the parameters of GTSA are tuned. The algorithm is verified by experiments on Project Scheduling Problem Library（PSPLIB）. The experimental results indicate that the multiple preemption strategy in RCPSP has significantly reduced the makespan, and the GTSA is able to achieve satisfactory solutions.

Key words: resource constrained, project scheduling, multiple preemption, genetic algorithm, tabu search, tuning parameter