Scheduling with testing on multiple identical parallel machines
From MaRDI portal
Publication:832831
DOI10.1007/978-3-030-83508-8_3OpenAlexW3159741798MaRDI QIDQ832831
Susanne Albers, Alexander Eckl
Publication date: 25 March 2022
Full work available at URL: https://arxiv.org/abs/2105.02052
competitive analysismakespan minimizationidentical parallel machinesonline schedulingexplorable uncertainty
Related Items (3)
Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing ⋮ Improved approximation algorithms for multiprocessor scheduling with testing ⋮ Stochastic graph exploration with limited resources
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A lower bound for randomized on-line multiprocessor scheduling
- The robust knapsack problem with queries
- Semi-online scheduling revisited
- Efficient update strategies for geometric computing with uncertainty
- An efficient algorithm for semi-online multiprocessor scheduling with given total processing time
- New algorithms for an ancient scheduling problem.
- Semi on-line algorithms for the partition problem
- A better lower bound for on-line scheduling
- A lower bound for randomized on-line scheduling algorithms
- On-line scheduling revisited
- A survey on makespan minimization in semi-online environments
- Explorable uncertainty in scheduling with non-uniform testing times
- An adversarial model for scheduling with testing
- Online makespan minimization with parallel schedules
- The update complexity of selection and related problems
- The Power of Reordering for Online Minimum Makespan Scheduling
- Computing shortest paths with uncertainty
- On randomized online scheduling
- Optimal Search for the Best Alternative
- An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
- Better Bounds for Online Scheduling
- Speed is as powerful as clairvoyance
- Computing the Median with Uncertainty
- A Better Algorithm for an Ancient Scheduling Problem
- Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
- Bounds for Certain Multiprocessing Anomalies
- Bounds on Multiprocessing Timing Anomalies
- On-line bin-stretching
This page was built for publication: Scheduling with testing on multiple identical parallel machines
