Robust scheduling in an uncertain environment

This thesis presents research on scheduling in an uncertain environment, which forms a part of the rolling stock life cycle logistics applied research and development program funded by Dutch railway industry companies. The focus therefore lies on scheduling of maintenance operations on rolling stock in the railway industry. The first chapter describes some of the history of the Dutch railways, focusing on the rolling stock used, and it introduces the context in which NedTrain, a major Dutch rolling stock maintenance company, operates. While maintenance of rolling stock is not a new problem, recent changes in the field are identified in this chapter which introduce new challenges: the first is the declining involvement of maintenance experts in the procurement of new rolling stock, the second is the on-going demand for increasing efficiency. Based on this discussion, the goal of this thesis is to devise a method with which schedules can be created based on a flexible process. The schedules resulting from this method are to be both flexible, meaning that they can be adapted easily, and robust, meaning that they are resilient to the effects of uncertain events. Lastly, our goal is to create the schedules in such a way that the effects of disturbances in one team have little or no effect on any other teams in the same workshop. Chapter 2 examines existing research in the context of the formulated research goals. It is shown that the well-known Resource-Constrained Project Scheduling Problem (RCPSP) can be mapped to the problem of scheduling maintenance tasks on trains in the NedTrain workshops. The most important methods to solve the RCPSP are discussed, among which are many exact methods. Both the scale of the problem and the requirement of having a flexible schedule instead of a fixed time assignment for the tasks prohibit using these methods. Among the heuristic methods discussed, the Precedence Constraint Posting method turns out to be an especially good fit: it is able to solve large-sized problems very quickly, and it uses a Simple Temporal Network (STN) as a way of representing many different solutions to the original problem, offering a lot of flexibility. Based on the research discussed, research questions are formulated to answer the research goals. - The first question asks how to define criteria encapsulating the notion of flexibility as posed by our research goals, and how to measure the flexibility of a schedule. - The second question asks how we can make the best use of available flexibility to attain robustness. - The third question asks if there is also a way to extend the concept of temporal flexibility to include a form of sequential flexibility. - The last question asks how we can use our work on robustness to decouple schedules, ensuring that disturbances in the schedule for one agent have no impact on any other agents. The third chapter investigates criteria corresponding to our intuitive notion of flexibility in scheduling. The concept of interval schedules serves as a basis for this investigation: the idea is that each task in the schedule is assigned an interval from which its start time can be picked, and the length of all these intervals serves as a representation for the flexibility of the schedule. We show that flexibility measures in existing research lead to an over-estimation of the total available flexibility, because dependencies between tasks are not taken into account properly: simply adding the interval sizes for two dependent tasks causes over-estimation, because the picked time for one task can reduce the interval size for another task. Our first major contribution is an independence requirement for the creation of these intervals: we state that intervals should be constructed in such a way that any choice in one interval has no impact on the available choices in any of the other intervals. Our second major contribution is a method to actually construct such intervals, which results in a valid interval schedule for an \stn, allowing efficient schedule execution under dynamic circumstances. Additionally, we note that an interval schedule can also serve as a mechanism to decouple a schedule, giving a partial answer to the last research question. In the fourth chapter, we investigate how to make use of the available flexibility to ensure that schedules are robust. We show that having a maximal total amount of flexibility does not imply that the schedule is as robust as possible: maximization might lead to a very skewed distribution of flexibility over the schedule. Different ways of distributing flexibility over a schedule are proposed and analyzed in an experimental setting. From the experiments it can be clearly concluded that sacrificing some of the total flexibility to improve the distribution of flexibility can have a positive influence on the robustness of the schedule. We also propose a different maximization strategy: one which maximizes the minimum of the interval sizes for the schedule. This strategy is shown to work especially well for small delays. So far we only discussed strategies concerning temporal flexibility, i.e., those in which start times remain flexible instead of fixed. Chapter 5 introduces a novel representation of solutions for planning problems in which not all ordering decisions needed to avoid resource contention are made in advance. This is achieved by grouping tasks which need to be executed sequentially together, in such a way that either ordering of the tasks remains feasible during execution time. An analysis using simulation experiments shows that this technique results in higher robustness, at the cost of somewhat lower resource utilization. The proposed algorithm to construct such schedules offers limited control over the size of the grouped tasks. The experiments show a slightly counter-intuitive results: schedules with larger groups offer lower robustness than those with smaller groups. A plausible explanation is the fact that delays can occur at any place in a schedule. Having multiple smaller groups instead of a few very large ones increases the chance that such a delay can be compensated for using a task group