DROPS

Document

DOI: 10.4230/LIPIcs.CP.2026.45

Instance Space Analysis and Complexity Estimation for Scheduling Problems

Authors: Christian Pérez, Isabel Catalá, Unai López, and Miguel A. Salido

Published in: LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)

Abstract

Benchmarking scheduling instances solely by nominal size is often misleading: instances with the same number of jobs and machines can differ by orders of magnitude in empirical hardness. This paper proposes a supervised, solver-aligned difficulty estimator for Job-shop Scheduling Problem (JSP) instances. Building on standard disjunctive-graph descriptors and ISA-inspired distributional summaries, we construct an auditable hardness target from normalised multi-solver traces and learn to predict it from static instance features. A Random Forest regressor learns a bounded hardness score 𝒫(x) ∈ [0,1], from which balanced easy/medium/hard categories are induced. The empirical evaluation shows that the learned score is strongly aligned with solver-effort indicators, provides interpretable feature-level explanations, and provides evidence of partial ordinal transfer on classical JSPLIB benchmarks under distribution shift. The proposed framework provides a practical and interpretable basis for difficulty-aware benchmarking, instance selection, and solver-behaviour analysis beyond nominal size parameters.

Cite as

Christian Pérez, Isabel Catalá, Unai López, and Miguel A. Salido. Instance Space Analysis and Complexity Estimation for Scheduling Problems. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{perez_et_al:LIPIcs.CP.2026.45,
  author =	{P\'{e}rez, Christian and Catal\'{a}, Isabel and L\'{o}pez, Unai and Salido, Miguel A.},
  title =	{{Instance Space Analysis and Complexity Estimation for Scheduling Problems}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{45:1--45:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-432-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{379},
  editor =	{Beldiceanu, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.45},
  URN =		{urn:nbn:de:0030-drops-266770},
  doi =		{10.4230/LIPIcs.CP.2026.45},
  annote =	{Keywords: Job-shop Scheduling, Instance Space Analysis, Solver Hardness, Multi-solver supervision, Supervised Learning}
}

Search Results

Documents authored by Salido, Miguel A.

Instance Space Analysis and Complexity Estimation for Scheduling Problems

Abstract

Cite as

Thanks for your feedback!

Could not send message