A multi-agent system for decentralised fractional shared resource constraint scheduling

Article type: Research Article

Authors: Singh, Gaurav | Weiskircher, Rene

Affiliations: CSIRO Mathematical and Information Sciences, Postal Bag 33, South Clayton VIC 3169, Australia E-mail: {Gaurav.Singh,Rene.Weiskircher}@csiro.au

Note: [] Corresponding author.

Abstract: We consider a collaborative scheduling problem motivated by mining in remote off-grid areas. In our model, jobs are preassigned to processors who have their own machine for executing them. Because each job needs a certain amount of a resource shared between the processors, a coordination mechanism between the processors is needed. We present a framework which collaboratively computes a schedule while exchanging only limited information between the processors and a central resource manager. Our computational experiments show that our negotiated approach outperforms a one-shot solution approach by a wide margin and produces fairer solutions than a centralised genetic algorithm that can make use of the private information of each processor. Depending on the number of processors, the solution quality found by the mechanism presented in this paper is competitive with or even better than that of the centralised genetic algorithm.

Keywords: Scheduling, collaboration, distributed optimisation, decentralised scheduling, approximation algorithms

DOI: 10.3233/WIA-2011-0208

Journal: Web Intelligence and Agent Systems: An International Journal, vol. 9, no. 2, pp. 99-108, 2011