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.

Equitable scheduling on a single machine Thumbnail


Authors

K. Heeger

D. Hermelin

H. Molter

R. Niedermeier

D. Shabtay



Abstract

We introduce a natural but seemingly yet unstudied generalization of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. Our generalization 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. (2021). Equitable scheduling on a single machine. . https://doi.org/10.1609/aaai.v35i13.17404

Conference Name 35th AAAI Conference on Artificial Intelligence (AAAI)
Conference Location Vancouver, Canada
Start Date Feb 2, 2021
End Date Feb 9, 2021
Acceptance Date Dec 2, 2020
Online Publication Date May 18, 2021
Publication Date 2021
Deposit Date Dec 3, 2020
Publicly Available Date Mar 28, 2024
Series Number 13
Series ISSN 2159-5399,2374-3468
DOI https://doi.org/10.1609/aaai.v35i13.17404

Files





You might also like



Downloadable Citations