Multi-agent Based Distributed MIS Selection for Dynamic Job Scheduling

This paper presents a distributed approach to solve dynamic Job Scheduling problem using the notion of distributed Maximal Independent Set (MIS) problem. Initial MIS selection may become improper due to the addition and deletion of vertices in a dynamic graph. This paper introduces a multi-agent based P-MIS algorithm to find out a dynamic schedule without violating the predefined constraints. Theoretical analysis of message passing complexity and anti-starvation property of the proposed distributed algorithm is provided in this paper. Using benchmark graph instances, experimental results are analyzed to compare the performance of proposed P-MIS with IoA-based and cooperative approach for job scheduling.