Stochastic Scheduling of Train Maintenance Projects

Abstract

We study the application of stochastic scheduling methods for dealing with the negative impact of uncertainty on the timely delivery of NedTrain maintenance projects. A stochastic scheduling problem includes a quantification of uncertainty by representing the duration of a maintenance activity with a probability distribution. The solution is no longer a schedule but a scheduling policy: a dynamic process for determining when to execute activities on-the-fly. Our objective is to find a policy that minimizes stochastic tardiness by expectation and also by variance, to minimize risk. We concentrate on the class of Early-Start (ES) policies. An ES policy is a PERT network representation of the projects in which the width of the partial order defined by the precedence edges is restricted such that resource requirement will not exceed resource availability. ES policies enable the use of standard PERT management practices (developed for handling uncertainty in projects with unlimited resources) to projects with limited resources (e.g., NedTrain projects). Simulation is considered as the only practical means to evaluate the objective function in stochastic scheduling. This approach is computationally expensive, especially for large (e.g., NedTrain-specific) instances with activity durations that exhibit high variability. We observe that circuit timing graphs in modern VLSI design use a PERT network-like representational mechanism. Statistical Static Timing Analysis (SSTA) is a new research area with a wealth of methods for solving the PERT problem on massive networks, offering high accuracy at low computational cost. We propose the use of SSTA techniques, treating a given ES policy as a circuit timing graph. This enables us to evaluate the objective function and more importantly to implement informed heuristics with efficiency. As a proof-of-concept we studied the use of Linear-Gaussian SSTA, applicable when activity durations exhibit Gaussian variability and may have linear interdependencies. Our other contribution is to propose efficient enumeration schemes for ES policies, overcoming the infeasibility of the existing scheme on problems of practical size. Experiments suggest that the proposed enumeration schemes in combination with SSTA establish a frame work for the design of competitive heuristic solvers, suitable for large-scale problem instances with high durational variability.