Reachability problems in scheduling and planning

Reachability problems are fundamental in the context of many mathematical models and abstractions which describe various computational processes. Intuitively, when many objects move within a shared environment, objects may have to wait for others before moving and so slow down, or objects may even get stuck and never reach their destination. In this thesis we study these phenomena within essentially two different discrete models. The first model comprises real-time multi-stage processing systems closely related to shop models from classical scheduling theory. In practice the model captures system behaviour which typically occurs in robotic cells and flexible manufacturing systems. The main worry for operators of these systems is that the system gets stuck and comes to a halt since no further processing is possible; such a state is called deadlock. Resolving a deadlock is usually expensive (with respect to time, energy, and resources), and harmfully diminishes the system performance. The second model captures motion planning of multiple robots in a discretized environment represented by a graph. Here the main questions are whether one can move from a given state to a final state of the system, and if so, to determine a shortest move sequence. Although the application areas are rather diverse, various models have a lot in common: A given system in these models consists of a discrete environment, i.e. a finite number of fixed locations (machines, respectively vertices), and objects (jobs, respectively robots or tokens) that will move within this environment. The objects have an initial location and a final destination. Furthermore, an object can only move to an empty location. When no required location is available it waits at its current location (also referred to as block and wait). For real-time multi-stage scheduling systems we provide a good and almost complete picture of the complexity landscape for several algorithmic problems centered around reachability and deadlock detection. We consider a general type of scheduling system in which the sequence of machines passed by a job is constrained by a strict partial order. We are not interested in such a system in its full generality, but use it as a common framework in which we can express, compare and study different scheduling systems. Our main contribution is that even for scheduling systems where all jobs have isomorphic small and primitive sequence restrictions, most reachability problems turn out to be NP-complete. The computational complexity of a small number of intriguing exceptional cases remain open. For motion planning on graphs the computational complexity of deciding reachability has been settled (linear time is enough) and we focus on the harder problem of determining shortest move sequences. We give a complete overview of the computational complexity of this question when considering two parameters; the number of colors and the cardinality of the largest color-class. Our main contribution lies here in exhibiting the first graph classes where determining a shortest move sequence is decidable in polynomial time.