Online makespan minimization with budgeted uncertainty

DOI10.1007/978-3-030-83508-8_4MaRDI QIDQ832833zbMATH OpenOpenAlexFDO

Authors Susanne Albers, Maximilian Janke

Publication date 25 March 2022

Full work available at URL https://doi.org/10.1007/978-3-030-83508-8_4

zbMATH Keywords

budgeted uncertaintycompetitive analysislower boundmakespan minimizationonline algorithmschedulinguncertainty

Mathematics Subject Classification ID

Data structures (68P05) Algorithms in computer science (68Wxx)

Recommendations

• Approximation results for makespan minimization with budgeted uncertainty
• Approximation results for makespan minimization with budgeted uncertainty
• Online makespan scheduling with sublinear advice
• Online scheduling on unbounded parallel-batch machines to minimize the makespan
• Makespan minimization in online scheduling with machine eligibility
• Makespan minimization in online scheduling with machine eligibility
• Online scheduling on an unbounded parallel-batch machine and a standard machine to minimize makespan

Cites work

• A Better Algorithm for an Ancient Scheduling Problem
• A better lower bound for on-line scheduling
• Algorithms and complexity analysis for robust single-machine scheduling problems
• An adversarial model for scheduling with testing
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• Approximating a two-machine flow shop scheduling under discrete scenario uncertainty
• Approximating robust bin packing with budgeted uncertainty
• Approximating Single Machine Scheduling with Scenarios
• Approximating the optimal algorithm for online scheduling problems via dynamic programming
• Approximation algorithms for scheduling unrelated parallel machines
• Approximation results for makespan minimization with budgeted uncertainty
• Better Bounds for Online Scheduling
• Bounds for Certain Multiprocessing Anomalies
• Complexity of single machine scheduling problems under scenario-based uncertainty
• Computing the median with uncertainty
• scientific article; zbMATH DE number 4130003 (Why is no real title available?)
• Linear programming under uncertainty
• New algorithms for an ancient scheduling problem.
• On-line scheduling revisited
• Online scheduling with bounded migration
• Parallel machine scheduling under uncertainty
• Query-competitive algorithms for cheapest set problems under uncertainty
• Robust discrete optimization and network flows
• Robust scheduling with budgeted uncertainty
• Scheduling In the random-order model
• Scheduling with explorable uncertainty
• Semi-on-line multiprocessor scheduling with given total processing time
• The Power of Reordering for Online Minimum Makespan Scheduling
• The price of information in combinatorial optimization
• The Price of Robustness
• The update complexity of selection and related problems
• Tight bounds for online vector scheduling

Cited in

(3)

• A single representative min-max-min robust selection problem with alternatives and budgeted uncertainty
• Total completion time scheduling under scenarios
• Perpetual scheduling with explorable uncertainty

This page was built for publication: Online makespan minimization with budgeted uncertainty

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