{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:13:28Z","timestamp":1759637608482},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2018,6]]},"abstract":"<jats:p> Scheduling on Unrelated Machines is a classical optimization problem where [Formula: see text] jobs have to be distributed to [Formula: see text] machines. Each of the jobs [Formula: see text] has on machine [Formula: see text] a processing time [Formula: see text]. The goal is to minimize the makespan, i.e., the maximum completion time of the longest-running machine. Unless [Formula: see text], this problem does not allow for a polynomial-time approximation algorithm with a ratio better than [Formula: see text]. A natural scenario is however that many machines are of the same type, like a CPU and GPU cluster: for each of the [Formula: see text] machine types, the machines [Formula: see text] of the same type [Formula: see text] satisfy [Formula: see text] for all jobs [Formula: see text]. For the case where the number [Formula: see text] of machine types is constant, this paper presents an approximation scheme, i.e., an algorithm of approximation ratio [Formula: see text] for [Formula: see text], with an improved running time only single exponential in [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s0129054118410071","type":"journal-article","created":{"date-parts":[[2018,6,29]],"date-time":"2018-06-29T07:14:49Z","timestamp":1530256489000},"page":"591-621","source":"Crossref","is-referenced-by-count":4,"title":["A PTAS for Scheduling Unrelated Machines of Few Different Types"],"prefix":"10.1142","volume":"29","author":[{"given":"Jan Clemens","family":"Gehrke","sequence":"first","affiliation":[]},{"given":"Klaus","family":"Jansen","sequence":"additional","affiliation":[{"name":"Algorithms and Complexity, Department of Computer Science, University of Kiel, 24098 Kiel, Germany"}]},{"given":"Stefan E. J.","family":"Kraft","sequence":"additional","affiliation":[{"name":"TNG Technology Consulting GmbH, Betastra\u00dfe 13a, 85774 Unterf\u00f6hring, Germany"}]},{"given":"Jakob","family":"Schikowski","sequence":"additional","affiliation":[]}],"member":"219","published-online":{"date-parts":[[2018,6,29]]},"reference":[{"key":"S0129054118410071BIB003","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.3359"},{"key":"S0129054118410071BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2014.06.003"},{"key":"S0129054118410071BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9086-6"},{"key":"S0129054118410071BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.056"},{"key":"S0129054118410071BIB009","volume-title":"Computers and Intractability. A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"S0129054118410071BIB012","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"S0129054118410071BIB013","doi-asserted-by":"publisher","DOI":"10.1137\/0217033"},{"key":"S0129054118410071BIB014","doi-asserted-by":"publisher","DOI":"10.1145\/7531.7535"},{"key":"S0129054118410071BIB015","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321951"},{"key":"S0129054118410071BIB016","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-003-0011-9"},{"key":"S0129054118410071BIB019","doi-asserted-by":"publisher","DOI":"10.1287\/moor.26.2.324.10559"},{"key":"S0129054118410071BIB023","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"S0129054118410071BIB025","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-012-9161-1"},{"key":"S0129054118410071BIB026","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-013-9191-3"},{"key":"S0129054118410071BIB027","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2004.05.004"},{"key":"S0129054118410071BIB028","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585178"},{"key":"S0129054118410071BIB029","doi-asserted-by":"publisher","DOI":"10.1137\/110851201"},{"key":"S0129054118410071BIB030","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-012-9164-y"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118410071","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T19:44:16Z","timestamp":1565120656000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118410071"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6]]},"references-count":18,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2018,6,29]]},"published-print":{"date-parts":[[2018,6]]}},"alternative-id":["10.1142\/S0129054118410071"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118410071","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6]]}}}