Optimization of Task Assignment to Collaborating Agents
Irfan Younas, Farzad Kamrani, Christian Schulte, Rassul Ayani.
The classic task assignment problem (AP) assigns m agents to n tasks, where each task is assigned to exactly one agent. This problem and many of its variations, including the case where a task is assigned to a group of agents working independently, have been discussed extensively in the literature. We consider a specific class of task assignment problems where each task is assigned to a group of collaborating agents that work as a team. Thus, changing one of the group members may have a vital impact on the output of the group. We assume that each agent has a set of capabilities and each task has certain requirements. The objective is to assign agents to teams such that the gain is maximized.
We suggest a Genetic Algorithm (GA) for finding a near optimal solution to this class of task assignment problems. To the best of our knowledge, this class of APs has not been considered in the literature, probably due to the difficulty of evaluating the performance of a team of agents. Recently, we have developed a formal method for measuring performance of a team which is used in this paper to formulate the objective function of our GA. We analyze the quality of the obtained solution by comparing the result of our GA with (a) the exact solution of some smaller problems, and (b) with the results of the exact solution of specific cases that can be obtained by the Hungarian algorithm. We provide experimental results on efficiency, stability, robustness and scalability of the solution obtained by our GA.
In: IEEE Symposium on Computational Intelligence in Scheduling, Paris, France, pages 17-24. April, 2011. DOI 10.1109/SCIS.2011.5976547.
Copyright © IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.