Online makespan minimization with budgeted uncertainty

DOI10.1007/978-3-030-83508-8_4OpenAlexW3191776655MaRDI QIDQ832833FDOQ832833

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

Recommendations

• Approximation results for makespan minimization with budgeted uncertainty
• Approximation results for makespan minimization with budgeted uncertainty
• Online makespan minimization with parallel schedules
• Online makespan minimization with parallel schedules
• 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

zbMATH Keywords

uncertaintycompetitive analysislower boundschedulingonline algorithmbudgeted uncertaintymakespan minimization

Mathematics Subject Classification ID

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

Cites Work

• On-line scheduling revisited
• The Price of Robustness
• Robust discrete optimization and network flows
• Semi-on-line multiprocessor scheduling with given total processing time
• Bounds for Certain Multiprocessing Anomalies
• Approximation algorithms for scheduling unrelated parallel machines
• Linear programming under uncertainty
• Complexity of single machine scheduling problems under scenario-based uncertainty
• A better lower bound for on-line scheduling
• Title not available (Why is that?)
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• New algorithms for an ancient scheduling problem.
• The update complexity of selection and related problems
• Approximating a two-machine flow shop scheduling under discrete scenario uncertainty
• Algorithms and complexity analysis for robust single-machine scheduling problems
• Better Bounds for Online Scheduling
• The Power of Reordering for Online Minimum Makespan Scheduling
• A Better Algorithm for an Ancient Scheduling Problem
• Approximating Single Machine Scheduling with Scenarios
• Online Scheduling with Bounded Migration
• Approximating the Optimal Algorithm for Online Scheduling Problems via Dynamic Programming
• Robust scheduling with budgeted uncertainty
• Parallel Machine Scheduling under Uncertainty
• Scheduling In the random-order model
• An adversarial model for scheduling with testing
• Approximating robust bin packing with budgeted uncertainty
• Computing the median with uncertainty
• Title not available (Why is that?)
• Tight Bounds for Online Vector Scheduling
• Title not available (Why is that?)
• Approximation results for makespan minimization with budgeted uncertainty
• Query-competitive algorithms for cheapest set problems under uncertainty

Cited In (2)

• Total completion time scheduling under scenarios
• A single representative min-max-min robust selection problem with alternatives and budgeted 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)