Abstract: With the scale, complexity and randomization brought by various uncertainties in modern projects, as an important means of optimizing the allocation of project resources, project scheduling becomes increasingly important and challenging. In many actual projects, the execution of activity often presents multi-mode characteristics(different combinations of activity duration and resources), thus forming the Multi-mode Resource Constrained Project Scheduling Problem(MRCPSP). MRCPSP is a generalized version of the RCPSP, where each activity can be performed in one out of a set of modes. The objective of MRCPSP is to find a mode and a start time for each activity so that the makespan is minimized and the schedule is feasible with respect to the precedence and renewable and nonrenewable resource constraints.
However, during the execution of the project, activity is often interrupted due to uncertainties, which changes the state of resources, execution duration and so on, how to schedule the project after activity interruption becomes a new problem. So, in this paper, the multi-mode resource-constrained project scheduling problem allowing for activity preemption is studied, which is the Preemptive Multi-mode Resource Constrained Project Scheduling Problem(P-MRCPSP). The problem brings more flexibility to the project scheduling while increasing the difficulty of scheduling. In order to optimize the project duration and fully consider the relationship between resources and active duration, a three-stage scheduling algorithm for mode-improvement based on renewable resources is designed, namely, mode preprocessing stage, activity interruption transformation stage and mode-improvement scheduling stage, so that the execution mode can be dynamically adjusted according to the optimization objective of the minimum duration during the execution of the project. By calling the Project Scheduling Problem Library(PSPLIB)for experimental design, the algorithm scheduling results under different algorithms and parameters are compared and analyzed.
The computational results show that the proposed algorithm is relatively superior and provides scientific decision-making guidance for the project management practice, especially for a large-scale project. By comparing the effects of different resource parameters on scheduling results(including renewable and nonrenewable resources), the results show that the changes in renewable resource parameters RSR and RFR have a significant impact on scheduling results. And when the resource supply is sufficient or the resource demand is small, scheduling results outperform the existing algorithms in literature.
However, with the expansion of the project scale, the project uncertainty also increases. How to take various uncertainties into account in P-MRCPSP, such as the uncertainty of the activity duration and resources, are worthy of further study. And, in this study, we just assume that execution after activity interruption does not consume additional costs and resources, and switching execution modes is not allowed. However, considering the complexity of the actual project, how to consider the cost consumption, resource consumption and mode-switch of re-execution after activity interruption in stochastic preemptive project scheduling is worthy of further study. At the same time, it is worth further exploring how to effectively embed the dynamic heuristic algorithm designed in this paper into more meta-heuristic algorithms for more complex problems.

Key words: activity preemption, multi-mode, project scheduling, mode-improvement, three-stage dynamic scheduling

摘要： 随着现代项目的规模化、复杂化以及各种不确定性带来的随机化,项目调度作为项目资源配置优化的重要手段愈发重要且更具挑战。在传统资源约束项目调度问题上所衍生出的抢占型多模式调度问题给项目调度带来更多灵活性的同时增加了调度的难度。对此,本文研究允许活动抢占的多模式资源约束项目调度问题,考虑活动执行“工期—资源”的多种组合形式,建立调度模型。为优化项目工期目标,充分考虑可更新资源与活动工期之间的关系,设计了一种基于可更新资源的模式优化三阶段调度算法,即模式预处理阶段、活动中断转化阶段、模式优化调度阶段,使项目在执行过程中,可以根据优化目标动态调整执行模式。通过调用PSPLIB数据库进行大规模实验设计,对比分析不同算法和参数下的算法性能。实验表明,本文所设计的算法具有相对较好的求解效果,为项目管理实践提供科学决策指导。

关键词: 活动抢占, 多模式, 项目调度, 模式优化, 三阶段动态调度