Fairness in repetitive scheduling

Danny Hermelin, Hendrik Molter, Rolf Niedermeier, Michael Pinedo and Dvir Shabtay

European Journal of Operational Research, 2025, vol. 323, issue 3, 724-738

Abstract: Recent research found that fairness plays a key role in customer satisfaction. Therefore, many manufacturing and services industries have become aware of the need to treat customers fairly. Still, there is a huge lack of models that enable industries to make operational decisions fairly, such as a fair scheduling of the customers’ jobs. Our main aim in this research is to provide a unified framework to enable schedulers to make fair decisions in repetitive scheduling environments. For doing so, we consider a set of repetitive scheduling problems involving a set of n clients. In each out of q consecutive operational periods (e.g. days), each one of the customers submits a job for processing by an operational system. The scheduler’s aim is to provide a schedule for each of the q periods such that the quality of service (QoS) received by each of the clients will meet a certain predefined threshold. The QoS of a client may take several different forms, e.g., the number of days that the customer receives its job later than a given due date, the number of times the customer receives his preferred time slot for service, or the sum of waiting times for service. We analyze the single machine variant of the problem for several different definitions of QoS, and classify the complexity of the corresponding problems using the theories of classical and parameterized complexity. We also study the price of fairness, i.e., the loss in the system’s efficiency that results from the need to provide fair solutions.

Keywords: (S) Scheduling; Algorithmic fairness; Repetitive scheduling; Parameterized complexity; Quality of service (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724009949
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:724-738

DOI: 10.1016/j.ejor.2024.12.052

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