A pair-based task scheduling algorithm for cloud computing environment

Journal of King Saud University: Computer and Information Sciences

卷:34

Sourav Kumar Bhoi¹  Shradha Surachita Nanda²  Sanjaya Kumar Panda³ 

[1] Corresponding author.;

[2] Department of Information Technology, Veer Surendra Sai University of Technology, Burla 768018, India;

[3] Department of Computer Science and Engineering, Indian Institute of Technology (ISM), Dhanbad 826004, India;

关键词: Cloud computing;    Task scheduling;    Hungarian algorithm;    Row opportunity matrix;    Column opportunity matrix;    Layover time;   

DOI  :  

来源: DOAJ

【 摘 要 】

In the cloud computing environment, scheduling algorithms show the vital role of finding a possible schedule of the tasks. Extant literatures have shown that the task scheduling problem is NP-Complete as the objective is to obtain the minimum overall execution time. In this paper, we address the problem of scheduling a set of l tasks with a set of |G| groups to a set of m clouds, such that the overall layover time is minimized. Note that overall layover time is the sum of the timing gaps between paired tasks. Here, we present a pair-based task scheduling algorithm for cloud computing environment, which is based on the well-known optimization algorithm, called Hungarian algorithm. The proposed algorithm considers an unequal number of tasks and clouds, and pairs the tasks to make the scheduling decision. We simulate the proposed algorithm and compare it with three existing algorithms, first-come-first-served, Hungarian algorithm with lease time and Hungarian algorithm with converse lease time in twenty-two different datasets. The performance evaluation shows that the proposed algorithm produces better layover time in comparison to existing algorithms. The proposed algorithm is analyzed theoretically and shown to require O (kpl2) time for k iterations, p repetitions and l tasks.

【 授权许可】

Unknown