Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware

Authors

  • Jiachen Zhang University of Toronto
  • Giovanni Lo Bianco University of Toronto
  • J. Christopher Beck University of Toronto

Keywords:

Specialized Hardware, QUBO, Job-shop Scheduling Problem, Large Neighborhood Search, Constraint Programming, Digital Annealer

Abstract

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.

Downloads

Published

2022-06-13

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. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/19826