A Multi-PR Heuristic for Distributed Multi-Project Scheduling With Uncertain Duration

Abstract

Multiple projects are often managed and run in a decentralized setting. In this paper, considering the uncertainty in project implementation, we study the distributed multi-project scheduling problem with uncertain duration. A multi-PR heuristic (MPR-H) is then proposed to dynamically coordinate the global resource conflicts while minimizing the expected total tardiness cost. Three priority rules based on current known information are also proposed and incorporated in our approach. We further consider the opportunistic behaviour of self-interested agents and design a payment negotiation process which is added to the MPR-H. In this paper, we then evaluate the performance of the MPR-H on the benchmark dataset MPSPLIB. The computational results confirm that MPR-H achieves significant improvements in comparison with several state-of-the-art distributed/centralized algorithms. The proposed algorithm also provides the senior manager with an efficient method to allocate global resources for large-size and strong conflicting instances under various activity duration distributions. Besides, we show that multi-projects with relative slack global resource constraints are more affected by the change of uncertainty. By analyzing the strategic behaviour of the agents in problems with two projects, we also show that in our MPR-H with payment negotiation approach, rational agents have to behave truthfully that is the dominant-strategy equilibrium leading to high-quality results.

Keywords

• Heuristic algorithms
• multi-project scheduling
• priority rule
• uncertainty