Comparison of D-Wave Quantum Computing Environment Solvers for a Two-Machine Jobs Scheduling Problem

Solving discrete optimization problems on D-Wave’s quantum platform requires formulating the problem in the form of quadratic programming. In this work we consider an NP-hard two-machine flow problem with minimization of the sum of jobs weighted tardinesses. We present two formulations of the Constrained Quadratic Model (CQM) for solving the considered problem, the transformation method to QUBO, and the results of computational experiments performed in three environments: LeapHybridSampler, DWaveSampler, and Gurobi. We propose a novel approach to constructing hybrid quantum annealing algorithms generating solutions very close to or equal to the optimal ones.