Analyzing the price of fairness in scheduling problems with two agents

Jin Yu, Peihai Liu, Xiwen Lu and Manzhan Gu

European Journal of Operational Research, 2025, vol. 321, issue 3, 750-759

Abstract: This paper focuses on the price of fairness in several scheduling problems with two agents, each with a set of nonpreemptive jobs, competing to execute their respective jobs on a single machine. Each agent expects to minimize its objective function, which depends on the completion times of its own jobs. Several objective functions are considered, including makespan, total (weighted) completion time and maximum tardiness. We focus on problems in which both agents pursue the same objective function. For each problem, we analyze the price of fairness and the complexity to find the fairness schedules among the Pareto optimal schedules. When the objective functions of both agents are total completion time, we design an algorithm to generate a near-fair solution and analyze its price of fairness.

Keywords: Scheduling; Price of fairness; Two-agent; Kalai–Smorodinsky fairness; Proportional fairness (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724007987
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:321:y:2025:i:3:p:750-759

DOI: 10.1016/j.ejor.2024.10.023

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