File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Energy-efficient due date scheduling

TitleEnergy-efficient due date scheduling
Authors
KeywordsArrival time
Competitive algorithms
Current speed
Different sizes
Energy cost
Issue Date2011
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 1st International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems (TAPAS 2011), Rome, Italy, 18-20 April 2011. In Lecture Notes In Computer Science, 2011, v. 6595, p. 69-80 How to Cite?
AbstractThis paper considers several online scheduling problems that arise from companies with made-to-order products. Jobs, which are product requests, arrive online with different sizes and weights. A company needs to assign a due date for each job once it arrives, and complete the job by this due date. The (weighted) quoted lead time of a job equals its due date minus its arrival time, multiplied by its weight. We focus on companies that mainly rely on computers for production. In those companies, energy cost is a large concern. For most modern processors, its rate of energy usage equals sα, where s is the current speed and α > 1 is a constant. Hence, reducing the processing speed can reduce the rate of energy usage. Algorithms are needed to optimize the (weighted) quoted lead time (for better user experience) and the energy usage (for a smaller energy cost). We propose an algorithm which is 4((log k)α-1 + -α/α-1)-competitive for minimizing the sum of the quoted lead time and energy usage, where k is the ratio between the maximum to minimum job density. Here, the density of a job equals its weight divided by its size. We also consider the setting where we may discard a job by paying a penalty, and the setting of scheduling on a multiprocessor. We propose competitive algorithms for both settings. © 2011 Springer-Verlag.
DescriptionLNCS v. 6595 is conference proceedings of TAPAS 2011
Persistent Identifierhttp://hdl.handle.net/10722/139994
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorLi, Ren_HK
dc.date.accessioned2011-09-23T06:04:29Z-
dc.date.available2011-09-23T06:04:29Z-
dc.date.issued2011en_HK
dc.identifier.citationThe 1st International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems (TAPAS 2011), Rome, Italy, 18-20 April 2011. In Lecture Notes In Computer Science, 2011, v. 6595, p. 69-80en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/139994-
dc.descriptionLNCS v. 6595 is conference proceedings of TAPAS 2011-
dc.description.abstractThis paper considers several online scheduling problems that arise from companies with made-to-order products. Jobs, which are product requests, arrive online with different sizes and weights. A company needs to assign a due date for each job once it arrives, and complete the job by this due date. The (weighted) quoted lead time of a job equals its due date minus its arrival time, multiplied by its weight. We focus on companies that mainly rely on computers for production. In those companies, energy cost is a large concern. For most modern processors, its rate of energy usage equals sα, where s is the current speed and α > 1 is a constant. Hence, reducing the processing speed can reduce the rate of energy usage. Algorithms are needed to optimize the (weighted) quoted lead time (for better user experience) and the energy usage (for a smaller energy cost). We propose an algorithm which is 4((log k)α-1 + -α/α-1)-competitive for minimizing the sum of the quoted lead time and energy usage, where k is the ratio between the maximum to minimum job density. Here, the density of a job equals its weight divided by its size. We also consider the setting where we may discard a job by paying a penalty, and the setting of scheduling on a multiprocessor. We propose competitive algorithms for both settings. © 2011 Springer-Verlag.en_HK
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Scienceen_HK
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectArrival time-
dc.subjectCompetitive algorithms-
dc.subjectCurrent speed-
dc.subjectDifferent sizes-
dc.subjectEnergy cost-
dc.titleEnergy-efficient due date schedulingen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChan, HL:hlchan@cs.hku.hken_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.authorityChan, HL=rp01310en_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-642-19754-3_9en_HK
dc.identifier.scopuseid_2-s2.0-79953829838en_HK
dc.identifier.hkuros194062en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-79953829838&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume6595 LNCSen_HK
dc.identifier.spage69en_HK
dc.identifier.epage80en_HK
dc.publisher.placeGermanyen_HK
dc.description.otherThe 1st International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems (TAPAS 2011), Rome, Italy, 18-20 April 2011. In Lecture Notes In Computer Science, 2011, v. 6595, p. 69-80-
dc.identifier.scopusauthoridChan, HL=7403402384en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridLi, R=36918615800en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats