@conference {4529, title = {Decentralised Parallel Machine Scheduling for Multi-Agent Task Allocation}, booktitle = {Proceedings of the 4th International Workshop on Optimization in Multi-Agent Systems Agents@AAMAS (OPTMAS 2011)}, year = {2011}, month = {May, 2011}, address = {Taipei, Taiiwan}, abstract = {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{\textendash}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.}, author = {Kathryn Macarthur and Meritxell Vinyals and Alessandro Farinelli and Sarvapali D. Ramchurn and Nicholas R. Jennings} }