Abstract: Focusing on the resource-constrained project scheduling problem under uncertainty environments, this paper studies a reactive scheduling method that addresses uncertain activity durations. Specifically, when the baseline project schedule is disrupted, the goal is to quickly generate a new optimal schedule. As the new schedule will inevitably deviate from the original baseline, leading to certain impacts and losses, the scheduling objective is set to minimize such deviations and associated losses. First, by introducing resource flows to represent resource constraints, a 0–1 mixed integer linear programming (MILP) model is formulated. Second, given the NP-hard nature of the problem, an iterative algorithm is designed to efficiently and accurately solve the model. This algorithm leverages Lagrangian relaxation, duality and decomposition techniques, and Benders decomposition, combined with the subgradient method, to reduce computational complexity and enhance tractability. Finally, numerical experiments are conducted to test the effectiveness of the proposed algorithm. The results verify that the method can produce more accurate solutions for medium- and even large-scale problem instances, demonstrating both practical feasibility and computational efficiency.

Key words: reactive resource-constrained project scheduling, 0-1 mixed integer linear programming (MILP), Langrange decomposition, Benders decomposition, subgradient

摘要： 针对不确定环境下的资源受限项目调度问题（RCPSP），研究工序工期不确定的反应性调度方法，重点研究项目基线计划中断时，如何快速生成新的最优计划。由于新计划将不可避免地偏离基线计划并对项目造成一定影响和损失，因此，以最小化影响与损失为调度目标。首先，通过引入资源流表示资源约束，构建0-1混合整数线性规划模型（MILP）；其次，针对该问题的NP-hard属性，结合Langrange松弛、对偶分解和Benders分解法，并运用次梯度法，对该模型进行优化以降低求解难度，设计出能够以较高的效率和精确度求解该问题的迭代算法。最后，通过数值实验测试该算法的有效性，结果表明该算法能有效求解中型甚至较大型规模问题案例，并获得更精确的解。

关键词: 反应性资源受限项目调度, 0-1混合线性规划, Langrange分解, Benders分解, 次梯度