An optimal algorithm for preemptive on-line scheduling
From MaRDI portal
Publication:1919176
DOI10.1016/0167-6377(95)00039-9zbMath0855.90069OpenAlexW2112475567MaRDI QIDQ1919176
Bo Chen, André van Vliet, Gerhard J. Woeginger
Publication date: 11 February 1997
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: http://repub.eur.nl/pub/100284
approximation algorithmmakespanidentical parallel machinespreemptionon-line schedulingworst-case guarantee
Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items (34)
A lower bound for randomized on-line multiprocessor scheduling ⋮ Separating online scheduling algorithms with the relative worst order ratio ⋮ An Optimal Preemptive Algorithm for Online MapReduce Scheduling on Two Parallel Machines ⋮ An optimal online algorithm for scheduling with general machine cost functions ⋮ On the value of job migration in online makespan minimization ⋮ Semi-online scheduling: a survey ⋮ Preemptive online scheduling with rejection of unit jobs on two uniformly related machines ⋮ Parallel solutions for preemptive makespan scheduling on two identical machines ⋮ A Lower Bound for the On-Line Preemptive Machine Scheduling with ℓ p Norm ⋮ Unnamed Item ⋮ Randomized on-line scheduling on three processors. ⋮ Preemptive scheduling on a small number of hierarchical machines ⋮ Optimal on-line algorithms to minimize makespan on two machines with resource augmentation ⋮ Robust algorithms for preemptive scheduling ⋮ A lower bound for on-line scheduling on uniformly related machines ⋮ Optimal semi-online algorithms for preemptive scheduling problems with inexact partial information ⋮ Semi-online scheduling with decreasing job sizes ⋮ On the optimality of list scheduling for online uniform machines scheduling ⋮ Semi-online preemptive scheduling: one algorithm for all variants ⋮ On-line scheduling of small open shops ⋮ Optimal semi-online preemptive algorithms for machine covering on two uniform machines ⋮ Preemptive online algorithms for scheduling with machine cost ⋮ Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios ⋮ Preemptive multiprocessor scheduling with rejection ⋮ Randomized on-line scheduling similar jobs to minimize makespan on two identical processors ⋮ Preemptive online scheduling: Optimal algorithms for all speeds ⋮ Robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizes ⋮ Optimal and online preemptive scheduling on uniformly related machines ⋮ Scheduling uniform machines on-line requires nondecreasing speed ratios ⋮ Resource augmentation in load balancing. ⋮ Preemptive on-line scheduling for two uniform processors ⋮ Preemptive machine covering on parallel machines ⋮ Optimal preemptive semi-online scheduling to minimize makespan on two related machines ⋮ On-line scheduling to minimize Max flow time: an optimal preemptive algorithm
Cites Work
This page was built for publication: An optimal algorithm for preemptive on-line scheduling
