Fair Scheduling for Time-dependent Resources

Bo Li; Minming Li; Ruilong Zhang

Fair Scheduling for Time-dependent Resources

Bo Li
, Minming Li
, Ruilong Zhang^*

^*Corresponding author for this work

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

20 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	NeurIPS Proceedings
Subtitle of host publication	Advances in Neural Information Processing Systems 34 (NeurIPS 2021)
Editors	M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, J. Wortman Vaughan
Publisher	Neural Information Processing Systems (NeurIPS)
Pages	21744-21756
Number of pages	13
Volume	34
ISBN (Print)	9781713845393
Publication status	Published - Dec 2021
Event	35th Conference on Neural Information Processing Systems (NeurIPS 2021) - Virtual, Los Angeles, United States Duration: 6 Dec 2021 → 14 Dec 2021 https://nips.cc/virtual/2021/index.html https://papers.nips.cc/paper/2021 https://media.neurips.cc/Conferences/NeurIPS2021/NeurIPS_2021_poster.pdf https://www.proceedings.com/63069.html

Conference

Conference	35th Conference on Neural Information Processing Systems (NeurIPS 2021)
Place	United States
City	Los Angeles
Period	6/12/21 → 14/12/21
Internet address	https://nips.cc/virtual/2021/index.html https://papers.nips.cc/paper/2021 https://media.neurips.cc/Conferences/NeurIPS2021/NeurIPS_2021_poster.pdf https://www.proceedings.com/63069.html

Funding

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.

Access Output

https://papers.nips.cc/paper/2021/hash/b5b1d9ada94bb80609d21eecf7a2ce7a-Abstract.html

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Li, B., Li, M., & Zhang, R. (2021). Fair Scheduling for Time-dependent Resources. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. S. Liang, & J. Wortman Vaughan (Eds.), NeurIPS Proceedings: Advances in Neural Information Processing Systems 34 (NeurIPS 2021) (Vol. 34, pp. 21744-21756). Neural Information Processing Systems (NeurIPS). https://papers.nips.cc/paper/2021/hash/b5b1d9ada94bb80609d21eecf7a2ce7a-Abstract.html

@inproceedings{e72a0ce7401142718dc9c716f851d535,

title = "Fair Scheduling for Time-dependent Resources",

abstract = "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.",

author = "Bo Li and Minming Li and Ruilong Zhang",

year = "2021",

month = dec,

language = "English",

isbn = "9781713845393",

volume = "34",

pages = "21744--21756",

editor = "M. Ranzato and A. Beygelzimer and Y. Dauphin and P.S. Liang and \{Wortman Vaughan\}, J.",

booktitle = "NeurIPS Proceedings",

publisher = "Neural Information Processing Systems (NeurIPS)",

address = "United States",

note = "35th Conference on Neural Information Processing Systems (NeurIPS 2021) ; Conference date: 06-12-2021 Through 14-12-2021",

url = "https://nips.cc/virtual/2021/index.html, https://papers.nips.cc/paper/2021, https://media.neurips.cc/Conferences/NeurIPS2021/NeurIPS\_2021\_poster.pdf, https://www.proceedings.com/63069.html",

}

Li, B, Li, M & Zhang, R 2021, Fair Scheduling for Time-dependent Resources. in M Ranzato, A Beygelzimer, Y Dauphin, PS Liang & J Wortman Vaughan (eds), NeurIPS Proceedings: Advances in Neural Information Processing Systems 34 (NeurIPS 2021). vol. 34, Neural Information Processing Systems (NeurIPS), pp. 21744-21756, 35th Conference on Neural Information Processing Systems (NeurIPS 2021), Los Angeles, United States, 6/12/21. <https://papers.nips.cc/paper/2021/hash/b5b1d9ada94bb80609d21eecf7a2ce7a-Abstract.html>

Fair Scheduling for Time-dependent Resources. / Li, Bo; Li, Minming ; Zhang, Ruilong.
NeurIPS Proceedings: Advances in Neural Information Processing Systems 34 (NeurIPS 2021). ed. / M. Ranzato; A. Beygelzimer; Y. Dauphin; P.S. Liang; J. Wortman Vaughan. Vol. 34 Neural Information Processing Systems (NeurIPS), 2021. p. 21744-21756.

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Fair Scheduling for Time-dependent Resources

AU - Li, Bo

AU - Li, Minming

AU - Zhang, Ruilong

PY - 2021/12

Y1 - 2021/12

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 - https://www.scopus.com/pages/publications/85130993714

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85130993714&origin=recordpage

M3 - RGC 32 - Refereed conference paper (with host publication)

AN - SCOPUS:85130993714

SN - 9781713845393

VL - 34

SP - 21744

EP - 21756

BT - NeurIPS Proceedings

A2 - Ranzato, M.

A2 - Beygelzimer, A.

A2 - Dauphin, Y.

A2 - Liang, P.S.

A2 - Wortman Vaughan, J.

PB - Neural Information Processing Systems (NeurIPS)

T2 - 35th Conference on Neural Information Processing Systems (NeurIPS 2021)

Y2 - 6 December 2021 through 14 December 2021

ER -

Fair Scheduling for Time-dependent Resources

Abstract

Conference

Funding

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this