Scheduling with testing on multiple identical parallel machines

DOI10.1007/978-3-030-83508-8_3MaRDI QIDQ832831zbMATH OpenOpenAlexFDO

Authors Susanne Albers, Alexander Eckl

Publication date 25 March 2022

Full work available at URL https://arxiv.org/abs/2105.02052

zbMATH Keywords

competitive analysisonline schedulingidentical parallel machinesmakespan minimizationexplorable uncertainty

Mathematics Subject Classification ID

Data structures (68P05) Algorithms in computer science (68Wxx)

Cites work

• scientific article; zbMATH DE number 4130003 (Why is no real title available?)
• scientific article; zbMATH DE number 7075885 (Why is no real title available?)
• A Better Algorithm for an Ancient Scheduling Problem
• A better lower bound for on-line scheduling
• A lower bound for randomized on-line multiprocessor scheduling
• A lower bound for randomized on-line scheduling algorithms
• A survey on makespan minimization in semi-online environments
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• An adversarial model for scheduling with testing
• An efficient algorithm for semi-online multiprocessor scheduling with given total processing time
• Better Bounds for Online Scheduling
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Computing minimum spanning trees with uncertainty
• Computing shortest paths with uncertainty
• Computing the Median with Uncertainty
• Efficient update strategies for geometric computing with uncertainty
• Explorable uncertainty in scheduling with non-uniform testing times
• New algorithms for an ancient scheduling problem.
• On randomized online scheduling
• On-line bin-stretching
• On-line scheduling revisited
• Optimal Search for the Best Alternative
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• Scheduling with explorable uncertainty
• Semi on-line algorithms for the partition problem
• Semi-online scheduling revisited
• Speed is as powerful as clairvoyance
• The Power of Reordering for Online Minimum Makespan Scheduling
• The price of information in combinatorial optimization
• The robust knapsack problem with queries
• The update complexity of selection and related problems

Cited in

(5)

• Stochastic graph exploration with limited resources
• Improved approximation algorithms for non-preemptive multiprocessor 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
• Generating Experimental Data for Computational Testing with Machine Scheduling Applications

This page was built for publication: Scheduling with testing on multiple identical parallel machines

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