{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T05:17:02Z","timestamp":1648703822052},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p> We consider the problem of preemptively scheduling n independent jobs {J<jats:sub>1<\/jats:sub>, J<jats:sub>2<\/jats:sub>, \u2026, J<jats:sub>n<\/jats:sub>} on m parallel machines {M<jats:sub>1<\/jats:sub>, M<jats:sub>2<\/jats:sub>, \u2026, M<jats:sub>m<\/jats:sub>}, where each job J<jats:sub>j<\/jats:sub> can only be processed on a prespecified subset [Formula: see text] of machines called its processing set. The machines are linearly ordered, and the processing set of J<jats:sub>j<\/jats:sub> is specified by two machine indexes a<jats:sub>j<\/jats:sub> and b<jats:sub>j<\/jats:sub>; i.e., [Formula: see text]. The processing sets are nested; i.e., for i \u2260 j, we have [Formula: see text], or [Formula: see text], or [Formula: see text]. Our goal is to minimize the makespan. We first give an O(n log n)-time algorithm to find an optimal schedule. We then give an O(mn + n log n)-time algorithm to find a maximal schedule, where a schedule is said to be maximal if it processes as much work as any other schedule in any time interval [0, t], t &gt; 0. <\/jats:p>","DOI":"10.1142\/s012905410900708x","type":"journal-article","created":{"date-parts":[[2009,11,22]],"date-time":"2009-11-22T20:28:50Z","timestamp":1258921730000},"page":"1147-1160","source":"Crossref","is-referenced-by-count":2,"title":["PREEMPTIVE SCHEDULING ALGORITHMS WITH NESTED PROCESSING SET RESTRICTION"],"prefix":"10.1142","volume":"20","author":[{"given":"YUMEI","family":"HUO","sequence":"first","affiliation":[{"name":"Department of Computer Science, CUNY at Staten Island, Staten Island, NY 10314, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JOSEPH Y.-T.","family":"LEUNG","sequence":"additional","affiliation":[{"name":"Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"XIN","family":"WANG","sequence":"additional","affiliation":[{"name":"R&amp;D Department, Bloomberg L.P., 731 Lexington Ave. New York, NY 10022, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"rf1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.20202"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2004.07.010"},{"key":"rf4","first-page":"236","volume":"5","author":"Graham R. L.","journal-title":"Annals of Discrete Math"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(03)00164-3"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1109\/12.166609"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1137\/0206014"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1145\/322092.322101"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijpe.2008.09.003"},{"key":"rf12","unstructured":"C.\u00a0Martel, Parallel and Large-Scale Computers: Performance, Architecture, Applications, eds. M.\u00a0Ruschitzka (North-Holland, Amsterdam, 1983)\u00a0pp. 67\u201375."},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.6.1.1"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1002\/nav.20286"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2004.05.004"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905410900708X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T08:36:16Z","timestamp":1565080576000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905410900708X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":14,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[2009,12]]}},"alternative-id":["10.1142\/S012905410900708X"],"URL":"https:\/\/doi.org\/10.1142\/s012905410900708x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12]]}}}