Finding an optimal Nash equilibrium to the multi-agent project scheduling problem

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F17%3A00311298" target="_blank" >RIV/68407700:21230/17:00311298 - isvavai.cz</a>

Result on the web

<a href="https://link.springer.com/article/10.1007%2Fs10951-017-0516-2" target="_blank" >https://link.springer.com/article/10.1007%2Fs10951-017-0516-2</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10951-017-0516-2" target="_blank" >10.1007/s10951-017-0516-2</a>

Result language

angličtina

Original language name

Finding an optimal Nash equilibrium to the multi-agent project scheduling problem

Original language description

Large projects often involve a set of contractors, each in charge of a part of the project. In this paper, we assume that every contractor is self-interested and can control the duration of his/her activities, which can be shortened up to an incompressible limit, by gathering extra resources at a given cost. In this context, the resulting project makespan depends on all the contractors’ decisions. The customer of the project is interested in a short project makespan and offers a reward, proportional to the project makespan reduction, to be shared by the contractors. In practice, either the reward sharing policy results from an upfront agreement or payments are freely allocated by the customer. Each contractor is only interested in the maximization of his/her profit and behaves accordingly. This paper addresses the problem of finding a Nash equilibrium and a sharing policy that minimize the project makespan. The aim is to help the customer to determine the duration of the activities and the reward sharing policy such that no agent has an incentive to unilaterally deviate from this solution. We show that this problem is NP-hard and how it can be modeled and solved by mixed integer linear programming. Computational analysis on large instances proves the effectiveness of our approach. Based on an empirical investigation of the influence of reward sharing policies on the project makespan, the paper provides new insight into how a project’s customer should offer rewards to the contractors.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA16-23509S" target="_blank" >GA16-23509S: Flexible Scheduling and Optimization Algorithms for Distributed Real-time Embedded Systems</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2017

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

1099-1425

Volume of the periodical

20

Issue of the periodical within the volume

5

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

17

Pages from-to

475-491

UT code for WoS article

000412544900004

EID of the result in the Scopus database

2-s2.0-85015958906