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

摘要： 研究多次抢占式资源受限的项目调度问题，假设任意时间点可作为资源抢占节点且抢占次数不受限制，建立满足多次资源抢占的线性整数规划模型并提出改进遗传算法对其进行求解。为克服遗传算法（GA）局部搜索能力缺陷，在算法中引入禁忌搜索（TS）进一步优化子代。针对性地设计了允许多次抢占的基于工作优先级编码策略以及串行调度方案生成机制。通过测试算例集实验调试算法参数，并以标准算例集（Project Scheduling Problem Library，PSPLIB）对算法进行可行性检验。实验结果表明，资源受限项目调度问题中引入多次抢占机制能有效缩减项目工期，设计的算法对问题求解效果良好。

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