基于自适应大邻域搜索的鲁棒多项目调度方法  

An Adaptive Large Neighborhood Search Metaheuristic for Robust Multi-project Scheduling

作　　者：胡雪君 赵雁[2] 单汩源[1] 王建江[3] 别黎[4] HU Xue-jun;ZHAO Yan;SHAN Mi-yuan;WANG Jian-jiang;BIE Li(Business School,Hunan University,Changsha 410082,China;School of Business Administration,Zhongnan University of Economics and Law,Wuhan 430073,China;College of Systems Engineering,National University of Defense Technology,Changsha 410073,China;School of Management,South-Central University for Nationalities,Wuhan 430074,China)

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

出　　处：《中国管理科学》2022年第9期217-231,共15页Chinese Journal of Management Science

基　　金：国家自然科学基金资助项目(72071075,71701067,71801218,71971094);湖南省自然科学基金资助项目(2019JJ50039,2020JJ4672);国防科技大学科研计划项目(ZK18-03-16)。

摘　　要：多项目资源管理有时需要采用一种资源专享-转移策略,该策略下可更新资源在多项目之间不共享,但在当前项目完工之后其资源可以转移至其它还未开始的项目。针对这一实际问题的理论研究非常有限。考虑活动工期的不确定性,从时差效用函数视角评价项目调度计划的鲁棒性,在考虑拖期成本-鲁棒性的多目标问题框架下,构建了一个资源专享-转移视角下的多项目资源分配(战术层)与鲁棒调度(运作层)双层决策优化模型。针对模型的NP-hard性质和多目标组合优化特征,设计了一种新的自适应大邻域搜索(adaptive large neighborhood search, ALNS)算法求解模型。该算法采用“项目-缓冲-资源-活动”列表的混合编码表示问题可行解,提出基于四类列表的destroy-repair邻域结构,设计一种超体积指标进行自适应搜索以提高算法性能。最后,为了验证ALNS算法的适用性和有效性,设计一种NSGA-II算法作为比较基准,通过大规模仿真实验对算法性能进行了对比分析,并探索工期不确定水平对多项目调度方案鲁棒性的影响。In multi-project management, it is critical to allocate limited resources among different projects and within each project, because it affects the resource utilization and the implementation of project plans. According to the execution environment of multiple projects or the characteristics of resources, there are two approaches to the management of renewable resources: resource sharing and resource dedication. The resource sharing policy has been studied a lot, but the research on the resource dedication problem is very limited. In this paper, a novel resource dedication-transferring policy for managing resources is proposed, in which renewable resources are dedicated to each individual project during execution but can be transferred to another one starting after the finish of the corresponding project.Considering the uncertainties of activity durations, a free-slack based utility function is designed to evaluate the solution robustness of a multi-project schedule. A two-level multi-objective optimization model is then constructed that both maximizes the robustness and minimizes the total weighted tardiness cost. The model optimizes both multi-project resource allocation at the tactical level and project scheduling at the operational level. Due to the NP-hardness and the multi-objective combinatorial optimization characteristics of the problem, an adaptive large neighborhood search algorithm(ALNS) is developed. The ALNS employs a hybrid coding scheme of “project-buffer-resource-activity” list to represent feasible solutions, proposes new destroy-repair neighborhood operators based on the four types of lists, and suggests a hypervolume-based adaptive search strategy to improve the algorithm performance. In addition, a customized NSGA-II algorithm with novel crossover and mutation operators is suggested for comparison.In order to evaluate the performance of the proposed algorithms, five sets of project instances are produced by a common project network generator—RanGen. Four types of performance evaluation c

关 键 词：多项目管理 资源专享 鲁棒性 时差效用函数 多目标优化 自适应大邻域搜索 

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