Job Scheduling Algorithms in Cloud Computing

Min-Min Scheduling

The main idea of the Min-Min algorithm is to map each task to resources which can complete the task in the shortest possible time. The min- min algorithm estimates the execution and completion time of each job on each available resources. It is two-phase in the Min-Min algorithm.

1.It calculates the minimum execution time for all tasks.

2.The task with the least execution time among all the tasks is chosen. The algorithm further proceeds by assigning the task to the resource that produces the minimum completion time. The same procedure is repeated until all tasks are scheduled.

Max-Min Scheduling

The working of the Max-min algorithm is similar to the Min-min algorithm. The differentiating feature is as per the name as the word “minimum” is replaced by “maximum” similarly, here the task having the maximum earliest completion time is assigned to the corresponding resource. Here, larger tasks are given priority over the smaller tasks.

Max Min is similar to the min- min algorithm except the following: after finding out minimum execution times, the maximum value is selected which is the maximum time among all the tasks on the resources. Then according to that maximum time, the task is scheduled on the corresponding machine. The execution time for all other tasks is updated on that machine and assigned task is removed from the list of the tasks that are to be assigned to the machines.

 

Resource-Aware-Scheduling (RASA)

RASA is a hybrid scheduling algorithm composed of two traditional techniques- Max-min and Min-min. The min-min strategy is used to execute small tasks before large tasks and Max- Min strategy is applied to avoid the delays in large tasks execution.

Both the strategies are used alternatively for tasks and alternative exchange results in the consecutive execution of a small and a large task on different resources hence ignoring the waiting time of the small tasks in the Max-min algorithm and the waiting time of the large tasks in the Min-min algorithm.

Example

Ant Colony Scheduling

• Ants navigate from nest to food source.
• Shortest path is discovered via Pheromone Trails.
• Each ant moves at random.
• Pheromone is deposited on path.
• More pheromone on path increases probability of path being followed.
• In context of Cloud Computing, “food” implies virtual machines and “ants” implies jobs. The path which is rich in pheromone is mostly chosen by other ants.
• In the ACO algorithm, the load is calculated on each host taking into account the CPU utilization made by all the VMs that are executing on each host. This metric is useful for an ant to choose the least loaded host to allocate its VM.

ACO in Cloud Computing Method

Step 1: Perform initialization of the pheromone
Step 2: while (stopping criteria not reached) do
Step 3: Set locations of all ants in an initial Virtual Machine
Step 4: while (all ants have not reached at a solution) do
Step 5: for each ant do
Step 6: Choose VM for the subsequent task using the intensity of pheromone trail
Step 7: end for
Step 8: end while
Step 9: Update the pheromone
Step 10: end while
Step 11: end

Bee Colony Scheduling

The BCO algorithm is based on the activities of bees while searching for nectar and sharing the information with other bees.

There are three types of agents –

• employed bees
• onlooker bees
• scout bees

The employed bee stays on a food source and provides its surroundings in memory; the onlooker acquires this data from the employed bees and selects one of the food sources to forage, and the scout performs the task of finding new nectar sources

BEE Colony Algorithm Flowchart

Comparison

Algorithms	Scheduling principle	Allocation Order	Findings	Type of system/environment
Min-Min	execution and completion time	Least exec time task assigned to resource producing min completion time	increase resource utilization rate	Batch system
Max-Min	completion time	Max earliest time task assigned to resource	small task delays for long time	Batch system
RASA	Make Span has to be reduced	number of resources decide the strategy	reduce make span	Batch system
Honeybee	Scout bees forage the food source	Each class performs Waggle dance and advertise about food source	Reduced makespan and improved performance	Cloud Environment
ACO scheduling	Pheromone updating rule	Loads each VM And defines load balancing factor	Reduced time, improved results by local Search	Cloud Environment