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, 475-491
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)
References: View references in EconPapers View complete reference list from CitEc
Citations: Track citations by RSS feed
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.
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
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
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 ().