Equitable scheduling on a single machine

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

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: Sep 20, 2023
• 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