Minimizing the makespan of a multiagent project scheduling problem: the price of stability In session Scheduling in supply chains and production systems

Cyril Briand (1) , Alessandro Agnetis , Jean-Charles Billaut (2) , Sandra Ulrich Ngueveu (1) , Přemysl Šůcha (3)

1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
2 LIFAT - Laboratoire d'Informatique Fondamentale et Appliquée de Tours
3 CAK - Centre for Applied Cybernetics

We consider cooperative projects involving a set of self-interested contractors, each in charge of a part of a project. Each contractor is able to reduce the duration of his activities at a given cost. Accordingly, the project makespan depends on all contractors' strategies. On his/her side, the project client is interested in a short makespan and, as an incentive, offers a daily reward to be shared among contractors. We take an interest in the problem of finding a strategy profile and a sharing policy that minimize the project makespan while ensuring schedule stability (Nash equilibrium).

Domaines: Complexité [cs.CC]; Recherche opérationnelle [math.OC]

Cyril Briand, Alessandro Agnetis, Jean-Charles Billaut, Sandra Ulrich Ngueveu, Přemysl Šůcha. Minimizing the makespan of a multiagent project scheduling problem: the price of stability In session Scheduling in supply chains and production systems. 26th European Conference on Operational Research, 2013, Rome, Italy. ⟨hal-01025863⟩