Abstract: In this paper, we investigate the resource-constrained project scheduling problem(RCPSP) with resource transfer times. In order to effectively obtain the optimal solution of the problem, a resource flow-based solution representation is adopted. Accordingly, a resource flow optimization model for the RCPSP with transfer time is proposed with the objective of minimizing the project makespan. An improved neighborhood operator for rerouting resource flows is designed, which adapts to the characteristics of the problem. For solving the model, an improved tabu search algorithm and a greedy randomized adaptive search procedurewith tabu search are developed, respectively. The experimental results show that, compared with the algorithm in the literature, the proposed two algorithms can obtain optimal solutions for a larger number of project instances and consume less computation time. In addition, we analyze the performance of the algorithms in solving project instances with different characteristics, and the results provide guidance for project managers to evaluate the applicability of the algorithms based on the project characteristics.

Key words: RCPSP, resource transfer time, resource flow, tabu search algorithm

摘要： 本文在传统资源受限项目调度问题(resource-constrained project scheduling problem, RCPSP)中引入资源转移时间,为有效获得问题的最优解,采用资源流编码方式表示可行解,建立了带有资源转移时间的RCPSP资源流优化模型,目标为最小化项目工期。根据问题特征设计了改进的资源流重构邻域算子,分别设计了改进的禁忌搜索算法和贪心随机自适应禁忌搜索算法求解模型。数据实验结果表明,相较于现有文献中的方法,所提两种算法均可针对更多的项目实例求得最优解,并且得到最优解的时间更短,求解效率更高。此外,分析了算法在求解具有不同特征的项目实例时的性能,所得结果为项目经理结合项目特征评价算法适用性提供了指导。

关键词: 资源受限项目调度问题, 资源转移时间, 资源流, 禁忌搜索算法