Paper Info
Title
New Results for the Heterogeneous Multi-Processor Scheduling Problem using a Fast, Effective Local Search and Random Disruption.
Abstract
The efficient scheduling of independent computational tasks in a heterogeneous computing environment is an important problem that occurs in domains such as Grid and Cloud computing. Finding optimal schedules is an NP-hard problem in general, so we have to rely on approximate algorithms to come up schedules that are as near to optimal as possible. In our previous work on this problem, we applied a fast, effective local search to generate reasonably good schedules in a short amount of time and used ant colony optimisation (ACO) to incrementally improve those schedules over a longer time period. In this work, we replace the ACO component with a random disruption algorithm and find that this produces results which are competitive with the current state of the art over a 90 second execution time. We also ran our algorithm for a longer time period on 12 well-known benchmark instances and as a result provide new upper bounds for these instances.
Year
Venue
Field
2013
CoRR
Mathematical optimization,Job shop scheduling,Computer science,Scheduling (computing),Symmetric multiprocessor system,Real-time computing,Schedule,Local search (optimization),Ant colony,Grid,Cloud computing,Distributed computing
DocType
Volume
Citations 
Journal
abs/1312.6246
0
PageRank 
References 
Authors
0.34
2
4
Name
Order
Citations
PageRank
John Levine1728.54
Graeme Ritchie2182.78
Alastair Andrew350.77
Simon Gates400.34