{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:39Z","timestamp":1740109299801,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T00:00:00Z","timestamp":1601424000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T00:00:00Z","timestamp":1601424000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100020884","name":"ANID","doi-asserted-by":"crossref","award":["BASAL AFB-180003","BASAL AFB-170001"],"award-info":[{"award-number":["BASAL AFB-180003","BASAL AFB-170001"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,2]]},"DOI":"10.1007\/s10107-020-01571-5","type":"journal-article","created":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T17:03:16Z","timestamp":1601485396000},"page":"847-869","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Performance guarantees of local search for minsum scheduling problems"],"prefix":"10.1007","volume":"191","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3012-7622","authenticated-orcid":false,"given":"Jos\u00e9 R.","family":"Correa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Felipe T.","family":"Mu\u00f1oz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,9,30]]},"reference":[{"key":"1571_CR1","doi-asserted-by":"crossref","unstructured":"Abed, F., Correa, J.R., Huang, C.: Optimal coordination mechanisms for multi-job scheduling games. In: ESA (2014)","DOI":"10.1007\/978-3-662-44777-2_2"},{"issue":"1\u20133","key":"1571_CR2","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0166-218X(01)00338-9","volume":"123","author":"R Ahuja","year":"2002","unstructured":"Ahuja, R., Ergun, O., Orlin, J., Punnen, A.: A survey of very large-scale neighborhood search techniques. Discrete Appl. Math. 123(1\u20133), 75\u2013102 (2002)","journal-title":"Discrete Appl. Math."},{"key":"1571_CR3","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/11671541_2","volume-title":"Efficient Approximation and Online Algorithms: Recent Progress on Classical Combinatorial Optimization Problems and New Applications","author":"E Angel","year":"2006","unstructured":"Angel, E.: A survey of approximation results for local search algorithms. In: Bampis, E., Jansen, K., Kenyon, C. (eds.) Efficient Approximation and Online Algorithms: Recent Progress on Classical Combinatorial Optimization Problems and New Applications, vol. 3484, pp. 30\u201373. Springer, Berlin (2006)"},{"key":"1571_CR4","doi-asserted-by":"crossref","unstructured":"Bansal, N., Srinivasan, A., Svensson, O.: Lift-and-round to improve weighted completion time on unrelated machines. In: STOC (2016)","DOI":"10.1145\/2897518.2897572"},{"issue":"1","key":"1571_CR5","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0166-218X(96)00036-4","volume":"72","author":"P Brucker","year":"1997","unstructured":"Brucker, P., Hurink, J., Werner, F.: Improving local search heuristics for some scheduling problems. part II. Discrete Appl. Math. 72(1), 47\u201369 (1997)","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"1571_CR6","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1016\/j.orl.2005.08.003","volume":"34","author":"T Brueggemann","year":"2006","unstructured":"Brueggemann, T., Hurink, J.L., Kern, W.: Quality of move-optimal schedules for minimizing total weighted completion time. Op. Res. Lett. 34(5), 583\u2013590 (2006)","journal-title":"Op. Res. Lett."},{"issue":"8","key":"1571_CR7","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1002\/nav.20485","volume":"58","author":"T Brueggemann","year":"2011","unstructured":"Brueggemann, T., Hurink, J.L., Vredeveld, T., Woeginger, G.J.: Exponential size neighborhoods for makespan minimization scheduling. Naval Res. Logist. 58(8), 795\u2013803 (2011)","journal-title":"Naval Res. Logist."},{"issue":"7","key":"1571_CR8","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/361011.361064","volume":"17","author":"J Bruno","year":"1974","unstructured":"Bruno, J., Coffman Jr., E.G., Sethi, R.: Scheduling independent tasks to reduce mean finishing time. Commun. ACM 17(7), 382\u2013387 (1974)","journal-title":"Commun. ACM"},{"issue":"3","key":"1571_CR9","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1007\/s00453-010-9427-8","volume":"61","author":"I Caragiannis","year":"2011","unstructured":"Caragiannis, I., Flammini, M., Kaklamanis, C., Kanellopoulos, P., Moscardelli, L.: Tight bounds for selfish and greedy load balancing. Algorithmica 61(3), 606\u2013637 (2011)","journal-title":"Algorithmica"},{"issue":"1","key":"1571_CR10","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/0209007","volume":"9","author":"Y Cho","year":"1980","unstructured":"Cho, Y., Sahni, S.: Bounds for list schedules on uniform processors. SIAM J. Comput. 9(1), 91\u2013103 (1980)","journal-title":"SIAM J. Comput."},{"key":"1571_CR11","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1016\/j.geb.2013.03.011","volume":"92","author":"R Cole","year":"2015","unstructured":"Cole, R., Correa, J.R., Gkatzelis, V., Mirrokni, V., Olver, N.: Decentralized utilitarian mechanisms for scheduling games. Games Econ. Behav. 92, 306\u2013326 (2015)","journal-title":"Games Econ. Behav."},{"key":"1571_CR12","volume-title":"Theory of Scheduling","author":"R Conway","year":"1967","unstructured":"Conway, R., Maxwell, W., Miller, L.: Theory of Scheduling. Addison-Wesley, Reading (1967)"},{"issue":"5","key":"1571_CR13","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1002\/nav.21497","volume":"59","author":"JR Correa","year":"2012","unstructured":"Correa, J.R., Queyranne, M.: Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost. Naval Res. Logist. 59(5), 384\u2013395 (2012)","journal-title":"Naval Res. Logist."},{"issue":"1","key":"1571_CR14","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s00453-003-1077-7","volume":"39","author":"L Epstein","year":"2004","unstructured":"Epstein, L., Sgall, J.: Approximation schemes for scheduling on uniformly related and identical parallel machines. Algorithmica 39(1), 43\u201357 (2004)","journal-title":"Algorithmica"},{"issue":"3","key":"1571_CR15","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/BF01930985","volume":"19","author":"G Finn","year":"1979","unstructured":"Finn, G., Horowitz, E.: A linear time approximation algorithm for multiprocessor scheduling. BIT Numer. Math. 19(3), 312\u2013320 (1979)","journal-title":"BIT Numer. Math."},{"issue":"2","key":"1571_CR16","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1023\/B:JOCO.0000031420.05971.29","volume":"8","author":"A Frangioni","year":"2004","unstructured":"Frangioni, A., Necciari, E., Scutell\u00e0, M.G.: A multi-exchange neighborhood for minimum makespan parallel machine scheduling problems. J. Comb. Optim. 8(2), 195\u2013220 (2004)","journal-title":"J. Comb. Optim."},{"issue":"3","key":"1571_CR17","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1145\/322077.322090","volume":"25","author":"MR Garey","year":"1978","unstructured":"Garey, M.R., Johnson, D.S.: Strong NP-Completeness results: motivation, examples, and implications. J. ACM 25(3), 499\u2013508 (1978)","journal-title":"J. ACM"},{"key":"1571_CR18","volume-title":"Computers and Intractability, a Guide to the Theory of NP-Completness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, a Guide to the Theory of NP-Completness. WH Freeman and Co, San Francisco (1979)"},{"key":"1571_CR19","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287\u2013326 (1979)","journal-title":"Ann. Discrete Math."},{"issue":"1","key":"1571_CR20","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"DS Hochbaum","year":"1987","unstructured":"Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM 34(1), 144\u2013162 (1987)","journal-title":"J. ACM"},{"issue":"3","key":"1571_CR21","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1137\/0217033","volume":"17","author":"DS Hochbaum","year":"1988","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A polynomial approximation scheme for scheduling on uniform processors: using the dual approximation approach. SIAM J. Comput. 17(3), 539\u2013551 (1988)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1571_CR22","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1287\/opre.21.3.846","volume":"21","author":"WA Horn","year":"1973","unstructured":"Horn, W.A.: Technical note-minimizing average flow time with parallel machines. Op. Res. 21(3), 846\u2013847 (1973)","journal-title":"Op. Res."},{"issue":"2","key":"1571_CR23","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1145\/321941.321951","volume":"23","author":"E Horowitz","year":"1976","unstructured":"Horowitz, E., Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. J. ACM 23(2), 317\u2013327 (1976)","journal-title":"J. ACM"},{"issue":"2","key":"1571_CR24","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.cosrev.2009.04.003","volume":"3","author":"E Koutsoupias","year":"2009","unstructured":"Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. Comput. Sci. Rev. 3(2), 65\u201369 (2009)","journal-title":"Comput. Sci. Rev."},{"key":"1571_CR25","first-page":"445","volume":"4","author":"EL Lawler","year":"1993","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: Sequencing and scheduling: algorithms and complexity. Handb. Op. Res. Manag. Sci. 4, 445\u2013522 (1993)","journal-title":"Handb. Op. Res. Manag. Sci."},{"key":"1571_CR26","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"J Lenstra","year":"1977","unstructured":"Lenstra, J., Rinnooy Kan, A.H.G., Brucker, P.: Complexity of machine scheduling problems. Ann. Discrete Math. 1, 343\u2013362 (1977)","journal-title":"Ann. Discrete Math."},{"issue":"1\u20133","key":"1571_CR27","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"JK Lenstra","year":"1990","unstructured":"Lenstra, J.K., Shmoys, D.B., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46(1\u20133), 259\u2013271 (1990)","journal-title":"Math. Program."},{"key":"1571_CR28","doi-asserted-by":"crossref","unstructured":"Li, S.: Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations. In: FOCS (2017)","DOI":"10.1109\/FOCS.2017.34"},{"key":"1571_CR29","volume-title":"Theoretical Aspects of Local Search","author":"W Michiels","year":"2007","unstructured":"Michiels, W., Aarts, E., Korst, J.: Theoretical Aspects of Local Search. Springer Science & Business Media, Berlin (2007)"},{"key":"1571_CR30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26580-3","volume-title":"Scheduling: Theory, Algorithms, and Systems","author":"ML Pinedo","year":"2016","unstructured":"Pinedo, M.L.: Scheduling: Theory, Algorithms, and Systems. Springer, Berlin (2016)"},{"key":"1571_CR31","doi-asserted-by":"crossref","unstructured":"Recalde, D., Rutten, C., Schuurman, P., Vredeveld, T.: Local search performance guarantees for restricted related parallel machine scheduling. In: LATIN (2010)","DOI":"10.1007\/978-3-642-12200-2_11"},{"issue":"4","key":"1571_CR32","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/j.orl.2012.04.002","volume":"40","author":"C Rutten","year":"2012","unstructured":"Rutten, C., Recalde, D., Schuurman, P., Vredeveld, T.: Performance guarantees of jump neighborhoods on restricted related parallel machines. Op. Res. Lett. 40(4), 287\u2013291 (2012)","journal-title":"Op. Res. Lett."},{"issue":"1","key":"1571_CR33","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1287\/ijoc.1050.0152","volume":"19","author":"P Schuurman","year":"2007","unstructured":"Schuurman, P., Vredeveld, T.: Performance guarantees of local search for multiprocessor scheduling. INFORMS J. Comput. 19(1), 52\u201363 (2007)","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"1571_CR34","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1287\/moor.25.1.63.15212","volume":"25","author":"M Skutella","year":"2000","unstructured":"Skutella, M., Woeginger, G.J.: A ptas for minimizing the total weighted completion time on identical parallel machines. Math. Op. Res. 25(1), 63\u201375 (2000)","journal-title":"Math. Op. Res."},{"issue":"1\u20132","key":"1571_CR35","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"WE Smith","year":"1956","unstructured":"Smith, W.E.: Various optimizers for single-stage production. Naval Res. Logist. 3(1\u20132), 59\u201366 (1956)","journal-title":"Naval Res. Logist."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01571-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01571-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01571-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,22]],"date-time":"2022-02-22T16:04:24Z","timestamp":1645545864000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01571-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,30]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["1571"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01571-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2020,9,30]]},"assertion":[{"value":"5 August 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 September 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}