Algoristics for Single-Machine Sequencing with Precedence Constraints

Although Horn, Sidney and Lawler have considered the problem of minimizing weighted mean flow time for n jobs with precedence constraints on one machine, practical exact algorithms for the general case remain elusive. Two relatively sophisticated heuristics are presented which are computationally attractive. Each is optimal on large subclasses of problems; computational study demonstrates each to be extremely close to optimal in general. Such heuristics are dubbed “algoristics.” The first-come first-served heuristic serves as a benchmark. Finally, a simple “myopic” heuristic produces about 80% of the savings of the algoristics; it possesses the advantages of a dispatching rule. A standard branch and bound procedure has also been computed for a large subset of problems for comparison purposes. Planning horizon results are also derived.