An algorithm for minimizing setups in precedence constrained scheduling

摘要

Consider a set of tasks to be scheduled on a single processor subject to precedence constraints. A setup occurs when a task is performed immediately after another task which is not its predecessor. The general problem is to find a schedule minimizing the number of setups. We present a decomposition approach for this problem. This leads to new complexity results and the identification of new classes of precedence constraints for which the problem is efficiently solvable.