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.

Agnetis, A., Chen, B.o., Nicosia, G., Pacifici, A. (2019). Price of fairness in two-agent single-machine scheduling problems. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 276(1), 79-87 [10.1016/j.ejor.2018.12.048].

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

Agnetis, Alessandro;Nicosia, Gaia;Pacifici, Andrea
2019-01-01

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.
2019
Agnetis, A., Chen, B.o., Nicosia, G., Pacifici, A. (2019). Price of fairness in two-agent single-machine scheduling problems. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 276(1), 79-87 [10.1016/j.ejor.2018.12.048].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/347051
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 28
  • ???jsp.display-item.citation.isi??? 26
social impact