Adaptive online scheduling of tasks with anytime property on heterogeneous resources

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F16%3A00243315" target="_blank" >RIV/68407700:21230/16:00243315 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.sciencedirect.com/science/article/pii/S030505481630140X" target="_blank" >http://www.sciencedirect.com/science/article/pii/S030505481630140X</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.cor.2016.06.008" target="_blank" >10.1016/j.cor.2016.06.008</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Adaptive online scheduling of tasks with anytime property on heterogeneous resources

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Adaptive online scheduling of tasks with anytime property on heterogeneous resources

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

JC - Počítačový hardware a software

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Computers & Operations Research

ISSN

0305-0548

e-ISSN

—

Svazek periodika

76

Číslo periodika v rámci svazku

December

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

23

Strana od-do

95-117

Kód UT WoS článku

000383008100009

EID výsledku v databázi Scopus

2-s2.0-84977674493