Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/5582
Title: | Subset-restricted interchange for dynamic min-max scheduling problems |
Authors: | Steiner, George Stephenson, Paul A. McMaster University, Michael G. DeGroote School of Business |
Keywords: | Business;Business |
Publication Date: | Oct-1996 |
Series/Report no.: | Research and working paper series (Michael G. DeGroote School of Business) no. 418 |
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> |
URI: | http://hdl.handle.net/11375/5582 |
Identifier: | dsb/41 1040 4944061 |
Appears in Collections: | DeGroote School of Business Working Paper Series |
Files in This Item:
File | Size | Format | |
---|---|---|---|
fulltext.pdf | 718.47 kB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.