Railway Maintenance Scheduling Under Concurrent Resource, Safety, and Mobility Constraints: A Directed-Graph Constructive Insertion Heuristic

Scheduling maintenance tasks within a railway depot requires more than accounting for task durations and precedence: parallel activities compete for qualified personnel, train safety states can be incompatible, state changes consume time, and technicians must move between work locations. This paper presents the Operational Maintenance Sequencing Algorithm (OMSA), a deterministic constructive insertion heuristic for developing feasible task-level schedules while seeking to reduce maintenance-stay duration. The underlying scheduling problem is defined independently in terms of task selection, timing, technician assignment, precedence, safety-state transitions, mobility, and depot time restrictions. The OMSA then represents the evolving schedule as a directed graph encoded by a connectivity matrix, systematically generates sequential and parallel candidate insertions for each prioritized task, and retains the feasible insertion with the shortest resulting makespan at each iteration. Its application to a high-speed train preventive maintenance intervention, analysis of alternative workforce configurations, and comparison with an expert-prepared schedule demonstrate the method’s ability to construct schedules under this combined set of constraints and reveal how qualification-specific bottlenecks and safety-state transitions shape depot-stay duration. By integrating directed-graph schedule construction with explicit operational feasibility checks and technician-level outputs, the OMSA provides a structured decision-support framework for maintenance sequencing and resource analysis. The present study does not claim global optimality or superiority over unimplemented benchmark algorithms; rather, it establishes the feasibility, interpretability, and industrial applicability of the proposed scheduling procedure.