Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing

DOI10.1007/S10878-022-00865-YzbMATH Open1498.90081OpenAlexW4280645929MaRDI QIDQ2168774FDOQ2168774

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

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

zbMATH Keywords

approximation algorithmcompetitive ratiomakespanmultiprocessor schedulingnon-preemptivescheduling with testing

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Cites Work

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

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)