An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
From MaRDI portal
Publication:4032943
DOI10.1137/0222026zbMATH Open0781.90051OpenAlexW1982084418MaRDI QIDQ4032943FDOQ4032943
Authors: 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
Recommendations
Cited In (47)
- Semi-online scheduling with decreasing job sizes
- Lower bounds for online makespan minimization on a small number of related machines
- 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
- On-line load balancing of temporary tasks revisited
- Semi-online scheduling revisited
- List's worst-average-case or WAC ratio
- On-line bin-stretching
- Semi on-line algorithms for the partition problem
- Title not available (Why is that?)
- Worst-case performance evaluation on multiprocessor task scheduling with resource augmentation
- A survey on makespan minimization in semi-online environments
- Pseudo lower bounds for online parallel machine scheduling
- Experimental analysis of online algorithms for the bicriteria scheduling problem
- A lower bound for randomized on-line multiprocessor scheduling
- On Approximation Algorithms for Two-Stage Scheduling Problems
- On-line scheduling revisited
- Improved bounds for online scheduling with eligibility constraints
- Scheduling In the random-order model
- Preemptive multiprocessor scheduling with rejection
- Optimal preemptive semi-online scheduling to minimize makespan on two related machines
- New lower and upper bounds for on-line scheduling
- The \(k\)-server problem
- On scheduling inclined jobs on multiple two-stage flowshops
- Worst-case analysis for on-line service policies
- Improved algorithm for a generalized on-line scheduling problem on identical machines
- A new on-line scheduling heuristic
- Online scheduling for jobs with nondecreasing release times and similar lengths on parallel machines
- An optimal online algorithm for scheduling two machines with release times
- An on-line algorithm for some uniform processor Scheduling
- Scheduling unit length jobs on parallel machines with lookahead information
- On two dimensional packing
- Scheduling web advertisements: a note on the minspace problem
- Online scheduling with rejection and reordering: exact algorithms for unit size jobs
- Randomized algorithms for that ancient scheduling problem
- Online scheduling with rejection and withdrawal
- On the Robustness of Graham’s Algorithm for Online Scheduling
- Machine covering in the random-order model
- Approximating the optimal algorithm for online scheduling problems via dynamic programming
- 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
- New results on competitive analysis of online SRPT scheduling
- Online scheduling with migration on two hierarchical machines
- Separating online scheduling algorithms with the relative worst order ratio
- Parallel Machine Scheduling with Uncertain Communication Delays
This page was built for publication: An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4032943)
