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

摘要： 实际项目进程中因不确定因素导致活动执行被迫中断的情况时有发生,该研究针对允许活动在任意单位时间节点被中断的抢占型资源约束项目调度问题,设计了一种启发式算法。算法首先通过网络图的转化规则将活动进行拆分,然后结合深度优先和广度优先搜索设计了一类基于时间窗延迟方案的调度生成机制。通过调用PSPLIB数据库,设置不同参数,设计多组实验进行分析,结果表明,相较于非抢占模式,该算法在求解允许抢占模式的项目调度问题时表现出更优的结果,尤其对于大规模项目,验证了算法的有效性。同时与基本精确算法对比,该算法表现出更好求解速率,该求解结果为实际项目调度提供了决策参考。

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