Dynamic Task Scheduling Algorithm with Deadline Constraint in Heterogeneous Volunteer Computing Platforms
Volunteer computing (VC) is a distributed computing paradigm, which provides unlimited computing resources in the form of donated idle resources for many large-scale scientific computing applications. Task scheduling is one of the most challenging problems in VC. Although, dynamic scheduling problem...
Main Authors: | , , , |
---|---|
Format: | Article |
Language: | English |
Published: |
MDPI AG
2019-05-01
|
Series: | Future Internet |
Subjects: | |
Online Access: | https://www.mdpi.com/1999-5903/11/6/121 |
_version_ | 1811321928798961664 |
---|---|
author | Ling Xu Jianzhong Qiao Shukuan Lin Wanting Zhang |
author_facet | Ling Xu Jianzhong Qiao Shukuan Lin Wanting Zhang |
author_sort | Ling Xu |
collection | DOAJ |
description | Volunteer computing (VC) is a distributed computing paradigm, which provides unlimited computing resources in the form of donated idle resources for many large-scale scientific computing applications. Task scheduling is one of the most challenging problems in VC. Although, dynamic scheduling problem with deadline constraint has been extensively studied in prior studies in the heterogeneous system, such as cloud computing and clusters, these algorithms can’t be fully applied to VC. This is because volunteer nodes can get offline whenever they want without taking any responsibility, which is different from other distributed computing. For this situation, this paper proposes a dynamic task scheduling algorithm for heterogeneous VC with deadline constraint, called deadline preference dispatch scheduling (DPDS). The DPDS algorithm selects tasks with the nearest deadline each time and assigns them to volunteer nodes (VN), which solves the dynamic task scheduling problem with deadline constraint. To make full use of resources and maximize the number of completed tasks before the deadline constraint, on the basis of the DPDS algorithm, improved dispatch constraint scheduling (IDCS) is further proposed. To verify our algorithms, we conducted experiments, and the results show that the proposed algorithms can effectively solve the dynamic task assignment problem with deadline constraint in VC. |
first_indexed | 2024-04-13T13:26:16Z |
format | Article |
id | doaj.art-81fb8a8a637a45fbaf403a40d785510f |
institution | Directory Open Access Journal |
issn | 1999-5903 |
language | English |
last_indexed | 2024-04-13T13:26:16Z |
publishDate | 2019-05-01 |
publisher | MDPI AG |
record_format | Article |
series | Future Internet |
spelling | doaj.art-81fb8a8a637a45fbaf403a40d785510f2022-12-22T02:45:08ZengMDPI AGFuture Internet1999-59032019-05-0111612110.3390/fi11060121fi11060121Dynamic Task Scheduling Algorithm with Deadline Constraint in Heterogeneous Volunteer Computing PlatformsLing Xu0Jianzhong Qiao1Shukuan Lin2Wanting Zhang3School of Computer Science and Engineering, Northeastern University, Shenyang 110819, ChinaSchool of Computer Science and Engineering, Northeastern University, Shenyang 110819, ChinaSchool of Computer Science and Engineering, Northeastern University, Shenyang 110819, ChinaSchool of Software Engineering, Dalian University of Foreign Languages, Dalian 116044, ChinaVolunteer computing (VC) is a distributed computing paradigm, which provides unlimited computing resources in the form of donated idle resources for many large-scale scientific computing applications. Task scheduling is one of the most challenging problems in VC. Although, dynamic scheduling problem with deadline constraint has been extensively studied in prior studies in the heterogeneous system, such as cloud computing and clusters, these algorithms can’t be fully applied to VC. This is because volunteer nodes can get offline whenever they want without taking any responsibility, which is different from other distributed computing. For this situation, this paper proposes a dynamic task scheduling algorithm for heterogeneous VC with deadline constraint, called deadline preference dispatch scheduling (DPDS). The DPDS algorithm selects tasks with the nearest deadline each time and assigns them to volunteer nodes (VN), which solves the dynamic task scheduling problem with deadline constraint. To make full use of resources and maximize the number of completed tasks before the deadline constraint, on the basis of the DPDS algorithm, improved dispatch constraint scheduling (IDCS) is further proposed. To verify our algorithms, we conducted experiments, and the results show that the proposed algorithms can effectively solve the dynamic task assignment problem with deadline constraint in VC.https://www.mdpi.com/1999-5903/11/6/121volunteer computingheterogeneous systemdynamic schedulingdeadline |
spellingShingle | Ling Xu Jianzhong Qiao Shukuan Lin Wanting Zhang Dynamic Task Scheduling Algorithm with Deadline Constraint in Heterogeneous Volunteer Computing Platforms Future Internet volunteer computing heterogeneous system dynamic scheduling deadline |
title | Dynamic Task Scheduling Algorithm with Deadline Constraint in Heterogeneous Volunteer Computing Platforms |
title_full | Dynamic Task Scheduling Algorithm with Deadline Constraint in Heterogeneous Volunteer Computing Platforms |
title_fullStr | Dynamic Task Scheduling Algorithm with Deadline Constraint in Heterogeneous Volunteer Computing Platforms |
title_full_unstemmed | Dynamic Task Scheduling Algorithm with Deadline Constraint in Heterogeneous Volunteer Computing Platforms |
title_short | Dynamic Task Scheduling Algorithm with Deadline Constraint in Heterogeneous Volunteer Computing Platforms |
title_sort | dynamic task scheduling algorithm with deadline constraint in heterogeneous volunteer computing platforms |
topic | volunteer computing heterogeneous system dynamic scheduling deadline |
url | https://www.mdpi.com/1999-5903/11/6/121 |
work_keys_str_mv | AT lingxu dynamictaskschedulingalgorithmwithdeadlineconstraintinheterogeneousvolunteercomputingplatforms AT jianzhongqiao dynamictaskschedulingalgorithmwithdeadlineconstraintinheterogeneousvolunteercomputingplatforms AT shukuanlin dynamictaskschedulingalgorithmwithdeadlineconstraintinheterogeneousvolunteercomputingplatforms AT wantingzhang dynamictaskschedulingalgorithmwithdeadlineconstraintinheterogeneousvolunteercomputingplatforms |