A Duplicate-Free State-Space Model for Optimal Task Scheduling

Show simple item record

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 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

Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace