https://scholars.lib.ntu.edu.tw/handle/123456789/490063
標題: | Power-Saving Scheduling for Weakly Dynamic Voltage Scaling Devices. | 作者: | Chen, Jian-Jia Kuo, Tei-Wei Lu, Hsueh-I TEI-WEI KUO |
公開日期: | 2005 | 起(迄)頁: | 338-349 | 來源出版物: | Algorithms and Data Structures, 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005, Proceedings | 摘要: | We study the problem of non-preemptive scheduling to minimize energy consumption for devices that allow dynamic voltage scaling. Specifically, consider a device that can process jobs in a non-preemptive manner. The input consists of (i) the set R of available speeds of the device, (ii) a set J of jobs, and (iii) a precedence constraint ∏ among J. Each job j in J, defined by its arrival time aj, deadline dj, and amount of computation cj, is supposed to be processed by the device at a speed in R. Under the assumption that a higher speed means higher energy consumption, the power-saving scheduling problem is to compute a feasible schedule with speed assignment for the jobs in J such that the required energy consumption is minimized. This paper focuses on the setting of weakly dynamic voltage scaling, i.e., speed change is not allowed in the middle of processing a job. To demonstrate that this restriction on many portable power-aware devices introduces hardness to the power-saving scheduling problem, we prove that the problem is NP-hard even if aj = aj′ and d j = dj′ hold for all j, j′ ε J and |R| = 2. If |R| < ∞, we also give fully polynomial-time approximation schemes for two cases of the general NP-hard problem: (a) all jobs share a common arrival time, and (b) ∏ = θ and for any j, j′ ε J, a j ≤ aj′ implies dj ≤ d j′. To the best of our knowledge, there is no previously known approximation algorithm for any special case of the NP-hard problem. © Springer-Verlag Berlin Heidelberg 2005. |
URI: | https://scholars.lib.ntu.edu.tw/handle/123456789/490063 | DOI: | 10.1007/11534273_30 | SDG/關鍵字: | Energy utilization; Polynomials; Problem solving; Scheduling; Set theory; Non-preemptive manners; Speed assignment; Voltage scaling; Electric potential |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。