Subset-restricted interchange for dynamic min-max scheduling problems
Loading...
Files
Date
Journal Title
Journal ISSN
Volume Title
Publisher
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><sub>max</sub>. Thus it applies to 1 / <em>r</em> / <em>L</em><sub>max</sub>, 1 / <em>r</em> ,<em> ̅d</em> / <em>C</em><sub>max</sub>, 1 /<em> r</em> / <em>WL</em><sub>max</sub>, 1 /<em> r</em> / <em>WC</em><sub>max</sub> and other problems. We also show that these problems remain strongly NP-hard for interval-ordered tasks.</p>
Description
<p>23 leaves. ; Includes bibliographical references. ; "October, 1996." ;</p> <p>This research was supported in part by the Natural Sciences and Engineering Research Council of Canada, under Grant No. OGP0001798.</p>