A Better Algorithm for an Ancient Scheduling Problem

DOI10.1006/JAGM.1996.0019MaRDI QIDQ4876699zbMATH OpenOpenAlexFDO

Authors David R. Karger, Steven J. Phillips, Eric Torng

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

zbMATH Keywords

online multiprocessor scheduling problem

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Theory of operating systems (68N25)

Recommendations

• scientific article; zbMATH DE number 1003243
• New algorithms for an ancient scheduling problem.
• Improved bounds for on-line load balancing
• Ancient and new algorithms for load balancing in the \(\ell_p\) norm

Cited in

(39)

• Semi-online scheduling problems on a small number of machines
• Online scheduling of two job types on a set of multipurpose machines with unit processing times
• Online makespan minimization with budgeted uncertainty
• Scheduling with testing on multiple identical parallel machines
• Semi-online scheduling with decreasing job sizes
• A manifesto for the computational method
• Semi-online scheduling jobs with tightly-grouped processing times on three identical machines
• Semi-online scheduling revisited
• Online scheduling of jobs with favorite machines
• List's worst-average-case or WAC ratio
• Semi on-line algorithms for the partition problem
• A survey on makespan minimization in semi-online environments
• Load balancing of temporary tasks in the \(\ell _{p}\) norm
• Robust polynomial-time approximation schemes for parallel machine scheduling with job arrivals and departures
• On-line scheduling revisited
• Improved bounds for online scheduling with eligibility constraints
• Online Makespan Scheduling with Job Migration on Uniform Machines
• Tight bounds for online vector scheduling
• Scheduling In the random-order model
• Preemptive multiprocessor scheduling with rejection
• Minimizing the maximum starting time on-line
• Online minimum makespan scheduling with a buffer
• Extension of algorithm list scheduling for a semi-online scheduling problem
• Online makespan minimization: the power of restart
• Online scheduling with rearrangement on two related machines
• Online scheduling for jobs with nondecreasing release times and similar lengths on parallel machines
• Scheduling unit length jobs on parallel machines with lookahead information
• An optimal online algorithm for scheduling two machines with release times
• Scheduling web advertisements: a note on the minspace problem
• Online scheduling with rejection and reordering: exact algorithms for unit size jobs
• Online makespan scheduling with job migration on uniform machines
• Randomized algorithms for that ancient scheduling problem
• Online scheduling with rejection and withdrawal
• On-line algorithms for packing rectangles into several strips
• Optimal on-line algorithms to minimize makespan on two machines with resource augmentation
• Machine covering in the random-order model
• 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
• Separating online scheduling algorithms with the relative worst order ratio

This page was built for publication: A Better Algorithm for an Ancient Scheduling Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4876699)