Low-time complexity and low-cost binary particle swarm optimization algorithm for task scheduling and load balancing in cloud computing

With the increasing large number of cloud users, the number of tasks is growing exponentially. Scheduling and balancing these tasks amongst different heterogeneous virtual machines (VMs) under constraints such as, low makespan, high resource utilization rate, low execution cost and low scheduling ti...

Full description

Saved in:
Bibliographic Details
Published in:Applied intelligence (Dordrecht, Netherlands) Netherlands), 2019-09, Vol.49 (9), p.3308-3330
Main Authors: Mapetu, Jean Pepe Buanga, Chen, Zhen, Kong, Lingfu
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Cloud computing
Completion time
Computer Science
Computing costs
Heuristic
Heuristic methods
Heuristic task scheduling
Load balancing
Low cost
Machines
Manufacturing
Mechanical Engineering
Optimization
Particle swarm optimization
Processes
Production scheduling
Scheduling
Task complexity
Virtual environments
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:With the increasing large number of cloud users, the number of tasks is growing exponentially. Scheduling and balancing these tasks amongst different heterogeneous virtual machines (VMs) under constraints such as, low makespan, high resource utilization rate, low execution cost and low scheduling time, become NP-hard optimization problem. So, due to the inefficiency of heuristic algorithms, many meta-heuristic algorithms, such as particle swarm optimization (PSO) have been introduced to solve the said problem. However, these algorithms do not guarantee that the optimal solution can be found, if they are not combined with other heuristic or meta-heuristic algorithms. Further, these algorithms have high time complexity, making them less useful in realistic scenarios. To solve the said NP-problem effectively, we propose an efficient binary version of PSO algorithm with low time complexity and low cost for scheduling and balancing tasks in cloud computing. Specifically, we define an objective function which calculates the maximum completion time difference among heterogeneous VMs subject to updating and optimization constraints introduced in this paper. Then, we devise a particle position updating with respect to load balancing strategy. The experimental results show that the proposed algorithm achieves task scheduling and load balancing better than existing meta-heuristic and heuristic algorithms.
ISSN:0924-669X
1573-7497
DOI:10.1007/s10489-019-01448-x