|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'500'096
Articles rated: 2609
18 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Energy-Efficient Scheduling with Time and Processors Eligibility Restrictions | | Xibo Jin
; Fa Zhang
; Ying Song
; Liya Fan
; Zhiyong Liu
; | | Date: |
17 Jan 2013 | | Abstract: | While previous work on energy-efficient algorithms focused on assumption that
tasks can be assigned to any processor, we initially study the problem of task
scheduling on restricted parallel processors. The objective is to minimize the
overall energy consumption while speed scaling (SS) method is used to reduce
energy consumption under the execution time constraint (Makespan $C_{max}$). In
this work, we discuss the speed setting in the continuous model that processors
can run at arbitrary speed in $[s_{min},s_{max}]$. The energy-efficient
scheduling problem, involving task assignment and speed scaling, is inherently
complicated as it is proved to be NP-Complete. We formulate the problem as an
Integer Programming (IP) problem. Specifically, we devise a polynomial time
optimal scheduling algorithm for the case tasks have a uniform size. Our
algorithm runs in $O(mn^3logn)$ time, where $m$ is the number of processors and
$n$ is the number of tasks. We then present a polynomial time algorithm that
achieves an approximation factor of $2^{alpha-1}(2-frac{1}{m^{alpha}})$
($alpha$ is the power parameter) when the tasks have arbitrary size work.
Experimental results demonstrate that our algorithm could provide an efficient
scheduling for the problem of task scheduling on restricted parallel
processors. | | Source: | arXiv, 1301.4131 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER