Nash equilibria for the multi-agent project scheduling problem with controllable processing times

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F15%3A00221582" target="_blank" >RIV/68407700:21230/15:00221582 - isvavai.cz</a>

Result on the web

<a href="http://link.springer.com/article/10.1007%2Fs10951-014-0393-x" target="_blank" >http://link.springer.com/article/10.1007%2Fs10951-014-0393-x</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10951-014-0393-x" target="_blank" >10.1007/s10951-014-0393-x</a>

Result language

angličtina

Original language name

Nash equilibria for the multi-agent project scheduling problem with controllable processing times

Original language description

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 ofthe agents? parameters and of the activity network, this problem is modeled as a non-cooperative 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 and some polyn

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BB - Applied statistics, operational research

OECD FORD branch

—

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2015

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Journal of Scheduling

ISSN

1094-6136

e-ISSN

—

Volume of the periodical

18

Issue of the periodical within the volume

1

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

13

Pages from-to

15-27

UT code for WoS article

000347896300003

EID of the result in the Scopus database

2-s2.0-84926613251