# Quantum Annealing Implementation of Job-Shop Scheduling

arXiv: https://arxiv.org/abs/1506.08479 · HTML: https://mlsanity.com/paper/1506.08479/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jun 2015.

## Built on by (most cited first, 6 of 6)

- [Assessment of image generation by quantum annealer](https://mlsanity.com/paper/2103.08373/) (2021)
- [Solving the Extended Job Shop Scheduling Problem with AGVs -- Classical and Quantum Approaches](https://mlsanity.com/paper/2109.04830/) (2021)
- [Relaxation-assisted reverse annealing on nonnegative/binary matrix factorization](https://mlsanity.com/paper/2501.02114/) (2025)
- [Skipper: Improving the Reach and Fidelity of Quantum Annealers by Skipping Long Chains](https://mlsanity.com/paper/2312.00264/) (2023)
- [Statistical Mechanics Calculations Using Variational Autoregressive Networks and Quantum Annealing](https://mlsanity.com/paper/2404.19274/) (2024)
- [Quantum-machine-assisted Drug Discovery](https://mlsanity.com/paper/2408.13479/) (2024)

## Abstract (arXiv)

A quantum annealing solver for the renowned job-shop scheduling problem (JSP) is presented in detail. After formulating the problem as a time-indexed quadratic unconstrained binary optimization problem, several pre-processing and graph embedding strategies are employed to compile optimally parametrized families of the JSP for scheduling instances of up to six jobs and six machines on the D-Wave Systems Vesuvius processor. Problem simplifications and partitioning algorithms, including variable pruning and running strategies that consider tailored binary searches, are discussed and the results from the processor are compared against state-of-the-art global-optimum solvers.