SEQUENCING TO MINIMIZE THE MAXIMUM JOB COST

The relationships among various maximum cost problems are explored. One such result is that the first three examples cited above are special cases of the final one; even though they appear to be quite different from the surface. A consequence of this fact is that the two machine-maximum completion time flow-shop problem is NP-hard when general precedence constraints are allowed. A maximum cost problem is formulated and shown to generalize the above-mentioned problems. An extension of E. L. Lawler's back-to-front sequencing algorithm efficiently solves the unconstrained version of this problem. Finally, two insertion properties, which were motivated by Smith's adjacent pairwise interchange (API) property, lead to efficient algorithms for sequencing with general precedence constraints.