This paper considers a project scheduling environment in which the activities of the project network are partitioned among a set of agents. Activity durations are controllable, i.e., every agent is allowed to shorten the duration of its activities, incurring a crashing cost. If the project makespan is reduced with respect to its normal value, a reward is offered to the agents and each agent receives a given ratio of the total reward. Agents want to maximize their profit. Assuming a complete knowledge of the agents’ parameters and of the activity network, this problem is modeled as a noncooperative game and Nash equilibria are analyzed.We characterize Nash equilibria in terms of the existence of certain types of cuts on the project network. We show that finding one Nash equilibrium is easy, while finding a Nash strategy that minimizes the project makespan is NP-hard in the strong sense. The particular case where each activity belongs to a different agent is also studied.
Agnetis, A., Briand, C., Billaut, J.C., Šůcha, P. (2015). Nash equilibria for the multi-agent project scheduling problem with controllable processing times. JOURNAL OF SCHEDULING, 18(1), 15-27 [10.1007/s10951-014-0393-x].
Nash equilibria for the multi-agent project scheduling problem with controllable processing times
Agnetis, Alessandro
;
2015-01-01
Abstract
This paper considers a project scheduling environment in which the activities of the project network are partitioned among a set of agents. Activity durations are controllable, i.e., every agent is allowed to shorten the duration of its activities, incurring a crashing cost. If the project makespan is reduced with respect to its normal value, a reward is offered to the agents and each agent receives a given ratio of the total reward. Agents want to maximize their profit. Assuming a complete knowledge of the agents’ parameters and of the activity network, this problem is modeled as a noncooperative game and Nash equilibria are analyzed.We characterize Nash equilibria in terms of the existence of certain types of cuts on the project network. We show that finding one Nash equilibrium is easy, while finding a Nash strategy that minimizes the project makespan is NP-hard in the strong sense. The particular case where each activity belongs to a different agent is also studied.File | Dimensione | Formato | |
---|---|---|---|
Nash equilibria for the multi-agent project scheduling problem with controllable processing times.pdf
non disponibili
Tipologia:
PDF editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
483.99 kB
Formato
Adobe PDF
|
483.99 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.
https://hdl.handle.net/11365/982914