{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T08:55:28Z","timestamp":1769936128292,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2016,6,17]],"date-time":"2016-06-17T00:00:00Z","timestamp":1466121600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2017,12]]},"DOI":"10.1007\/s10951-016-0484-y","type":"journal-article","created":{"date-parts":[[2016,6,17]],"date-time":"2016-06-17T07:44:16Z","timestamp":1466149456000},"page":"545-555","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Minimizing worst-case and average-case makespan over scenarios"],"prefix":"10.1007","volume":"20","author":[{"given":"Esteban","family":"Feuerstein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alberto","family":"Marchetti-Spaccamela","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frans","family":"Schalekamp","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ren\u00e9","family":"Sitters","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suzanne","family":"van der Ster","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leen","family":"Stougie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anke","family":"van Zuylen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,6,17]]},"reference":[{"key":"484_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and approximation: Combinatorial optimization problems and their approximability properties","author":"G Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Kann, V., Gambosi, G., Marchetti-Spaccamela, A., & Protasi, M. (1999). Complexity and approximation: Combinatorial optimization problems and their approximability properties. Berlin: Springer."},{"key":"484_CR2","unstructured":"Austrin, P., H\u00e5stad, J., & Guruswami, V. (2014). $$(2+\\epsilon )$$ ( 2 + \u03f5 ) -SAT is NP-hard. In: Proceedings of 55th Annual IEEE Symposium on Foundations of Computer Science (pp. 1\u201310)."},{"issue":"3","key":"484_CR3","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1007\/s101070100286","volume":"92","author":"A Ben-Tal","year":"2002","unstructured":"Ben-Tal, A., & Nemirovski, A. (2002). Robust optimization\u2014methodology and applications. Mathematical Programming, 92(3), 453\u2013480.","journal-title":"Mathematical Programming"},{"key":"484_CR4","doi-asserted-by":"crossref","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. (2011). Introduction to stochastic programming. New York: Springer Science & Business Media."},{"issue":"4","key":"484_CR5","doi-asserted-by":"crossref","first-page":"837","DOI":"10.1137\/S0097539799356265","volume":"33","author":"C Chekuri","year":"2004","unstructured":"Chekuri, C., & Khanna, S. (2004). On multidimensional packing problems. SIAM Journal on Computing, 33(4), 837\u2013851.","journal-title":"SIAM Journal on Computing"},{"key":"484_CR6","unstructured":"Chen, L., Megow, N., Rischke, R., & Stougie, L. (2015). Stochastic and robust scheduling in the cloud. In: Proceedings of the 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (pp. 175\u2013186)."},{"key":"484_CR7","doi-asserted-by":"crossref","unstructured":"Epstein, L., Levin, A., Marchetti-Spaccamela, A., Megow, N., Mestre, J., Skutella, M., & Stougie, L. (2012). Universal sequencing on an unreliable machine. SIAM Journal on Computing, 41(3), 565\u2013586.","DOI":"10.1137\/110844210"},{"key":"484_CR8","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"MR Garey","year":"1990","unstructured":"Garey, M. R., & Johnson, D. S. (1990). Computers and intractability: A guide to the theory of NP-completeness. New York: W. H. Freeman & Co."},{"issue":"6","key":"484_CR9","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M. X., & Williamson, D. P. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6), 1115\u20131145.","journal-title":"Journal of the ACM"},{"issue":"5","key":"484_CR10","doi-asserted-by":"crossref","first-page":"1361","DOI":"10.1137\/080732250","volume":"40","author":"A Gupta","year":"2011","unstructured":"Gupta, A., P\u00e1l, M., Ravi, R., & Sinha, A. (2011). Sampling and cost-sharing: Approximation algorithms for stochastic optimization problems. SIAM Journal on Computing, 40(5), 1361\u20131401.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"484_CR11","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J. (2001). Some optimal inapproximability results. Journal of the ACM, 48(4), 798\u2013859.","journal-title":"Journal of the ACM"},{"key":"484_CR12","unstructured":"Jaillet, P. (1985). Probabilistic traveling salesman problems. Technical Report 185, Operations Research Center, MIT."},{"key":"484_CR13","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1287\/opre.36.6.929","volume":"36","author":"P Jaillet","year":"1988","unstructured":"Jaillet, P. (1988). A priori solution of a traveling salesman problem in which a random subset of the customers are visited. Operations Research, 36, 929\u2013936.","journal-title":"Operations Research"},{"key":"484_CR14","doi-asserted-by":"crossref","unstructured":"Karloff, H. J., & Zwick, U. (1997). A 7\/8-approximation algorithm for MAX 3SAT? In: Proceedings of 38th Annual IEEE Symposium on Foundations of Computer Science (pp. 406\u2013415).","DOI":"10.1109\/SFCS.1997.646129"},{"key":"484_CR15","doi-asserted-by":"crossref","unstructured":"Kasperski, A., Kurpisz, A., & Zieli\u0144ski, P. (2012). Parallel machine scheduling under uncertainty. In: Proceedings of 14th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU) (pp. 74\u201383).","DOI":"10.1007\/978-3-642-31724-8_9"},{"key":"484_CR16","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.ipl.2012.10.001","volume":"113","author":"A Kasperski","year":"2013","unstructured":"Kasperski, A., Kurpisz, A., & Zieli\u0144ski, P. (2013). Approximating the min-max (regret) selecting items problem. Information Processing Letters, 113, 23\u201329.","journal-title":"Information Processing Letters"},{"key":"484_CR17","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/s10951-015-0444-y","volume":"19","author":"A Kasperski","year":"2016","unstructured":"Kasperski, A., & Zieli\u0144ski, P. (2016). Single machine scheduling problems with uncertain parameters and the OWA criterion. Journal of Scheduling, 19, 177\u2013190.","journal-title":"Journal of Scheduling"},{"key":"484_CR18","unstructured":"Khot, S. (2002). On the power of unique 2-prover 1-round games. In: Proceedings of 34th ACM Symposium on Theory of Computing (pp. 767\u2013775)."},{"issue":"1","key":"484_CR19","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1137\/S0097539705447372","volume":"37","author":"S Khot","year":"2007","unstructured":"Khot, S., Kindler, G., Mossel, E., & O\u2019Donnell, R. (2007). Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM Journal on Computing, 37(1), 319\u2013357.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"484_CR20","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1137\/S1052623499363220","volume":"12","author":"A Kleywegt","year":"2002","unstructured":"Kleywegt, A., Shapiro, A., & de Mello, T. H. (2002). The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2), 479\u2013502.","journal-title":"SIAM Journal on Optimization"},{"key":"484_CR21","doi-asserted-by":"crossref","unstructured":"Lin, X., Janak, S., & Floudas, C. (2004). A new robust optimization approach for scheduling under uncertainty: I. bounded uncertainty. Computers and Chemical Engineering, 28, 1069\u20131085.","DOI":"10.1016\/j.compchemeng.2003.09.020"},{"issue":"4","key":"484_CR22","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1016\/j.orl.2013.04.011","volume":"41","author":"G Oriolo","year":"2013","unstructured":"Oriolo, G., Sanit\u00e0, L., & Zenklusen, R. (2013). Network design with a discrete set of traffic matrices. Operations Research Letters, 41(4), 390\u2013396.","journal-title":"Operations Research Letters"},{"key":"484_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4614-2361-4","volume-title":"Theory, scheduling algorithms and systems","author":"M Pinedo","year":"2012","unstructured":"Pinedo, M. (2012). Theory, scheduling algorithms and systems. Berlin: Springer."},{"issue":"2","key":"484_CR24","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1109\/TSMC.2014.2329284","volume":"45","author":"Z Wang","year":"2015","unstructured":"Wang, Z., & Chan, F. (2015). A robust replenishment and production control policy for a single-stage production\/inventory system with inventory inaccuracy. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 45(2), 326\u2013337.","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics: Systems"},{"issue":"1\u20133","key":"484_CR25","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/j.dam.2002.07.001","volume":"142","author":"J Zhang","year":"2004","unstructured":"Zhang, J., Ye, Y., & Han, Q. (2004). Improved approximations for max set splitting and max NAE SAT. Discrete Applied Mathematics, 142(1\u20133), 133\u2013149.","journal-title":"Discrete Applied Mathematics"},{"key":"484_CR26","doi-asserted-by":"crossref","unstructured":"Zwick, U. (1999). Outward rotations: A tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems. In: Proceedings of 31st ACM Symposium on Theory of Computing (pp. 679\u2013687).","DOI":"10.1145\/301250.301431"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-016-0484-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-016-0484-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-016-0484-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-016-0484-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,18]],"date-time":"2023-08-18T22:50:41Z","timestamp":1692399041000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-016-0484-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,17]]},"references-count":26,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["484"],"URL":"https:\/\/doi.org\/10.1007\/s10951-016-0484-y","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,17]]}}}