A \(2.28\)-competitive algorithm for online scheduling on identical machines

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

zbMATH Keywords

competitive analysisonline algorithmsinstance reductionidentical machines scheduling

Mathematics Subject Classification ID

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