A Better Algorithm for an Ancient Scheduling Problem
From MaRDI portal
Publication:4876699
DOI10.1006/jagm.1996.0019zbMath0844.68010OpenAlexW2027593932MaRDI QIDQ4876699
David R. Karger, Eric Torng, Steven J. Phillips
Publication date: 5 September 1996
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.1996.0019
Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Theory of operating systems (68N25)
Related Items (41)
A survey on makespan minimization in semi-online environments ⋮ Online makespan minimization with parallel schedules ⋮ Scheduling with testing on multiple identical parallel machines ⋮ Online makespan minimization with budgeted uncertainty ⋮ List's worst-average-case or WAC ratio ⋮ Separating online scheduling algorithms with the relative worst order ratio ⋮ Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures ⋮ ONLINE MINIMUM MAKESPAN SCHEDULING WITH A BUFFER ⋮ On the value of job migration in online makespan minimization ⋮ Scheduling web advertisements: a note on the minspace problem ⋮ Randomized algorithms for that ancient scheduling problem ⋮ Semi-online scheduling problems on a small number of machines ⋮ Machine covering in the random-order model ⋮ Online scheduling with rearrangement on two related machines ⋮ Unnamed Item ⋮ Semi-online scheduling revisited ⋮ Tight Bounds for Online Vector Scheduling ⋮ Online scheduling with rejection and withdrawal ⋮ Optimal on-line algorithms to minimize makespan on two machines with resource augmentation ⋮ Scheduling unit length jobs on parallel machines with lookahead information ⋮ Online scheduling with rejection and reordering: exact algorithms for unit size jobs ⋮ Scheduling In the random-order model ⋮ Online Makespan Scheduling with Job Migration on Uniform Machines ⋮ Semi-online scheduling with decreasing job sizes ⋮ Online scheduling for jobs with nondecreasing release times and similar lengths on parallel machines ⋮ Online scheduling of two job types on a set of multipurpose machines with unit processing times ⋮ Minimizing the maximum starting time on-line ⋮ On-line algorithms for packing rectangles into several strips ⋮ Improved bounds for online scheduling with eligibility constraints ⋮ Load balancing of temporary tasks in the \(\ell _{p}\) norm ⋮ Preemptive multiprocessor scheduling with rejection ⋮ An optimal online algorithm for scheduling two machines with release times ⋮ Online scheduling of jobs with favorite machines ⋮ Extension of algorithm list scheduling for a semi-online scheduling problem ⋮ Semi on-line algorithms for the partition problem ⋮ Online makespan scheduling with job migration on uniform machines ⋮ The optimal on-line parallel machine scheduling ⋮ A 2-competitive largest job on least loaded machine online algorithm based on the multi list scheduling model ⋮ Semi-online scheduling jobs with tightly-grouped processing times on three identical machines ⋮ On-line scheduling revisited ⋮ A manifesto for the computational method
This page was built for publication: A Better Algorithm for an Ancient Scheduling Problem
