Subset-restricted interchange for dynamic min-max scheduling problems

Abstract

<p>The traditional method of pairwise job interchange compares the cost of sequences that differ only in the interchange of two jobs. It assumes that either there are no intermediate jobs (<em>adjacent pairwise interchange</em>) or that the interchange can be performed no matter what the intermediate jobs are (<em>nonadjacent pairwise interchange</em>). We introduce a generalization that permits the pairwise interchange of jobs provided that the intermediate jobs belong to a restricted subset of jobs (<em>subset-restricted pairwise interchange</em>).</p> <p>In general, even if an adjacent interchange relation is a partial order it need not be a precedence order. We introduce a unified 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 / <em>r</em> / <em>f</em>_max. Thus it applies to 1 / <em>r</em> / <em>L</em>_max, 1 / <em>r</em> ,<em> ̅d</em> / <em>C</em>_max, 1 /<em> r</em> / <em>WL</em>_max, 1 /<em> r</em> / <em>WC</em>_max and other problems. We also show that these problems remain strongly NP-hard for interval-ordered tasks.</p>