An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time

DOI10.3934/jimo.2017057zbMath1412.90053OpenAlexW2642679724MaRDI QIDQ1716959

Jiping Tao, Ran Ma

Publication date: 5 February 2019

Published in: Journal of Industrial and Management Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3934/jimo.2017057

zbMATH Keywords

schedulingcompetitive analysisonline algorithmsparallel machinetotal weighted completion time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Related Items (4)

A best possible algorithm for an online scheduling problem with position-based learning effect ⋮ An optimal online algorithm for single-processor scheduling problem with learning effect ⋮ Randomized selection algorithm for online stochastic unrelated machines scheduling ⋮ A Semi-Online Algorithm for Single Machine Scheduling with Rejection

Cites Work

• Unnamed Item
• A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time
• Online scheduling with linear deteriorating jobs to minimize the total weighted completion time
• On-line scheduling to minimize average completion time revisited.
• 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
• The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates
• A \(2.28\)-competitive algorithm for online scheduling on identical machines
• Single Machine Scheduling with Release Dates
• Efficient Algorithms for Average Completion Time Scheduling
• Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time

This page was built for publication: An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time