EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A Novel Model for Online Scheduling of Approximation Jobs

Qi Li, Xiaolei Wang, Shuo Wen, Wei Du, Li Mao, Lijun Cai

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →