TitleDecentralised Parallel Machine Scheduling for Multi-Agent Task Allocation
Publication TypeConference Paper
Year of Publication2011
AuthorsMacarthur K, Vinyals M, Farinelli A, Ramchurn SD, Jennings NR
Conference NameProceedings of the 4th International Workshop on Optimization in Multi-Agent Systems Agents@AAMAS (OPTMAS 2011)
Conference LocationTaipei, Taiiwan
Date PublishedMay, 2011

Multi-agent task allocation problems pervade a wide range of real-world applications, such as search and rescue in disaster manage- ment, or grid computing. In these applications, where agents are given tasks to perform in parallel, it is often the case that the performance of all agents is judged based on the time taken by the slowest agent to complete its tasks. Hence, effcient distribution of tasks across het- erogeneous agents is important to ensure a short completion time. An equivalent problem to this can be found in operations research, and is known as scheduling jobs on unrelated parallel machines (also known as RjjCmax). In this paper, we draw parallels between unrelated parallel machine scheduling and multi-agent task allocation problems, and, in so doing, we present the decentralised task distribution algorithm (DTDA), the first decentralised solution to RjjCmax. Empirical evaluation of the DTDA is shown to generate solutions within 86–97% of the optimal on sparse graphs, in the best case, whilst providing a very good estimate (within 1%) of the global solution at each agent.