Improved approximation algorithms for multiprocessor scheduling with testing

DOI10.1007/978-3-030-97099-4_5zbMath1528.68046OpenAlexW4214905240MaRDI QIDQ6113912

Guo-Hui Lin, Mingyang Gong

Publication date: 10 August 2023

Published in: Frontiers of Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-97099-4_5

zbMATH Keywords

multiprocessor schedulingapproximation algorithmcompetitive ratiomakespannon-preemptivescheduling with testing

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Semi-online scheduling problems on a small number of machines
• Scheduling with testing on multiple identical parallel machines
• Semi on-line scheduling on two identical machines
• On-line scheduling revisited
• Pseudo lower bounds for online parallel machine scheduling
• New lower and upper bounds for on-line scheduling
• Explorable uncertainty in scheduling with non-uniform testing times
• Improved Bounds for the Online Scheduling Problem
• Bounds for Certain Multiprocessing Anomalies

This page was built for publication: Improved approximation algorithms for multiprocessor scheduling with testing