Sequencing to Minimize the Maximum Job Cost

Publisher Website
Google Scholar
Abstract
Consider the problem of sequencing a set of jobs in order to minimize the maximum job cost. Examples of such a problem include the one-machine maximum lateness and maximum earliness problems, the maximum cumulative cost problem, and Johnson's two-machine maximum completion time flow-shop problem. 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 on 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 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.

This publication has 0 references indexed in Scilit: