基于动态资源权重的多技能项目调度启发式算法  

Dynamic resource priority-based heuristics for multi-skill resource constrained project scheduling problem

作　　者：胡振涛 崔南方[1] 张艳[1] 胡雪君 HU Zhen-tao;CUI Nan-fang;ZHANG Yan;HU Xue-jun(School of Management,Huazhong University of Science and Technology,Wuhan 430074,China;Business School,Hunan University,Changsha 410082,China)

机构地区：[1]华中科技大学管理学院,武汉430074 [2]湖南大学工商管理学院,长沙410082

出　　处：《控制与决策》2021年第10期2553-2561,共9页Control and Decision

基　　金：国家自然科学基金项目(71971094);国家自然科学基金项目(71701067);湖南省自然科学基金项目(2019JJ50039)。

摘　　要：多技能资源受限项目调度问题中,一个资源可同时具备多项技能,相较于传统的单技能项目调度,其资源分配对调度计划的工期影响程度更大,因此在对多技能项目进行排程时更加重视资源的分配.基于此,从资源视角提出一种启发式算法求解工期最短的调度计划.算法以并行调度为主体,并设计一种动态资源权重计算方法,在每一决策点,首先采用二分图最大匹配法确定当前可排活动集,而后将动态资源权重值作为调度过程中资源分配的依据,其核心思想是将资源灵活度高、对后续活动影响大的资源留置,以待下一决策点调用.最后,为验证算法有效性,对不同参数设置下的算例进行实验,结果表明,相较于随机资源分配算法和静态资源权重算法,新算法具有明显优势.The resources in the multi-skilled project scheduling problem(MSPSP) are assumed to be multi-skilled.Compared with the single-skilled project scheduling problem, the resource allocation has more influence on the makespan in the MSPSP. Therefore, more attention should be paid to resource allocation when scheduling a multi-skilled project.In this paper, we propose a heuristic algorithm to solve the MSPSP from the perspective of resource allocation. The algorithm uses a maximum matching method of bipartite graphs to select schedulable activities and develops a dynamic resource priority to allocate resources based on the parallel scheduling scheme. The core idea of the algorithm is to retain resources which are more flexible or more important to the subsequent activities for the next decision time. In order to verify the effectiveness of the proposed heuristics, a series of computational tests are conducted. The results show that the proposed algorithm has a significant advantage over the algorithms based on random or static resource priority.

关 键 词：项目调度 多技能资源 并行调度 二分图 资源权重 启发式算法 

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