Scheduling multi-task jobs with extra utility in data centers
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...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SpringerOpen
2017-11-01
|
| Series: | EURASIP Journal on Wireless Communications and Networking |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1186/s13638-017-0986-0 |
| _version_ | 1811264490318069760 |
|---|---|
| author | Xiaolin Fang Junzhou Luo Hong Gao Weiwei Wu Yingshu Li |
| author_facet | Xiaolin Fang Junzhou Luo Hong Gao Weiwei Wu Yingshu Li |
| author_sort | Xiaolin Fang |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-12T20:04:12Z |
| format | Article |
| id | doaj.art-1508eb3fbbfb4b0ba8cec4fc95816831 |
| institution | Directory Open Access Journal |
| issn | 1687-1499 |
| language | English |
| last_indexed | 2024-04-12T20:04:12Z |
| publishDate | 2017-11-01 |
| publisher | SpringerOpen |
| record_format | Article |
| series | EURASIP Journal on Wireless Communications and Networking |
| spelling | doaj.art-1508eb3fbbfb4b0ba8cec4fc958168312022-12-22T03:18:25ZengSpringerOpenEURASIP Journal on Wireless Communications and Networking1687-14992017-11-012017111210.1186/s13638-017-0986-0Scheduling multi-task jobs with extra utility in data centersXiaolin Fang0Junzhou Luo1Hong Gao2Weiwei Wu3Yingshu Li4School of Computer Science and Engineering, Southeast UniversitySchool of Computer Science and Engineering, Southeast UniversitySchool of Computer Science and Technology, Harbin Institute of TechnologySchool of Computer Science and Engineering, Southeast UniversityDepartment of Computer Science, Georgia State UniversityAbstract 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.http://link.springer.com/article/10.1186/s13638-017-0986-0Multi-task jobsExtra utilityScheduling |
| spellingShingle | Xiaolin Fang Junzhou Luo Hong Gao Weiwei Wu Yingshu Li Scheduling multi-task jobs with extra utility in data centers EURASIP Journal on Wireless Communications and Networking Multi-task jobs Extra utility Scheduling |
| title | Scheduling multi-task jobs with extra utility in data centers |
| title_full | Scheduling multi-task jobs with extra utility in data centers |
| title_fullStr | Scheduling multi-task jobs with extra utility in data centers |
| title_full_unstemmed | Scheduling multi-task jobs with extra utility in data centers |
| title_short | Scheduling multi-task jobs with extra utility in data centers |
| title_sort | scheduling multi task jobs with extra utility in data centers |
| topic | Multi-task jobs Extra utility Scheduling |
| url | http://link.springer.com/article/10.1186/s13638-017-0986-0 |
| work_keys_str_mv | AT xiaolinfang schedulingmultitaskjobswithextrautilityindatacenters AT junzhouluo schedulingmultitaskjobswithextrautilityindatacenters AT honggao schedulingmultitaskjobswithextrautilityindatacenters AT weiweiwu schedulingmultitaskjobswithextrautilityindatacenters AT yingshuli schedulingmultitaskjobswithextrautilityindatacenters |