Title: An effective compaction strategy for bi-criteria DAG scheduling in grids

Authors: Amit Agarwal, Padam Kumar

Addresses: Department of Electronics & Computer Engineering, Indian Institute of Technology Roorkee, Roorkee 247 667, Uttarakhand, India. ' Department of Electronics & Computer Engineering, Indian Institute of Technology Roorkee, Roorkee 247 667, Uttarakhand, India

Abstract: The bi-criteria scheduling approach may require several different criteria to be considered simultaneously when evaluating the quality of solution or a schedule. In general, scheduling directed acyclic graph (DAG) in grid occupies large number of computing resources or processors. To address this problem, we present an effective bi-criteria scheduling heuristic called |schedule optimisation with duplication-based bi-criteria scheduling algorithm| (SODA). The proposed approach comprises two stages: 1) duplication-based scheduling – optimises the primary criterion, i.e., execution time; 2) compaction of schedules – minimises the processor requirements and optimises secondary criterion, i.e., economic cost without increasing the makespan obtained in primary scheduling. The experimental results reveal that the proposed approach generates schedules with low processor requirements which are fairly optimised for both economic cost and makespan for executing DAG applications in the grid environments.

Keywords: grid computing; bi-criterion scheduling; directed acyclic graph; DAG scheduling; optimisation; duplication-based scheduling; economic cost; schedule compaction.

DOI: 10.1504/IJCNDS.2010.034952

International Journal of Communication Networks and Distributed Systems, 2010 Vol.5 No.3, pp.331 - 346

Published online: 31 Aug 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article