Performance Analysis of Workflow Scheduling Algorithm in Cloud Computing Environment using Priority Attribute

Abstract

Workflow scheduling is represented by a well known graph that is Directed Acyclic Graph (DAG)  and

the  scheduling problem is also known as NP-complete. There are number of heuristics algorithms has been developed for workflow scheduling and its primary objective to minimize the overall execution time that is scheduling length of the tasks of a given DAG. This paper presents new algorithm for workflow scheduling in cloud computing environment using priority attribute. The priority attribute is  computed by using adjacency matrix which consists  of the communication time between the tasks.  If there is a  direct path between the tasks then assign its communication time as matrix element otherwise zero in the matrix. Then after ,find maximum column element allocated into max array. This algorithm is worked in two phases such first phase compute max array and sort the max array as per their  attribute value. Second phase,  to remove entry task(s) from priority queue  and allocate entry task as duplicate into all available virtual machine. To allocate non entry if satisfied precedence constraint otherwise insert at end of the queue. The propose algorithm is compared with well known four heuristic algorithms such as Heterogeneous Earliest Finish Time(HEFT), Critical-Path-on-a-Processor(CPOP), As Late As Possible(ALAP), and Performance Effective Task Scheduling (PETS) algorithms. The performance analysis of the algorithms has been done based on well known metrics such as speedup, efficiency, scheduling length ratio, cost and resource utilization. The proposed algorithm gives good results in respect of performance metrics as compared to four heuristic algorithms.

 Keywords: DAG, Scheduling Length, Cloud Computing, Speedup, Efficiency , Critical Path.