# Balancer Genetic Algorithm--A Novel Task Scheduling Optimization Approach in Cloud Computing
#### 3.2.6 Bancer Operator
After the assignment, if the VM share drops below 0 the respective task is added to a pool of tasks, which is later used in remapping. After the traversal of the last gene, VMs are sorted according to their remaining VM share in \(VM_{pool}\). Tasks in \(cloudlet_{pool}\) are also sorted in descending order. The maximum sized task in the task pool is mapped to VM with the maximum remaining VM share. The \(cloudlet_{pool}\) and \(vm_{pool}\) both are updated accordingly. This process of remapping continues until there are no remaining tasks in \(cloudlet_{pool}\). #### 3.2.7 Fusion of Heuristic

A load balancing mechanism is embedded in GA to have the tendency of load balancing in a chromosome. This provides additional guidance to GA. Using a heuristic just at the initialization phase cannot have a significant impact. The benefit of fusing the balancer mechanism is that it balances the chromosomes based on their VM share. BGA explores the large search space where there are many possible solutions. Consequently, a large number of chromosomes pass through the balancer operation. It is possible to explore many solutions in which the load balancing is the same, but the fitness value varies according to their makespan, and this could not be achieved otherwise. ## 4 Performance Metrics

To evaluate the performance of BGA, we compared it with benchmark techniques. To this end, the following performance metrics are used:

### Makespan

Makespan is the finishing time of batch of tasks and is calculated as:

\[ \begin{array}{c}\mathit{makespan}=\mathit{max}(CT\_VM\_j),\\ j=1,2,...,n\end{array}  \tag{9}\]

where \(CT\) is the completion time of a specific VM, and the maximum time taken by any VM is the makespan. ### Arir

ARUR is the average resource utilization ratio, and it is between 0 and 1, where 0 represents minimum and 1 maximum resource utilization. It is computed through completion time as:

\[ARUR=\frac{(\sum_{j=1}^{n}CT_{VM_{j}})/n}{\mathit{makespan}} \tag{10}\]

## 5 Experimental results and Discussion

This section details the experimental setup and dataset used in the experimentation. The benchmark techniques are also defined, and then the results are expressed with necessary discussion. ### Experimental Setup

CloudSim [37] is used to simulate the cloud-based environment for experimentation. All experiments are performed using the same settings mentioned for the benchmark techniques. However, the number of iterations are fixed to 1000 for all meta-heuristic techniques as a stopping criterion. One data center is created in cloudsim. The data center has 30 host machines and a total of 50 VMs. The RAM of host machines is 16,384 MBs. Host machines have a Linux Operating System, and 4 machines are dual-core whereas 26 machines are Quad-core. Dual and Quad-core machines have processing power of 4000 MIPS. The space sharing VM scheduling algorithm of CloudSim is used for experimentation. The processing power of 50 heterogeneous VMs is detailed in Table 2.

### Workload Generation

A synthetic dataset [2; 24] is used, and it has four different categories which are defined as follows:

1. Left Skewed: Large-sized tasks are numerous. 2. Right Skewed: Small-sized tasks are numerous. 3. Normal: Small- and large-sized tasks are almost equal in number. 4. Uniform: Tasks are of almost same sizes. These four categories can better express the overall behavior of BGA on different possible workloads. Each category has batches of 100, 200, 300, 400, 500, 600, 700, 800, 900 and 1000 tasks. ### Benchmark Techniques

Table 3 lists the baseline techniques used for the performance evaluation. _MGGS_[13] is selected because it has a load balancing mechanism embedded in GA. BGA also has the same method of fusing the load balancing mechanism, but the working of GA and the mechanism of load balancing are unique. _ETA-GA_[18] is compared as it is a pure GA-based technique. _DSOS_[24] is a meta-heuristic, and _RALBA_[3] is a state-of-the-art heuristic technique. All of these techniques are compared with BGA.