Adaptive online scheduling of tasks with anytime property on heterogeneous resources. (December 2016)
- Record Type:
- Journal Article
- Title:
- Adaptive online scheduling of tasks with anytime property on heterogeneous resources. (December 2016)
- Main Title:
- Adaptive online scheduling of tasks with anytime property on heterogeneous resources
- Authors:
- Módos, István
Šůcha, Přemysl
Václavík, Roman
Smejkal, Jan
Hanzálek, Zdeněk - Abstract:
- Abstract: An acceptable response time of a server is an important aspect in many client–server applications; this is evident in situations in which the server is overloaded by many computationally intensive requests. In this work, we consider that the requests, or in this case tasks, generated by the clients are instances of optimization problems solved by anytime algorithms, i.e. the quality of the solution increases with the processing time of a task. These tasks are submitted to the server which schedules them to the available computational resources where the tasks are processed. To tackle the overload problem, we propose a scheduling algorithm which combines traditional scheduling approaches with a quality control heuristic which adjusts the requested quality of the solutions and thus changes the processing time of the tasks. Two efficient quality control heuristics are introduced: the first heuristic sets a global quality for all tasks, whereas the second heuristic sets the quality for each task independently. Moreover, in practice, the relationship between the processing time and the quality is not known a priori . Because it is crucial for scheduling algorithms to know at least the estimation of these relationships, we propose a general procedure for estimating these relationships using information obtained from the already executed tasks. Finally, the performance of the proposed scheduling algorithm is demonstrated on a real-world problem from the domain ofAbstract: An acceptable response time of a server is an important aspect in many client–server applications; this is evident in situations in which the server is overloaded by many computationally intensive requests. In this work, we consider that the requests, or in this case tasks, generated by the clients are instances of optimization problems solved by anytime algorithms, i.e. the quality of the solution increases with the processing time of a task. These tasks are submitted to the server which schedules them to the available computational resources where the tasks are processed. To tackle the overload problem, we propose a scheduling algorithm which combines traditional scheduling approaches with a quality control heuristic which adjusts the requested quality of the solutions and thus changes the processing time of the tasks. Two efficient quality control heuristics are introduced: the first heuristic sets a global quality for all tasks, whereas the second heuristic sets the quality for each task independently. Moreover, in practice, the relationship between the processing time and the quality is not known a priori . Because it is crucial for scheduling algorithms to know at least the estimation of these relationships, we propose a general procedure for estimating these relationships using information obtained from the already executed tasks. Finally, the performance of the proposed scheduling algorithm is demonstrated on a real-world problem from the domain of personnel rostering with very good results. Abstract : Highlights: We study a problem of keeping acceptable response time in client–server applications. The requests are tasks solved by anytime algorithms on heterogeneous resources. Two heuristics for controlling the requested quality of the solutions are proposed. Machine learning is used for approximating the processing time of the tasks. The proposed scheduling system gives very good results on a real world problem. … (more)
- Is Part Of:
- Computers & operations research. Volume 76(2016)
- Journal:
- Computers & operations research
- Issue:
- Volume 76(2016)
- Issue Display:
- Volume 76, Issue 2016 (2016)
- Year:
- 2016
- Volume:
- 76
- Issue:
- 2016
- Issue Sort Value:
- 2016-0076-2016-0000
- Page Start:
- 95
- Page End:
- 117
- Publication Date:
- 2016-12
- Subjects:
- Online scheduling -- Anytime algorithms -- Machine learning -- Adaptive systems
Operations research -- Periodicals
Electronic digital computers -- Periodicals
004.05 - Journal URLs:
- http://www.sciencedirect.com/science/journal/03050548 ↗
http://www.elsevier.com/journals ↗ - DOI:
- 10.1016/j.cor.2016.06.008 ↗
- Languages:
- English
- ISSNs:
- 0305-0548
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 3394.770000
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 323.xml