Finding Pure Nash Equilibrium for the Resource Constrained Project Scheduling Problem

Abstract

The paper focuses on solving the Resource-Constrained Project Scheduling (RCPS) problem witha method based on intelligent agents. Parallelism forperforming the tasks is allowed. Common and limitedresources are available to all agents. The agents arenon-cooperative and compete with each other for theuse of common resources, thereby forming instances ofRCPS problem. We analyze the global joint interaction ofscheduling via a congestion network and seek to arriveat stable assignments of scheduling. For this class ofnetwork, stable assignments of scheduling correspondto a pure Nash equilibrium, and we show that in this casethere is a guarantee of obtaining a pure Nash equilibriumin polynomial time complexity. The pure Nash equilibriumpoint for this congestion network will be a localoptimum in the neighborhood structure of the projects,where no project can improve its completion time withoutnegatively affecting the completion time of the totalsystem. In our case, each state of the neighborhoodrepresents an instance of the RCPS problem, and forsolving such problem, we apply a novel greedy heuristic.It has a polynomial time complexity and works similar tothe well-knowing heuristic NEH.