EFX Feasible Scheduling for Time-dependent Resources

Jiazhu Fang; Qizhi Fang; Minming Li; Wenjing Liu

doi:10.24963/ijcai.2025/426

EFX Feasible Scheduling for Time-dependent Resources

Jiazhu Fang
, Qizhi Fang
, Minming Li^*
, Wenjing Liu

^*Corresponding author for this work

Ocean University of China
City University of Hong Kong

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

In this paper, we study a fair resource scheduling problem involving the assignment of a set of interval jobs among a group of heterogeneous machines. Each job is associated with a release time, a deadline, and a processing time. A machine can process a job if the entire processing period falls within the release time and deadline of the job. Each machine can process at most one job at any given time, and different jobs yield different utilities for the machine. The goal is to find a fair and efficient schedule of the jobs. We discuss the compatibility between envy-freeness up to any item (EFX) and various efficiency concepts. Additionally, we present polynomial-time algorithms for various settings.

Original language	English
Title of host publication	Proceedings of the 34th International Joint Conference on Artificial Intelligence, IJCAI 2025
Editors	James Kwok
Publisher	International Joint Conferences on Artificial Intelligence
Pages	3830-3838
Number of pages	9
ISBN (Electronic)	9781956792065
DOIs	https://doi.org/10.24963/ijcai.2025/426
State	Published - 2025
Externally published	Yes
Event	34th Internationa Joint Conference on Artificial Intelligence, IJCAI 2025 - Montreal, Canada Duration: 16 Aug 2025 → 22 Aug 2025

Publication series

Name	IJCAI International Joint Conference on Artificial Intelligence
ISSN (Print)	1045-0823

Conference

Conference	34th Internationa Joint Conference on Artificial Intelligence, IJCAI 2025
Country/Territory	Canada
City	Montreal
Period	16/08/25 → 22/08/25

Access to Document

10.24963/ijcai.2025/426

Cite this

Fang, J., Fang, Q., Li, M., & Liu, W. (2025). EFX Feasible Scheduling for Time-dependent Resources. In J. Kwok (Ed.), Proceedings of the 34th International Joint Conference on Artificial Intelligence, IJCAI 2025 (pp. 3830-3838). (IJCAI International Joint Conference on Artificial Intelligence). International Joint Conferences on Artificial Intelligence. https://doi.org/10.24963/ijcai.2025/426

@inproceedings{d18c81c80a3747c38507e57feab0fba6,

title = "EFX Feasible Scheduling for Time-dependent Resources",

abstract = "In this paper, we study a fair resource scheduling problem involving the assignment of a set of interval jobs among a group of heterogeneous machines. Each job is associated with a release time, a deadline, and a processing time. A machine can process a job if the entire processing period falls within the release time and deadline of the job. Each machine can process at most one job at any given time, and different jobs yield different utilities for the machine. The goal is to find a fair and efficient schedule of the jobs. We discuss the compatibility between envy-freeness up to any item (EFX) and various efficiency concepts. Additionally, we present polynomial-time algorithms for various settings.",

author = "Jiazhu Fang and Qizhi Fang and Minming Li and Wenjing Liu",

note = "Publisher Copyright: {\textcopyright} 2025 International Joint Conferences on Artificial Intelligence. All rights reserved.; 34th Internationa Joint Conference on Artificial Intelligence, IJCAI 2025 ; Conference date: 16-08-2025 Through 22-08-2025",

year = "2025",

doi = "10.24963/ijcai.2025/426",

language = "英语",

series = "IJCAI International Joint Conference on Artificial Intelligence",

publisher = "International Joint Conferences on Artificial Intelligence",

pages = "3830--3838",

editor = "James Kwok",

booktitle = "Proceedings of the 34th International Joint Conference on Artificial Intelligence, IJCAI 2025",

address = "美国",

}

Fang, J, Fang, Q, Li, M & Liu, W 2025, EFX Feasible Scheduling for Time-dependent Resources. in J Kwok (ed.), Proceedings of the 34th International Joint Conference on Artificial Intelligence, IJCAI 2025. IJCAI International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence, pp. 3830-3838, 34th Internationa Joint Conference on Artificial Intelligence, IJCAI 2025, Montreal, Canada, 16/08/25. https://doi.org/10.24963/ijcai.2025/426

EFX Feasible Scheduling for Time-dependent Resources. / Fang, Jiazhu; Fang, Qizhi; Li, Minming et al.
Proceedings of the 34th International Joint Conference on Artificial Intelligence, IJCAI 2025. ed. / James Kwok. International Joint Conferences on Artificial Intelligence, 2025. p. 3830-3838 (IJCAI International Joint Conference on Artificial Intelligence).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - EFX Feasible Scheduling for Time-dependent Resources

AU - Fang, Jiazhu

AU - Fang, Qizhi

AU - Li, Minming

AU - Liu, Wenjing

PY - 2025

Y1 - 2025

N2 - In this paper, we study a fair resource scheduling problem involving the assignment of a set of interval jobs among a group of heterogeneous machines. Each job is associated with a release time, a deadline, and a processing time. A machine can process a job if the entire processing period falls within the release time and deadline of the job. Each machine can process at most one job at any given time, and different jobs yield different utilities for the machine. The goal is to find a fair and efficient schedule of the jobs. We discuss the compatibility between envy-freeness up to any item (EFX) and various efficiency concepts. Additionally, we present polynomial-time algorithms for various settings.

AB - In this paper, we study a fair resource scheduling problem involving the assignment of a set of interval jobs among a group of heterogeneous machines. Each job is associated with a release time, a deadline, and a processing time. A machine can process a job if the entire processing period falls within the release time and deadline of the job. Each machine can process at most one job at any given time, and different jobs yield different utilities for the machine. The goal is to find a fair and efficient schedule of the jobs. We discuss the compatibility between envy-freeness up to any item (EFX) and various efficiency concepts. Additionally, we present polynomial-time algorithms for various settings.

UR - https://www.scopus.com/pages/publications/105021807820

U2 - 10.24963/ijcai.2025/426

DO - 10.24963/ijcai.2025/426

M3 - 会议稿件

AN - SCOPUS:105021807820

T3 - IJCAI International Joint Conference on Artificial Intelligence

SP - 3830

EP - 3838

BT - Proceedings of the 34th International Joint Conference on Artificial Intelligence, IJCAI 2025

A2 - Kwok, James

PB - International Joint Conferences on Artificial Intelligence

T2 - 34th Internationa Joint Conference on Artificial Intelligence, IJCAI 2025

Y2 - 16 August 2025 through 22 August 2025

ER -

Fang J, Fang Q, Li M, Liu W. EFX Feasible Scheduling for Time-dependent Resources. In Kwok J, editor, Proceedings of the 34th International Joint Conference on Artificial Intelligence, IJCAI 2025. International Joint Conferences on Artificial Intelligence. 2025. p. 3830-3838. (IJCAI International Joint Conference on Artificial Intelligence). doi: 10.24963/ijcai.2025/426

EFX Feasible Scheduling for Time-dependent Resources

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this