The Complexity of Stability

Abstract

In dynamic scheduling, some of the information about the scheduling problem is learnt during the execution of the schedule. Because of this, creating a low cost schedule that does not have to be changed is impossible in most cases. When changes are made during the execution, focussing solely on the performance of the schedule may result in very large differences between the original schedule and the realised schedule. These differences are undesirable particularly if tasks or resources are human. In order to quantify them, several stability metrics are considered, as well as the performance objective makespan. The complexity of computing these metrics when a single disruption to the duration of one of the tasks occurred is considered. For single machine scheduling problems and constraint programming the complexity of several stability metrics is known. For parallel processor scheduling, very little has been investigated. Optimizing just the stability metrics turns out to be possible in polynomial time. We further show that many of the multi objective optimizations problems that consider both a stability metric and the makespan are strongly NP-complete. For the instances that are not, an algorithm is given. In order to reduce the complexity, reducing the search space to a partial order schedule is investigated. This is a promising method as optimizing the makespan in this reduced search space can be done in polynomial time. Surprisingly, the resulting complexities are the same as those of the original problems.