Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware
Keywords:Specialized Hardware, QUBO, Job-shop Scheduling Problem, Large Neighborhood Search, Constraint Programming, Digital Annealer
AbstractThe emergence of specialized hardware, such as quantum computers and Digital/CMOS annealers, and the slowing of performance growth of general-purpose hardware raises an important question for our community: how can the high-performance, specialized solvers be used for planning and scheduling problems? In this work, we focus on the job-shop scheduling problem (JSP) and Quadratic Unconstrained Binary Optimization (QUBO) models, the mathematical formulation shared by a number of novel hardware platforms. We study two direct QUBO models of JSP and propose a novel large neighborhood search (LNS) approach, that hybridizes a QUBO model with constraint programming (CP). Empirical results show that our LNS approach significantly outperforms classical CP-based LNS methods and a mixed integer programming model, while being competitive with CP for large problem instances. This work is the first approach that we are aware of that can solve non-trivial JSPs using QUBO hardware, albeit as part of a hybrid algorithm.
How to Cite
Zhang, J., Lo Bianco, G., & Beck, J. C. (2022). Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware. Proceedings of the International Conference on Automated Planning and Scheduling, 32(1), 404-412. https://doi.org/10.1609/icaps.v32i1.19826