A Study on Heuristic Task Scheduling Optimizing Task Deadline Violations in Heterogeneous Computational Environments
In this paper, we focus on the problem of optimizing deadline violations for executing tasks in various heterogeneous computational environments. To address the problem, we formulated it as a binary nonlinear programming (BNP) model, which maximize the number of completed tasks and optimize the reso...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2020-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9258999/ |
| _version_ | 1818330549475868672 |
|---|---|
| author | Bo Wang Ying Song Changhai Wang Wanwei Huang Xiaoyun Qin |
| author_facet | Bo Wang Ying Song Changhai Wang Wanwei Huang Xiaoyun Qin |
| author_sort | Bo Wang |
| collection | DOAJ |
| description | In this paper, we focus on the problem of optimizing deadline violations for executing tasks in various heterogeneous computational environments. To address the problem, we formulated it as a binary nonlinear programming (BNP) model, which maximize the number of completed tasks and optimize the resource utilization of servers. To solve the BNP model in a polynomial complexity, we propose a heuristic task scheduling method, which iteratively schedules a task to the first core such that the accumulated slack time of all scheduled tasks is minimum, until the core cannot finish any task, and executes tasks with the earliest deadline first in each core to execute as many task as possible in a core. Experiment results based on a real world trace show that our method has upto 100% less task violations, and has the best performance in resource efficiency optimization in overall, compared with eight classical and state-of-the-art heuristic methods. |
| first_indexed | 2024-12-13T13:05:43Z |
| format | Article |
| id | doaj.art-9ca10ec3fee8414cbd5b2d573b6876b4 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-13T13:05:43Z |
| publishDate | 2020-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-9ca10ec3fee8414cbd5b2d573b6876b42022-12-21T23:44:51ZengIEEEIEEE Access2169-35362020-01-01820563520564510.1109/ACCESS.2020.30379659258999A Study on Heuristic Task Scheduling Optimizing Task Deadline Violations in Heterogeneous Computational EnvironmentsBo Wang0https://orcid.org/0000-0003-3598-5359Ying Song1Changhai Wang2https://orcid.org/0000-0002-1506-2058Wanwei Huang3Xiaoyun Qin4https://orcid.org/0000-0002-8900-1231Software Engineering College, Zhengzhou University of Light Industry, Zhengzhou, ChinaBeijing Advanced Innovation Center for Materials Genome Engineering, Beijing Information Science and Technology University, Beijing, ChinaSoftware Engineering College, Zhengzhou University of Light Industry, Zhengzhou, ChinaSoftware Engineering College, Zhengzhou University of Light Industry, Zhengzhou, ChinaDepartment of Material and Chemical Engineering, Zhengzhou University of Light Industry, Zhengzhou, ChinaIn this paper, we focus on the problem of optimizing deadline violations for executing tasks in various heterogeneous computational environments. To address the problem, we formulated it as a binary nonlinear programming (BNP) model, which maximize the number of completed tasks and optimize the resource utilization of servers. To solve the BNP model in a polynomial complexity, we propose a heuristic task scheduling method, which iteratively schedules a task to the first core such that the accumulated slack time of all scheduled tasks is minimum, until the core cannot finish any task, and executes tasks with the earliest deadline first in each core to execute as many task as possible in a core. Experiment results based on a real world trace show that our method has upto 100% less task violations, and has the best performance in resource efficiency optimization in overall, compared with eight classical and state-of-the-art heuristic methods.https://ieeexplore.ieee.org/document/9258999/Batch schedulingheuristic schedulingtask schedulingdeadline violation |
| spellingShingle | Bo Wang Ying Song Changhai Wang Wanwei Huang Xiaoyun Qin A Study on Heuristic Task Scheduling Optimizing Task Deadline Violations in Heterogeneous Computational Environments IEEE Access Batch scheduling heuristic scheduling task scheduling deadline violation |
| title | A Study on Heuristic Task Scheduling Optimizing Task Deadline Violations in Heterogeneous Computational Environments |
| title_full | A Study on Heuristic Task Scheduling Optimizing Task Deadline Violations in Heterogeneous Computational Environments |
| title_fullStr | A Study on Heuristic Task Scheduling Optimizing Task Deadline Violations in Heterogeneous Computational Environments |
| title_full_unstemmed | A Study on Heuristic Task Scheduling Optimizing Task Deadline Violations in Heterogeneous Computational Environments |
| title_short | A Study on Heuristic Task Scheduling Optimizing Task Deadline Violations in Heterogeneous Computational Environments |
| title_sort | study on heuristic task scheduling optimizing task deadline violations in heterogeneous computational environments |
| topic | Batch scheduling heuristic scheduling task scheduling deadline violation |
| url | https://ieeexplore.ieee.org/document/9258999/ |
| work_keys_str_mv | AT bowang astudyonheuristictaskschedulingoptimizingtaskdeadlineviolationsinheterogeneouscomputationalenvironments AT yingsong astudyonheuristictaskschedulingoptimizingtaskdeadlineviolationsinheterogeneouscomputationalenvironments AT changhaiwang astudyonheuristictaskschedulingoptimizingtaskdeadlineviolationsinheterogeneouscomputationalenvironments AT wanweihuang astudyonheuristictaskschedulingoptimizingtaskdeadlineviolationsinheterogeneouscomputationalenvironments AT xiaoyunqin astudyonheuristictaskschedulingoptimizingtaskdeadlineviolationsinheterogeneouscomputationalenvironments AT bowang studyonheuristictaskschedulingoptimizingtaskdeadlineviolationsinheterogeneouscomputationalenvironments AT yingsong studyonheuristictaskschedulingoptimizingtaskdeadlineviolationsinheterogeneouscomputationalenvironments AT changhaiwang studyonheuristictaskschedulingoptimizingtaskdeadlineviolationsinheterogeneouscomputationalenvironments AT wanweihuang studyonheuristictaskschedulingoptimizingtaskdeadlineviolationsinheterogeneouscomputationalenvironments AT xiaoyunqin studyonheuristictaskschedulingoptimizingtaskdeadlineviolationsinheterogeneouscomputationalenvironments |