On a decomposition algorithm for sequencing problems with precedence constraints

Abstract

<p>In this paper we introduce a class of sequencing problems, which includes many widely-studied problems; for example the one­ machine total weighted completion time problem, the directed linear ordering problem, the least cost fault detection problem and the total weighted exponential completion time problem. Sidney developed a decomposition algorithm for the one-machine total weighted completion time problem which was later shown to be applicable to all the problems in the class. We discuss how recently developed decomposition theories for directed acyclic graphs enable us to execute efficiently one of the ·two main steps in Sidney's algorithm. This is followed by complexity results, where it is shown that all of the above sequencing problems remain NP-complete even if we restrict the precedence constraints between the jobs to a special class of precedence graphs. At the end we introduce a class of precedence constraints for which the sequencing problems have polynomial time and space complexity.</p>