Subset-restricted interchange for dynamic min-max scheduling problems

The traditional method of pairwise job interchange compares the cost of sequences which differ only in the interchange of two jobs. It assumes that either there are no intermediate jobs (adjacent pairwise interchange) or that the interchange can be performed no matter what the intermediate jobs are (nonadjacent pairwise interchange). We introduce a generalization that permits the pairwise interchange of jobs provided that the intermediate jobs belong to a restricted subset of jobs (subset-restricted pairwise interchange). In general, even if an adjacent interchange relation is a partial order, it need not be a precedence order. We introduce a uni ed theory of dominance relations based on subset-restricted interchange. This yields a precedence order for the class of unconstrained, regular, single machine scheduling problems 1/r(j)/f(max). Thus it applies to 1/r(j)/L-max, 1/r(j), (d(j)) over bar /C-max, 1/r(j)/max w(j)L(j), 1/r(j)/max w(j)C(j), and other problems. We also show that these problems remain strongly NP-hard for interval-ordered tasks. The strength of the precedence orders was tested in a large-scale computational experiment for 1/r(j)/max w(j)C(j). The results show that using the precedence orders in branch and bound algorithms speeds these up on average by about 58 percent.