Worst-case performance of critical path type algorithms

Singh, G; Zinder, Y

Worst-case performance of critical path type algorithms

Singh, G Zinder, Y

Permalink

Publisher:: Australian Society for Operations Research
Publication Type:: Conference Proceeding
Citation:: 15th National Conference of Australian Society for Operations Research, 2000, 7 pp. 383 - 399
Issue Date:: 2000-01

Closed Access

	Filename	Description	Size
	2010004989OK.pdf		343.61 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Singh, G	en_US
dc.contributor.author	Zinder, Y	en_US
dc.contributor.editor	Kozan, E	en_US
dc.date	1999-01-01	en_US
dc.date.issued	2000-01	en_US
dc.identifier.citation	15th National Conference of Australian Society for Operations Research, 2000, 7 pp. 383 - 399	en_US
dc.identifier.issn	0969-6016	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.publisher	Australian Society for Operations Research	en_US
dc.relation.ispartof	15th National Conference of Australian Society for Operations Research	en_US
dc.title	Worst-case performance of critical path type algorithms	en_US
dc.type	Conference Proceeding
utslib.citation.volume	7	en_US
utslib.location	Australia	en_US
utslib.location.activity	Gold Coast	en_US
utslib.for	080201 Analysis of Algorithms and Complexity	en_US
utslib.for	0102 Applied Mathematics	en_US
utslib.for	0806 Information Systems	en_US
utslib.for	1503 Business and Management	en_US
dc.location.activity	Gold Coast	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Science
pubs.organisational-group	/University of Technology Sydney/Faculty of Science/School of Mathematical and Physical Sciences
utslib.copyright.status	closed_access
pubs.consider-herdc	false	en_US
pubs.place-of-publication	Australia	en_US
pubs.start-date	1999-01-01	en_US
pubs.volume	7	en_US

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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/19199