Scheduling UET-UCT tasks: Branch-and-bound search in the priority space

Zinder, Y; Su, B; Singh, G; Sorli, R

Scheduling UET-UCT tasks: Branch-and-bound search in the priority space

Zinder, Y

Su, B Singh, G Sorli, R

Permalink

Publication Type:: Journal Article
Citation:: Optimization and Engineering, 2010, 11 (4), pp. 627 - 646
Issue Date:: 2010-12-01

Closed Access

	Filename	Description	Size
	2010004994OK.pdf		413.87 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	Zinder, Y https://orcid.org/0000-0003-2024-8129	en_US
dc.contributor.author	Su, B	en_US
dc.contributor.author	Singh, G	en_US
dc.contributor.author	Sorli, R	en_US
dc.date.issued	2010-12-01	en_US
dc.identifier.citation	Optimization and Engineering, 2010, 11 (4), pp. 627 - 646	en_US
dc.identifier.issn	1389-4420	en_US
dc.identifier.uri	http://hdl.handle.net/10453/29267
dc.description.abstract	The paper is concerned with the problem of scheduling partially ordered unit execution time tasks on parallel processors with unit communication delays and release times. Two criteria are considered, the maximum lateness and its particular case, the makespan. This problem plays an important role in scheduling theory and was originally inspired by the applications to multi-processor computer systems. It is well known that for both criteria the problem is NP-hard in the strong sense. The paper presents an implementation of the branch-and-bound method which does not partition the feasible region explicitly. The theoretical results are complemented by computational experiments. © 2009 Springer Science+Business Media, LLC.	en_US
dc.relation.ispartof	Optimization and Engineering	en_US
dc.relation.isbasedon	10.1007/s11081-009-9080-8	en_US
dc.subject.classification	Operations Research	en_US
dc.title	Scheduling UET-UCT tasks: Branch-and-bound search in the priority space	en_US
dc.type	Journal Article
utslib.citation.volume	4	en_US
utslib.citation.volume	11	en_US
utslib.for	010206 Operations Research	en_US
utslib.for	01 Mathematical Sciences	en_US
utslib.for	09 Engineering	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.issue	4	en_US
pubs.publication-status	Published	en_US
pubs.volume	11	en_US

Abstract:

The paper is concerned with the problem of scheduling partially ordered unit execution time tasks on parallel processors with unit communication delays and release times. Two criteria are considered, the maximum lateness and its particular case, the makespan. This problem plays an important role in scheduling theory and was originally inspired by the applications to multi-processor computer systems. It is well known that for both criteria the problem is NP-hard in the strong sense. The paper presents an implementation of the branch-and-bound method which does not partition the feasible region explicitly. The theoretical results are complemented by computational experiments. © 2009 Springer Science+Business Media, LLC.

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

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