A Novel Model for Online Scheduling of Approximation Jobs
Algorithms · 02.07.2026 · 19 (7) · 539
DOI: 10.3390/a19070539 ↗Kurz gefasst
Fachartikel in der Zeitschrift Algorithms, online erschienen am 02.07.2026. Verfasst von Qi Li und 5 weiteren Autor:innen. Die Arbeit nennt 35 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Guangdong Police College.
Abstract (Originalsprache)
Approximation jobs are widely deployed on Amazon EC2, which compute partial task segments to obtain useful results. For such jobs, maximizing total profit is the primary goal, where profit equals the sum of job utilities minus the total machine costs. Unfortunately, maximizing the total profit of approximation jobs is an NP-hard problem. This problem is further complicated by online job arrivals and heterogeneous resource demands across different tasks. This work builds an optimization framework that clearly characterizes job utility and machine costs to resolve this problem. Within this framework, we propose an efficient dual algorithm for job scheduling. The proposed method leverages the dual-fitting approach to measure algorithm performance by analyzing the primal and dual objective growth at each step. This work proves that our algorithm achieves a constant competitive ratio. The results from the trace-driven simulations demonstrate that our algorithms consistently outperform these baselines across various metrics.
Förderung
- Guangdong Police College
Zitieren
APA
Li, Q., Wang, X., Wen, S., Du, W., Mao, L., & Cai, L. (2026). A Novel Model for Online Scheduling of Approximation Jobs. Algorithms, 19(7), 539. https://doi.org/10.3390/a19070539
Vancouver
Li Q, Wang X, Wen S, Du W, Mao L, Cai L. A Novel Model for Online Scheduling of Approximation Jobs. Algorithms. 2026;19(7):539. doi:10.3390/a19070539
BibTeX
@article{Li2026,
author = {Li, Qi and Wang, Xiaolei and Wen, Shuo and Du, Wei and Mao, Li and Cai, Lijun},
title = {A Novel Model for Online Scheduling of Approximation Jobs},
journal = {Algorithms},
year = {2026},
volume = {19},
number = {7},
pages = {539},
doi = {10.3390/a19070539}
}
EUVIMED