A multi-agent based cooperative approach to decentralized multi-project scheduling and resource allocation

While project crashing is a prominent practice in project management and can be approached by the well-known time–cost tradeoff problem (TCTP), the existing methodologies assume a centralized decision paradigm. In this paper, we study a new decentralized multi-project time-cost tradeoff problem, called MPTCTP-D, where project scheduling and resource allocation decisions are made in a distributed way by autonomous project managers to optimize their local objective, subject to a global available budget for all the projects. We show and prove the existence of price of anarchy as the difference between the optimal objective value of MPTCTP-D and its centralized counterpart. A multi-agent based cooperative approach with negotiation protocol is proposed to mitigate resource competition of autonomous local decisions and achieve a reasonable allocation of resource for global decision-maker, with both exact and local-search based heuristic algorithms developed. Our exact algorithm is able to find optimal solutions and prove optimality for instances with up to five projects and 120 activities per project. The hybrid randomized and 2-opt improvement algorithm is able to efficiently find optimal solutions to small instances and significantly better solutions than other heuristics alone for instances with up to 20 projects and 120 activities per project. Managerial insights on the optimal solutions and the price of anarchy are obtained and discussed.