Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/5483
Title: | On a decomposition algorithm for sequencing problems with precedence constraints |
Authors: | Steiner, George McMaster University, Faculty of Business |
Publication Date: | Nov-1983 |
Series/Report no.: | Research and working paper series (McMaster University. Faculty of Business) no. 213 |
Abstract: | <p>In this paper we introduce a class of sequencing problems, which includes many widely-studied problems; for example the one machine total weighted completion time problem, the directed linear ordering problem, the least cost fault detection problem and the total weighted exponential completion time problem. Sidney developed a decomposition algorithm for the one-machine total weighted completion time problem which was later shown to be applicable to all the problems in the class. We discuss how recently developed decomposition theories for directed acyclic graphs enable us to execute efficiently one of the ·two main steps in Sidney's algorithm. This is followed by complexity results, where it is shown that all of the above sequencing problems remain NP-complete even if we restrict the precedence constraints between the jobs to a special class of precedence graphs. At the end we introduce a class of precedence constraints for which the sequencing problems have polynomial time and space complexity.</p> |
Description: | <p>19, 7 leaves : ; Includes bibliographical references (leaves 15-16). ;</p> |
URI: | http://hdl.handle.net/11375/5483 |
Identifier: | dsb/142 1141 4944165 |
Appears in Collections: | DeGroote School of Business Working Paper Series |
Files in This Item:
File | Size | Format | |
---|---|---|---|
fulltext.pdf | 713.41 kB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.