Multi-Organizational Scheduling: Individual Rationality, Optimality, and Complexity
Authors: Jiehua Chen, Martin Durand, Christian Hatschka
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our analysis reveals that finding an individually rational schedule with minimum makespan is ΘP 2-hard, placing it in a complexity class strictly harder than both NP and co NP. 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. We systematically investigate the algorithmic complexity of two optimization problems: Cmax MOS and CΣ-MOS. Generally speaking, both problems are computationally hard. More precisely, the decision variant of Cmax-MOS is ΘP 2-complete1 while the one of CΣ-MOS is NP-complete. We also present parameterized complexity analysis considering key parameters (and their combinations). |
| Researcher Affiliation | Academia | 1TU Wien, Institute of Logic and Computation, Vienna, Austria 2Sorbonne Universit e, CNRS, LIP6, Paris, France EMAIL, EMAIL |
| Pseudocode | No | The paper describes algorithms using Integer Linear Programming (ILP) and dynamic programming (DP) concepts, such as "We can then introduce an integer variable for each machine type and use ILP to find an optimal solution." and "We now describe the recurrence:", but does not present these as structured pseudocode or algorithm blocks. The descriptions are given in mathematical and textual form. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code for the described methodology, nor does it provide any links to code repositories. |
| Open Datasets | No | This paper is theoretical research focusing on algorithmic complexity. It defines problem instances but does not use or refer to any specific publicly available datasets for experimental evaluation. Therefore, there is no information regarding open datasets. |
| Dataset Splits | No | This paper is theoretical research and does not involve experimental evaluation on datasets. Therefore, there is no information regarding dataset splits. |
| Hardware Specification | No | This paper is theoretical research focusing on algorithmic complexity. It does not describe any empirical experiments that would require specific hardware, hence no hardware specifications are mentioned. |
| Software Dependencies | No | This paper is theoretical research and does not detail any empirical experiments or software implementations with specific version numbers for reproducibility. It mentions using ILP as a technique but not a specific solver version. |
| Experiment Setup | No | This paper is theoretical research and does not describe any empirical experiments, hence no experimental setup details like hyperparameters or training configurations are provided. |