Myopic
It is an individual task scheduling heruristic
It is the simplest scheduling method for scheduling workflow applications.
It makes scheduling decisions based on individual task.
System Implemented : Condor DAGMan
It schedules an unmapped ready task in arbitrary order to the resource, which is expected to complete the task earliest.
Min-min
This prioritizes workflow tasks based on their priorities
It assigns task priority on the basis of its expected completion time (ECT) on a resource.
It organizes workflow tasks on the basis of its expected ECT on a resource.
It organizes WF tasks into several independent task groups
schedules each group of independent tasks interactively.
In every iteration, it takes the set of all unmapped independent tasks T.
generates the minimum ECTs (MCT) for each task t in T where MCT t = min ECT (t,r) or every resource in R.
** It considers all unmapped tasks during each mapping decision.
In comparison, Myopic only considers one task at a time.
Systems implemented in : vGrADS, Pegasus
http://vgrads.rice.edu/
Max -min
It is similar to min-min
it sets the priority of the task to that which requires the longest execution time rather than shortest execution time.
At
each iteration after attaining MCT values for all unmapped independent
tasks, tasks having maximum MCT is chosen to be scheduled earliest. Any
attempts to minimize WF execution time by assigning longer tasks to
comparitively best resources.
System Implemented in : Pegasus
HEFT (Heterogeneous Earliest Finish Time)
It is a list scheduling algorithm
gives higher priority to WF task having higher rank value
rank value:
It is calculated by utilizing avg. execution time for each task and
avg. communication times between resources of two successive tasks.
Tasks in CP have comparitively higher rank values.
It sorts the tasks in decreasing order of their rank values.
tasks with higher rank value have higher priority.
tasks are scheduled in order of their priorities.
each task is assigned to the resource that can complete the task at the earliest time.
WF
is represented as DAG and rank values are calculated by traversing the
task graph in BFS (Breadth First Search) manner. in reverse order of
task dependencies.
Advantage over min-min and max-min
while assigning priorities to tasks, it considers entire WF rather than focusing on only unmapped independent tasks.
Systems Implemented :
ASKALON WF manager to provide scheduling for quantum chemistry appln
WIEN2K
Metaheuristics
GRASP: Greedy ranodmized adaptive search procedure
iterative radomized search technique
A number of iterations are conducted to search a possible optimal solution for mapping tasks on resources.
A solution is generated at each iterative step.
best solution is kept as the final schedule.
It terminates when the specified termination criterion (no. of iterations) is satisfied.
* can generate better schedules than other scheduling techniques.
* It searches the whole solution space considering entire workflow and available resources.
GA : Genetic Algorithm
similar to GRASP
It allows high quality solution to be derived from a large search space in polynomial time by applying principles of evolution.
It combines exploitation of best solution from past searches with exploration of new regions of solution space.
Instead
of creating a new solution by randomized search as in GRASP, GA
generates new solution at each step by randomly modifying the good
solutions generated in previous steps.
This results in a better solution.
