File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/978-3-642-19754-3_9
- Scopus: eid_2-s2.0-79953829838
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Energy-efficient due date scheduling
Title | Energy-efficient due date scheduling |
---|---|
Authors | |
Keywords | Arrival time Competitive algorithms Current speed Different sizes Energy cost |
Issue Date | 2011 |
Publisher | Springer 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? |
Abstract | This 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. |
Description | LNCS v. 6595 is conference proceedings of TAPAS 2011 |
Persistent Identifier | http://hdl.handle.net/10722/139994 |
ISSN | 2023 SCImago Journal Rankings: 0.606 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, HL | en_HK |
dc.contributor.author | Lam, TW | en_HK |
dc.contributor.author | Li, R | en_HK |
dc.date.accessioned | 2011-09-23T06:04:29Z | - |
dc.date.available | 2011-09-23T06:04:29Z | - |
dc.date.issued | 2011 | en_HK |
dc.identifier.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 | en_HK |
dc.identifier.issn | 0302-9743 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/139994 | - |
dc.description | LNCS v. 6595 is conference proceedings of TAPAS 2011 | - |
dc.description.abstract | This 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.language | eng | en_US |
dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ | en_HK |
dc.relation.ispartof | Lecture Notes in Computer Science | en_HK |
dc.rights | The original publication is available at www.springerlink.com | - |
dc.subject | Arrival time | - |
dc.subject | Competitive algorithms | - |
dc.subject | Current speed | - |
dc.subject | Different sizes | - |
dc.subject | Energy cost | - |
dc.title | Energy-efficient due date scheduling | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Chan, HL:hlchan@cs.hku.hk | en_HK |
dc.identifier.email | Lam, TW:twlam@cs.hku.hk | en_HK |
dc.identifier.authority | Chan, HL=rp01310 | en_HK |
dc.identifier.authority | Lam, TW=rp00135 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1007/978-3-642-19754-3_9 | en_HK |
dc.identifier.scopus | eid_2-s2.0-79953829838 | en_HK |
dc.identifier.hkuros | 194062 | en_US |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-79953829838&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 6595 LNCS | en_HK |
dc.identifier.spage | 69 | en_HK |
dc.identifier.epage | 80 | en_HK |
dc.publisher.place | Germany | en_HK |
dc.description.other | 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 | - |
dc.identifier.scopusauthorid | Chan, HL=7403402384 | en_HK |
dc.identifier.scopusauthorid | Lam, TW=7202523165 | en_HK |
dc.identifier.scopusauthorid | Li, R=36918615800 | en_HK |
dc.identifier.issnl | 0302-9743 | - |