TY - GEN
T1 - Fair Scheduling for Time-dependent Resources
AU - Li, Bo
AU - Li, Minming
AU - Zhang, Ruilong
N1 - Funding Information:
The authors thanks Warut Suksompong for reading a draft of this paper and for helpful discussions. Bo Li was partially funded by The Hong Kong Polytechnic University under Grant No. P0034420. Minming Li was partially supported by NSFC under Grant No. 11771365, and by Project No. CityU 11200518 from Research Grants Council of HKSAR.
Publisher Copyright:
© 2021 Neural information processing systems foundation. All rights reserved.
PY - 2021/9
Y1 - 2021/9
N2 - We study a fair resource scheduling problem,nwhere a set of interval jobs are to be allocated to heterogeneous machines controlled by intellectual agents. Each job is associated with release time, deadline and processing time such that it can be processed if its complete processing period is between its release time and deadline. The machines gain possibly different utilities by processing different jobs, and all jobs assigned to the same machine should be processed without overlap. We consider two widely studied solution concepts, namely, maximin share fairness and envy-freeness. For both criteria, we discuss the extent to which fair allocations exist and present constant approximation algorithms for various settings.
AB - We study a fair resource scheduling problem,nwhere a set of interval jobs are to be allocated to heterogeneous machines controlled by intellectual agents. Each job is associated with release time, deadline and processing time such that it can be processed if its complete processing period is between its release time and deadline. The machines gain possibly different utilities by processing different jobs, and all jobs assigned to the same machine should be processed without overlap. We consider two widely studied solution concepts, namely, maximin share fairness and envy-freeness. For both criteria, we discuss the extent to which fair allocations exist and present constant approximation algorithms for various settings.
UR - http://www.scopus.com/inward/record.url?scp=85130993714&partnerID=8YFLogxK
M3 - Conference article published in proceeding or book
AN - SCOPUS:85130993714
T3 - Advances in Neural Information Processing Systems
SP - 21744
EP - 21756
BT - Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021
A2 - Ranzato, Marc'Aurelio
A2 - Beygelzimer, Alina
A2 - Dauphin, Yann
A2 - Liang, Percy S.
A2 - Wortman Vaughan, Jenn
PB - Neural information processing systems foundation
T2 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021
Y2 - 6 December 2021 through 14 December 2021
ER -