Reachability and Deadlocking Problems in Multi-stage Scheduling

We study reachability and deadlock detection questions in multi-stage scheduling systems. The jobs have partially ordered processing plans that dictate the order in which the job passes through the machines. Our results draw a sharp. borderline between tractable and intractable cases of these questions: certain types of processing plans (that we call unconstrained and source-constrained) lead to algorithmically tractable problems, whereas all remaining processing plans lead to NP-hard problems. We give conditions under which safe system states can be recognized in polynomial time, and we prove that without these conditions the recognition of safe system states is NP-hard. We show that deciding reachability of a given state is essentially equivalent to deciding safety. Finally, we establish NP-hardness of deciding whether the system can ever fall into a deadlock state.