{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,3]],"date-time":"2023-11-03T08:58:12Z","timestamp":1699001892733},"reference-count":13,"publisher":"World Scientific Pub Co Pte Ltd","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2015,8]]},"abstract":"<jats:p>This paper studies the online hierarchical scheduling problem on two uniform machines with rejection. Two uniform machines M<jats:sub>1<\/jats:sub>, M<jats:sub>2<\/jats:sub>run at the speeds of s \u2208 (0, +\u221e), 1 separately; and they are provided with different capabilities. Each machine has a certain GOS level 1 or 2 and every job is also associated with a hierarchy 1 or 2. The job can only be assigned to the machine whose GOS level does not exceed the job's hierarchy. Preemption is permitted but idle is not introduced. Jobs come one by one over list. When a job arrives, it can be accepted and scheduled on some machine or rejected by paying its penalty. The objective is to minimize the sum of makespan yielded by accepted jobs and total penalties of all rejected jobs. For this problem, we propose a family of several online algorithms according to the range of s and the related lower bound is also obtained. These algorithms achieve optimal competitive ratio when s \u2208 (0, 1) \u222a [1.618, +\u221e), but have a small gap between upper bound and lower bound in interval [1, 1.618).<\/jats:p>","DOI":"10.1142\/s021759591550027x","type":"journal-article","created":{"date-parts":[[2015,2,24]],"date-time":"2015-02-24T08:23:21Z","timestamp":1424766201000},"page":"1550027","source":"Crossref","is-referenced-by-count":1,"title":["Online Preemptive Hierarchical Scheduling on Two Uniform Machines with Rejection"],"prefix":"10.1142","volume":"32","author":[{"given":"Xiao","family":"Min","sequence":"first","affiliation":[{"name":"College of Mathematics, Physics and Information Engineering, Jiaxing University, Jiaxing 314001, P. R. China"}]},{"given":"Jing","family":"Liu","sequence":"additional","affiliation":[{"name":"College of Mathematics, Physics and Information Engineering, Jiaxing University, Jiaxing 314001, P. R. China"}]},{"given":"Yanxia","family":"Dong","sequence":"additional","affiliation":[{"name":"College of Mathematics, Shanghai University, Shanghai 200444, P. R. China"}]},{"given":"Ming","family":"Jiang","sequence":"additional","affiliation":[{"name":"College of Computer Science, Hangzhou Dianzi University, Hangzhou 310018, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2015,7,23]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798346135"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480196300522"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00341-X"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-007-9078-0"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-005-0130-6"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2007.11.004"},{"key":"rf7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/PL00021409","volume":"65","author":"He Y.","year":"2000","journal-title":"Computing"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-007-9095-z"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1631\/jzus.2006.A0309"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2005.11.004"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00288-7"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-008-9195-4"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.04.007"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S021759591550027X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,30]],"date-time":"2022-04-30T15:33:00Z","timestamp":1651332780000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S021759591550027X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,23]]},"references-count":13,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2015,7,23]]},"published-print":{"date-parts":[[2015,8]]}},"alternative-id":["10.1142\/S021759591550027X"],"URL":"https:\/\/doi.org\/10.1142\/s021759591550027x","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"value":"0217-5959","type":"print"},{"value":"1793-7019","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7,23]]}}}