Approximating the Optimal Algorithm for Online Scheduling Problems via Dynamic Programming

DOI10.1142/S0217595915400114zbMath1311.90058MaRDI QIDQ5245846

Lin Chen, Deshi Ye, Guo-Chuan Zhang

Publication date: 15 April 2015

Published in: Asia-Pacific Journal of Operational Research (Search for Journal in Brave)

zbMATH Keywords

dynamic programmingcompetitive analysisonline scheduling

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Stochastic scheduling theory in operations research (90B36) Dynamic programming (90C39)

Related Items (3)

Online makespan minimization with budgeted uncertainty ⋮ An asymptotic competitive scheme for online bin packing ⋮ Scheduling In the random-order model

Cites Work

• New algorithms for an ancient scheduling problem.
• A better lower bound for on-line scheduling
• On-line scheduling revisited
• New lower and upper bounds for on-line scheduling
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• Better Bounds for Online Scheduling
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Improved Bounds for the Online Scheduling Problem
• On-Line Load Balancing for Related Machines
• An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
• Bounds for Certain Multiprocessing Anomalies
• Ancient and new algorithms for load balancing in the \(\ell_p\) norm

This page was built for publication: Approximating the Optimal Algorithm for Online Scheduling Problems via Dynamic Programming