Bibliographic Details
| Title: |
Scheduling multi-task jobs with extra utility in data centers |
| Authors: |
Xiaolin Fang, Junzhou Luo, Hong Gao, Weiwei Wu, Yingshu Li |
| Source: |
EURASIP Journal on Wireless Communications and Networking, Vol 2017, Iss 1, Pp 1-12 (2017) |
| Publisher Information: |
SpringerOpen, 2017. |
| Publication Year: |
2017 |
| Collection: |
LCC:Telecommunication
LCC:Electronics |
| Subject Terms: |
Multi-task jobs, Extra utility, Scheduling, Telecommunication, TK5101-6720, Electronics, TK7800-8360 |
| More Details: |
Abstract This paper investigates the problem of maximizing utility for job scheduling where each job consists of multiple tasks, each task has utility and each job also has extra utility if all tasks of that job are completed. We provide a 2-approximation algorithm for the single-machine case and a 2-approximation algorithm for the multi-machine problem. Both algorithms include two steps. The first step employs the Earliest Deadline First method to compute utility with only extra job utility, and it is proved that it obtains the optimal result for this sub-problem. The second step employs a Dynamic Programming method to compute utility without extra job utility, and it also derives the optimal result. An approximation result can then be obtained by combining the results of the two steps. |
| Document Type: |
article |
| File Description: |
electronic resource |
| Language: |
English |
| ISSN: |
1687-1499 |
| Relation: |
http://link.springer.com/article/10.1186/s13638-017-0986-0; https://doaj.org/toc/1687-1499 |
| DOI: |
10.1186/s13638-017-0986-0 |
| Access URL: |
https://doaj.org/article/1508eb3fbbfb4b0ba8cec4fc95816831 |
| Accession Number: |
edsdoj.1508eb3fbbfb4b0ba8cec4fc95816831 |
| Database: |
Directory of Open Access Journals |
