Optimal Sequencing Via Modular Decomposition: Characterization of Sequencing Functions

Abstract
With the recent development of efficient algorithms for locating modules in a precedence network, a new class of sequencing algorithms has become promising. These algorithms obtain optimal sequences by finding optimal subsequences of progressively larger modules, until all jobs are sequenced. To guarantee optimality of resulting sequences, the sequencing (objective) function must satisfy the “job module property” defined herein. In this paper, three properties of sequencing functions are defined, and it is shown that a sequencing function satisfying these properties possesses the job module property; many other decomposition results previously shown by the second author to hold for the total weighted completion time problem follow as well. Moreover, the class of problems defined by these sequencing functions includes the total weighted completion time problem, the least-cost fault detection problem, and the total weighted exponential completion time problem.

This publication has 0 references indexed in Scilit: