EFX Feasible Scheduling for Time-dependent Resources

Fang, Jiazhu; Fang, Qizhi; Li, Minming; Liu, Wenjing

doi:10.24963/ijcai.2025/426

EFX Feasible Scheduling for Time-dependent Resources

Jiazhu Fang, Qizhi Fang, Minming Li, Wenjing Liu

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 3830-3838.

https://doi.org/10.24963/ijcai.2025/426

Keywords

Game Theory and Economic Paradigms: GTEP: Fair division
Planning and Scheduling: PS: Scheduling

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 machines. 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.

Jiazhu Fang, Qizhi Fang, Minming Li, and Wenjing Liu. 2025. EFX Feasible Scheduling for Time-dependent Resources. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 3830–3838. https://doi.org/10.24963/ijcai.2025/426

@inproceedings{ijcai2025p426,
  title     = {EFX Feasible Scheduling for Time-dependent Resources},
  author    = {Fang, Jiazhu and Fang, Qizhi and Li, Minming and Liu, Wenjing},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {3830--3838},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/426},
  url       = {https://doi.org/10.24963/ijcai.2025/426},
}

TY  - CPAPER
TI  - EFX Feasible Scheduling for Time-dependent Resources
AU  - Fang, Jiazhu
AU  - Fang, Qizhi
AU  - Li, Minming
AU  - Liu, Wenjing
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 3830
EP  - 3838
DO  - 10.24963/ijcai.2025/426
UR  - https://doi.org/10.24963/ijcai.2025/426
ER  -