2026-07-20T10:39:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26677 2026-07-13T14:00:38Z ddc:004 open_access

Instance Space Analysis and Complexity Estimation for Scheduling Problems Pérez, Christian Catalá, Isabel López, Unai Salido, Miguel A. Job-shop Scheduling Instance Space Analysis Solver Hardness Multi-solver supervision Supervised Learning 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christian Pérez and Isabel Catalá and Unai López and Miguel A. Salido 2026 Is Part Of LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2026.45 urn:nbn:de:0030-drops-266770 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.45 eng https://creativecommons.org/licenses/by/4.0/legalcode