2.1. Task Scheduling and Load Balancing in Cloud Computing

Cloud computing system creates a shared network resource and service with the user. Due to its diversified, dynamic, and flexible nature, different resources and services offering to different users, are the advantages of cloud computing. It provides a service upon user's request [24,30]. Cloud service providers offer various cloud services to user [22,23]. Resource management in cloud computing varies depending on the kind of user's request.

Heterogeneity in cloud computing depends on the infrastructure and service provided by providers. In case of providing the system with the same infrastructure to software packages and resources, the environment in the system will be called homogeneous cloud environment [31], while the environment in a system with different resources are provided by different providers, software packages by some other, infrastructure by yet another will be called heterogeneous cloud environment [32].

Over the last few years, exhaustive researchers have proposed several different task scheduling algorithms which run under the cloud computing resource utilization. Task scheduling algorithms mostly aimed to balance the workload that users requested for within the limitation of the system resources and to increase the efficiency of cloud computing. For example, Chase et al. [33] presented implementation of an architecture for resource management for large server clusters in order to provision server resources for co-hosted services and improve the energy efficiency of server clusters by dynamically resizing the active server set.

In 2009, D. Kusic et al. [34] presented a lookahead control scheme to solve a dynamic resource provisioning framework for a multi-objective optimization in a virtualized server environment. The technique can approach accounts for the switching costs incurred while provisioning VMs and explicitly encodes the corresponding risk in the optimization problem.

In 2011, D. Minarolli and B. Freisleben [35], proposed a scheme that dynamically allocates the resources to VMs. Such that quality of service constraints is satisfied, and its operating costs are minimized by a two-tier resource management approach based on adequate utility functions. Later in 2012, A. Gorbenko and V. Popov [36] proposed a logical model to solve the task-resource scheduling problem that minimized the resource and cost by applying algorithms for the satisfiability problem (SAT).

In 2013, S. Son et al. [37] proposed a Service Level Agreement (SLA) based on cloud computing framework to facilitate resource allocation considering the workload and geographical location of distributed data centers. This approach was suggested to tackle using the automated SLA negotiation mechanism and a Workload and Location-aware Resource Allocation scheme (WLARA) supports providers in earning higher profits. In 2015, A. Singh and K. Dutta [38], presented the resource allocation algorithm by Analytic Hierarchy Process (AHP) with a pairwise comparison matrix technique. This proposed technique made a better resource allocation than other algorithms. In 2017, Ullah et al. [39] presented a real-time resource usage prediction system which took real-time utilization of resources and fed utilization values into several buffers based on the resource types and time span size. Scheduling problem have been also discussed in different contents as in Refs. [40–42].

2.2. Related Work about Bioinspired and Meta-Heuristics Algorithms to Solve Cloud Computing

The nature-inspired metaheuristics algorithms attempt to attain the global optimal solution by examining the most suitable locations in the search space domain, based on the natural mechanism. The methods are different depending on type of algorithms, because some algorithms are suitable in solving specific type of problems but not suitable for others. This is due to the randomization or stochastic strategies that are used in solving those NP-Hard problems.

There are many previous works had proposed many metaheuristic-based approaches to scheduling workflow applications [43]. In particular, Genetic Algorithms (GA) [44,45], Particle Swarm Optimization (PSO) algorithms [46–49], Cuckoo Search (CS) algorithm [50–54], and Ant Colony Optimization (ACO) algorithm [55–56] have been used for scheduling workflows. For instance, Dasgupta et al. [45] proposed GA which is a balance the load of the cloud and minimizing the make span of a given tasks set. In 2010, S. Pandey et al. [46] proposed a PSO based heuristic to schedule applications to cloud resources that considers both computation cost and data transmission cost.

In 2019, H. Saleh et al. [49] proposed a cloud task scheduling with improved PSO (IPSO) algorithm that minimizes makespan and uses the resources in the system to the best advantage for a large number of tasks. T. P. Jacob and K. Pradeep [54] proposed hybrid algorithm is called as, CS algorithm, and particle swarm optimization (CPSO) for multi-objective-based task scheduling. They focused on the comparison of processing in terms of minimization of makespan, cost, and deadline violation rate in the heterogeneous cloud environment.

Many researchers had proposed approaches using metaheuristic-based to QoS-aware cloud service composition and cloud migration problem. In 2010, W. Li and H. Yan –xiang [57] developed a Chaos Particle Swarm Optimization (CPSM) method and provided a novel selection algorithm based on global QoS optimizing to solve QoS-aware service composition.

In 2014, Wang et al. [58] presented a modified GA to support data-intensive service composition. The research idea is to reduce the cost of service composition that involves large amounts of data transfer, data placement, and data storage.

In 2016, L. Wang and J. Shen [59] presented ant colony system for the dynamic service composition problem multi-phase, multi-party negotiation protocol. The ant colony system was applied to select services with the best or near-optimal utility outputs. Ferdaus et al. [60] proposed a novel ACO-based Migration impact-aware Dynamic VM Consolidation (AMDVMC) algorithm in order to solve the Multi-objective, Dynamic VM Consolidation Problem (MDVCP) in computing clouds for minimizing data center resource wastage, power consumption, and overall migration overhead due to VM consolidation.

In 2019, S. K. Gavvala et al. [61] proposed a novel Eagle Strategy with Whale Optimization Algorithm (ESWOA) with eagle strategy to balance the exploration and exploitation in QoS-aware Cloud service composition.

2.3. Overview of the ABC Algorithm

ABC algorithm [1,2,62] is an optimization technique for finding an optimal solution. It was inspired by the foraging behavior and collective work of different kinds of bees. In a bee colony, there are 3 types of artificial bees: Scout bees with a duty to randomly search for new food sources, Employed bees that go to the food sources and come back to dance in the hive according to the position and the amount of the food to Onlooker bees that are waiting in the hives, and the last one is Onlooker bees that calculate the fitness value of each food source and choose the optimal source for the Employed bees to go to and collect the food.

If a food source was chosen and all the food was collected, the Employed bees which are the owners of the food source will turn into Scout bees and randomly search for new food sources again. In nature, bees communicate the quality of food sources at a dance floor. They dance a “Waggle Dance” to inform others about the direction to go, the distance from a food source, and the amount of honey of a food source. The Onlooker bees compare all of the food sources and determine the best one. The steps in the ABC algorithm are shown in Figure 1.

Figure 1

Flowchart of Artificial Bee Colony (ABC) algorithm

ABC algorithm was used in many fields such as job shop scheduling [6,7], binary optimization [8–10], travelling salesman [11], digital signal processing [63], and so on. For example, Mizan et al. [18] presented job scheduling in Hybrid cloud by modifying Bee Life algorithm and Greedy algorithm to achieve an affirmative response from the end users and utilize the resources. Accordingly, the objective of this study is to optimize task scheduling, resource allocation, and load balancing using applying Heuristic Task Scheduling with Artificial Bee Colony (HABC) based on the proposed reducing or minimizing makespan in cloud computing environment. This research focused on both cases of homogeneous and heterogeneous environments and investigated how efficient the HABC algorithm performed when the tasks in the system were increased and the data distribution was changed.

3.1. Heuristic Scheduling Algorithm

Heuristic method is an approach to problem solving using rules such as priority rule or using a random method to find an optimal solution for a problem. A heuristic method may provide a good result, but it cannot guarantee an optimal solution. Nevertheless, it is simple to use. A heuristic task scheduling with priority as a criterion for selecting a process in a system was used in this study because it is a basic method for scheduling tasks [64,65]. We selected the following 3 simple priority criteria for investigation [66]:

• First Come First Serve (FCFS): is a task scheduling scheme that processes the first job that the user has requested first.

• Smallest Job First (SJF): is a task scheduling scheme that processes with the smallest job first

• Largest Job First (LJF): is a task scheduling scheme that processes the largest job first.

3.2. Proposed Method

Let VM=vm1,vm2,vm3,…,vmm, variables used in this study and their definitions derive from Table 1. Let the system be set to run in an uninterruptible manner, i.e., nonpreemptive. Before the ABC algorithm was run, the tasks were arranged into 3 different arrangements by using the Heuristic algorithms. The best arrangement would use the least computation time when the tasks were processed by the ABC algorithm as mentioned above. The ABC algorithm then scheduled the tasks to access the VMs in the following steps:

1. First step: the number of bees (n) in the population was specified. They were assigned randomly to go to all of the different food sources (m) that represented the VMs and their fitness values were calculated, therefore initializing the VMs as shown in Algorithm 1.

   Algorithm 1: Initialization

   1. For i = 1 to n

   2. Send the population of bees into the system to find appropriate VMs by Random search.

   3. Calculate the fitness of each VM by using (1)

   Cj=Pej×Mij+Bwj(1)

   where j = index of the VM that the i^th bee found.

   4. End For

2. Second step: a different default value was assigned to each food source according to the specifications of the VM. Bees were grouped into 3 types: Scout Bees, Employed Bees, and Onlooker Bees. A Scout Bee found the initial position of a food source. An Employed Bee went to the food source, recalculated and updated the fitness value of food source. An Onlooker Bee decided which food source was the best food source. The operation of an employed bee is presented in Algorithm 2.

   Algorithm 2: Employed bee phase

   1. For i = 1 to n

   2. Employed bees are sent randomly to food sources (VMs in cloud computing).

   3. Fitness of each VM is calculated based on (2)

   Fij=∑i=1nTlijEvaluate capacity of VMj Cj(2)

   4. Update the fitness value

   5. End For

3. Third step: the Employed bees have searched around for food sources, they brought back information about the food sources to the Onlooker bee. The Onlooker bee then recalculated the fitness values of the food sources. The operation of the onlooker bee is shown in Algorithm 3.

   Algorithm 3: Onlooker bee phase

   1. The onlooker bee chooses the first m food sources (VM) with the highest fitness values and perform “Neighborhood Search” around the food sources

   2. An nsp number of employed bees are sent to bring back new positions of the first m food sources while a nep number of employed bees are sent to all food sources to bring back new positions of these food sources; all of them come back to relay the information to the onlooker bee

   3. The onlooker bee calculates the new fitness values of the food sources according to (3),

   fitij=∑i=1nTli+InlengthEvaluate capacity of VMj Cj(3)

   where Inlengthis the length of the task that is waiting to access a VM at that time

   4. The onlooker bee chooses the best food source (VM) and assigns a task to the VM

4. Fourth step: the employed bee that was the owner of the best food source was then transformed into a scout bee. The operation of a scout bee is shown in Algorithm 4.

   Algorithm 4: Scout bee phase

   1. If food source = null then

   2. Send the previously transformed scout bee into the system to find an appropriate VM by Random search.

   3. Calculate the fitness value of that VM by using (1)

   4. End If

5. Fifth step: the overall operation of HABC algorithm is described in Algorithm 5.

   Algorithm 5: Improved HABC Algorithm

   Input: Dataset, Bee's Parameters;

   Output: Minimum makespan;

   1. Initialize the individual in the population.

   2. Set the default values of the food sources (VM) by using (2).

   3. Initialization (Algorithm 1)

   4. Repeat

   5. Employed bee phase(Algorithm 2)

   6. Onlooker bee phase (Algorithm 3)

   7. Calculate the load balance value of the system after task scheduling on VMs. It is calculated by using Standard Deviation (S.D.) [67] as in (4) and (5),

   S.D.=1n∑j=0nXj−X¯2(4)

   imbalance=Xmax−XminXavg(5)

   The processing time for each VM (X_j) is calculated according to (6),

   Xj=∑i=1ktask_lengthicapacityj(6)

   The average processing time for running a VM in the system (X¯) is calculated according to (7),

   X¯=∑j=1nXjn(7)

   If S.D. ≤ X¯, it means that the system is in a balanced condition whereas if S.D. ≤ X¯, it means that the system is in a state of imbalance.

   8. Scout bee phase (Algorithm 4)

   9. Until (the termination condition is met)

4.1. System Environment Parameter Settings

The algorithms: HABC, ACO, PSO, and IPSO described were run using CloudSim-3.0.1 [68,69] tools on a personal computer. The experiments were performed on 10 data centers and 50 VMs. In the experiments, we focused on both kinds of environments: homogeneous and heterogeneous environments in cloud computing.

For each VM in cloud computing within a homogeneous environment, the following parameters were set: Instructions Per Second in millions (MIPS is a measurement of the processing speed of a computer) of Processing Element (PE) were fixed at 9726; Number of PE per VM was fixed at 1; and RAM used was fixed at 1024 Megabytes (MB).

For each VM in cloud computing within a heterogeneous environment, the following parameters were set: MIPS were in the range of 5000–9726; Number of PE per VM was fixed at 2; RAM used was set in the range of 512–4096 MB; and Bandwidth was set in the range of 1000–10000.

4.2. The Datasets Used in the Experiments

To evaluate the effectiveness of the proposed approach, twelve datasets, shown in Table 2, were used. Those datasets were of 4 types. The set D₁–D₃ of the first type was a set of random information, i.e., there are no definite terms, no specific format, and no specific distribution of information. The set D₄–D₆ of the second type was a set of random data with normal distribution. The set D₇–D₉ of the third type was a set of random data with a Right-Skewed Distribution [70]. Lastly, the set D₁₀–D₁₂ of the fourth type was a set of random data with a Left-Skewed Distribution. Each type of datasets had a different range of job size and each dataset comprised a number of groups of 100, 200, 300, …, 1500 submitted tasks.

4.3. Parameters Settings for the Proposed Algorithm and the Comparing Algorithms

In these experiments, we have determined the parameters of the population and various conditions according to the related works, which are referred to HABC [20], ACO [55,56], PSO [48], and IPSO [49]. It is well known that these parameters are highly effect on the algorithms. The determination of parameters is varied according to the dimension of problems or characteristics. One reason that we need tuning the parameters [20] is in order to get the suitable parameters for the pattern of problems and datasets. However, we do not claim that the proposed algorithm or the specified parameters outperform other algorithms for all types of problems and datasets. Therefore, tuning parameters is the best way to get the suitable parameters to solve problems.

The experiments had been performed to determine the optimal bee parameters for the proposed algorithm [20] which are shown in Table 3. In addition, the scheduling performance of the proposed algorithm was also compared with those of ACO [55,56], PSO [48], and IPSO [49] that used the parameter settings as shown in Table 3.

Those optimal settings were based on the original papers. The number of iterations that each algorithm would be run in the experiment was 20.

4.4. Experimental Results and Discussions

In one of our previous papers [20], the performances of the proposed algorithm in combination with 3 heuristics-HABC_FCFS, HABC_LJF, and HABC_SJF-were compared with those of the heuristics alone-FCFS, LJF, and SJF. The results of previous experiments showed that when the largest job was considered first (HABC_LJF), its scheduling performance was better than those of HABC_FCFS and HABC_SJF.

The HABC_LJF also balanced the load of submitted tasks with minimal makespan. In this paper, we used 2 VM environments: heterogeneous and homogeneous to evaluate the performance of HABC_LJF method on different datasets and to compare it with other scheduling algorithms. The number of VMs was fixed throughout the experiment but the number of tasks was increased in 100 incremental steps from 100 to 1,500 tasks.

In the evaluation of the performance of HABC_LJF algorithm in cloud computing, we divided our experiment into two parts. In the first part, the datasets of various types as described in Table 3 were used. In the second part, the performance of the heuristic task scheduling with ABC in terms of load imbalance was evaluated. In the first part, the performance evaluation was performed on 4 cases according to the type of datasets used. The following are the results of the 4 cases for evaluation of the makespan.

Case 1: Random datasets

The makespan of HABC_LJF running on random datasets D₁–D₃ was compared with those of ACO, PSO, and IPSO algorithms. The number of groups of submitted tasks was varied in each run from 100 to 1500 submitted tasks in an increment of 100 tasks. The average makespan for 300, 900, and 1,500 tasks in cloud computing within homogeneous and heterogeneous environments are shown in Tables 4 and 5, respectively. Actually, a higher number of tasks were run but the results are not shown here due to lack of space.

According to Table 4, HABC_LJF performed the best as the number of tasks was increased. Moreover, the minimum makespan, the maximum makespan, and the average makespan, all three of them were the lowest. The performance of HABC_LJF was outstanding in the homogeneous environment.

In addition, in order to observe the effect of the range of job size on performance scalability of the system, we evaluated the average makespan with three datasets that had different ranges of job size (D₁–D₃). The results show that the HABC_LJF algorithm also outperformed the others for all size ranges tested in the homogeneous environment.

The results for the average makespan of HABC_LJF algorithm and the other algorithms with an increasing number of submitted tasks in cloud computing within a heterogeneous environment when used with random datasets are shown in Table 5. The performance of HABC_LJF was the best because its minimum makespan, maximum makespan, and average makespan were mostly the lowest in cloud computing within a heterogeneous environment. Furthermore, when datasets with different ranges of job size were used, HABC_LJF still outperformed the others in the same way that it did in homogeneous environment.

Case 2: Random data with a normal distribution

Table 6 shows the makespan of every algorithm tested with datasets (D₄–D₆) : random datasets with normal distribution. The results showed that the HABC_LJF used the lowest minimum makespan, the lowest maximum makespan, and the lowest average makespan than the other algorithms did in the homogeneous environment.

The makespan of the algorithms working within a heterogeneous environment when random datasets with normal distribution were used are shown in Table 7. The results show that for the datasets that had different ranges of job size, HABC_LJF outperformed the others in the same way as they did in a homogeneous environment except for the case of dataset D₄ and D₆. For the case of dataset D₄with the number of submitted tasks equaled to 900, the ACO_LJF gave the lowest minimum makespan. Meanwhile, the D₆ dataset with 900 submitted tasks in which ACO_LJF used the lowest minimum makespan and ACO_SJF used the lowest maximum makespan. However, this makespan was not very different from that used by HABC_LJF. When the makespan for all cases were considered, HABC_LJF still outperformed the other algorithms.

Case 3: Random data with Right-Skewed Distribution

Tables 8 and 9 show the results obtained from using datasets (D₇–D₉)—random datasets with Right-Skewed Distribution—in homogeneous and heterogeneous environments, respectively. The experimental results indicate that HABC_LJF used the lowest minimum makespan, the lowest maximum makespan, and the lowest average makespan than the other algorithms did in the homogeneous environment. The results were the same as in Case 1.

In the same direction, HABC_LJF outperformed the other two algorithms in a heterogeneous environment except when D₉ was used with the number of submitted tasks equaled to 900 and 1500 tasks. For the case of 900 tasks, ACO_FCFS used the lowest minimum makespan. For the case of 1500 tasks, ACO_LJF used the lowest maximum makespan. Nevertheless, in both cases, the minimum makespan used by ACO_FCFS and ACO_LJF were not very different from that used by HABC_LJF. Overall, HABC_LJF still outperformed them both.

Case 4: Random data with Left-Skewed Distribution

The makespan of HABC_LJF were compared with those of ACO, PSO, and IPSO algorithms running on Left-Skewed Distribution (D₁₀–D₁₂) datasets. Their minimum, maximum, and average makespan in cloud computing within homogeneous and heterogeneous environments are shown in Tables 10 and 11, respectively.

The results in Table 10 show that HABC_LJF outperformed the other three algorithms in a homogeneous environment. The results were the same as in other case.

In the same direction, HABC_LJF outperformed the other three algorithms in a heterogeneous environment except for one case: when using D₁₁ dataset with 900 submitted tasks, the ACO_LJF gave the lowest maximum makespan but this makespan was not much different from that of HABC_LJF. When the makespan of all cases were considered, the HABC_LJF still outperformed the others.

In the second part, the performance of the HABC algorithm in terms of load imbalance was evaluated. Unbalanced workload for VMs can be avoided by balancing the workload during allocation. The datasets of various types were used as described in Table 3. Four cases of performance evaluation were considered according to the type of datasets used. The number of groups of submitted tasks was varied in each run from 100 to 1500 in an increment of 100 tasks. Performance evaluation was also done separately for the homogeneous and heterogeneous VM environments to obtain the average degree of load imbalance of 20 runs for each algorithm. The degrees of load imbalance in cloud computing within the homogeneous and heterogeneous environments are shown in Figures 2 and 3, respectively.

Figure 2

Degrees of load imbalance in a homogeneous environment when Heuristic Task Scheduling with Artificial Bee Colony (HABC), Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), and improved PSO (IPSO) were used with (a) datasets D₁ - Random dataset, (b) datasets D₄- Normal distribution dataset, (c) datasets D₇- Random dataset with left-skewed distribution, (d) datasets D₁₀ - Random dataset with right-skewed distribution.

Figure 3

Degrees of load imbalance in a heterogeneous environment when Heuristic Task Scheduling with Artificial Bee Colony (HABC), Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), and improved PSO (IPSO) were used with (a) datasets D₁ - Random dataset, (b) datasets D₄- Normal distribution dataset, (c) datasets D₇- Random dataset with left-skewed distribution, (d) datasets D₁₀ - Random dataset with right-skewed distribution.

As shown in Figure 2, in order to consider the effect of different types of dataset on performance scalability of the system, we evaluated the average degrees of load imbalance with four datasets of different types: D₁, D₄, D₇, and D₁₀. The results show that the HABC algorithm (HABC_FCFS, HABC_LJF, HABC_SJF) performed lower average degrees of load imbalance than any of the compared algorithms (PSO and ACO algorithms) in the homogeneous environment.

In the same direction, the results in Figure 3 showed that the HABC algorithm (HABC_FCFS, HABC_LJF, HABC_SJF) outperformed the other two algorithms in the heterogeneous environment.

In the tuhird part, the performance of the HABC algorithm in terms of Standard Deviation (S.D.) was evaluated. In order to ensure that the tasks are equally distributed into VMs and the system is balanced workload.

We evaluated the S.D. with dataset D₁ in Table 3. The number of groups of submitted tasks was varied in each run from 100 to 1500 submitted tasks in an increment of 100 tasks. The S.D. for 300, 600, 900, 1200, and 1500 tasks in cloud computing within homogeneous and heterogeneous environments are shown in Tables 12 and 13, respectively. Table 12 shows the S.D. of all tested algorithms with datasets (D₁) in homogeneous environment. The results show that HABC algorithm has less S.D. values than other methods. In the same direction of heterogeneous environment in Table 13.

The result of the experiment indicated that the makespan and the degree of imbalance are slight difference. On the other hand, if considered the performance measurement using S.D. between the HABC algorithm and ACO algorithm are very different. The results show that HABC algorithm highly enhanced the S.D. compared to the other algorithms in cloud computing within homogeneous and heterogeneous environments. The goal is to achieve a balance between the resources in the system and to minimize the makespan time.

To summarize, even though all of the presented algorithms utilize a similar scheduling process based on a heuristic method. When they were compared, the HABC algorithm was able to show a better performance than those shown by ACO, PSO, and IPSO algorithms, especially in the case of using large job submitting first (HABC_LJF). Moreover, the system still balanced the load of submitting tasks adequately with minimum makespan.