Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.12377 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912381221732352 |
|---|---|
| author | Chen, Jiehua Durand, Martin Hatschka, Christian |
| author_facet | Chen, Jiehua Durand, Martin Hatschka, Christian |
| contents | We investigate multi-organizational scheduling problems, building upon the framework introduced by Pascual et al.[2009]. In this setting, multiple organizations each own a set of identical machines and sequential jobs with distinct processing times. The challenge lies in optimally assigning jobs across organizations' machines to minimize the overall makespan while ensuring no organization's performance deteriorates. To formalize this fairness constraint, we introduce individual rationality, a game-theoretic concept that guarantees each organization benefits from participation.
Our analysis reveals that finding an individually rational schedule with minimum makespan is $Θ_2^{\text{P}}$-hard, placing it in a complexity class strictly harder than both NP and coNP. We further extend the model by considering an alternative objective: minimizing the sum of job completion times, both within individual organizations and across the entire system. The corresponding decision variant proves to be NP-complete. Through comprehensive parameterized complexity analysis of both problems, we provide new insights into these computationally challenging multi-organizational scheduling scenarios. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_12377 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multi-Organizational Scheduling: Individual Rationality, Optimality, and Complexity Chen, Jiehua Durand, Martin Hatschka, Christian Computer Science and Game Theory We investigate multi-organizational scheduling problems, building upon the framework introduced by Pascual et al.[2009]. In this setting, multiple organizations each own a set of identical machines and sequential jobs with distinct processing times. The challenge lies in optimally assigning jobs across organizations' machines to minimize the overall makespan while ensuring no organization's performance deteriorates. To formalize this fairness constraint, we introduce individual rationality, a game-theoretic concept that guarantees each organization benefits from participation. Our analysis reveals that finding an individually rational schedule with minimum makespan is $Θ_2^{\text{P}}$-hard, placing it in a complexity class strictly harder than both NP and coNP. We further extend the model by considering an alternative objective: minimizing the sum of job completion times, both within individual organizations and across the entire system. The corresponding decision variant proves to be NP-complete. Through comprehensive parameterized complexity analysis of both problems, we provide new insights into these computationally challenging multi-organizational scheduling scenarios. |
| title | Multi-Organizational Scheduling: Individual Rationality, Optimality, and Complexity |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2505.12377 |