File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Online scheduling with partial job values: Does timesharing or randomization help?

TitleOnline scheduling with partial job values: Does timesharing or randomization help?
Authors
KeywordsLower bounds
Online algorithms
Partial job values
Scheduling
Timesharing
Issue Date2003
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
Citation
Algorithmica (New York), 2003, v. 37 n. 3, p. 149-164 How to Cite?
AbstractWe study the following online preemptive scheduling problem: given a set of jobs with release times, deadlines, processing times and weights, schedule them so as to maximize the total value obtained. Unlike traditional scheduling problems, partially completed jobs can get partial values proportional to their amounts processed. Recently Chrobak et al. gave improved lower and upper bounds [1.236, 1.8] on the competitive ratio for this problem, the upper bound being achieved by using timesharing to simulate two equal-speed processors. In this paper we (1) give a new algorithm MIXED-κ with competitive ratio 1/(1 - (κ/(κ + 1))κ) which approaches e/(e-1) ≈ 1.582 when κ → ∞, by using timesharing to simulate κ equal-speed processors; (2) give an equivalent but much more practical algorithm MIX, which is e/(e - 1)-competitive (independent of κ), by timesharing the processor with different speeds (depending on the job weights), and use its interesting properties to devise an efficient implementation; (3) improve the lower bound to 1.25 by showing an identical lower bound for randomized algorithms; and (4) prove a lower bound of 1.618 on the competitive ratio when timesharing is not allowed, thus answering an open problem raised by Chang and Yap, showing that timesharing provably helps in giving better algorithms for this problem.
Persistent Identifierhttp://hdl.handle.net/10722/48425
ISSN
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.905
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorFung, SPYen_HK
dc.date.accessioned2008-05-22T04:12:40Z-
dc.date.available2008-05-22T04:12:40Z-
dc.date.issued2003en_HK
dc.identifier.citationAlgorithmica (New York), 2003, v. 37 n. 3, p. 149-164en_HK
dc.identifier.issn0178-4617en_HK
dc.identifier.urihttp://hdl.handle.net/10722/48425-
dc.description.abstractWe study the following online preemptive scheduling problem: given a set of jobs with release times, deadlines, processing times and weights, schedule them so as to maximize the total value obtained. Unlike traditional scheduling problems, partially completed jobs can get partial values proportional to their amounts processed. Recently Chrobak et al. gave improved lower and upper bounds [1.236, 1.8] on the competitive ratio for this problem, the upper bound being achieved by using timesharing to simulate two equal-speed processors. In this paper we (1) give a new algorithm MIXED-κ with competitive ratio 1/(1 - (κ/(κ + 1))κ) which approaches e/(e-1) ≈ 1.582 when κ → ∞, by using timesharing to simulate κ equal-speed processors; (2) give an equivalent but much more practical algorithm MIX, which is e/(e - 1)-competitive (independent of κ), by timesharing the processor with different speeds (depending on the job weights), and use its interesting properties to devise an efficient implementation; (3) improve the lower bound to 1.25 by showing an identical lower bound for randomized algorithms; and (4) prove a lower bound of 1.618 on the competitive ratio when timesharing is not allowed, thus answering an open problem raised by Chang and Yap, showing that timesharing provably helps in giving better algorithms for this problem.en_HK
dc.format.extent281547 bytes-
dc.format.extent461335 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeimage/jpeg-
dc.languageengen_HK
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htmen_HK
dc.relation.ispartofAlgorithmica (New York)en_HK
dc.rightsThe original publication is available at www.springerlink.comen_HK
dc.subjectLower boundsen_HK
dc.subjectOnline algorithmsen_HK
dc.subjectPartial job valuesen_HK
dc.subjectSchedulingen_HK
dc.subjectTimesharingen_HK
dc.titleOnline scheduling with partial job values: Does timesharing or randomization help?en_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0178-4617&volume=37&issue=3&spage=149&epage=164 &date=2003&atitle=Online+Scheduling+with+Partial+Job+Values:+Does+Timesharing+or+Randomization+Help?en_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturepostprinten_HK
dc.identifier.doi10.1007/s00453-003-1025-6en_HK
dc.identifier.scopuseid_2-s2.0-0242406107en_HK
dc.identifier.hkuros85447-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0242406107&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume37en_HK
dc.identifier.issue3en_HK
dc.identifier.spage149en_HK
dc.identifier.epage164en_HK
dc.identifier.isiWOS:000185227800001-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridFung, SPY=7201970079en_HK
dc.identifier.issnl0178-4617-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats