Back

Quantum annealing for job-shop scheduling

"”Quantum Annealing Implementation of Job-Shop Scheduling"

Published by Davide Venturelli, Dominic J.J. Marchand, Galo Rojo (NASA Ames RC, RIACS, 1QBit), 17th October 2016

arXiv:1506.08479
Optimization
Quantum annealing
Quantum annealing for job-shop scheduling

Qu&Co comments on this publication:

In this paper, Venturelli et al. present a quantum annealing solver for the renowned job-shop scheduling problem (JSP). They formulate 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 (DW2) processor. Problem simplifications and partitioning algorithms are discussed and the results from the processor are compared against state-of-the-art global-optimum solvers.