Optimal task partitioning strategy with duplication (OTPSD) in parallel computing environments

Algorithms for scheduling tasks onto the heterogeneous processors must achieve remarkable performance in terms of scheduling length. Most of the scheduling algorithms do not provide the mechanism about minimum communication overhead. This paper introduces Optimal Task Partitioning Strategy with Duplication (OTPSD) that minimizes the scheduling length as well as communication overhead. The proposed scheduling algorithm is NP-complete. We introduce three phase algorithm in which the first phase comprises of grain_packSubDAG formation. The second phase is priority assignment phase. In the third phase, processors are grouped according to their processing capabilities. Proposed algorithm minimizes makespan and shows better performance in terms of normalized schedule length and processors utilization over the MCP and HEFT algorithms.