The research presented in this thesis is part of the Rolling Stock Life Cycle Logistics applied research and development program, conducted by NedTrain. As a company, NedTrain belongs to Nederlandse Spoorwegen (NS; the principal railway company in the Netherlands) and provides maintenance services for the NS train-fleet. The aim of this program is to enhance NedTrain’s competitiveness as a rolling-stock maintenance services provider. Our work focuses on the operational aspects of this R&D program, motivated by the challenge of scheduling tasks (or operations) in a NedTrain maintenance workshop, such that trains are delivered on-time for circulation in the rail network. Most tasks in the workshop have uncertain durations (or processing times), which complicates the scheduling process. ... Read more

This paper concerns networks of precedence constraints between tasks with random durations, known as stochastic task networks, often used to model uncertainty in real-world applications. In some applications, we must associate tasks with reliable start-times from which realized start-times will (most likely) not deviate too far. We examine a dispatching strategy according to which a task starts as early as precedence constraints allow, but not earlier than its corresponding planned release-time. As these release-times are spread farther apart on the time-axis, the randomness of realized start-times diminishes (i.e. stability increases). Effectively, task start-times becomes less sensitive to the outcome durations of their network predecessors. With increasing stability, however, performance deteriorates (e.g. expected makespan increases). Assuming a sample of the durations is given, we define an LP for finding release-times that minimize the performance penalty of reaching a desired level of stability. The resulting LP is costly to solve, so, targeting a specific part of the solution-space, we define an associated Simple Temporal Problem (STP) and show how optimal release-times can be constructed from its earliest-start-time solution. Exploiting the special structure of this STP, we present our main result, a dynamic programming algorithm that finds optimal release-times with considerable efficiency gains. ... Read more

We discuss two flexibility metrics for Simple Temporal Networks (STNs): the so-called naive flexibility metric based on the difference between earliest and latest starting times of temporal variables, and a recently proposed concurrent flexibility metric. We establish an interesting connection between the computation of these flexibility metrics and properties of the minimal distance matrix DS of an STN S: the concurrent flexibility metric can be computed by finding a minimum weight matching of a weighted bipartite graph completely specified by DS, while the naive flexibility metric corresponds to computing a maximum weight matching in the same graph. From a practical point of view this correspondence offers an advantage: instead of using an O(n5) LP-based approach, reducing the problem to a matching problem we derive an O(n3) algorithm for computing the concurrent flexibility metric. ... Read more