Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing

DOI10.1007/s10878-022-00865-yzbMath1498.90081OpenAlexW4280645929MaRDI QIDQ2168774

Eiji Miyano, Mingyang Gong, Randy Goebel, Guo-Hui Lin

Publication date: 26 August 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-022-00865-y

zbMATH Keywords

multiprocessor schedulingapproximation algorithmcompetitive ratiomakespannon-preemptivescheduling with testing

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

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
• An adversarial model for scheduling with testing
• On randomized online scheduling
• Improved Bounds for the Online Scheduling Problem
• Bounds for Certain Multiprocessing Anomalies

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