A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time

DOI10.1016/J.COR.2013.09.016zbMath1348.68299OpenAlexW2082271152MaRDI QIDQ336914

Jiping Tao

Publication date: 10 November 2016

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2013.09.016

zbMATH Keywords

competitive ratioparallel machineonline schedulingtotal weighted completion timeinstance reduction

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Online algorithms; streaming algorithms (68W27)

Related Items (6)

Online scheduling to minimize the total weighted completion time plus the rejection cost ⋮ An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time ⋮ Online scheduling with linear deteriorating jobs to minimize the total weighted completion time ⋮ Online Parallel-Machine Scheduling in KRT Environment to Minimize Total Weighted Completion Time ⋮ A competitive online algorithm for minimizing total weighted completion time on uniform machines ⋮ Randomized selection algorithm for online stochastic unrelated machines scheduling

Cites Work

• Unnamed Item
• Unnamed Item
• Online scheduling of weighted equal-length jobs with hard deadlines on parallel machines
• 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
• Computation of approximate \(\alpha \)-points for large scale single machine scheduling problem
• The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates
• Single Machine Scheduling with Release Dates
• An Experimental Study of LP-Based Approximation Algorithms for Scheduling Problems
• Efficient Algorithms for Average Completion Time Scheduling
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Scheduling Unrelated Machines by Randomized Rounding
• Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time

This page was built for publication: A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time