A heuristic-based task scheduling algorithm for scientific workflows in heterogeneous cloud computing platforms
Task scheduling problem in a cloud computing environment is one of the most important issues in this field. Because task schedulers should be aware of underlying platform heterogeneity, task interdependencies, and virtual machine (VM) variable configurations. An efficient task scheduling algorithm c...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2022-09-01
|
| Series: | Journal of King Saud University: Computer and Information Sciences |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S1319157821001269 |
| _version_ | 1811217306489978880 |
|---|---|
| author | Reza NoorianTalouki Mirsaeid Hosseini Shirvani Homayun Motameni |
| author_facet | Reza NoorianTalouki Mirsaeid Hosseini Shirvani Homayun Motameni |
| author_sort | Reza NoorianTalouki |
| collection | DOAJ |
| description | Task scheduling problem in a cloud computing environment is one of the most important issues in this field. Because task schedulers should be aware of underlying platform heterogeneity, task interdependencies, and virtual machine (VM) variable configurations. An efficient task scheduling algorithm can potentially increase the efficiency of cloud computing, by choosing the appropriate virtual machine to do a specific task-scheduling problem, for dependent tasks on heterogeneous resources which is a well-known NP-Hard problem. To reduce minimum total execution time, makespan, in cloud computing many heuristics were presented in literature but lots of them suffer from low efficiency. In this article, a new task priority strategy and applying task duplication methods are proposed, for solving the task scheduling problem of the dependent tasks in heterogeneous cloud computing systems. The novelty of the current paper is to present a new list scheduling algorithm with a new task priority strategy and applying pertinent task duplication techniques. This paper uses optimistic cost table downward (OCTd) and optimistic cost table upward (OCTu) procedures to prioritize tasks in an efficient ordered list; then, it utilizes Heterogeneous Earliest Finish Time (HEFT)-duplication method for performing task duplication technique which significantly reduces makespan. To validate the proposal, we experimentally analyzed the proposed scheduling algorithm with different scientific workflows such as Molecular, LU-Like, FFT, and Montage datasets. The performance comparison of the novel heuristic scheduling algorithm against other existing approaches proved the superiority of proposed algorithm in terms of makespan, speedup, SLR, and efficiency which are prominent scheduling evaluation metrics. |
| first_indexed | 2024-04-12T06:53:13Z |
| format | Article |
| id | doaj.art-e8e8f2325a7f4497a30cee6f4951f9b4 |
| institution | Directory Open Access Journal |
| issn | 1319-1578 |
| language | English |
| last_indexed | 2024-04-12T06:53:13Z |
| publishDate | 2022-09-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Journal of King Saud University: Computer and Information Sciences |
| spelling | doaj.art-e8e8f2325a7f4497a30cee6f4951f9b42022-12-22T03:43:16ZengElsevierJournal of King Saud University: Computer and Information Sciences1319-15782022-09-0134849024913A heuristic-based task scheduling algorithm for scientific workflows in heterogeneous cloud computing platformsReza NoorianTalouki0Mirsaeid Hosseini Shirvani1Homayun Motameni2Department of Computer Engineering, Sari Branch, Islamic Azad University, Sari, IranCorresponding author.; Department of Computer Engineering, Sari Branch, Islamic Azad University, Sari, IranDepartment of Computer Engineering, Sari Branch, Islamic Azad University, Sari, IranTask scheduling problem in a cloud computing environment is one of the most important issues in this field. Because task schedulers should be aware of underlying platform heterogeneity, task interdependencies, and virtual machine (VM) variable configurations. An efficient task scheduling algorithm can potentially increase the efficiency of cloud computing, by choosing the appropriate virtual machine to do a specific task-scheduling problem, for dependent tasks on heterogeneous resources which is a well-known NP-Hard problem. To reduce minimum total execution time, makespan, in cloud computing many heuristics were presented in literature but lots of them suffer from low efficiency. In this article, a new task priority strategy and applying task duplication methods are proposed, for solving the task scheduling problem of the dependent tasks in heterogeneous cloud computing systems. The novelty of the current paper is to present a new list scheduling algorithm with a new task priority strategy and applying pertinent task duplication techniques. This paper uses optimistic cost table downward (OCTd) and optimistic cost table upward (OCTu) procedures to prioritize tasks in an efficient ordered list; then, it utilizes Heterogeneous Earliest Finish Time (HEFT)-duplication method for performing task duplication technique which significantly reduces makespan. To validate the proposal, we experimentally analyzed the proposed scheduling algorithm with different scientific workflows such as Molecular, LU-Like, FFT, and Montage datasets. The performance comparison of the novel heuristic scheduling algorithm against other existing approaches proved the superiority of proposed algorithm in terms of makespan, speedup, SLR, and efficiency which are prominent scheduling evaluation metrics.http://www.sciencedirect.com/science/article/pii/S1319157821001269Heuristic list-schedulingCloud computingHeterogeneous systemsTask duplication |
| spellingShingle | Reza NoorianTalouki Mirsaeid Hosseini Shirvani Homayun Motameni A heuristic-based task scheduling algorithm for scientific workflows in heterogeneous cloud computing platforms Journal of King Saud University: Computer and Information Sciences Heuristic list-scheduling Cloud computing Heterogeneous systems Task duplication |
| title | A heuristic-based task scheduling algorithm for scientific workflows in heterogeneous cloud computing platforms |
| title_full | A heuristic-based task scheduling algorithm for scientific workflows in heterogeneous cloud computing platforms |
| title_fullStr | A heuristic-based task scheduling algorithm for scientific workflows in heterogeneous cloud computing platforms |
| title_full_unstemmed | A heuristic-based task scheduling algorithm for scientific workflows in heterogeneous cloud computing platforms |
| title_short | A heuristic-based task scheduling algorithm for scientific workflows in heterogeneous cloud computing platforms |
| title_sort | heuristic based task scheduling algorithm for scientific workflows in heterogeneous cloud computing platforms |
| topic | Heuristic list-scheduling Cloud computing Heterogeneous systems Task duplication |
| url | http://www.sciencedirect.com/science/article/pii/S1319157821001269 |
| work_keys_str_mv | AT rezanooriantalouki aheuristicbasedtaskschedulingalgorithmforscientificworkflowsinheterogeneouscloudcomputingplatforms AT mirsaeidhosseinishirvani aheuristicbasedtaskschedulingalgorithmforscientificworkflowsinheterogeneouscloudcomputingplatforms AT homayunmotameni aheuristicbasedtaskschedulingalgorithmforscientificworkflowsinheterogeneouscloudcomputingplatforms AT rezanooriantalouki heuristicbasedtaskschedulingalgorithmforscientificworkflowsinheterogeneouscloudcomputingplatforms AT mirsaeidhosseinishirvani heuristicbasedtaskschedulingalgorithmforscientificworkflowsinheterogeneouscloudcomputingplatforms AT homayunmotameni heuristicbasedtaskschedulingalgorithmforscientificworkflowsinheterogeneouscloudcomputingplatforms |