An efficient Task Scheduling and Load Balancing in Cloud Computing using KD-Tree Algorithm
Usha Kirana S P1, Demian Antony D’Mello2

1Usha Kirana S P*, Department of Computer Science and Engineering, Visvesvaraya Technological University, Belagavi, India.
2Demian Antony D’Mello, Department of Computer Science and Engineering, Canara College of Engineering, Mangaluru, India.

Manuscript received on November 15, 2019. | Revised Manuscript received on 20 November, 2019. | Manuscript published on December 10, 2019. | PP: 2426-2433 | Volume-9 Issue-2, December 2019. | Retrieval Number: B7001129219/2019©BEIESP | DOI: 10.35940/ijitee.B7001.129219
Open Access | Ethics and Policies | Cite | Mendeley | Indexing and Abstracting
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC-BY-NC-ND license (

Abstract: Cloud Computing provides the sharing ability and access for available cloud host and various distributed environments, namely Load Balancing (LB), virtualization technologies and scheduling techniques. The satisfaction of both users and cloud providers are the major issues for effective LB and task scheduling algorithms in cloud resource management, where the requirements namely high resource utilization, low monetary costs and minimum makespan. Many researchers tried to develop various heuristic and meta-heuristic algorithms to attain the aforementioned user requirements. But, when the number of tasks grows exponentially, these algorithms failed to achieve LB, lower running time, and it faces the high time complexity. In this research work, a KD-Tree algorithm is developed to address the issues of heuristic algorithms and provide efficient LB by partitioning the environments into several tasks. According to the deadline of task execution, the remaining tasks are adjusted dynamically by the proposed KD-tree algorithm in the virtual environment. The experiments are conducted to evaluate the efficiency of KD-Tree algorithm with existing heuristic techniques by using makespan, energy consumption and task migrations. When the number of tasks is 20, the proposed KD-Tree algorithm achieved 71.33% makespan and 5% task migrations. 
Keywords: Cloud Computing, Heuristic Methods, KD-Tree Algorithm, Load Balancing, Makespan, Time Complexity.
Scope of the Article: Cloud Computing