Nash equilibrium solutions in multi-agent project scheduling with milestones

Přemysl Šůcha, Alessandro Agnetis, Marko Šidlovský and Cyril Briand

European Journal of Operational Research, 2021, vol. 294, issue 1, 29-41

Abstract: This paper addresses a project scheduling environment in which the activities are partitioned among a set of agents. The project owner is interested in completing the project as soon as possible. Therefore, she/he defines rewards and penalties to stimulate the agents to complete the project faster. The project owner offers a per-day reward for early project completion and defines intermediate project milestones to be met within specific due dates, with associated per-day penalties. Each agent can, therefore, decide the duration of her/his activities, taking into account linear activity crashing costs, the reward for early project completion, and the penalty arising from violating milestone due-dates. We consider Nash equilibria, i.e., situations in which no agent has an interest in individually changing the duration of any of her/his activities, and in particular, the problem of finding a minimum-makespan equilibrium. This problem is known to be NP-hard, and in this paper, we (i) propose a new and efficient exact algorithmic approach for finding the minimum-makespan equilibrium and (ii) through an extensive computational campaign we evaluate the role played by milestones in driving the project towards the owner’s goal.

Keywords: Project scheduling; Nash equilibria; Flow networks; Milestones; Lazy-constraint generation (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721000400
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:294:y:2021:i:1:p:29-41

DOI: 10.1016/j.ejor.2021.01.023

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().