@article{Zhang_Lo Bianco_Beck_2022, title={Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware}, volume={32}, url={https://ojs.aaai.org/index.php/ICAPS/article/view/19826}, DOI={10.1609/icaps.v32i1.19826}, abstractNote={The 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.}, number={1}, journal={Proceedings of the International Conference on Automated Planning and Scheduling}, author={Zhang, Jiachen and Lo Bianco, Giovanni and Beck, J. Christopher}, year={2022}, month={Jun.}, pages={404-412} }