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

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

多项目资源管理有时需要采用一种资源专享-转移策略,该策略下可更新资源在多项目之间不共享,但在当前项目完工之后其资源可以转移至其它还未开始的项目。针对这一实际问题的理论研究非常有限。考虑活动工期的不确定性,从时差效用函数视角评价项目调度计划的鲁棒性,在考虑拖期成本-鲁棒性的多目标问题框架下,构建了一个资源专享-转移视角下的多项目资源分配(战术层)与鲁棒调度(运作层)双层决策优化模型。针对模型的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 criteria are adopted, which are error ratio, general distance, hypervolume and spacing. The experimental results show that the NSGA-II algorithm performs better for the small-scale instances, but the proposed ALNS algorithm is more advantageous regarding large-scale instances. In conclusion, the ALNS algorithm can efficiently solve our resource dedication-transferring problem with better solution stability. Besides, the influence of the uncertainty level of activity durations on the robustness of multi-project schedules is further explored.This research enriches the solution methods of the multi-project scheduling problem, and extends the application of the large neighborhood search algorithm. Especially, it provides a good reference for project management practitioners in terms of resource allocation and project scheduling.