关键词: 多次抢占, 资源约束项目调度, 时间窗延迟, 启发式算法

Abstract: With the development of economy, the projects of enterprises are generally large, diversified and complicated. And there are many uncertainties accompanying the project execution process. In many actual projects, the execution of activities is often interrupted due to uncertainties. Activity interruption can change the state of resources, execution duration of the activity and the logical relationship between activities, and how to schedule the project after activity interruption has become a new topic, gradually forming a preemptive resource constrained project scheduling problem, namely PRCPSP.
However, most of the existing studies on PRCPSP are based on the assumption that the number of preemptions is one or more at fixed nodes, which is not entirely consistent with the realistic background. With the changing complexity of the environment, the execution of projects is becoming increasingly complex, especially for large and emergency projects, where there are more uncertain factors. Random multiple preemptions have become an effective way to alleviate resource conflicts and shorten project time. In this context, studying project scheduling with random preemption has become particularly important. Therefore, based on the existing research, this paper studies the stochastic preemptive project scheduling problem in uncertain environments, constructs a model of preemptive resource-constrained project scheduling problem in which any activity is allowed to be interrupted at any time node, and designs a heuristic algorithm with time window delay scheme, which provides a new approach to solving stochastic preemption problem.
In the algorithm, the transformation rule of active network graph is first introduced, and then, based on the depth-first and breadth-first solution strategies, a scheduling generation scheme based on time-window delay scheme is produced. By invoking the PSPLIB (Project scheduling problem library) datasets, setting different parameters, and designing several groups of computational experiments. The computational results show that, compared with the non-preemption problem, the algorithm performs better in solving the project scheduling problems with preemption, especially for large-scale projects, which verifies the effectiveness of the algorithm. Moreover, when other parameters are constant, with the increase of project network complexity (NC), resource constraint degree (RC), and resource coefficient (RF), and compared to non-preemptive resource-constrained project scheduling problem, this algorithm obtains better project duration in finite time. At the same time, compared with the basic exact algorithm, this algorithm is more efficient. The solutions can provide support for the decisions of actual project scheduling.
However, in this study, it is assumed that execution after activity interruption does not consume costs and additional resources. However, considering the complexity of the actual project, how to consider the cost and resource consumption 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 heuristic algorithm designed in this paper into the meta heuristic algorithm and design efficient algorithms suitable for more complex problems.

Key words: multiple preemption, resource-constrained project scheduling, time-window delay, heuristic algorithm