File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A tight lower bound for job scheduling with cancellation

TitleA tight lower bound for job scheduling with cancellation
Authors
Zheng, FChin, FYLFung, SPYPoon, CKXu, Y
KeywordsLower bounds
On-line algorithms
Scheduling
Issue Date2006
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/ipl
Citation
Information Processing Letters, 2006, v. 97 n. 1, p. 1-3 How to Cite?
DOI: http://dx.doi.org/10.1016/j.ipl.2005.09.001
AbstractThe Job Scheduling with Cancellation problem is a variation of classical scheduling problems in which jobs can be cancelled while waiting for execution. In this paper we prove a tight lower bound of 5 for the competitive ratio of any deterministic online algorithm for this problem, for the case where all jobs have the same processing time. © 2005 Elsevier B.V. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/89103
ISSN
0020-0190
2023 Impact Factor: 0.7
2023 SCImago Journal Rankings: 0.404
ISI Accession Number ID
WOS:000233778000001
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorZheng, Fen_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorFung, SPYen_HK
dc.contributor.authorPoon, CKen_HK
dc.contributor.authorXu, Yen_HK
dc.date.accessioned2010-09-06T09:52:25Z-
dc.date.available2010-09-06T09:52:25Z-
dc.date.issued2006en_HK
dc.identifier.citationInformation Processing Letters, 2006, v. 97 n. 1, p. 1-3en_HK
dc.identifier.issn0020-0190en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89103-
dc.description.abstractThe Job Scheduling with Cancellation problem is a variation of classical scheduling problems in which jobs can be cancelled while waiting for execution. In this paper we prove a tight lower bound of 5 for the competitive ratio of any deterministic online algorithm for this problem, for the case where all jobs have the same processing time. © 2005 Elsevier B.V. All rights reserved.en_HK
dc.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/iplen_HK
dc.relation.ispartofInformation Processing Lettersen_HK
dc.rightsInformation Processing Letters. Copyright © Elsevier BV.en_HK
dc.subjectLower boundsen_HK
dc.subjectOn-line algorithmsen_HK
dc.subjectSchedulingen_HK
dc.titleA tight lower bound for job scheduling with cancellationen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0020-0190&volume=97&issue=1&spage=1&epage=3&date=2006&atitle=A+Tight+Lower+Bound+for+Job+Scheduling+with+Cancellationen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/j.ipl.2005.09.001en_HK
dc.identifier.scopuseid_2-s2.0-27844494751en_HK
dc.identifier.hkuros117579en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-27844494751&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume97en_HK
dc.identifier.issue1en_HK
dc.identifier.spage1en_HK
dc.identifier.epage3en_HK
dc.identifier.isiWOS:000233778000001-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridZheng, F=9276481100en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridFung, SPY=7201970079en_HK
dc.identifier.scopusauthoridPoon, CK=7202673523en_HK
dc.identifier.scopusauthoridXu, Y=7406449677en_HK
dc.identifier.issnl0020-0190-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats