Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing

DOI10.1007/S10878-022-00865-YMaRDI QIDQ2168774zbMATH OpenOpenAlexFDO

Authors Mingyang Gong, Randy Goebel, Eiji Miyano, Guohui 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

approximation algorithmcompetitive ratiomakespanmultiprocessor schedulingnon-preemptivescheduling with testing

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

• Improved approximation algorithms for multiprocessor scheduling with testing
• scientific article; zbMATH DE number 1979517
• An approximation algorithm for nonpreemptive scheduling on hypercube parallel task systems
• A constant-approximate feasibility test for multiprocessor real-time scheduling
• A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling
• scientific article; zbMATH DE number 1223040
• An Approximation Algorithm for Preemptive Scheduling on Parallel-Task Systems
• Exact speedup factors for linear-time schedulability tests for fixed-priority preemptive and non-preemptive scheduling
• A parallel approximation scheme for the multiprocessor scheduling problem

Cites work

• scientific article; zbMATH DE number 4130003 (Why is no real title available?)
• scientific article; zbMATH DE number 5669942 (Why is no real title available?)
• An adversarial model for scheduling with testing
• Bounds for Certain Multiprocessing Anomalies
• Explorable uncertainty in scheduling with non-uniform testing times
• Improved Bounds for the Online Scheduling Problem
• New lower and upper bounds for on-line scheduling
• On randomized online scheduling
• On-line scheduling revisited
• Pseudo lower bounds for online parallel machine scheduling
• Scheduling with explorable uncertainty
• Scheduling with testing on multiple identical parallel machines
• Semi on-line scheduling on two identical machines
• Semi-online scheduling problems on a small number of machines

Cited in

(4)

• Scheduling with explorable uncertainty
• An adversarial model for scheduling with testing
• Improved approximation algorithms for multiprocessor scheduling with testing
• Approximation Algorithms for Multiprocessor Scheduling with Testing to Minimize the Total Job Completion Time

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

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