{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,28]],"date-time":"2022-03-28T23:12:18Z","timestamp":1648509138271},"reference-count":7,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,6]]},"abstract":"<jats:p> We consider the following online scheduling problem. We are given a set of jobs, each having an integral release time and deadline, unit processing length, and a nonnegative real weight. In each time unit one job is to be scheduled, and the objective is to maximize the total value (weight) obtained by scheduling the jobs. This problem arises in the scheduling of packets in network switches supporting quality-of-service (QoS). Previous algorithms for this problem are 2-competitive. <\/jats:p><jats:p> In this paper we propose a new algorithm that achieves an improved competitive ratio when the importance ratio is bounded. Specifically, for job weights within the range [1..B], our algorithm is 2 - 1\/(\u2308 lg B\u2309 + 2)-competitive, and the bound is tight. <\/jats:p>","DOI":"10.1142\/s0129054105003170","type":"journal-article","created":{"date-parts":[[2005,7,5]],"date-time":"2005-07-05T10:52:13Z","timestamp":1120560733000},"page":"581-598","source":"Crossref","is-referenced-by-count":1,"title":["ONLINE SCHEDULING OF UNIT JOBS WITH BOUNDED IMPORTANCE RATIO"],"prefix":"10.1142","volume":"16","author":[{"given":"STANLEY P. Y.","family":"FUNG","sequence":"first","affiliation":[{"name":"Department of Computer Science, The University of Hong Kong, Pokfulam Road, Hong Kong, China"}]},{"given":"FRANCIS Y. L.","family":"CHIN","sequence":"additional","affiliation":[{"name":"Department of Computer Science, The University of Hong Kong, Pokfulam Road, Hong Kong, China"}]},{"given":"HONG","family":"SHEN","sequence":"additional","affiliation":[{"name":"Graduate School of Information Science, Japan Advanced Institute of Science and Technology, 1-1 Asahidai, Tatsunokuchi, Ishikawa, 923-1292, Japan"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/BF00365406"},{"key":"rf4","volume-title":"Online Computation and Competitive Analysis","author":"Borodin A.","year":"1998"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1025-6"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00070-9"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236882"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0029570"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054105003170","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:39:53Z","timestamp":1565123993000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105003170"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,6]]},"references-count":7,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,6]]}},"alternative-id":["10.1142\/S0129054105003170"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105003170","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,6]]}}}