Scheduling Workflow Tasks With Unknown Task Execution Time by Combining Machine-Learning and Greedy-Optimization
IEEE Transactions on Services Computing · 2024-05 · 17 (3) · 1181-1195
DOI: 10.1109/tsc.2024.3351622 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Services Computing, 2024-05. Verfasst von Yuanhao Yang und 2 weiteren Autor:innen. Die Arbeit wurde bisher 24-mal zitiert (Crossref) und nennt 28 Literaturangaben. Gefördert von: Science and Technology Development Fund of Macao, Key-Area Research and Development Plan of Guangdong Province.
Abstract (Originalsprache)
Workflow tasks are time-sensitive and their task completion utility, i.e., value of task completion, is inversely proportional to their completion time. Existing solutions to the NP-hard problem of utility-maximization task scheduling were achieved under the assumptions of linear Time Utility Function (TUF), i.e., utility is inversely proportional to completion time following a linear function, and prior knowledge of task execution time, which is unrealistic for many applications and dynamic systems. This article proposes a novel model of combining greedy optimization with machine learning for scheduling time-sensitive tasks with convex TUF and unknown task execution time on heterogeneous cloud servers offline nonpreemptively to maximize the total utility of input tasks. For a set of time-sensitive tasks with data dependencies, we first employ multi-layer perceptron neural networks to predict task execution time by utilizing historical data. Then, by solving a linear program after relaxing the disjunctive constraint introduced by the nonpreemption requirement to calculate maximum utility increment, we propose a novel greedy algorithm of marginal incremental utility maximization that jointly determines the task-to-processor allocation plan and tasks’ execution sequence on each processor. We then show that our algorithm has an expected approximation ratio of $\frac{(e-1)(\tau -2)}{e\tau }$ ( e - 1 ) ( τ - 2 ) e τ for convex TUF and $\frac{e-1}{3e}\approx 0.21$ e - 1 3 e ≈ 0 . 21 for linear TUF, where $\tau$ τ is the ratio of total completion utility over total delay cost under optimal scheduling. Our result presents the first polynomial-time approximation solution for this problem that achieves a performance guarantee of bounded ratio for convex TUF and constant ratio for linear TUF respectively. Extensive experiment results through both simulation and real cloud implementation demonstrate significant performance improvement of our algorithm over the known results.
Förderung
- Science and Technology Development Fund of Macao
- Key-Area Research and Development Plan of Guangdong Province
Zitieren
APA
Yang, Y., Shen, H., & Tian, H. (2024). Scheduling Workflow Tasks With Unknown Task Execution Time by Combining Machine-Learning and Greedy-Optimization. IEEE Transactions on Services Computing, 17(3), 1181-1195. https://doi.org/10.1109/tsc.2024.3351622
Vancouver
Yang Y, Shen H, Tian H. Scheduling Workflow Tasks With Unknown Task Execution Time by Combining Machine-Learning and Greedy-Optimization. IEEE Transactions on Services Computing. 2024;17(3):1181-1195. doi:10.1109/tsc.2024.3351622
BibTeX
@article{Yang2024,
author = {Yang, Yuanhao and Shen, Hong and Tian, Hui},
title = {Scheduling Workflow Tasks With Unknown Task Execution Time by Combining Machine-Learning and Greedy-Optimization},
journal = {IEEE Transactions on Services Computing},
year = {2024},
volume = {17},
number = {3},
pages = {1181--1195},
doi = {10.1109/tsc.2024.3351622}
}
EUVIMED