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.

Sucha, P., Agnetis, A., Sidlovsky, M., & Briand, C. (2021). Nash equilibrium solutions in multi-agent project scheduling with milestones. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 294(1), 29-41 [10.1016/j.ejor.2021.01.023].

Nash equilibrium solutions in multi-agent project scheduling with milestones

Agnetis A.;
2021

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.
Sucha, P., Agnetis, A., Sidlovsky, M., & Briand, C. (2021). Nash equilibrium solutions in multi-agent project scheduling with milestones. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 294(1), 29-41 [10.1016/j.ejor.2021.01.023].
File in questo prodotto:
File Dimensione Formato  
Nash equilibrium solutions in multi-agent project scheduling with milestones.pdf

non disponibili

Tipologia: PDF editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 841.64 kB
Formato Adobe PDF
841.64 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11365/1191827