Author:

Keywords:

Lock scheduling, Graph coloring, Interval scheduling

Abstract:

We investigate a problem inspired by the practical setting of scheduling a lock with parallel chambers. We show how this problem relates to known interval scheduling problems, as well as to a particular graph coloring problem on multiple unit interval graphs. We explore the relationships between these problems and discuss the complexity of different problem variants. In particular, for a lock consisting of two chambers we are able to characterize the feasible instances and use this result to obtain efficient algorithms. We also provide an efficient algorithm for the special case with identical lock chambers. Furthermore, we describe a dynamic programming approach for the more general case with arbitrary chambers, and prove that the problem is strongly NP-complete when the number of chambers is part of the input.