Bounds on the performance of heuristic algorithms for multiprocessor scheduling of hard real-time tasks

Abstract

The authors analyze the performance of a heuristic algorithm, Hk, which tries to keep at least k processors busy, if possible. Hk combines the features of two known heuristic scheduling algorithms: list scheduling and the H scheduling algorithm. The authors analyze its schedule length bound for both uniform tasks, i.e. tasks with the same computation time, and nonuniform tasks, i.e. tasks with arbitrary computation times. When k=2, the time complexity of H is the same as the complexity of the H scheduling algorithm and list scheduling, which is O(n2r), where n is the number of tasks and r is the number of resources. Whereas the H scheduling algorithm has a poor schedule length bound but performs very well in finding feasible schedules, and list scheduling does not perform well in finding feasible schedules but has a good bound, the results show that H2 has both a good schedule length bound and performs well in finding feasible schedules.