Total completion time scheduling under scenarios

DOI10.1007/S00224-025-10232-ZMaRDI QIDQ6911397zbMATH OpenFDO

Authors Thomas Bosman, Martijn van Ee, Ekin Ergen, Csanád Imreh, Alberto Marchetti-Spaccamela, Martin Skutella, L. Stougie

Publication date 24 October 2025

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00224-025-10232-Z

zbMATH Keywords

complexitymachine schedulingscenariostotal completion time

Mathematics Subject Classification ID

Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35)

Cites work

• (2 + )-SAT is NP-hard
• A Priori Optimization
• A priori TSP in the scenario model
• A state-of-the-art survey on multi-scenario scheduling
• Algorithms and data structures. 17th international symposium, WADS 2021, virtual event, August 9--11, 2021. Proceedings
• Approximation and randomization in scheduling
• Approximation results for makespan minimization with budgeted uncertainty
• Complexity of single machine scheduling problems under scenario-based uncertainty
• Dual techniques for scheduling on a machine with varying speed
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 2146482 (Why is no real title available?)
• scientific article; zbMATH DE number 6469210 (Why is no real title available?)
• scientific article; zbMATH DE number 6607459 (Why is no real title available?)
• Introduction to stochastic programming.
• Minimizing worst-case and average-case makespan over scenarios
• Multicriteria global minimum cuts
• On the robust single machine scheduling problem
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Parallel machine scheduling under uncertainty
• Robust discrete optimization and its applications
• Robust optimization
• Scheduling independent tasks to reduce mean finishing time
• Scheduling Unrelated Machines by Randomized Rounding
• Single machine scheduling problems with uncertain parameters and the OWA criterion
• Single machine scheduling with scenarios
• Some optimal inapproximability results
• SPT optimality (mostly) via linear programming
• The sample average approximation method for stochastic discrete optimization
• Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler
• When the optimum is also blind: a new perspective on universal optimization

This page was built for publication: Total completion time scheduling under scenarios

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