  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.
