A \(2.28\)-competitive algorithm for online scheduling on identical machines
From MaRDI portal
Publication:2514649
DOI10.3934/jimo.2015.11.185zbMath1304.90104OpenAlexW2312781965MaRDI QIDQ2514649
Ronghuan Huang, Tundong Liu, Jiping Tao
Publication date: 3 February 2015
Published in: Journal of Industrial and Management Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.3934/jimo.2015.11.185
Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)
Related Items (5)
Scheduling jobs on a single serial-batching machine with dynamic job arrivals and multiple job types ⋮ An effective scheduling method to single-arm cluster tools for processing multiple wafer types ⋮ An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time ⋮ Online Parallel-Machine Scheduling in KRT Environment to Minimize Total Weighted Completion Time ⋮ Randomized selection algorithm for online stochastic unrelated machines scheduling
Cites Work
- Unnamed Item
- On-line scheduling to minimize average completion time revisited.
- A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times
- An optimal semi-online algorithm for a single machine scheduling problem with bounded processing time
- On-line scheduling of parallel machines to minimize total completion times
- LP-based online scheduling: From single to parallel machines
- Minimizing average completion time in the presence of release dates
- A class of on-line scheduling algorithms to minimize total completion time
- The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates
- Single Machine Scheduling with Release Dates
- Efficient Algorithms for Average Completion Time Scheduling
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
- Optimal on-line algorithms for single-machine scheduling
- Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time
- Scheduling
This page was built for publication: A \(2.28\)-competitive algorithm for online scheduling on identical machines