Context

This research is executed in the context of a research program at NedTrain. NedTrain is a part of NS Group, and is currently contracted to perform maintenance on all rolling stock of NSR (the passenger transport division of NS Group) and NS HiSpeed (which exploits the high-speed railway network in the Netherlands). The fleet used by these two carriers has a size of around 3000 passenger carriages, of which about 250 are in maintenance at any one time.

The core task of NedTrain is to maintain the rolling stock. The performance of maintenance operations is measured by looking at the fleet availability, transport quality and total cost of ownership. Here, fleet availability means that enough carriages should be available to the carrier, and transport quality means that the available carriages should perform at some specified level.

The research is motivated by the inefficiencies of current operational scheduling. Schedules are constructed largely by hand, and uncertainty during execution is absorbed by having large amounts of slack in the schedule and a large assortment of spare parts in the warehouse. Nevertheless, maintenance sometimes still does not finish in time.

A second motivation is the anticipation of future developments which require a more flexible scheduling of maintenance operations. Specifically, there are plans to perform some maintenance operations between rush hours, at a time when peak transport capacity is not needed and a train can thus be removed more easily from service. Another development is the introduction of data collection equipment on trains which can transmit measurements to a central location. These measurements can be used to gain insight into the maintenance requirements of a specific train even before it arrives at a workplace, but the scheduling system must be designed to take advantage of such information.

Research

The scheduling of maintenance operations is modeled as a Resource Constraint Multiple Project Scheduling Problem (RCMPSP), mapping each train to a project. Existing solutions to RCMPSP do not apply to the NedTrain case, due to various existing requirements:

• Exact approaches do not scale well enough to be able to solve the NedTrain project. Linear programming approaches have difficulty due to the required temporal resolution: every possible time point adds decision variables. Also, the number of tasks in a two-week schedule for NedTrain is large: at least 300-600 activities, if one train comprises 10-20 maintenance tasks.
• The context of maintenance scheduling differs from most other scheduling problems. Uncertainty plays a much more prominent role. In production scheduling, uncertainty is usually only present before the start of execution (i.e., how many items do I produce, what type/specification), whereas in maintenance scheduling, uncertainty is present during execution: the majority of tasks are composed of an inspection (is the component within specification?), optionally followed by repair tasks.
• Often, research focuses on optimizing the makespan of schedules. In the case of NedTrain, the due date of each train is fixed in advance. Improving upon this due date does not bring any gain; focus should lie on minimizing the probability of violating this due date.
• Stability is an important factor in the context of maintenance scheduling. Updates to the schedule to accomodate changing tasks should be small, to avoid changing existing commitments.

Research concentrates on constraint posting procedures. Such procedures are not affected by the large temporal horizon of the problem and the large number of tasks, since they are based on heuristics. Constraint posting uses a solution representation which retains a large amount of execution time flexibility, instead of giving a fixed execution time for each task. Also, a solution contains all decisions of the algorithm, such that updating and/or repairing the solution in case of changes is easy.