Trade-off between utility and fairness in two-agent single-machine scheduling

Alessandro Agnetis, Mario Benini, Gaia Nicosia and Andrea Pacifici

European Journal of Operational Research, 2025, vol. 323, issue 3, 767-779

Abstract: We consider the problem arising when two agents, each owning a set of jobs, compete to schedule their jobs on a common processing resource. Each schedule implies a certain utility for each agent and an overall system utility. We are interested in solutions that incorporate some criterion of fairness for the agents and, at the same time, are satisfactory from the viewpoint of system utility. More precisely, we investigate the trade-off between fairness and system utility when both agents want to minimize the total completion time of their respective jobs. We analyze the structure of the set of such trade-off solutions, and propose an exact algorithm for their computation, based on the Lagrangian relaxation of a MILP formulation of the problem. A large set of computational experiments has been carried out to show the viability of the approach. Moreover, the results show that in most cases a solution having a high degree of fairness can be obtained by sacrificing a very limited amount of system utility.

Keywords: Two-agent scheduling; Kalai-Smorodinsky fairness; Lagrangian relaxation; Branch and bound (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725000517
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:323:y:2025:i:3:p:767-779

DOI: 10.1016/j.ejor.2025.01.025

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 ().