An effective compaction strategy for bi-criteria DAG scheduling in grids. (1st September 2010)

• Record Type: Journal Article
• Authors: Agarwal, Amit; Kumar, Padam
• Is Part Of: International journal of communication networks and distributed systems. Volume 5:Number 3(2010)
• Page Start: 331
• Page End: 346
• Publication Date: 2010-09-01
• Subjects: grid computing -- bi-criterion scheduling -- directed acyclic graph -- DAG scheduling -- optimisation -- duplication-based scheduling -- economic cost -- schedule compaction; Computer networks -- Periodicals; Telecommunication systems -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; 004.6
• Languages: English
• ISSNs: 1754-3916

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.