Price of fairness in two-agent single-machine scheduling problems

Alessandro Agnetis, Bo Chen, Gaia Nicosia and Andrea Pacifici

European Journal of Operational Research, 2019, vol. 276, issue 1, 79-87

Abstract: We investigate the concept of price of fairness in resource allocation and apply it to two-agent single-machine scheduling problems, in which two agents, each having a set of jobs, compete for use of a single machine to execute their jobs. We consider the situation where one agent aims at minimizing the total of the completion times of his jobs, while the other seeks to minimize the maximum tardiness with respect to a common due date for her jobs. We first explore and propose a definition of utility, then we study both max-min and proportionally fair solutions, providing a tight bound on the price of fairness for each notion of fairness. We extend our study further to the problem in which both agents wish to minimize the total of the completion times of their own jobs.

Keywords: Two-agent scheduling; Max–min fairness; Kalai–Smorodinsky fairness; Proportional fairness; Price of fairness (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719300025
Full text for ScienceDirect subscribers only

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:eee:ejores:v:276:y:2019:i:1:p:79-87

DOI: 10.1016/j.ejor.2018.12.048

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().