Preemptive Scheduling with Honey Bee Foraging

Extended bee algorithm utilizes divisible load scheduling theorem and follows honey bees’ foraging behavior. A new agent model is suggested to reduce network delay and to increase throughput. The authors have mapped the dancing floor of honey bees to the routing table in the network. A new algorithm based on the transportation problem is presented in [11] to provide a fault tolerant cloud computing environment in such a way to maximize the cloud providers’ profit, minimize the execution cost, resource allocation cost, total turnaround time, total waiting time and the total execution time. With a focus towards contributing to the green environment, an energy-aware dynamic resource allocation framework for cloud data centers has been suggested in [12]. The fully distributed algorithm (DRA) in [13] focused on minimizing resource consumption. Applications that are running in tree-structured and hierarchical networks are considered here. DRA is extended to reduce the network cost and to check the capacity of destination nodes before migration.

In [14], the authors suggested a dynamic task scheduling algorithm applying the genetic algorithm with an aim to attain optimal mapping of tasks to resources thereby minimizing the makespan. They also worked towards reducing the task failure rate based on the failure frequency rate and decreasing the task starvation rate by scheduling the tasks based on a special ordering. The tasks’ order preference is based on parameters like priority, workload, deadline, and wasted time. Honey bee behavior inspired load balancing (HBB-LB) [16] is a dynamic algorithm which balances the load on VMs such that it maximizes the throughput by scheduling tasks in a non-preemptive manner. It mimics honey bees’ foraging behavior to perform load balancing and also considers the priority of tasks to reduce their waiting time.

A new hybrid scheduling algorithm has been devised for scheduling real-time divisible loads in computing clusters in [15]. Here the scheduling process is distributed among two components named the admission controller and the dispatcher. This algorithm partitions each task by applying divisible load theory (DLT) and also incorporates all nodes assignment (ANA) policy and minimum node assignment (MNA) policy in to the admission controller to reduce the scheduling overhead. MNA policy is applied when the waiting queue length is small whereas ANA policy is applied when the waiting queue length is large. The authors have considered the average scheduling time and the real-time performance of the algorithm as the performance metrics. Weiwei Lin et al proposed a bandwidth-aware task-scheduling (BATS) algorithm [21] for scheduling the tasks to the VMs.

The algorithm considered network bandwidth as the additional resource along with CPU and memory resources. They also tried to optimize the above mentioned resources. But the total completion time of all the tasks (makespan) is the only metric that was considered to evaluate the performance of the algorithm. All the above methods do not consider multiple QoS metrics such as makespan, response time, execution time, number of task migrations, and task priority to optimize task scheduling and to balance the load on the system. Inorder to optimize task scheduling for performing load balancing, an improved version of HBB-LB [15] is proposed by incorporating preemptive scheduling and also considering the above metrics. During preemption, priority and expected remaining completion time of the tasks are also considered.

Honey Bee Foraging for Collective Decision Making

Honey bees are social insects which are well known for their decision making capability that is obtained through their foraging behavior [17-19]. Honey bees search for their food sources and select the best among the available food sources by means of their foraging activity. Forager bees are involved in finding the food source for the other bees in the bee hive. There are two kinds of foragers: employed foragers and unemployed foragers. The employed foragers are bees that are associated with a particular food source. They share the information such as distance, direction, and profitability of their associated food source with the other bees in the nest through a kind of dance called waggle dance [16-20].

The profitability is based upon the factors such as nearness to the food source, concentration of energy, and the effort required for pulling out the energy. Unemployed foragers are those looking for a food source to make use of it. They are of two types: scouts, which search the environment surrounding their nest for the food sources and the onlookers, which will wait in their nest to receive information from employed foragers to find the food sources. Onlookers will have the information about all food sources perceived from the waggle dance and will be able to select the most profitable one among the available sources. An employed forager continues consuming its food source and becomes an unemployed forager when its food source exhausts.