Approximation Algorithms for Multiprocessor Scheduling with Testing to Minimize the Total Job Completion Time

DOI10.1007/S00453-023-01198-WMaRDI QIDQ6492085zbMATH OpenFDO

Authors Mingyang Gong, Zhi-Zhong Chen

Publication date 24 April 2024

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00453-023-01198-W

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Cites work

• An adversarial model for scheduling with testing
• Bounds for Certain Multiprocessing Anomalies
• Computing the Median with Uncertainty
• Efficient update strategies for geometric computing with uncertainty
• Explorable uncertainty in scheduling with non-uniform testing times
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2146482 (Why is no real title available?)
• Improved approximation algorithms for multiprocessor scheduling with testing
• Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing
• Scheduling with a processing time oracle
• Scheduling with explorable uncertainty
• Scheduling with testing on multiple identical parallel machines
• Scheduling. Theory, algorithms, and systems
• The update complexity of selection and related problems

Cited in

(4)

• Scheduling with testing: competitive algorithms for minimizing the total weighted completion time in the adversarial model
• Scheduling with obligatory tests
• Randomized algorithms for fully online multiprocessor scheduling with testing
• Approximation schemes for multiprocessor scheduling within budget

This page was built for publication: Approximation Algorithms for Multiprocessor Scheduling with Testing to Minimize the Total Job Completion Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6492085)