An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
From MaRDI portal
Publication:4032943
DOI10.1137/0222026zbMath0781.90051OpenAlexW1982084418MaRDI QIDQ4032943
Gábor Galambos, Gerhard J. Woeginger
Publication date: 17 May 1993
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0222026
Related Items (44)
A survey on makespan minimization in semi-online environments ⋮ Online makespan minimization with parallel schedules ⋮ A lower bound for randomized on-line multiprocessor scheduling ⋮ Scheduling with testing on multiple identical parallel machines ⋮ Online makespan minimization with budgeted uncertainty ⋮ List's worst-average-case or WAC ratio ⋮ New lower and upper bounds for on-line scheduling ⋮ On two dimensional packing ⋮ Parallel Machine Scheduling with Uncertain Communication Delays ⋮ Separating online scheduling algorithms with the relative worst order ratio ⋮ 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 ⋮ Lower bounds for online makespan minimization on a small number of related machines ⋮ An on-line algorithm for some uniform processor Scheduling ⋮ Machine covering in the random-order model ⋮ Improved algorithm for a generalized on-line scheduling problem on identical machines ⋮ Semi-online scheduling revisited ⋮ The \(k\)-server problem ⋮ Online scheduling with rejection and withdrawal ⋮ Scheduling unit length jobs on parallel machines with lookahead information ⋮ On Approximation Algorithms for Two-Stage Scheduling Problems ⋮ Online scheduling with rejection and reordering: exact algorithms for unit size jobs ⋮ Scheduling In the random-order model ⋮ 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 ⋮ Improved bounds for online scheduling with eligibility constraints ⋮ Pseudo lower bounds for online parallel machine scheduling ⋮ Preemptive multiprocessor scheduling with rejection ⋮ On-line load balancing of temporary tasks revisited ⋮ On-line bin-stretching ⋮ An optimal online algorithm for scheduling two machines with release times ⋮ Semi on-line algorithms for the partition problem ⋮ The optimal on-line parallel machine scheduling ⋮ On scheduling inclined jobs on multiple two-stage flowshops ⋮ A 2-competitive largest job on least loaded machine online algorithm based on the multi list scheduling model ⋮ New results on competitive analysis of online SRPT scheduling ⋮ Approximating the Optimal Algorithm for Online Scheduling Problems via Dynamic Programming ⋮ Online scheduling with migration on two hierarchical machines ⋮ On-line scheduling revisited ⋮ A new on-line scheduling heuristic ⋮ Optimal preemptive semi-online scheduling to minimize makespan on two related machines
This page was built for publication: An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
