Improved Pulse Discrete Time Model for Resource-Constrained Project Scheduling Problem

To address the resource-constrained project scheduling problem (RCPSP), the pulse discrete time (PDT) model is commonly used and then solved by integer programming optimization. This method can obtain the exact optimal solution, but it encounters difficulties with low computational efficiency when the RCPSP has a large size and high complexity. This study hypothesizes that a reasonably reduced scheduling horizon, derived from a feasible heuristic solution, can preserve the optimal solution while significantly reducing the computational burden of the PDT formulation. To test this hypothesis, the research analyzes the scheduling horizon of RCPSP and strictly proves that a reasonably reduced scheduling horizon keeps the same optimal solution. Based on this proof, the serial schedule generation scheme algorithm is adopted to obtain the reduced scheduling horizon, and then an improved PDT model is proposed accordingly. The key novelty lies in: (1) the rigorous mathematical proof of optimality preservation under horizon reduction, and (2) the systematic integration of SSGS-based horizon reduction with explicit elimination of redundant pulse variables. Numerical experiments demonstrate that, for RCPSP instances with 90 and 120 activities, compared with the original PDT model, the improved PDT model contains significantly fewer decision variables and constraints, reducing the number of decision variables to 6.6–9.8% and the number of constraints to 24.7–26.5% of those in the original PDT model, and thus achieves significant improvement in computational efficiency while obtaining the exact optimal solution.