{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:36:58Z","timestamp":1759847818499},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2020,3,28]],"date-time":"2020-03-28T00:00:00Z","timestamp":1585353600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,3,28]],"date-time":"2020-03-28T00:00:00Z","timestamp":1585353600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"BSF","award":["2016049"],"award-info":[{"award-number":["2016049"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,9]]},"DOI":"10.1007\/s00453-020-00702-w","type":"journal-article","created":{"date-parts":[[2020,3,28]],"date-time":"2020-03-28T13:02:25Z","timestamp":1585400545000},"page":"2644-2667","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Parameterized Multi-Scenario Single-Machine Scheduling Problems"],"prefix":"10.1007","volume":"82","author":[{"given":"Danny","family":"Hermelin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George","family":"Manoussakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Pinedo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dvir","family":"Shabtay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liron","family":"Yedidsion","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,3,28]]},"reference":[{"key":"702_CR1","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/s10951-010-0183-z","volume":"14","author":"H Aissi","year":"2011","unstructured":"Aissi, H., Aloulou, M., Kovalyov, M.: Minimizing the number of late jobs on a single machine under due date uncertainty. J. Sched. 14, 351\u2013360 (2011)","journal-title":"J. Sched."},{"key":"702_CR2","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1016\/j.orl.2007.11.005","volume":"36","author":"A Aloulou","year":"2008","unstructured":"Aloulou, A., Della Croce, F.: Complexity of single machine scheduling problems under scenario-based uncertainty. Oper. Res. Lett. 36, 338\u2013342 (2008)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"702_CR3","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s10852-005-9011-4","volume":"5","author":"P Brucker","year":"2006","unstructured":"Brucker, P., Kravchenko, S.: Scheduling equal processing time jobs to minimize the weighted number of late jobs. J. Math. Model. Algorithms 5(2), 143\u2013165 (2006)","journal-title":"J. Math. Model. Algorithms"},{"key":"702_CR4","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0167-6377(99)00056-5","volume":"25","author":"D Chudak","year":"1999","unstructured":"Chudak, D., Hochbaum, A.: A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine. Oper. Res. Lett. 25, 199\u2013204 (1999)","journal-title":"Oper. Res. Lett."},{"key":"702_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M.: Parameterized Algorithms. Springer, Berlin (2015)"},{"issue":"2","key":"702_CR6","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1287\/mnsc.41.2.363","volume":"41","author":"R Daniels","year":"1995","unstructured":"Daniels, R., Kouvelis, M.: Robust scheduling to hedge against processing time uncertainty in single-stage production. Manag. Sci. 41(2), 363\u2013376 (1995)","journal-title":"Manag. Sci."},{"issue":"9","key":"702_CR7","doi-asserted-by":"publisher","first-page":"1610","DOI":"10.1016\/j.cor.2009.12.001","volume":"37","author":"IR de Farias","year":"2010","unstructured":"de Farias, I.R., Zhao, H., Zhao, M.: A family of inequalities valid for the robust single machine scheduling polyhedron. Comput. Oper. Res. 37(9), 1610\u20131614 (2010)","journal-title":"Comput. Oper. Res."},{"key":"702_CR8","unstructured":"Downey, R., Fellows, M.: Fixed-parameter intractability. In: Proceedings of the 7th Annual Structure in Complexity Theory Conference (COCO \u201992), pp. 36\u201349 (1992)"},{"key":"702_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer, Berlin (1999)"},{"key":"702_CR10","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0377-2217(90)90088-S","volume":"47","author":"H Emmons","year":"1990","unstructured":"Emmons, H., Pinedo, M.: Scheduling stochastic jobs with due dates on parallel machines. Eur. J. Oper. Res. 47, 49\u201355 (1990)","journal-title":"Eur. J. Oper. Res."},{"key":"702_CR11","volume-title":"Parameterized Complexity Theory. An EATCS Series: Texts in Theoretical Computer Science","author":"J Flum","year":"1998","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. An EATCS Series: Texts in Theoretical Computer Science. Springer, Berlin (1998)"},{"issue":"1","key":"702_CR12","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A Frank","year":"1987","unstructured":"Frank, A., Tardos, \u00c9.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49\u201365 (1987)","journal-title":"Combinatorica"},{"issue":"3","key":"702_CR13","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"ML Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596\u2013615 (1987)","journal-title":"J. ACM"},{"key":"702_CR14","doi-asserted-by":"publisher","DOI":"10.1080\/01605682.2019.1578628","author":"M Gilenson","year":"2019","unstructured":"Gilenson, M., Shabtay, D.: Multi-scenario scheduling to maximize the weighted number of just-in-time jobs. J. Oper. Res. Soc. (2019). https:\/\/doi.org\/10.1080\/01605682.2019.1578628","journal-title":"J. Oper. Res. Soc."},{"key":"702_CR15","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s10951-018-0588-7","volume":"22","author":"M Gilenson","year":"2019","unstructured":"Gilenson, M., Naseraldin, H., Yedidsion, L.: An approximation scheme for the bi-scenario sum of completion times trade-off problem. J. Sched. 22, 289\u2013304 (2019)","journal-title":"J. Sched."},{"key":"702_CR16","doi-asserted-by":"publisher","first-page":"685","DOI":"10.2307\/3213099","volume":"16","author":"K Glazebrook","year":"1979","unstructured":"Glazebrook, K.: Scheduling tasks with exponential service times on parallel processors. J. Appl. Probab. 16, 685\u2013689 (1979)","journal-title":"J. Appl. Probab."},{"key":"702_CR17","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1287\/opre.37.1.126","volume":"37","author":"T Kampke","year":"1989","unstructured":"Kampke, T.: Optimal scheduling of jobs with exponential service times on identical parallel machines. Oper. Res. 37, 126\u2013133 (1989)","journal-title":"Oper. Res."},{"issue":"3","key":"702_CR18","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan, R.: Minkowski\u2019s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415\u2013440 (1987)","journal-title":"Math. Oper. Res."},{"key":"702_CR19","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R Karp","year":"1972","unstructured":"Karp, R.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J., Bohlinger, D. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Springer, Berlin (1972)"},{"key":"702_CR20","unstructured":"Kasperski, A., Zieli\u0144ski, P.: Minmax (regret) scheduling problems. In: Sotskov, Y., Werner, F. (eds.) Sequencing and Scheduling with Inaccurate Data, pp. 159\u2013210. Nova Science Publishers, Inc., Hauppauge, NY (2014)"},{"key":"702_CR21","doi-asserted-by":"crossref","unstructured":"Kasperski, A., Zieli\u0144ski, P.: Robust single machine scheduling problem with weighted number of late jobs criterion. In: Operations Research Proceedings, pp. 279\u2013284. Springer, New York (2014)","DOI":"10.1007\/978-3-319-28697-6_39"},{"issue":"2","key":"702_CR22","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(2), 177\u2013190 (2016)","journal-title":"J. Sched."},{"issue":"5","key":"702_CR23","first-page":"421","volume":"32","author":"R Kouvelis","year":"2000","unstructured":"Kouvelis, R., Daniels, M., Vairaktarakis, G.: Robust scheduling of a two-machine flow shop with uncertain processing times. IIE Trans. 32(5), 421\u2013432 (2000)","journal-title":"IIE Trans."},{"issue":"8","key":"702_CR24","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1016\/0305-0548(95)00078-X","volume":"23","author":"A Lann","year":"1996","unstructured":"Lann, A., Mosheiov, G.: Single machine scheduling to minimize the number of early and tardy jobs. Comput. OR 23(8), 769\u2013781 (1996)","journal-title":"Comput. OR"},{"issue":"1","key":"702_CR25","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1287\/mnsc.16.1.77","volume":"16","author":"E Lawler","year":"1969","unstructured":"Lawler, E., Moore, J.: A functional equation and its application to resource allocation and sequencing problems. Manag. Sci. 16(1), 77\u201384 (1969)","journal-title":"Manag. Sci."},{"issue":"4","key":"702_CR26","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"H Lenstra","year":"1983","unstructured":"Lenstra, H.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"issue":"7","key":"702_CR27","doi-asserted-by":"publisher","first-page":"1682","DOI":"10.1016\/j.cor.2011.10.003","volume":"39","author":"KLS Lu","year":"2012","unstructured":"Lu, K.L.S., Lin, C.C., Ying, S.W., Ying, K.: Robust scheduling on a single machine to minimize total flow time. Comput. Oper. Res. 39(7), 1682\u20131691 (2012)","journal-title":"Comput. Oper. Res."},{"issue":"7","key":"702_CR28","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. Theor. Comput. Sci. 477(7), 57\u201366 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"702_CR29","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1287\/mnsc.15.1.102","volume":"15","author":"J Moore","year":"1968","unstructured":"Moore, J.: An $$n$$ job, one machine sequencing algorithm for minimizing the number of late jobs. Manag. Sci. 15(1), 102\u2013109 (1968)","journal-title":"Manag. Sci."},{"key":"702_CR30","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford Univerity Press, Oxford (2006)"},{"issue":"10","key":"702_CR31","doi-asserted-by":"publisher","first-page":"1089","DOI":"10.1016\/0305-0548(94)00090-U","volume":"22","author":"J Peha","year":"1995","unstructured":"Peha, J.: Heterogeneous-criteria scheduling: minimizing weighted number of tardy jobs and weighted completion time. Comput. Oper. Res. 22(10), 1089\u20131100 (1995)","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"702_CR32","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/321921.321934","volume":"23","author":"S Sahni","year":"1976","unstructured":"Sahni, S.: Algorithms for scheduling independent tasks. J. ACM 23(1), 116\u2013127 (1976)","journal-title":"J. ACM"},{"key":"702_CR33","doi-asserted-by":"publisher","first-page":"851","DOI":"10.1287\/moor.2015.0757","volume":"41","author":"M Skutella","year":"2016","unstructured":"Skutella, M., Sviridenko, M., Uetz, M.: Unrelated machine scheduling with stochastic processing times. Math. Oper. Res. 41, 851\u2013864 (2016)","journal-title":"Math. Oper. Res."},{"key":"702_CR34","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W Smith","year":"1956","unstructured":"Smith, W.: Various optimizers for single-stage production. Naval Res. Logist. 3, 59\u201366 (1956)","journal-title":"Naval Res. Logist."},{"key":"702_CR35","doi-asserted-by":"publisher","first-page":"187","DOI":"10.2307\/3212936","volume":"17","author":"G Weiss","year":"1980","unstructured":"Weiss, G., Pinedo, M.: Scheduling tasks with exponential service times on non identical processors to minimize various cost functions. J. Appl. Probab. 17, 187\u2013202 (1980)","journal-title":"J. Appl. Probab."},{"issue":"12","key":"702_CR36","doi-asserted-by":"publisher","first-page":"3532","DOI":"10.1080\/00207543.2012.751510","volume":"51","author":"X Xu","year":"2013","unstructured":"Xu, X., Chi, W., Lin, J., Qian, Y.: Robust makespan minimisation in identical parallel machine scheduling problem with interval data. Int. J. Prod. Res. 51(12), 3532\u20133548 (2013)","journal-title":"Int. J. Prod. Res."},{"issue":"1","key":"702_CR37","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."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00702-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00702-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00702-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,28]],"date-time":"2021-03-28T00:16:53Z","timestamp":1616890613000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00702-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,28]]},"references-count":37,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["702"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00702-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,28]]},"assertion":[{"value":"29 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 March 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 March 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}