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

• An adversarial model for scheduling with testing
• Bounds for Certain Multiprocessing Anomalies
• Explorable uncertainty in scheduling with non-uniform testing times
• scientific article; zbMATH DE number 4130003 (Why is no real title available?)
• scientific article; zbMATH DE number 5669942 (Why is no real title available?)
• 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

(9)

• An adversarial model for scheduling with testing
• Scheduling with explorable uncertainty
• Improved approximation algorithms for multiprocessor scheduling with testing
• Approximation Algorithms for Multiprocessor Scheduling with Testing to Minimize the Total Job Completion Time
• Scheduling with testing: competitive algorithms for minimizing the total weighted completion time in the adversarial model
• Perpetual scheduling with explorable uncertainty
• 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: 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)