{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:31Z","timestamp":1740122371477,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,3,31]],"date-time":"2024-03-31T00:00:00Z","timestamp":1711843200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,3,31]],"date-time":"2024-03-31T00:00:00Z","timestamp":1711843200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["National Natural Science Foundation of China"],"award-info":[{"award-number":["National Natural Science Foundation of China"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,4]]},"DOI":"10.1007\/s10878-024-01118-w","type":"journal-article","created":{"date-parts":[[2024,3,31]],"date-time":"2024-03-31T17:01:30Z","timestamp":1711904490000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines"],"prefix":"10.1007","volume":"47","author":[{"given":"Ruiqing","family":"Sun","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,3,31]]},"reference":[{"key":"1118_CR1","doi-asserted-by":"crossref","unstructured":"Afrati FN, Bampis E, Chekuri C, Karger DR, Kenyon C, Khanna S, Milis I, Queyranne M, Skutella M, Stein C, Sviridenko M (1999) Approximation schemes for minimizing average weighted completion time with release dates. In: Proceedings of the 40th annual IEEE symposium on foundations of computer science. IEEE Computer Society Press, Los Alamitos, CA, pp 32\u201343","DOI":"10.1109\/SFFCS.1999.814574"},{"issue":"1","key":"1118_CR2","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J","volume":"1","author":"N Alon","year":"1998","unstructured":"Alon N, Azar Y, Woeginger GJ, Yadid T (1998) Approximation schemes for scheduling on parallel machines. J Sched 1(1):55\u201366","journal-title":"J Sched"},{"key":"1118_CR3","doi-asserted-by":"crossref","unstructured":"Bansal N, Srinivasan A, Svensson O (2016) Lift-and-round to improve weighted completion time on unrelated machines. In: Proceedings of 48th annual ACM symposium theory computing (STOC). ACM, pp 156\u2013167","DOI":"10.1145\/2897518.2897572"},{"key":"1118_CR4","doi-asserted-by":"crossref","unstructured":"Baveja A, Qu X, Srinivasan A (2023) Approximating weighted completion time via stronger negative correlation. J Sched 1\u201310","DOI":"10.1007\/s10951-023-00780-y"},{"issue":"6","key":"1118_CR5","doi-asserted-by":"publisher","first-page":"1625","DOI":"10.1002\/cpe.3359","volume":"27","author":"R Bleuse","year":"2015","unstructured":"Bleuse R, Kedad-Sidhoum S, Monna F, Mouni\u00e9 G, Trystram D (2015) Scheduling independent tasks on multi-cores with gpu accelerators. Concurr Comput Pract Exp 27(6):1625\u20131638","journal-title":"Concurr Comput Pract Exp"},{"key":"1118_CR6","doi-asserted-by":"publisher","first-page":"1850048","DOI":"10.1142\/S0217595918500483","volume":"35","author":"X Chai","year":"2018","unstructured":"Chai X, Lu LF, Li WH, Zhang LQ (2018) Best-possible online algorithms for single machine scheduling to minimize the maximum weighted completion time. Asia-Pac J Oper Res 35:1850048","journal-title":"Asia-Pac J Oper Res"},{"key":"1118_CR7","first-page":"121","volume":"11","author":"Q Feng","year":"2007","unstructured":"Feng Q, Yuan JJ (2007) NP-hardness of a multicriteria scheduling on two families of jobs. OR Trans 11:121\u2013126","journal-title":"OR Trans"},{"issue":"4","key":"1118_CR8","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1142\/S0129054118410071","volume":"29","author":"JC Gehrke","year":"2018","unstructured":"Gehrke JC, Jansen K, Kraft SE, Schikowski J (2018) A PTAS for scheduling unrelated machines of few different types. Int J Found Comput Sci 29(4):591\u2013621","journal-title":"Int J Found Comput Sci"},{"issue":"9","key":"1118_CR9","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"RL Graham","year":"1966","unstructured":"Graham RL (1966) Bounds for certain multiprocessing anomalies. Bell Syst Tech J 45(9):1563\u20131581","journal-title":"Bell Syst Tech J"},{"issue":"2","key":"1118_CR10","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham RL (1969) Bounds on multiprocessing timing anomalies. SIAM J Appl Math 17(2):416\u2013429","journal-title":"SIAM J Appl Math"},{"key":"1118_CR11","volume-title":"Approximation algorithms","author":"DS Hochbaum","year":"1997","unstructured":"Hochbaum DS (1997) Various notions of approximations: good, better, best and more. In: Hochbaum DS (ed) Approximation algorithms. PWS Publishing Company, Boston"},{"issue":"1","key":"1118_CR12","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"DS Hochbaum","year":"1987","unstructured":"Hochbaum DS, Shmoys DB (1987) Using dual approximation algorithms for scheduling problems theoretical and practical results. J ACM 34(1):144\u2013162","journal-title":"J ACM"},{"issue":"4","key":"1118_CR13","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/s00607-003-0011-9","volume":"70","author":"C Imreh","year":"2003","unstructured":"Imreh C (2003) Scheduling problems on two sets of identical machines. Computing 70(4):277\u2013294","journal-title":"Computing"},{"key":"1118_CR14","doi-asserted-by":"crossref","unstructured":"Im S, Shadloo M (2020) Weighted completion time minimization for unrelated machines via iterative fair contention resolution. In: Symposium on discrete algorithms, SODA, pp 2790\u20132809","DOI":"10.1137\/1.9781611975994.170"},{"key":"1118_CR15","doi-asserted-by":"publisher","first-page":"4134","DOI":"10.1007\/s00453-019-00581-w","volume":"81","author":"K Jansen","year":"2019","unstructured":"Jansen K, Maack M (2019) An EPTAS for scheduling on unrelated machines of few different types. Algorithmica 81:4134\u20134164","journal-title":"Algorithmica"},{"issue":"4","key":"1118_CR16","doi-asserted-by":"publisher","first-page":"1371","DOI":"10.1287\/moor.2019.1036","volume":"45","author":"K Jansen","year":"2020","unstructured":"Jansen K, Klein KM, Verschae J (2020) Closing the gap for makespan scheduling via sparsification techniques. Math Oper Res 45(4):1371\u20131392","journal-title":"Math Oper Res"},{"issue":"4","key":"1118_CR17","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1137\/0215081","volume":"15","author":"T Kawaguchi","year":"1986","unstructured":"Kawaguchi T, Kyan S (1986) Worst case bound of an LRF schedule for the mean weighted flow-time problem. SIAM J Comput 15(4):1119\u20131129","journal-title":"SIAM J Comput"},{"issue":"7","key":"1118_CR18","doi-asserted-by":"publisher","first-page":"3025","DOI":"10.1007\/s00453-019-00566-9","volume":"81","author":"I Kones","year":"2019","unstructured":"Kones I, Levin A (2019) A unified framework for designing EPTAS for load balancing on parallel machines. Algorithmica 81(7):3025\u20133046","journal-title":"Algorithmica"},{"issue":"4","key":"1118_CR19","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra Jr","year":"1983","unstructured":"Lenstra HW Jr (1983) Integer programming with a fixed number of variables. Math Oper Res 8(4):538\u2013548","journal-title":"Math Oper Res"},{"key":"1118_CR20","doi-asserted-by":"publisher","first-page":"1550030","DOI":"10.1142\/S021759591550030X","volume":"32","author":"WJ Li","year":"2015","unstructured":"Li WJ (2015) A best possible online algorithm for the parallel-machine scheduling to minimize the maximum weighted completed time. Asia-Pac J Oper Res 32:1550030","journal-title":"Asia-Pac J Oper Res"},{"issue":"4","key":"1118_CR21","doi-asserted-by":"publisher","first-page":"FOCS 17-409","DOI":"10.1137\/17M1156332","volume":"49","author":"S Li","year":"2020","unstructured":"Li S (2020) Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations. SIAM J Comput 49(4):FOCS 17-409","journal-title":"SIAM J Comput"},{"key":"1118_CR22","doi-asserted-by":"crossref","unstructured":"Lu L, Zhang L, Ou J (2021) Single machine scheduling with rejection to minimize the weighted makespan. In: Wu W, Du H (eds) AAIM 2021, vol 13153. LNCS. Springer, Cham, pp 96\u2013110","DOI":"10.1007\/978-3-030-93176-6_9"},{"key":"1118_CR23","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/BF01585872","volume":"82","author":"C Phillips","year":"1998","unstructured":"Phillips C, Stein C, Wein J (1998) Minimizing average completion time in the presence of release dates. Math Program 82:199\u2013223","journal-title":"Math Program"},{"key":"1118_CR24","doi-asserted-by":"crossref","unstructured":"Raravi G, N\u00e9lis V (2012) A PTAS for assigning sporadic tasks on two-type heterogeneous multiprocessors. In: 2012 IEEE 33rd real-time systems symposium (RTSS). IEEE, pp 117\u2013126","DOI":"10.1109\/RTSS.2012.64"},{"issue":"1","key":"1118_CR25","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/321921.321934","volume":"23","author":"SK Sahni","year":"1976","unstructured":"Sahni SK (1976) Algorithms for scheduling independent tasks. J ACM 23(1):116\u2013127","journal-title":"J ACM"},{"issue":"2","key":"1118_CR26","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1145\/375827.375840","volume":"48","author":"M Skutella","year":"2001","unstructured":"Skutella M (2001) Convex quadratic and semidefinite programming relaxations in scheduling. J ACM 48(2):206\u2013242","journal-title":"J ACM"},{"issue":"1","key":"1118_CR27","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 GJ (2000) A PTAS for minimizing the total weighted completion time on identical parallel machines. Math Oper Res 25(1):63\u201375","journal-title":"Math Oper Res"},{"key":"1118_CR28","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"WE Smith","year":"1956","unstructured":"Smith WE (1956) Various optimizers for single-stage production. Nav Res Logist Quart 3:59\u201366","journal-title":"Nav Res Logist Quart"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01118-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01118-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01118-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,24]],"date-time":"2024-04-24T19:05:50Z","timestamp":1713985550000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01118-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,31]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["1118"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01118-w","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,3,31]]},"assertion":[{"value":"22 February 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 March 2024","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 author has no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"34"}}