Worst-case performance of critical path type algorithms

UTSePress Research/Manakin Repository

Search UTSePress Research

Advanced Search


My Account

Show simple item record

dc.contributor.author Singh, G. en_US
dc.contributor.author Zinder, Yakov en_US
dc.contributor.editor E. Kozan en_US
dc.date.accessioned 2012-10-12T03:36:21Z
dc.date.available 2012-10-12T03:36:21Z
dc.date.issued 2000 en_US
dc.identifier 2010004989 en_US
dc.identifier.citation Singh G. and Zinder Yakov 2000, 'Worst-case performance of critical path type algorithms', , Australian Society for Operations Research, Australia, , pp. 383-399. en_US
dc.identifier.issn 0969-6016 en_US
dc.identifier.other E1UNSUBMIT en_US
dc.identifier.uri http://hdl.handle.net/10453/19199
dc.description.abstract The critical path method remains one of the most popular approaches in practical scheduling. Being developed for the makespan problem this method can also be generalized to the maximum lateness problem. For the unit execution time task system and parallel processors this generalization is known as the Brucker?Garey?Johnson algorithm. We characterize this algorithm by introducing an upper bound on the deviation of the criterion from its optimal value. The bound is stated in terms of parameters characterizing the problem, namely number of processors, the length of the longest path, and the total required processing time. We also derive a similar bound for the preemptive version of the Brucker-Garey-Johnson algorithm. en_US
dc.language en_US
dc.publisher Australian Society for Operations Research en_US
dc.relation.isbasedon en_US
dc.title Worst-case performance of critical path type algorithms en_US
dc.parent 15th National Conference of Australian Society for Operations Research en_US
dc.journal.volume 7 en_US
dc.journal.number en_US
dc.publocation Australia en_US
dc.identifier.startpage 383 en_US
dc.identifier.endpage 399 en_US
dc.cauo.name SCI.Mathematical Sciences en_US
dc.conference Verified OK en_US
dc.for 080201 en_US
dc.personcode 0000070210 en_US
dc.personcode 930901 en_US
dc.percentage 100 en_US
dc.classification.name Analysis of Algorithms and Complexity en_US
dc.classification.type FOR-08 en_US
dc.edition en_US
dc.custom 15th National Conference of Australian Society for Operations Research en_US
dc.date.activity 19990101 en_US
dc.location.activity Gold Coast en_US
dc.description.keywords Deterministic scheduling problems; Parallel identical machines; Precedence constraints; Maximum lateness; Worst-case analysis en_US
dc.staffid en_US
dc.staffid 930901 en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record