Sequencing on single machine with general precedence constraints: the job module algorithm

Abstract

<p>We introduce a class of sequencing problems based on some common, easily verifiable properties. Some well­ known members of this class are the Total weighted completion time problem and the Least cost fault detection problem, both with general precedence constraints. We present an efficient algorithm for solving these problems. It decomposes the original problem into smaller sub­ problems, called job-modules and sequences these in an optimal w ay. The main result of this paper is a polynomial-time algorithm for finding job modules in a general precedence graph.</p>