Abstract
This paper presents a fast preemptive list heuristic scheduling algorithm, called the Fast Preemptive Scheduling Algorithm (FPS), for both homogeneous and heterogeneous distributed memory systems. Time complexity of FPS is just O(vertical bar V vertical bar * (log vertical bar V vertical bar + log vertical bar P vertical bar) + vertical bar E vertical bar). Such an algorithm is useful during the compilation of the parallel applications. A preemptive schedule can better utilize the resources and offers a lot of flexibility. In order to schedule tasks, FPS simulates preemptive task execution at a very low overhead and requires very little runtime support. The experimental results show that, the scheduling cost of FPS is lower than that of other well known non-preemptive and preemptive list heuristic scheduling algorithms for both homogeneous and heterogeneous systems. Also the scheduling performance of FPS is same or better than that of those algorithms.