{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T04:54:48Z","timestamp":1743051288302,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031498145"},{"type":"electronic","value":"9783031498152"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-49815-2_8","type":"book-chapter","created":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T07:02:28Z","timestamp":1703142148000},"page":"104-118","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Total Completion Time Scheduling Under Scenarios"],"prefix":"10.1007","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":[[2023,12,22]]},"reference":[{"key":"8_CR1","unstructured":"Adamczyk, M., Grandoni, F., Leonardi, S., Wlodarczyk, M.: When the optimum is also blind: a new perspective on universal optimization. In: 44th International Colloquium on Automata, Languages and Programming, ICALP, volume 80 of LIPIcs, pp. 35:1\u201335:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017)"},{"key":"8_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/978-3-030-83508-8_4","volume-title":"Algorithms and Data Structures","author":"S Albers","year":"2021","unstructured":"Albers, S., Janke, M.: Online makespan minimization with budgeted uncertainty. In: Lubiw, A., Salavatipour, M. (eds.) WADS 2021. LNCS, vol. 12808, pp. 43\u201356. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-83508-8_4"},{"issue":"3","key":"8_CR3","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1016\/j.orl.2007.11.005","volume":"36","author":"Mohamed Ali Aloulou and Federico Della Croce","year":"2008","unstructured":"Mohamed Ali Aloulou and Federico Della Croce: Complexity of single machine scheduling problems under scenario-based uncertainty. Oper. Res. Lett. 36(3), 338\u2013342 (2008)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"8_CR4","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"},{"key":"8_CR5","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. IEEE (2014)","DOI":"10.1109\/FOCS.2014.9"},{"key":"8_CR6","doi-asserted-by":"publisher","DOI":"10.1515\/9781400831050","volume-title":"Robust Optimization","author":"A Ben-Tal","year":"2009","unstructured":"Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization, vol. 28. Princeton University Press, Princeton (2009)"},{"issue":"6","key":"8_CR7","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":"8_CR8","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, Cham (2011). https:\/\/doi.org\/10.1007\/978-1-4614-0237-4"},{"issue":"6","key":"8_CR9","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":"1","key":"8_CR10","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.orl.2022.12.007","volume":"51","author":"W-H Cho","year":"2023","unstructured":"Cho, W.-H., 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":"8_CR11","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)"},{"issue":"2","key":"8_CR12","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."},{"key":"8_CR13","first-page":"1","volume":"20","author":"E Feuerstein","year":"2016","unstructured":"Feuerstein, E., et al.: Minimizing worst-case and average-case makespan over scenarios. J. Sched. 20, 1\u201311 (2016)","journal-title":"J. Sched."},{"issue":"3","key":"8_CR14","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":"4","key":"8_CR15","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"},{"key":"8_CR16","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. Society for Industrial and Applied Mathematics (2004)"},{"key":"8_CR17","series-title":"Communications in Computer and Information Science","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/978-3-642-31724-8_9","volume-title":"Advances in Computational Intelligence","author":"A Kasperski","year":"2012","unstructured":"Kasperski, A., Kurpisz, A., Zieli\u0144ski, P.: Parallel machine scheduling under uncertainty. In: Greco, S., Bouchon-Meunier, B., Coletti, G., Fedrizzi, M., Matarazzo, B., Yager, R.R. (eds.) IPMU 2012. CCIS, vol. 300, pp. 74\u201383. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31724-8_9"},{"key":"8_CR18","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."},{"issue":"1","key":"8_CR19","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":"2","key":"8_CR20","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":"8_CR21","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, Boston (1997)"},{"key":"8_CR22","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."},{"issue":"3","key":"8_CR23","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":"4","key":"8_CR24","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":"8_CR25","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.ejor.2022.11.014","volume":"310","author":"D Shabtay","year":"2022","unstructured":"Shabtay, D., Gilenson, M.: A state-of-the-art survey on multi-scenario scheduling. Eur. J. Oper. Res. 310, 3\u201323 (2022)","journal-title":"Eur. J. Oper. Res."},{"key":"8_CR26","unstructured":"Skutella, M.: Approximation and Randomization in Scheduling. PhD thesis, Technische Universit\u00e4t Berlin (1998)"},{"key":"8_CR27","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."},{"issue":"1","key":"8_CR28","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1023\/A:1013333232691","volume":"6","author":"J Yang","year":"2002","unstructured":"Yang, J., Gang, Yu.: On the robust single machine scheduling problem. J. Comb. Optim. 6(1), 17\u201333 (2002)","journal-title":"J. Comb. Optim."}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-49815-2_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T07:03:21Z","timestamp":1703142201000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-49815-2_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031498145","9783031498152"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-49815-2_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"22 December 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Amsterdam","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 September 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 September 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo-conference.org\/2023\/waoa\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"43","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"16","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"37% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.05","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7.7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}