Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/5582
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Steiner, George | en_US |
dc.contributor.author | Stephenson, Paul A. | en_US |
dc.contributor.author | McMaster University, Michael G. DeGroote School of Business | en_US |
dc.date.accessioned | 2014-06-17T20:35:36Z | - |
dc.date.available | 2014-06-17T20:35:36Z | - |
dc.date.created | 2013-12-23 | en_US |
dc.date.issued | 1996-10 | en_US |
dc.identifier.other | dsb/41 | en_US |
dc.identifier.other | 1040 | en_US |
dc.identifier.other | 4944061 | en_US |
dc.identifier.uri | http://hdl.handle.net/11375/5582 | - |
dc.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> | en_US |
dc.description.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> | en_US |
dc.relation.ispartofseries | Research and working paper series (Michael G. DeGroote School of Business) | en_US |
dc.relation.ispartofseries | no. 418 | en_US |
dc.subject | Business | en_US |
dc.subject | Business | en_US |
dc.subject.lcc | Production scheduling Sequences (Mathematics) | en_US |
dc.title | Subset-restricted interchange for dynamic min-max scheduling problems | en_US |
dc.type | article | en_US |
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.