Equitable scheduling on a single machine

Klaus Heeger (), Danny Hermelin (), George B. Mertzios (), Hendrik Molter (), Rolf Niedermeier () and Dvir Shabtay ()
Additional contact information
Klaus Heeger: Algorithmics and Computational Complexity, Faculty IV, TU Berlin
Danny Hermelin: Ben-Gurion University of the Negev
George B. Mertzios: Durham University
Hendrik Molter: Ben-Gurion University of the Negev
Rolf Niedermeier: Algorithmics and Computational Complexity, Faculty IV, TU Berlin
Dvir Shabtay: Ben-Gurion University of the Negev

Journal of Scheduling, 2023, vol. 26, issue 2, No 6, 209-225

Abstract: Abstract We introduce a natural but seemingly yet unstudied variant of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. The novelty of our new variant lies in simultaneously considering several instances of the problem at once. In particular, we have n clients over a period of m days, where each client has a single job with its own processing time and deadline per day. Our goal is to provide a schedule for each of the m days, so that each client is guaranteed to have their job meet its deadline in at least $$k \le m$$ k ≤ m days. This corresponds to an equitable schedule where each client is guaranteed a minimal level of service throughout the period of m days. We provide a thorough analysis of the computational complexity of three main variants of this problem, identifying both efficient algorithms and worst-case intractability results.

Keywords: Resource allocation; Fairness; Equity; Fixed-parameter tractability; Approximation (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-022-00754-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jsched:v:26:y:2023:i:2:d:10.1007_s10951-022-00754-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-022-00754-6

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().