Subset-restricted interchange for dynamic min-max scheduling problems

Steiner, George; Stephenson, Paul A.; McMaster University, Michael G. DeGroote School of Business

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 Open Access	718.47 kB	Adobe PDF	View/Open

Show simple item record