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

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