A competitive online algorithm for minimizing total weighted completion time on uniform machines

DOI10.1155/2020/7527862MaRDI QIDQ6534502zbMATH OpenFDO

Authors Xuyang Chu, Jiping Tao

Publication date 7 May 2021

Published in Mathematical Problems in Engineering (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1155/2020/7527862

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Online scheduling on \(m\) uniform machines to minimize total (weighted) completion time
• Online scheduling of two uniform machines to minimize total completion times
• An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time
• A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time
• Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time

Cites work

• A \(2.28\)-competitive algorithm for online scheduling on identical machines
• A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time
• A class of on-line scheduling algorithms to minimize total completion time
• A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times
• An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time
• An optimal semi-online algorithm for a single machine scheduling problem with bounded processing time
• Asymptotical optimality of WSEPT for stochastic online scheduling on uniform machines
• Bounds for Certain Multiprocessing Anomalies
• Discovering dispatching rules using data mining
• Fifty years of scheduling: a survey of milestones
• scientific article; zbMATH DE number 5345854 (Why is no real title available?)
• scientific article; zbMATH DE number 2114378 (Why is no real title available?)
• scientific article; zbMATH DE number 6472636 (Why is no real title available?)
• Job Shop Scheduling by Simulated Annealing
• LP-based online scheduling: From single to parallel machines
• Makespan minimization on uniform parallel machines with release times
• Minimizing average completion time in the presence of release dates
• On-line scheduling of parallel machines to minimize total completion times
• On-line scheduling to minimize average completion time revisited.
• Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time
• Online scheduling of two uniform machines to minimize total completion times
• Online scheduling on \(m\) uniform machines to minimize total (weighted) completion time
• Online scheduling on two uniform machines to minimize the makespan
• Optimal on-line algorithms for single-machine scheduling
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Sequencing jobs on a single machine: A neural network approach
• Single machine scheduling with release dates
• Solving Parallel Machine Scheduling Problems by Column Generation
• The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates

Cited in

(2)

• On the Asymptotic Optimality of a Simple On-Line Algorithm for the Stochastic Single-Machine Weighted Completion Time Problem and Its Extensions
• Comments on ``Competitive analysis of a better on-line algorithm to minimize total completion time on a single-machine

This page was built for publication: A competitive online algorithm for minimizing total weighted completion time on uniform machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6534502)