Skip to main content

Research Repository

Advanced Search

Equitable scheduling on a single machine

Heeger, K.; Hermelin, D.; Mertzios, G.B.; Molter, H.; Niedermeier, R.; Shabtay, D.

Authors

K. Heeger

D. Hermelin

H. Molter

R. Niedermeier

D. Shabtay



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≤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.

Citation

Heeger, K., Hermelin, D., Mertzios, G., Molter, H., Niedermeier, R., & Shabtay, D. (2023). Equitable scheduling on a single machine. Journal of Scheduling, 26(2), 209-225. https://doi.org/10.1007/s10951-022-00754-6

Journal Article Type Article
Acceptance Date Aug 11, 2022
Online Publication Date Sep 19, 2022
Publication Date 2023-04
Deposit Date Sep 26, 2022
Publicly Available Date Mar 28, 2024
Journal Journal of Scheduling
Print ISSN 1094-6136
Electronic ISSN 1099-1425
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 26
Issue 2
Pages 209-225
DOI https://doi.org/10.1007/s10951-022-00754-6
Public URL https://durham-repository.worktribe.com/output/1190980

Files

Accepted Journal Article (407 Kb)
PDF

Copyright Statement
This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/s10951-022-00754-6





You might also like



Downloadable Citations