{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T05:38:44Z","timestamp":1772775524374,"version":"3.50.1"},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2012,10]]},"abstract":"<jats:p> We consider the offline scheduling problem to minimize the makespan on m parallel and identical machines with certain features. Each job and machine are labeled with the grade of service (GoS) levels, and each job can only be executed on the machine whose GoS level is no more than that of the job. In this paper, we present an efficient polynomial-time approximation scheme (EPTAS) with running time O(n log n) for the special case where the GoS level is either 1 or 2. This partially solves an open problem posed in (Ou et al., 2008). We also present a simpler full polynomial-time approximation scheme (FPTAS) with running time O(n) for the case where the number of machines is fixed. <\/jats:p>","DOI":"10.1142\/s0217595912500297","type":"journal-article","created":{"date-parts":[[2012,10,24]],"date-time":"2012-10-24T08:43:23Z","timestamp":1351068203000},"page":"1250029","source":"Crossref","is-referenced-by-count":13,"title":["TWO APPROXIMATION SCHEMES FOR SCHEDULING ON PARALLEL MACHINES UNDER A GRADE OF SERVICE PROVISION"],"prefix":"10.1142","volume":"29","author":[{"given":"WEIDONG","family":"LI","sequence":"first","affiliation":[{"name":"Department of Atmospheric Science, Yunnan University, Kunming 650091, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JIANPING","family":"LI","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Yunnan University, Kunming 650091, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"TONGQUAN","family":"ZHANG","sequence":"additional","affiliation":[{"name":"School of Mathematics and Computer Science, Yunnan Nationalities University, Kunming 650031, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,10,24]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9086-6"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321951"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(03)00164-3"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1287\/moor.26.2.324.10559"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.04.021"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-007-9095-z"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.05.031"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijpe.2008.09.003"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026272526225"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1002\/nav.20286"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.08.014"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.12.1.57.11901"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.11.008"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.04.007"},{"key":"rf19","first-page":"275","volume":"22","author":"Zhou P.","journal-title":"Applied Mathematics: A Journal of Chinese Universities (Series A)"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595912500297","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T19:23:04Z","timestamp":1565119384000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0217595912500297"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10]]},"references-count":18,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2012,10,24]]},"published-print":{"date-parts":[[2012,10]]}},"alternative-id":["10.1142\/S0217595912500297"],"URL":"https:\/\/doi.org\/10.1142\/s0217595912500297","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"value":"0217-5959","type":"print"},{"value":"1793-7019","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,10]]}}}