{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:23:35Z","timestamp":1757312615018},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2009,9]]},"abstract":"<jats:p> The max-min allocation problem under a grade of service provision is defined in the following model: given a set [Formula: see text] of m parallel machines and a set [Formula: see text] of n jobs, where machines and jobs are all entitled to different levels of grade of service (GoS), each job [Formula: see text] has its processing time p<jats:sub>j<\/jats:sub> and it can only be allocated to a machine M<jats:sub>i<\/jats:sub> whose GoS level is no more than the GoS level the job J<jats:sub>j<\/jats:sub> has. The goal is to allocate all jobs to m machines to maximize the minimum machine load among these m machines, where the machine load of M<jats:sub>i<\/jats:sub> is the sum of the processing time of jobs executed on M<jats:sub>i<\/jats:sub>. The best known approximation algorithm [4] to solve this problem produces an allocation in which the minimum machine completion time is at least \u03a9 ( log log log m\/ log log m) of the optimal value. <\/jats:p><jats:p> In this paper, we respectively present four approximation schemes to solve this problem and its two special versions: (1) a polynomial time approximation scheme (PTAS) with a running time [Formula: see text] for the general version, where \u03f5 &gt; 0; (2) a PTAS and a fully polynomial time approximation scheme (FPTAS) with the running time O(n) for the version where the number m of machines is fixed; (3) a PTAS with the running time O(n) for the version where the number of GoS levels is bounded by k. <\/jats:p>","DOI":"10.1142\/s1793830909000282","type":"journal-article","created":{"date-parts":[[2009,9,30]],"date-time":"2009-09-30T07:00:24Z","timestamp":1254294024000},"page":"355-368","source":"Crossref","is-referenced-by-count":11,"title":["POLYNOMIAL APPROXIMATION SCHEMES FOR THE MAX-MIN ALLOCATION PROBLEM UNDER A GRADE OF SERVICE PROVISION"],"prefix":"10.1142","volume":"01","author":[{"given":"JIANPING","family":"LI","sequence":"first","affiliation":[{"name":"Department of Mathematics, Yunnan University, Kunming 650091, P. R. China"}]},{"given":"WEIDONG","family":"LI","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Yunnan University, Kunming 650091, P. R. China"}]},{"given":"JIANBO","family":"LI","sequence":"additional","affiliation":[{"name":"School of Management and Economics, Kunming University of Science and Technology, Kunming 650031, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"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":"rf6","doi-asserted-by":"publisher","DOI":"10.1145\/1120680.1120683"},{"key":"rf8","first-page":"43","volume":"39","author":"Epstein L.","journal-title":"Algorithmica"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(03)00164-3"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijpe.2008.09.003"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1002\/nav.20286"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1425(199909\/10)2:5<203::AID-JOS26>3.0.CO;2-5"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.12.1.57.11901"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830909000282","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T01:29:09Z","timestamp":1565141349000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830909000282"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9]]},"references-count":11,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2009,9]]}},"alternative-id":["10.1142\/S1793830909000282"],"URL":"https:\/\/doi.org\/10.1142\/s1793830909000282","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9]]}}}