An effective compaction strategy for bi-criteria DAG scheduling in grids. (1st September 2010) - Agarwal, Amit; Kumar, Padam
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.