dc.contributor.author |
Orr, M |
en |
dc.contributor.author |
Sinnen, Oliver |
en |
dc.contributor.editor |
Traff, JL |
en |
dc.contributor.editor |
Hunold, S |
en |
dc.contributor.editor |
Versaci, F |
en |
dc.coverage.spatial |
Vienna, Austria |
en |
dc.date.accessioned |
2016-09-05T02:24:40Z |
en |
dc.date.issued |
2015-07-25 |
en |
dc.identifier.isbn |
978-3-662-48095-3 |
en |
dc.identifier.issn |
0302-9743 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/30215 |
en |
dc.description.abstract |
The problem of task scheduling with communication delays (P|prec,cij|Cmax ) is NP-hard, and therefore solutions are often found using a heuristic method. However, an optimal schedule can be very useful in applications such as time critical systems, or as a baseline for the evaluation of heuristics. Branch-and-bound algorithms such as A* have previously been shown to be a promising approach to the optimal solving of this problem, using a state-space model which we refer to as exhaustive list scheduling. However, this model suffers from the possibility of producing high numbers of duplicate states. In this paper we define a new state-space model in which we divide the problem into two distinct subproblems: first we decide the allocations of all tasks to processors, and then we order the tasks on their allocated processors to produce a complete schedule. This two-phase state-space model offers no potential for the production of duplicates. An empirical evaluation shows that the use of this new state-space model leads to a marked reduction in the number of states considered by an A* search in many cases, particularly for task graphs with a high communication-to-computation ratio. With additional refinement, and the development of specialised pruning techniques, the performance of this state-space model could be improved. |
en |
dc.description.uri |
http://link.springer.com/book/10.1007/978-3-662-48096-0 |
en |
dc.publisher |
Springer Verlag (Germany) |
en |
dc.relation.ispartof |
Euro-Par 2015: 21st International European Conference on Parallel and Distributed Computing |
en |
dc.relation.ispartofseries |
Euro-Par 2015: Parallel Processing: 21st International Conference on Parallel and Distributed Computing, Vienna, Austria, August 24-28, 2015, Proceedings |
en |
dc.rights |
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. http://www.sherpa.ac.uk/romeo/issn/0302-9743/ |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.subject |
Science & Technology |
en |
dc.subject |
Technology |
en |
dc.subject |
Computer Science, Information Systems |
en |
dc.subject |
Computer Science, Software Engineering |
en |
dc.subject |
Computer Science, Theory & Methods |
en |
dc.subject |
Computer Science |
en |
dc.subject |
COMMUNICATION DELAYS |
en |
dc.subject |
SYSTEMS |
en |
dc.subject |
GRAPHS |
en |
dc.title |
A Duplicate-Free State-Space Model for Optimal Task Scheduling |
en |
dc.type |
Conference Item |
en |
dc.identifier.doi |
10.1007/978-3-662-48096-0_8 |
en |
pubs.begin-page |
97 |
en |
pubs.volume |
9233 |
en |
dc.description.version |
AM - Accepted Manuscript |
en |
dc.rights.holder |
Copyright: Springer Verlag (Germany) |
en |
pubs.author-url |
http://link.springer.com/chapter/10.1007/978-3-662-48096-0_8 |
en |
pubs.end-page |
108 |
en |
pubs.finish-date |
2015-08-28 |
en |
pubs.publication-status |
Published |
en |
pubs.start-date |
2015-08-24 |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |
pubs.subtype |
Proceedings |
en |
pubs.elements-id |
502401 |
en |
pubs.org-id |
Engineering |
en |
pubs.org-id |
Department of Electrical, Computer and Software Engineering |
en |
pubs.record-created-at-source-date |
2016-09-05 |
en |