Time critical task assignment problems are frequently found in operating systems andudflight control applications. Tasks have to be assigned in less than one second, otherwiseudoperating systems don’t work properly or catastrophes could happen. For instance, in a flightudcontrol real time application, one wrong task assignment decision could result in an airplaneudaccident. To make things worse, these crucial decisions have to be taken in milliseconds,udtherefore, the efficiency of these kind of algorithm has to be optimized.udIn order to address time critical task assignment problems, the Clustering Task AssignmentudApproach CTA is proposed. The idea is to cluster the groups into tasks with the bestudcandidates(free agents) according to a heuristic. In other words, the place where agents needsudto reach(task facility) is designed as a cluster centroid and the agents inside each cluster areudthe candidates to execute each task. Agents compete with each other by means of an objectiveudfunction in order to define the assigned task. This heuristic is capable of dramaticallyudreduce the number of calls to the score function, thus assigning groups of agents efficientlyudto groups of tasks.udThe algorithm is compared against the well known Contract Net Protocol(CNET) and outperformudit in terms of speed reducing the number of calls to the score function in 400%, theudsolution quality is 28% better as well. This algorithm was designed to work with time criticaludapplications in which agents have to move from one place to another and when the scoreudfunction is very costly. However results show that it can also be applied to time non criticaludapplications because the solution quality found are outstanding in comparison to otherudapproaches.
展开▼
