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

Cyril Briand (), Sandra Ulrich Ngueveu () and Přemysl Šůcha ()
Additional contact information
Cyril Briand: CNRS, LAAS
Sandra Ulrich Ngueveu: CNRS, LAAS
Přemysl Šůcha: CNRS, LAAS

Journal of Scheduling, 2017, vol. 20, issue 5, No 4, 475-491

Abstract: Abstract 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.

Keywords: Project scheduling; Time-cost trade-off; Nash equilibrium; Mixed integer programming (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-017-0516-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:20:y:2017:i:5:d:10.1007_s10951-017-0516-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-017-0516-2

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().