Quantum-Inspired Optimization for Large-Scale Combinatorial Scheduling Problems

Abstract

Large-scale combinatorial scheduling problems -- job-shop scheduling, flow-shop scheduling, and vehicle routing among them
-- remain NP-hard at practically relevant scale, and quantum computing has entered this space along two related tracks:
genuinely quantum solvers, principally quantum annealers and gate-based devices running the quantum approximate
optimization algorithm (QAOA), and quantum-inspired classical solvers, such as coherent Ising machines and digital
annealers, that borrow the same Ising/QUBO problem structure without requiring quantum hardware. This article synthesizes
both tracks as applied specifically to scheduling. We trace the theoretical foundations from quantum and simulated annealing
through the QUBO formulation techniques that make scheduling problems solver-ready, then review direct applications to
job-shop, flow-shop, and vehicle-routing problems, reporting the concrete, verified numbers the underlying studies provide. The
consistent finding is that quantum hardware remains constrained by qubit connectivity, embedding overhead, and shallow
achievable circuit depth to small benchmark instances, while quantum-inspired classical solvers, unconstrained by qubit
count, already reach scheduling-relevant problem sizes with reported performance competitive with or exceeding classical
heuristics. We close by identifying benchmarking rigor, hardware connectivity, and the near-total absence of work on dynamic,
online scheduling as the field's clearest open problems.