A multi-agent system for distributed multi-project scheduling: An auction-based negotiation approach

Simultaneously running multiple projects are quite common in industries. These projects require local (always available to the concerned project) and global (shared among the projects) resources that are available in limited quantity. The limited availability of the global resources coupled with compelling schedule requirements at different projects leads to resource conflicts among projects. Effectively resolving these resource conflicts is a challenging task for practicing managers. This paper proposes a novel distributed multi-agent system using auctions based negotiation (DMAS/ABN) approach for resolving the resource conflicts and allocating multiple different types of shared resources amongst multiple competing projects. The existing multi-agent system (MAS) using auction makes use of exact methods (e.g. dynamic programming relaxation) for solving winner determination problem to resolve resource conflicts and allocation of single unit of only one type of shared resource. Consequently these methods fail to converge for some multi-project instances and unsuitable for real life large problems. In this paper the multi-unit combinatorial auction is proposed and winner determination problem is solved by efficient new heuristic.The proposed approach can solve complex large-sized multi-project instances without any limiting assumptions regarding the number of activities, shared resources or the number of projects. Additionally our approach further allows to random project release-time of projects which arrives dynamically over the planning horizon. The DMAS/ABN is tested on standard set of 140 problem instances. The results obtained are benchmarked against the three state-of-the-art decentralized algorithms and two existing centralized methods. For 82 of 140 instances DMAS/ABN found new best solutions with respect to average project delay (APD) and produced schedules on an average 16.79% (with maximum 57.09%) lower APD than all the five methods for solving the same class of problems.