Quantum annealing methods for realistic job shop scheduling problems

In quantum annealers the system of qubits of the quantum processing unit (QPU) is adiabatically evolved to reach, at the end of the coherent quantum evolution, the target state that encodes the solution to the optimization problem.

A difficult application of this computational paradigm is the job shop scheduling problem (JSSP), an NP-hard problem often utilized in the literature to implement realistic scheduling tasks, which are crucial for mission planning in the space exploration field. The JSSP is a constrained optimization problem that can be implemented in a QUBO (quadratic unconstrained binary optimization) formulation.

We used D-Wave Advantage, Advantage2, and hybrid classical-quantum solver service (HSS) to tackle different instances of the JSSP from available datasets or ad hoc generated, to study the capabilities and limitations of D-Wave’s QPUs and HSS in terms of the number of binary variables, ranging from about 20 to 1000, which correspond respectively to problems with approximately from 9 to 36 operations to be performed in the shortest possible time. We address schedule optimization by replacing linear quantum annealing with tailored pausing or reverse annealing approaches. Alternative formulations of the problem and classical pre-processing are also included in our work.

The results demonstrate that quantum annealing can solve small instances of the JSSP, while the hybrid approach, with a classical post-processing step, finds the exact solution also for bigger instances.