Bi-linear reductions for the Multiprocessor Scheduling Problem with Communication Delays using Integer Linear Programming

Show simple item record

dc.contributor.author Venugopalan, Sarad en
dc.contributor.author Sinnen, Oliver en
dc.contributor.editor Haywood, J en
dc.coverage.spatial Wellington, New Zealand en
dc.date.accessioned 2017-11-13T20:54:01Z en
dc.date.issued 2012 en
dc.identifier.citation Editors: Haywood J. Proceedings of the 46th Annual Conference of the Operations Research Society of New Zealand (ORSNZ). Operational Research Society of New Zealand (Inc.), Auckland, New Zealand. 378-386. 2012 en
dc.identifier.issn 0114-6602 en
dc.identifier.uri http://hdl.handle.net/2292/36405 en
dc.description.abstract With computer processors running at speeds closer to their theoretical limit, the recent focus has turned to the use of parallelism in hardware by the use of multicore processors for speedup. However, duplicating processors do not automatically translate to faster task execution. The tasks are to be carefully assigned and scheduled so that their total execution time on the multiple processors is minimal. We propose an optimal Integer Linear Programming formulation for the Multiprocessor Scheduling Problem with Communication Delays (MSPCD). The formulations use an effective method to linearise the bi-linear forms arising out of communication delays and introduce new overlap constraints to ensure that no two tasks running on the same processor overlap in time. The proposed formulation is compared with known ILP formulations that solve the MSPCD problem. en
dc.description.uri http://orsnz.org.nz/ en
dc.publisher Operational Research Society of New Zealand (Inc.) en
dc.relation.ispartof 46th Annual ORSNZ Conference en
dc.relation.ispartofseries Proceedings of the 46th Annual Conference of the Operations Research Society of New Zealand (ORSNZ) 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. en
dc.rights.uri https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm en
dc.title Bi-linear reductions for the Multiprocessor Scheduling Problem with Communication Delays using Integer Linear Programming en
dc.type Conference Item en
pubs.begin-page 378 en
dc.rights.holder Copyright: Operational Research Society of New Zealand (Inc.) en
pubs.author-url https://secure.orsnz.org.nz/conf46/content/ORSNZ12_conference_proceedings.pdf en
pubs.end-page 386 en
pubs.finish-date 2012-12-11 en
pubs.place-of-publication Auckland, New Zealand en
pubs.start-date 2012-12-10 en
dc.rights.accessrights http://purl.org/eprint/accessRights/RestrictedAccess en
pubs.subtype Proceedings en
pubs.elements-id 644075 en
pubs.org-id Engineering en
pubs.org-id Department of Electrical, Computer and Software Engineering en
pubs.record-created-at-source-date 2017-08-03 en


Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record

Share

Search ResearchSpace


Browse

Statistics