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

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