A pair-based task scheduling algorithm for cloud computing environment

Abstract

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.

Keywords

• Cloud computing
• Task scheduling
• Hungarian algorithm
• Row opportunity matrix
• Column opportunity matrix
• Layover time