A pair-based task scheduling algorithm for cloud computing environment
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 pro...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Springer
2022-01-01
|
| Series: | Journal of King Saud University: Computer and Information Sciences |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S1319157818302970 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849315897776275456 |
|---|---|
| author | Sanjaya Kumar Panda Shradha Surachita Nanda Sourav Kumar Bhoi |
| author_facet | Sanjaya Kumar Panda Shradha Surachita Nanda Sourav Kumar Bhoi |
| author_sort | Sanjaya Kumar Panda |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-3c51975d4c9642a09ff2be232f431220 |
| institution | Kabale University |
| issn | 1319-1578 |
| language | English |
| publishDate | 2022-01-01 |
| publisher | Springer |
| record_format | Article |
| series | Journal of King Saud University: Computer and Information Sciences |
| spelling | doaj-art-3c51975d4c9642a09ff2be232f4312202025-08-20T03:52:00ZengSpringerJournal of King Saud University: Computer and Information Sciences1319-15782022-01-013411434144510.1016/j.jksuci.2018.10.001A pair-based task scheduling algorithm for cloud computing environmentSanjaya Kumar Panda0Shradha Surachita Nanda1Sourav Kumar Bhoi2Department of Computer Science and Engineering, Indian Institute of Technology (ISM), Dhanbad 826004, India; Department of Information Technology, Veer Surendra Sai University of Technology, Burla 768018, India; Corresponding author.Department of Information Technology, Veer Surendra Sai University of Technology, Burla 768018, IndiaDepartment of Computer Science and Engineering, Parala Maharaja Engineering College, Brahmapur 761003, IndiaIn 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.http://www.sciencedirect.com/science/article/pii/S1319157818302970Cloud computingTask schedulingHungarian algorithmRow opportunity matrixColumn opportunity matrixLayover time |
| spellingShingle | Sanjaya Kumar Panda Shradha Surachita Nanda Sourav Kumar Bhoi A pair-based task scheduling algorithm for cloud computing environment Journal of King Saud University: Computer and Information Sciences Cloud computing Task scheduling Hungarian algorithm Row opportunity matrix Column opportunity matrix Layover time |
| title | A pair-based task scheduling algorithm for cloud computing environment |
| title_full | A pair-based task scheduling algorithm for cloud computing environment |
| title_fullStr | A pair-based task scheduling algorithm for cloud computing environment |
| title_full_unstemmed | A pair-based task scheduling algorithm for cloud computing environment |
| title_short | A pair-based task scheduling algorithm for cloud computing environment |
| title_sort | pair based task scheduling algorithm for cloud computing environment |
| topic | Cloud computing Task scheduling Hungarian algorithm Row opportunity matrix Column opportunity matrix Layover time |
| url | http://www.sciencedirect.com/science/article/pii/S1319157818302970 |
| work_keys_str_mv | AT sanjayakumarpanda apairbasedtaskschedulingalgorithmforcloudcomputingenvironment AT shradhasurachitananda apairbasedtaskschedulingalgorithmforcloudcomputingenvironment AT souravkumarbhoi apairbasedtaskschedulingalgorithmforcloudcomputingenvironment AT sanjayakumarpanda pairbasedtaskschedulingalgorithmforcloudcomputingenvironment AT shradhasurachitananda pairbasedtaskschedulingalgorithmforcloudcomputingenvironment AT souravkumarbhoi pairbasedtaskschedulingalgorithmforcloudcomputingenvironment |