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: https://hdl.handle.net/11365/1191827