Parallel solutions for preemptive makespan scheduling on two identical machines
From MaRDI portal
Abstract: We consider online preemptive scheduling of jobs arriving one by one, to be assigned to two identical machines, with the goal of makespan minimization. We study the effect of selecting the best solution out of two independent solutions constructed in parallel in an online fashion. Two cases are analyzed, where one case is purely online, and in the other one jobs are presented sorted by non-increasing sizes. We show that using two solutions rather than one improves the performance significantly, but that an optimal solution cannot be obtained for any constant number of solutions constructed in parallel. Our algorithms have the best possible competitive ratios out of algorithms for each one of the classes.
Recommendations
Cites work
- A lower bound for randomized on-line multiprocessor scheduling
- Algorithms better than LPT for semi-online scheduling with decreasing processing times
- An efficient algorithm for bin stretching
- An efficient algorithm for semi-online multiprocessor scheduling with given total processing time
- An optimal algorithm for preemptive on-line scheduling
- Better Bounds for Online Scheduling
- Bin stretching revisited
- Bounds for Certain Multiprocessing Anomalies
- Bounds on Multiprocessing Timing Anomalies
- scientific article; zbMATH DE number 4130003 (Why is no real title available?)
- Improved Bounds for the Online Scheduling Problem
- Lower bounds for online makespan minimization on a small number of related machines
- New approximation bounds for LPT scheduling
- On-line bin-stretching
- On-Line Load Balancing for Related Machines
- On-line routing of virtual circuits with applications to load balancing and machine scheduling
- On-line scheduling revisited
- Online algorithms with advice for bin packing and scheduling problems
- Online algorithms with advice: the tape model
- Online makespan scheduling with sublinear advice
- Online scheduling with bounded migration
- Optimal algorithms for online scheduling with bounded rearrangement at the end
- Optimal and online preemptive scheduling on uniformly related machines
- Optimal non-preemptive semi-online scheduling on two related machines
- Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios
- Optimal preemptive semi-online scheduling to minimize makespan on two related machines
- Parallel online algorithms for the Bin Packing Problem
- Preemptive online scheduling: Optimal algorithms for all speeds
- Randomized on-line scheduling on two uniform machines
- Robust algorithms for preemptive scheduling
- Robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizes
- Scheduling with deadlines and loss functions
- Semi on-line algorithms for the partition problem
- Semi-online preemptive scheduling: one algorithm for all variants
- Semi-online scheduling revisited
- Semi-online scheduling with decreasing job sizes
- Weighted online problems with advice
Cited in
(9)- Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
- Discrete parallel machine makespan ScheLoc problem
- An online scheduling of two type parallel jobs on identical machines
- scientific article; zbMATH DE number 2221458 (Why is no real title available?)
- On preemption redundancy in scheduling unit processing time jobs on two parallel machines
- Parallel solutions for ordinal scheduling with a small number of machines
- Online early work scheduling on parallel machines
- Tighter bounds for the harmonic bin packing algorithm
- Semi-online models for cardinality constrained bin packing
This page was built for publication: Parallel solutions for preemptive makespan scheduling on two identical machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6102847)
