Clustering task assignment: an algorithm for time critical task assignment problems

Abstract

Time critical task assignment problems are frequently found in operating systems and
flight control applications. Tasks have to be assigned in less than one second, otherwise
operating systems don’t work properly or catastrophes could happen. For instance, in a flight
control real time application, one wrong task assignment decision could result in an airplane
accident. To make things worse, these crucial decisions have to be taken in milliseconds,
therefore, the efficiency of these kind of algorithm has to be optimized.
In order to address time critical task assignment problems, the Clustering Task Assignment
Approach CTA is proposed. The idea is to cluster the groups into tasks with the best
candidates(free agents) according to a heuristic. In other words, the place where agents needs
to reach(task facility) is designed as a cluster centroid and the agents inside each cluster are
the candidates to execute each task. Agents compete with each other by means of an objective
function in order to define the assigned task. This heuristic is capable of dramatically
reduce the number of calls to the score function, thus assigning groups of agents efficiently
to groups of tasks.
The algorithm is compared against the well known Contract Net Protocol(CNET) and outperform
it in terms of speed reducing the number of calls to the score function in 400%, the
solution quality is 28% better as well. This algorithm was designed to work with time critical
applications in which agents have to move from one place to another and when the score
function is very costly. However results show that it can also be applied to time non critical
applications because the solution quality found are outstanding in comparison to other
approaches.