A Better Algorithm for an Ancient Scheduling Problem
From MaRDI portal
Publication:4876699
DOI10.1006/jagm.1996.0019zbMath0844.68010MaRDI 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
68M20: Performance evaluation, queueing, and scheduling in the context of computer systems
68N25: Theory of operating systems
Related Items
Online scheduling for jobs with nondecreasing release times and similar lengths on parallel machines, On-line algorithms for packing rectangles into several strips, Semi-online scheduling with decreasing job sizes, Preemptive multiprocessor scheduling with rejection, An optimal online algorithm for scheduling two machines with release times, Semi-online scheduling problems on a small number of machines, Semi-online scheduling revisited, Online scheduling with rejection and reordering: exact algorithms for unit size jobs, Online scheduling with rearrangement on two related machines, Online scheduling with rejection and withdrawal, Scheduling unit length jobs on parallel machines with lookahead information, Improved bounds for online scheduling with eligibility constraints, List's worst-average-case or WAC ratio, Scheduling web advertisements: a note on the minspace problem, Optimal on-line algorithms to minimize makespan on two machines with resource augmentation, Extension of algorithm list scheduling for a semi-online scheduling problem, Semi on-line algorithms for the partition problem, The optimal on-line parallel machine scheduling, On-line scheduling revisited, A manifesto for the computational method, Online scheduling of two job types on a set of multipurpose machines with unit processing times, Minimizing the maximum starting time on-line, Separating online scheduling algorithms with the relative worst order ratio, Load balancing of temporary tasks in the \(\ell _{p}\) norm, Semi-online scheduling jobs with tightly-grouped processing times on three identical machines, ONLINE MINIMUM MAKESPAN SCHEDULING WITH A BUFFER
