{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T18:53:15Z","timestamp":1771267995909,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,9,22]],"date-time":"2025-09-22T00:00:00Z","timestamp":1758499200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,9,22]],"date-time":"2025-09-22T00:00:00Z","timestamp":1758499200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006764","name":"Technische Universit\u00e4t Berlin","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006764","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Scheduling jobs with given processing times on identical parallel machines so as to minimize their total completion time is one of the most basic scheduling problems. We study this classical problem under uncertainty, in which the uncertainty is modeled by a set of scenarios. In our model, a scenario is defined as a subset of a predefined and fully specified set of jobs. The aim is to find an assignment of the whole set of jobs to identical parallel machines such that the schedule, obtained for the given scenarios by simply skipping the jobs not in the scenario, optimizes a function of the total completion times over all scenarios. While the underlying scheduling problem without scenarios can be solved efficiently by a simple greedy procedure (SPT rule), scenarios, in general, make the problem NP-hard. We paint an almost complete picture of the evolving complexity landscape, drawing the line between easy and hard. One of our main algorithmic contributions relies on a deep structural result on the maximum imbalance of an optimal schedule, based on a subtle connection to Hilbert bases of a related convex cone.<\/jats:p>","DOI":"10.1007\/s00224-025-10232-z","type":"journal-article","created":{"date-parts":[[2025,9,22]],"date-time":"2025-09-22T11:45:48Z","timestamp":1758541548000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Total Completion Time Scheduling Under Scenarios"],"prefix":"10.1007","volume":"69","author":[{"given":"Thomas","family":"Bosman","sequence":"first","affiliation":[]},{"given":"Martijn","family":"van Ee","sequence":"additional","affiliation":[]},{"given":"Ekin","family":"Ergen","sequence":"additional","affiliation":[]},{"given":"Csan\u00e1d","family":"Imreh","sequence":"additional","affiliation":[]},{"given":"Alberto","family":"Marchetti-Spaccamela","sequence":"additional","affiliation":[]},{"given":"Martin","family":"Skutella","sequence":"additional","affiliation":[]},{"given":"Leen","family":"Stougie","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,9,22]]},"reference":[{"key":"10232_CR1","volume-title":"Theory of Scheduling","author":"RW Conway","year":"1967","unstructured":"Conway, R.W., Maxwell, W.L., Miller, L.W.: Theory of Scheduling. Addison-Wesley Publishing Company, Boston (1967)"},{"key":"10232_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-0237-4","volume-title":"Introduction to Stochastic Programming","author":"JR Birge","year":"2011","unstructured":"Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer, New York (2011)"},{"issue":"2","key":"10232_CR3","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1137\/S1052623499363220","volume":"12","author":"AJ Kleywegt","year":"2002","unstructured":"Kleywegt, A.J., Shapiro, A., Homem-de-Mello, T.: The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2), 479\u2013502 (2002)","journal-title":"SIAM J. Optim."},{"key":"10232_CR4","doi-asserted-by":"crossref","unstructured":"Ben-Tal, A., Ghaoui, L.E., Nemirovski, A.: Robust Optimization. Princeton Series in Applied Mathematics, vol. 28. Princeton University Press, Princeton (2009)","DOI":"10.1515\/9781400831050"},{"issue":"6","key":"10232_CR5","doi-asserted-by":"publisher","first-page":"1019","DOI":"10.1287\/opre.38.6.1019","volume":"38","author":"D Bertsimas","year":"1990","unstructured":"Bertsimas, D., Jaillet, P., Odoni, A.R.: A priori optimization. Oper. Res. 38(6), 1019\u20131033 (1990)","journal-title":"Oper. Res."},{"key":"10232_CR6","doi-asserted-by":"crossref","unstructured":"Shabtay, D., Gilenson, M.: A state-of-the-art survey on multi-scenario scheduling. European Journal of Operational Research. (2022)","DOI":"10.1016\/j.ejor.2022.11.014"},{"key":"10232_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2620-6","volume-title":"Robust Discrete Optimization and Its Applications","author":"P Kouvelis","year":"1997","unstructured":"Kouvelis, P., Yu, G.: Robust Discrete Optimization and Its Applications. Kluwer Academic Publishers, London (1997)"},{"key":"10232_CR8","unstructured":"Immorlica, N., Karger, D., Minkoff, M., Mirrokni, V.S.: On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 691\u2013700 (2004)"},{"key":"10232_CR9","unstructured":"Adamczyk, M., Grandoni, F., Leonardi, S., Wlodarczyk, M.: When the optimum is also blind: a new perspective on universal optimization. In: Chatzigiannakis, I., Indyk, P., Kuhn, F., Muscholl, A. (eds.) 44th International Colloquium on Automata, Languages and Programming. LIPIcs, vol. 80, pp. 35:1\u201335:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2017)"},{"key":"10232_CR10","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/j.dam.2018.04.002","volume":"250","author":"M van Ee","year":"2018","unstructured":"van Ee, M., van Iersel, L., Janssen, T., Sitters, R.: A priori TSP in the scenario model. Discret. Appl. Math. 250, 331\u2013341 (2018)","journal-title":"Discret. Appl. Math."},{"key":"10232_CR11","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/s10951-016-0484-y","volume":"20","author":"E Feuerstein","year":"2017","unstructured":"Feuerstein, E., Marchetti-Spaccamela, A., Schalekamp, F., Sitters, R., van der Ster, S., Stougie, L., van Zuylen, A.: Minimizing worst-case and average-case makespan over scenarios. J. Sched. 20, 545\u2013555 (2017)","journal-title":"J. Sched."},{"issue":"1","key":"10232_CR12","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1023\/A:1013333232691","volume":"6","author":"J Yang","year":"2002","unstructured":"Yang, J., Yu, G.: On the robust single machine scheduling problem. J. Comb. Optim. 6(1), 17\u201333 (2002)","journal-title":"J. Comb. Optim."},{"issue":"3","key":"10232_CR13","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1016\/j.orl.2007.11.005","volume":"36","author":"MA Aloulou","year":"2008","unstructured":"Aloulou, M.A., Croce, F.D.: Complexity of single machine scheduling problems under scenario-based uncertainty. Oper. Res. Lett. 36(3), 338\u2013342 (2008)","journal-title":"Oper. Res. Lett."},{"key":"10232_CR14","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.tcs.2012.12.006","volume":"477","author":"M Mastrolilli","year":"2013","unstructured":"Mastrolilli, M., Mutsanas, N., Svensson, O.: Single machine scheduling with scenarios. Theoret. Comput. Sci. 477, 57\u201366 (2013)","journal-title":"Theoret. Comput. Sci."},{"key":"10232_CR15","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s10951-015-0444-y","volume":"19","author":"A Kasperski","year":"2016","unstructured":"Kasperski, A., Zieli\u0144ski, P.: Single machine scheduling problems with uncertain parameters and the OWA criterion. J. Sched. 19, 177\u2013190 (2016)","journal-title":"J. Sched."},{"key":"10232_CR16","doi-asserted-by":"crossref","unstructured":"Kasperski, A., Kurpisz, A., Zieli\u0144ski, P.: Parallel machine scheduling under uncertainty. In: Advances in Computational Intelligence - 14th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems, pp. 74\u201383. Springer, Berlin, Heidelberg (2012)","DOI":"10.1007\/978-3-642-31724-8_9"},{"key":"10232_CR17","doi-asserted-by":"crossref","unstructured":"Albers, S., Janke, M.: Online makespan minimization with budgeted uncertainty. In: Lubiw, A., Salavatipour, M.R. (eds.) Algorithms and Data Structures - 17th Int. Symposium, WADS 2021. Lecture Notes in Computer Science, vol. 12808, pp. 43\u201356. Springer, Cham (2021)","DOI":"10.1007\/978-3-030-83508-8_4"},{"issue":"6","key":"10232_CR18","doi-asserted-by":"publisher","first-page":"903","DOI":"10.1007\/s00224-020-10024-7","volume":"65","author":"M Bougeret","year":"2021","unstructured":"Bougeret, M., Jansen, K., Poss, M., Rohwedder, L.: Approximation results for makespan minimization with budgeted uncertainty. Theory Comput. Syst. 65(6), 903\u2013915 (2021)","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"10232_CR19","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM 48(4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"issue":"1","key":"10232_CR20","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1137\/S0097539705447372","volume":"37","author":"S Khot","year":"2007","unstructured":"Khot, S., Kindler, G., Mossel, E., O\u2019Donnell, R.: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput. 37(1), 319\u2013357 (2007)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"10232_CR21","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1137\/S0895480199357078","volume":"15","author":"AS Schulz","year":"2002","unstructured":"Schulz, A.S., Skutella, M.: Scheduling unrelated machines by randomized rounding. SIAM J. Discret. Math. 15(4), 450\u2013469 (2002)","journal-title":"SIAM J. Discret. Math."},{"key":"10232_CR22","unstructured":"Skutella, M.: Approximation and randomization in scheduling. PhD thesis, Technische Universit\u00e4t Berlin (1998)"},{"key":"10232_CR23","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1145\/361011.361064","volume":"17","author":"Scheduling independent tasks to reduce mean finishing time","year":"1974","unstructured":"Scheduling independent tasks to reduce mean finishing time: Bruno, J.L., Jr., E.G.C., Sethi, R. Commun. ACM 17, 382\u2013387 (1974)","journal-title":"Commun. ACM"},{"issue":"2","key":"10232_CR24","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1287\/mnsc.11.2.268","volume":"11","author":"WL Eastman","year":"1964","unstructured":"Eastman, W.L., Even, S., Isaacs, I.M.: Bounds for the optimal scheduling of $$n$$ jobs on $$m$$ processors. Manage. Sci. 11(2), 268\u2013279 (1964)","journal-title":"Manage. Sci."},{"issue":"3","key":"10232_CR25","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/S0895480197330254","volume":"13","author":"MX Goemans","year":"2000","unstructured":"Goemans, M.X., Williamson, D.P.: Two-dimensional gantt charts and a scheduling algorithm of Lawler. SIAM J. Discret. Math. 13(3), 281\u2013294 (2000)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"10232_CR26","doi-asserted-by":"publisher","first-page":"1541","DOI":"10.1137\/16M105589X","volume":"32","author":"N Megow","year":"2018","unstructured":"Megow, N., Verschae, J.: Dual techniques for scheduling on a machine with varying speed. SIAM J. Discret. Math. 32(3), 1541\u20131571 (2018)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"10232_CR27","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.orl.2022.12.007","volume":"51","author":"W Cho","year":"2023","unstructured":"Cho, W., Shmoys, D.B., Henderson, S.G.: SPT optimality (mostly) via linear programming. Oper. Res. Lett. 51(1), 99\u2013104 (2023)","journal-title":"Oper. Res. Lett."},{"key":"10232_CR28","doi-asserted-by":"crossref","unstructured":"Austrin, P., Hastad, J., Guruswami, V.: ($$2+\\epsilon$$)-SAT is NP-hard. In: Proceedings of 55th Annual Symposium on Foundations of Computer Science, pp. 1\u201310 (2014). IEEE","DOI":"10.1109\/FOCS.2014.9"},{"key":"10232_CR29","volume-title":"Introduction to Linear Algebra","author":"G Strang","year":"2016","unstructured":"Strang, G.: Introduction to Linear Algebra. Wellesley-Cambridge Press, Wellesley, MA (2016)"},{"key":"10232_CR30","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. John Wiley & Sons, Chichester (1986)"},{"issue":"1","key":"10232_CR31","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/s00453-006-0068-x","volume":"46","author":"A Armon","year":"2006","unstructured":"Armon, A., Zwick, U.: Multicriteria global minimum cuts. Algorithmica 46(1), 15\u201326 (2006)","journal-title":"Algorithmica"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10232-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10232-z","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10232-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T08:52:49Z","timestamp":1769244769000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10232-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,22]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["10232"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10232-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,22]]},"assertion":[{"value":"16 July 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 September 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"33"}}