带有资源转移时间的RCPSP资源流模型及算法  

Resource Flow-based Model and Algorithms for theRCPSP with Resource Transfer Times

作　　者：胡雪君 王建江[2] 谭跃进[2] 徐培德[2] 崔南方[3] HU Xue-jun;WANG Jian-jiang;TAN Yue-jin;Xu Pei-de;CUI Nan-fang(Business School,Hunan University,Changsha 410082,China;College of Systems Engineering,National University of Defense Technology,Changsha 410073,China;School of Management,Huazhong University of Science and Technology,Wuhan 430074,China)

机构地区：[1]湖南大学工商管理学院,湖南长沙410082 [2]国防科技大学系统工程学院,湖南长沙410073 [3]华中科技大学管理学院,湖北武汉430074

出　　处：《运筹与管理》2021年第12期42-50,共9页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(71701067,71801218,71971094);湖南省自然科学基金资助项目(2019JJ50039,2020JJ4672);装备军内科研项目(GK2019A010193)。

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

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

分 类 号：F224.3[经济管理—国民经济]