The solvable cases of a scheduling algorithm

Walker, S; Zinder, Y

The solvable cases of a scheduling algorithm

Walker, S Zinder, Y

Permalink

Publication Type:: Conference Proceeding
Citation:: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, 8283 LNCS pp. 229 - 239
Issue Date:: 2013-12-01

Closed Access

	Filename	Description	Size
	2013003789OK.pdf		192.88 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	Walker, S	en_US
dc.contributor.author	Zinder, Y https://orcid.org/0000-0003-2024-8129	en_US
dc.date.issued	2013-12-01	en_US
dc.identifier.citation	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, 8283 LNCS pp. 229 - 239	en_US
dc.identifier.isbn	9783642450297	en_US
dc.identifier.issn	0302-9743	en_US
dc.identifier.uri	http://hdl.handle.net/10453/28123
dc.description.abstract	When considering the NP-hard problem of scheduling precedence constrained tasks with preemptions on identical parallel machines with the goal of minimising the maximum lateness, approximation algorithms are commonly studied. It is desirable to characterise in some way the circumstances under which a given algorithm will provide an optimal solution. This paper considers a well-known scheduling algorithm called the Brucker-Garey-Johnson Algorithm, known to produce optimal schedules whenever the precedence constraints are in the form of in-trees. A new class of partial orders is presented and it is proved not only that the Brucker-Garey-Johnson Algorithm will solve every problem instance constrained by a partial order from that class but also that no larger class has this property. © 2013 Springer-Verlag.	en_US
dc.relation.ispartof	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)	en_US
dc.relation.isbasedon	10.1007/978-3-642-45030-3_22	en_US
dc.subject.classification	Artificial Intelligence & Image Processing	en_US
dc.title	The solvable cases of a scheduling algorithm	en_US
dc.type	Conference Proceeding
utslib.citation.volume	8283 LNCS	en_US
utslib.for	0802 Computation Theory and Mathematics	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.publication-status	Published	en_US
pubs.volume	8283 LNCS	en_US

Abstract:

When considering the NP-hard problem of scheduling precedence constrained tasks with preemptions on identical parallel machines with the goal of minimising the maximum lateness, approximation algorithms are commonly studied. It is desirable to characterise in some way the circumstances under which a given algorithm will provide an optimal solution. This paper considers a well-known scheduling algorithm called the Brucker-Garey-Johnson Algorithm, known to produce optimal schedules whenever the precedence constraints are in the form of in-trees. A new class of partial orders is presented and it is proved not only that the Brucker-Garey-Johnson Algorithm will solve every problem instance constrained by a partial order from that class but also that no larger class has this property. © 2013 Springer-Verlag.

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

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