Abstract
Cloud computing is gaining a huge popularity for on-demand services on a pay-per-use basis. However, single data centre is restricted in offering the services, as it does not have unlimited resource capacity mostly in the peak demand time. Generally, the count of Virtual Machines (VM) is more in public cloud; still, the security is not ensured. In contrast, the VMs are limited in private cloud with high security. So, the consideration of security levels in task scheduling is remains to be more critical for secured processing. This works intends to afford the optimization strategies for optimal task scheduling with multi-objective constraints in cloud environment. Accordingly, the proposed optimal task allocation framework considers the objectives such as execution time, risk probability, and task priority. For this, a new hybrid optimization algorithm known as Clan Updated Seagull Optimization (CUSO) algorithm is introduced in this work, which is the conceptual blending of Elephant Herding Optimization (EHO) and Seagull Optimization Algorithm (SOA). Finally, the performance of proposed work is evaluated over other conventional models with respect to certain performance measures.
Introduction
‘Cloud computing is a large-scale distributed computing concept, which includes the development of traditional grid computing and distributed computing’. Task scheduling exists as a remarkable issue in cloud environment [6, 14]. It is the process of scheduling the tasks to use the resources in a timely and secured manner. Thereby, the tasks are allocated to the specific resources that makethe better scheduling of the jobs [26, 8]. The major objective of task scheduling is to improve the Quality of Service (QoS) by maintaining the efficacy of task completion, henceminimizing the cost. This strategy can be attained only if the available virtual resources are deployed in an optimal manner to schedule the tasks [23, 34, 22]. With effective scheduling of resources, a better cloud computing environment can be created. In general, the constraints that are regarded in scheduling methods are task completion cost, execution and allocation time, resource utilization and so on [20, 37].
Moreover, the traditional task-scheduling approaches concern more on Central Processing Unit (CPU) memory, task-resource needs, execution cost and execution time [9, 17, 24]. The task scheduling in the cloud computing is regarded as a Non-deterministic Polynomial-time hardness (NP-hard problem), which can be computed by means of certain heuristic schemes. The traditional works have used Particle Swarm Optimization (PSO) algorithm for scheduling the task in cloud [10, 29, 7]. Furthermore, the scheduling models in conventional distributed computing could not employ in an efficient way as it is dynamic and large-scale.
To date, evolutionary algorithms like Genetic Algorithm (GA) and Estimation of Distribution Algorithm (EDA) were introduced for solving many scheduling and mapping problems [27, 5]. Moreover, the optimization algorithms [39, 16] based on single-objective would apply the traditional algorithms including Max-Min, Suffrage, and Min-Min models. However, the existing algorithms related to scheduling provides less extensibility and adaptability. Some other traditional schemes [21, 35, 11] would not consider the security factors endeavored while decreasing the completion time of task [28, 12, 38]. Hence, it is necessary to develop a new task scheduling model [25, 1] that should take account of the security constraints as well. The main contribution of this adopted method is given as follows:
Implements a multi-objective task scheduling model including the constraint like execution time, risk probability, and task priority that ensures secured scheduling process. Proposes a new hybrid optimization algorithm known as Clan Updated Seagull Optimization (CUSO), which is a conceptual blending of Elephant Herding Optimization (EHO) and Seagull Optimization Algorithm (SOA). The proposed method overcomes the drawbacks of the traditional SOA, like high computational cost and easily falling into the local optima and enhances its performance.
In this paper, the review on tasks scheduling in cloud environment is determined in Section 2. Proposed task scheduling scheme: an overview is portrayed in Section 3. Cloud setup and multi-objectives for scheduling the task is portrayed in Section 4. Proposed hybrid task scheduling algorithm: combined elephant herding and seagull optimization is depicted in Section 5. The result and discussion are specified in Section 6. At the end, the conclusion of this paper is depicted in Section 7.
In 2017, Liu et al. [6] has established a multi-task scheduling model, which incorporated task workload model by considering service quantity and service coefficient. Subsequently, the impacts of diverse workload-oriented task scheduling techniques were analyzed in terms of utilization and total completion time. Scenario without or with time parameters were separately analysed thoroughly. Finally, the simulated outcomes have indicated that the large workload tasks with high priority shortened the make span and increased the utilization without affecting the quality.
In 2019, Abazari et al. [33] have designed a novel efficient technique that considered both interaction and tasks security while scheduling the tasks in cloud. Moreover, a heuristic model was used for task scheduling on the basics of task’s completion time and security requirements for improving the security. In addition, a novel attack response method was presented for reducing the definite security risks in the cloud. Furthermore, the outcomes demonstrated that the designed algorithm has reduced the threats, thus enhancing the security of the network.
In 2019, Panda et al. [36] have developed multi-cloud network, where several clouds were integrated mutually for providing a combined service in a mutual manner. On the other hand, the scheduling of task in multi-cloud was highly difficult when compared to single cloud. Three algorithms have been proposed for a multi-cloud network. The presented model depends on the conventional Min-Min and Max-Min algorithm. Finally, the developed model was evaluated with respect to average cloud consumption, throughput, and make span over other approaches.
In 2019, Pang et al. [2] have developed an EDA-GA and GA based hybrid algorithm for task scheduling. Initially, the sampling and probability models of EDA were exploited for generating specific viable solutions. As the final step, the optimum scheduling approach for allocating tasks to VM’s were realized. This model has benefits of stronger searching capability and faster convergence speed. The investigational results illustrated that the presented scheme has efficiently improved the load balancing capability and reduced the completion time.
In 2019, Sanaj and Joe [13] has explored Chaotic Squirrel Search Algorithm (CSSA) for optimal multitask scheduling in an IaaS cloud environment. The technique has generated job plans continuously, which make the present schemes more cost-efficient. To guarantee global convergence, the network was generated with chaotic optimization for well-organized task allocation. Finally, the developed CSSA model has revealed better outcomes when compared over the traditional Squirrel Search Algorithm (SSA) model.
In 2020, Wilczyński and Joanna [26] has introduced a novel method for scheduling the tasks depending on block chain mechanism. In contrast to traditional schemes, the execution of block chain modules was offloaded. In addition, a new proof-of-schedule consensus algorithm (instead of ‘proof-of-work’) was developed and have used Stackelberg games to enhance the authorization of the created schedules. The experimentations has revealed that the presented method significantly enhanced the effectiveness of created schedules with improved make span.
In 2020, Lavanya et al. [8] has explored two allocation models termed asThreshold based Task scheduling algorithm (TBTS) algorithm and Service level agreement-based Load Balancing (SLA-LB) models. TBTS scheduled the tasks in batches and it aids the scheduling of tasks in virtual machines with diverse configurations. SLA-LB scheduled the tasks in a dynamic manner depending on the necessity of users, like budget and deadline. Experimental outcomes revealed that the outcome of the developed approach outperformed the traditional models regarding utilization factor, penalty, gain cost and make span.
In 2020, Ismayilov and Haluk [23] have investigated a prediction-oriented approach named as Neural Network Dominated Sorted Genetic Algorithm (DNN-DNSGA-II) that incorporated Non-Dominated Sorted Genetic Algorithm (NSGA-II) with ANN framework. In addition, five foremost non-prediction oriented dynamic approaches were adopted for solving the workflow scheduling issue. The proposed work concerned on six objectives namely, enhancement of utilization and reliability reduction of energy, cost, make span and level of imbalance.
Review on conventional task scheduling models in cloud environment: Features and challenges
Review on conventional task scheduling models in cloud environment: Features and challenges
Table 1 demonstrate the review on task scheduling in cloud environment and the works are arranged in a year wise manner. The years are arranged as per the ascending order.
Initially, SAW model was deployed in [6] that offer high reliability with reduced make span. MOWS was developed in [33] that offers improved make span with minimal security threats, but it have to analyze the dynamic work flow. In addition, Min-Min and Max-Min model was used in [36], which provides minimal complexity with high utilization of cloud; nevertheless, it needs deliberation on fault tolerance. Likewise, EDA-GA was presented in [2] that enhance the load balance and it concerns on the minimal execution time. However, it needs consideration on real cloud environments. Nevertheless, continuous arrival of task is not considered. CSSA algorithm was deployed in [13] that are cost effective and it also increased the throughput, however, analysis on real time has to be concentrated more. In addition, Stackelberg Game was presented in [26] that offers improved make span and it is highly secure. Nevertheless, real scenario has to be focused more. Also, SLA-LB model were employed in [8] that provides minimal execution time with reduced penalty cost. However, it requires consideration on energy utilization. Finally, NN model was presented in [23] that offers reduced make span with higher reliability; but, machine learning models are not considered. There, these limitations have to be considered for improving the performance of scheduling the task in cloud effectively in the current research work.
The issue of user communication and task scheduling in a device-to-device (D2D) network is a costly method and the dynamic workflow scheduling was not taken into account. A pair-wise comparison matrix technique is used to allocate the resources. It is not possible to find a solution if the matrix size is too large. However, the majority of these works were not considered for publication of environment with multiple clouds [36]. Reduce the makespan and balance the workload in the network while having no effect on the other fundamental parameters. A meta-heuristic method consists of a task sequencing method and a virtual machine searching strategy. The similarity function, task type, dependency relationship between the tasks and the input and output data size are not considered. Moreover, the study does not provide detailed examination of convergence rate [36].
The major components of cloud environment are listed below:
Cloud Manager: This is a central entity that handles the customers’ service requests and collects the significance of cloud providers’ VMs. Customer ( CSP: It is a cloud distributor and it deploys the VMs on the physical server. The CSP provide on-demand services. Each cloud has a management server to direct the peak demands that interrelates with other manager servers to pass the customer requests. Moreover, the demands of customer are often extended in the clouds, and the requests are controlled through a distributed scheme.
The following connections occur among the components of the cloud approach are as follows: “(a) CU-cloud manager, (b) cloud manager-CSP, (c) CSP-CSP, (d) CSP-cloud manager, and (e) cloud manager-CU”. Additionally, the overhead will occurred for making a decision on the individual part. However, the flexibility of the cloud model creates these marginal overheads. Figure 1 illustrates the adopted task scheduling model in cloud.
The manager locates the task in a waiting queue while the cloud manager get a task, and an active VM is identified for assigning the task depending on the objectives. Moreover, the defined objectives in this proposed work are execution time, risk probability, and task priority. The adopted model has concerned on optimal allocation of tasks through the optimization model. Further, the tasks are allocated concurrently in the VMs and the scheduling has occurred in parallel. A new hybrid algorithm referred to CUSO model is introduced for optimal scheduling. In addition, the risk probability is the major consideration, as the parameter ensures secured scheduling of task. The VM allocation is done for each task based on the risk probability (along with other metrics).
Cloud task scheduling architecture.
Cloud setup
Consider a cloud
Workflow model.
In Eq. (1),
The mapping is performed in terms of allocating, scheduling, and matching tasks. The mapping function
The parameters are given in the Table 2. Only one physical machine is considered and the 20 virtual machine are considered.
Cloud parameters
Cloud parameters
As per the proposed work using optimization logic, the multi-objective functions are defined as the single-objective function during the scheduling process, and the defined objective function of this proposed work is given in Eq. (3), in which, the weight
The VM and tasks are the input solution to the proposed CUSO model for optimal scheduling regarding its objectives. The solution encoding of the adopted work is given in Fig. 3.
Solution encoding of proposed work.
Execution time of VM (
In Eq. (4),
Execution time for all tasks
Risk Probability
In Eq. (6),
The risk probability of workflow is an average of the probabilities of all tasks. The average probability of composed tasks being attacked in a workflow is determined in Eq. (8).
Task Priority: Assume the following scheduling approaches [33].
Certain tasks are scheduled on the similar VM; still, they work in a specific way. The task would not start till all the input data is obtained. The task would not begin until all predecessor tasks are performed.
Here, the rank is assigned to each task through DAG’s bottom-up traversal. The security to the task rank is added unlike other scheduling approaches. Similarly, if two tasks have the identical communication cost and complexity, the high security task defines high rank because it schedules faster. Moreover, the task with more security demand would program on highly secure VM.
In Eq. (9),
Proposed CUSO model
Even though, the existing SOA [3] model solves the complex large-scale constrained issues, the constraints provide high computational complexity. In this work, SOA is combined with EHO [18] to propose the hybrid model termed as CUSO scheme. Generally, the hybrid optimization schemes are said to be more appropriate for specific search issues [40]. Accuracy is improved by employing the hybridization concept.In the meta-heuristic approach, the hybridization concept means merging the algorithms in order to provide a new powerful algorithm based on the features of the merged ones. In the adopted model EHO is merged with SOA. The main disadvantage of SOA is that it relies on local optima and has a high computational complexity. To overcome the certain drawback the SOA is hybridized with EHO. The EHO will provide low computational complexity and it escapes from the local optima.
Seagull is a sea bird found all over the world and its scientific name is Laridae. Seagulls are the large range of species with various lengths and masses. It is an intelligent bird and they use bread crumbs to catch the attention of the fish. Generally, the seagulls exist in colonies and they use their intelligence to attack and find the prey. Two phases of seagull behaviour includes like migration and attacking behaviours. The seasonal moments of seagulls is Migration that moves from one place to other for finding the most abundant and richest food sources that provides more adequate energy.
Seagulls move towards the best survival fittest seagull direction in a group (i.e.), the seagull’s fitness value is less than others. In addition, other seagulls updated their early locations on the basis of fittest seagull. The seagulls often attack the other migrating birds in the sea. The seagulls generate the spiral shape moment in the attacking phase. Moreover, the seagulls travel in a group throughout the migration phase. The seagull’s prior locations are dissimilar that avoids the collision among each other.
(i) Migration (exploration): The SOA stimulates the group of seagulls’ moment from one location to other during the migration phase. Further, the seagull must assure 3 conditions in this phase:
Collision avoidance: An extra variable
In Eq. (10),
In Eq. (11),
Movement towards best direction of neighbors: Conventionally, in SOA, the search agents are moved towards the best direction of nearby search agent onceit neglects the collision among the neighbors. However, as per the proposed CUSO method, the positions are updated based on the clan update of EHO, and it is given in Eq. (12).
In Eq. (12),
Further, the behavior of
In Eq. (13), rand is the random number within [0, 1].
Remain close to the best search agent: Further, the position of search agent is updated based on the best search agent, and it is specified in Eq. (14).
In Eq. (14),
(ii) Attacking or exploitation: This phase aims to develop the experience and history of the search process. In addition, the Seagulls continuously alter the angle of attack and its speed during the migration. The seagulls maintain their altitude by their weight and wings. The spiral movement behavior occurred in the air during the prey attack. This behavior in
where
In Eq. (18),
In the attacking phase, the search agent could sustain the positions based on the best solution. However, as per the proposed CUSO method, the positions of search agent are updated as given in Eq. (20).
In Eq. (20),
The SOA begins with a random created population. During the iteration process, the search agents could update their positions in terms of best search agent.
Simulation environment
The adopted task scheduling in cloud environment with CUSO model was implemented in PYTHON. The performance of proposed CUSO model for optimal task scheduling is validated over other models with respect toexecution time, makespan, response time, resource utilization, and risk probability as well. It consists of only one physical machine and 20 virtual machines are considered. The overall count of the task to be accomplished is varied as 200, 400, 600, 800, and 1000, respectively. This evaluation is done with a varying count of VMs. Further, the proposed CUSO model is evaluated over the existing works like PSO [31], Whale Optimization Algorithm (WOA) [4], Modified Mean Grey Wolf Optimization MGWO [30], Grey Wolf Optimization (GWO) [32], Grasshopper Optimization Algorithm (GOA) [15], EHO [18], and SOA [3], respectively.
Convergence graph
The convergence of the adopted CUSO model and the traditional models is assessed by varying the count of iterations from 0, 20, 40, 60, 80, and 100, correspondingly. Figure 4 represents the convergence analysis of adopted approach over other existing approaches like PSO, WOA, MGWO, GWO, GOA, EHO, SOA, CSSA and NN, respectively. The proposed approach attains the minimum cost function as per the defined objectives in Eq. (3). Initially, the cost function at 0
In particular, the cost function of proposed CUSO model had a fall in between the range 0 to 45 count of iterations and then it remains constant till 100
Convergence graph of proposed Clan Updated Seagull Optimization model and existing approaches.
The analysis of execution time for each task is not the similar, as it varies on the basis of the application used. Nevertheless, the VMs should execute the tasks with minimal execution time. Figure 5 illustrates the execution time analysis of the proposed work over conventional model. From the graph, the adopted CUSO model is 51.578%, 54%, and 11.53% better with minimum execution time than the traditional models like WOA, MGWO, and SOA, respectively for task count
Analysis on execution time of proposed Clan Updated Seagull Optimization model and existing approaches.
The Evaluation on makespan of the adopted CUSO scheme and existing schemes for various task counts is shown in Fig. 6. In graph, the proposed CUSO model had achieved the least makespan while scheduling task count 200 than other task counts. The proposed CUSO model attains better outcomes with less makespan value than the existing works like PSO, WOA, MGWO, GWO, GOA, EHO, SOA, CSSA and NN,respectively while scheduling 400 counts of tasks. On observing the figure, the proposed CUSO model had recorded the least makespan value (
Evaluationon makespan of proposed Clan Updated Seagull Optimization model and existing approaches.
Figure 7 represents the resource utilization of both the adopted CUSO scheme and the traditional approaches. As per the objectives of the proposed model in Eq. (3), the resource utilization is less to execute more tasks. On observing the graph, the proposed CUSO model had utilized less resource to execute the 800 task when compared to other traditional models like PSO, WOA, MGWO, GWO, GOA, EHO, SOA, CSSA and NN, respectively. Moreover, the presented CUSO model is 5.17% better than the extant approaches like PSO for task count
Evaluationon resource utilization of proposed Clan Updated Seagull Optimization model and existing approaches.
Analysis on risk probability of adopted Clan Updated Seagull Optimizationschemes and existing approaches.
Figure 8 represents the analysis on risk probability of adopted CUSO scheme over other existing algorithms. On observing the graph, it is proved that the proposed CUSO model ensures lower risk probability for scheduling and executing the task counts. Nevertheless, the traditional model portrays more risk. From the graph, the proposed CUSO model had attained minimum risk probability for task count 600 while scheduling the tasks when compared to other traditional models like PSO, WOA, MGWO, GWO, GOA, EHO, SOA, CSSA and NN, respectively. Moreover, the risk probability acquired by the proposed CUSO model while scheduling the task 800 that is the least value (
Overall performance examination
Tables 6 to 7 represents the overall performance Examination of the adopted CUSO scheme over other existing models for task count 200, 400, 600, 800, and 1000, respectively. From the Table 6, the presented CUSO model provides better outcomes with lower execution time, risk probability, makespan, and resource utilization at task count 200 than other traditional models like PSO, WOA, MGWO, GWO, GOA, EHO, SOA, CSSA and NN, respectively. In addition, the proposed attain minimum risk probability (
Parametric evaluationon proposed model
Table 8 shows theparametric evaluationof presented CUSO model over the prevailing approaches based on the measure. The parametric evaluation is obtained by varying the random variable
Limitations
The cloud environment is a complex system with many shared resources and unpredictability, and it is influenced by uncontrollable external events. The machines are also located in cloudy environments in various areas, with varying processing capabilities and specifications, as well as varying costs. In this case, the cost and duration of the schedule, as well as the resources allocated, are critical and cannot be
| Metrics | PSO [31] | WOA [4] | MGWO [30] | GWO [29] | GOA [15] | EHO [18] | SOA [3] | CSSA [13] | NN [23] | Proposed CUSO | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Makespan | 41. | 44103 | 397. | 5558 | 31. | 84453 | 36. | 21801 | 48. | 12479 | 63. | 68906 | 44. | 91647 | 39. | 1424 | 52. | 1432 | 35. | 29151 |
| Resource Utilization | 5. | 828261 | 3. | 018444 | 5. | 792937 | 5. | 420987 | 5. | 534353 | 5. | 088743 | 5. | 16775 | 4. | 0914 | 2. | 175 | 5. | 638709 |
| Execution Time | 0. | 532631 | 0. | 52999 | 0. | 525607 | 0. | 52127 | 0. | 527377 | 0. | 485561 | 0. | 525626 | 0. | 3254 | 0. | 5172 | 0. | 523005 |
| Risk Probability | 52. | 56233 | 61. | 53523 | 58. | 03437 | 65. | 51242 | 59. | 31379 | 54. | 08728 | 54. | 31907 | 55. | 2107 | 64. | 3129 | 51. | 65806 |
Overall performance Examinationof adopted Clan Updated Seagull Optimizationscheme over other existing techniques for task count 400
Overall performance examination of adopted Clan Updated Seagull Optimizationscheme over other existing techniques for task count 600
Overall performance examination of adopted Clan Updated Seagull Optimizationscheme over other existing techniques for task count 800
Overall performance examination of adopted Clan Updated Seagull Optimizationscheme over other existing techniques for task count 1000
overlooked. As a result, in order to provide an optimal schedule, there must be coordination between the task schedule and resource allocation. In this way, we can achieve an optimal schedule by reducing costs and schedule duration. Complex policies and decisions are required for multi-objective optimization of cloud resources.
Parametric evaluation of proposed Clan Updated Seagull Optimization model over traditional algorithms
This work has intended to afford the optimization strategies for optimal task scheduling with multi-objective constraints in cloud environment. Accordingly, the proposed optimal task allocation framework considers the objectives such as execution time, risk probability, and task priority. For this, a new hybrid optimization algorithm known as CUSO algorithm is introduced in this work, which is the conceptual blending of EHO and SOA. Finally, the performance of proposed work was evaluated over other conventional models with respect to certain performance measures. On observing the graph, The cost function of the adopted CUSO scheme provides lower value (
Footnotes
Abbreviations
Author’s Bios
