Approximating the optimal algorithm for online scheduling problems via dynamic programming

DOI10.1142/S0217595915400114MaRDI QIDQ5245846zbMATH OpenFDO

Authors Lin Chen, Deshi Ye, Guochuan Zhang

Publication date 15 April 2015

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

Full work available at URL https://doi.org/10.1142/S0217595915400114

zbMATH Keywords

competitive analysisdynamic programmingonline scheduling

Mathematics Subject Classification ID

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

Recommendations

• A new approach to online scheduling: approximating the optimal competitive ratio
• A new approach to online scheduling: approximating the optimal competitive ratio
• Competitive-ratio approximation schemes for makespan scheduling problems
• scientific article; zbMATH DE number 1559597
• scientific article; zbMATH DE number 1670659

Cites work

• A better lower bound for on-line scheduling
• An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• Ancient and new algorithms for load balancing in the \(\ell_p\) norm
• Better Bounds for Online Scheduling
• Bounds for Certain Multiprocessing Anomalies
• Improved Bounds for the Online Scheduling Problem
• New algorithms for an ancient scheduling problem.
• New lower and upper bounds for on-line scheduling
• On-Line Load Balancing for Related Machines
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• On-line scheduling revisited

Cited in

(13)

• Scheduling In the random-order model
• A best possible algorithm for an online scheduling problem with deteriorating effect in steel box girder section production
• An on-line LS algorithm for some \(Q_m|r_j|C_{\max}\) scheduling
• Competitive-ratio approximation schemes for makespan scheduling problems
• Almost sure asymptotic optimality for online routing and machine scheduling problems
• The optimality of the online greedy algorithm in carpool and chairman assignment problems
• A new approach to online scheduling: approximating the optimal competitive ratio
• A dynamic programming framework for non-preemptive scheduling problems on multiple machines
• A new approach to online scheduling: approximating the optimal competitive ratio
• Online hierarchical scheduling: an approach using mathematical programming
• Scheduling in the random-order model
• Online makespan minimization with budgeted uncertainty
• An asymptotic competitive scheme for online bin packing

This page was built for publication: Approximating the optimal algorithm for online scheduling problems via dynamic programming

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