Efficient task scheduling with duplication for bounded number of processors

Task scheduling has been known to be one of the challenging issues in parallel and distributed computing. There have been many scheduling algorithms proposed for scheduling tasks onto unlimited number of processors, while, in practical situations, there are only a limited number of processors available. Thus, the goal of this work is to propose several new features to vastly improve the already-efficient bounded-CPFD algorithm (Ahmad and Kwok, 1998). The proposed technique, instead of considering only parent processors when scheduling a task in the original bounded-CPFD algorithm, allows other processors to be considered as well. This heuristic intends to provide a better load balance among the processors in leading to a shorter overall schedule length by allowing potentially more task duplication. Results from an extensive simulation show significant performance improvement from the proposed techniques over the bounded-CPFD.