  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.
