Quantum annealing-driven branch and bound for the single machine total weighted number of tardy jobs scheduling problem

In the paper we present a new approach to solving NP -hard problems of discrete optimization adapted to the architecture of quantum processors (QPU, Quantum Processor Unit) implementing hardware quantum annealing. This approach is based on the use of the quantum annealing metaheuristic in the exact branch and bound algorithm to compute the lower and upper bounds of the objective function. To determine the lower bound, a new method of defining the Lagrange function for the dual problem (the generalized discrete knapsack problem) was used, the value of which is calculated on the QPU of a quantum machine. In turn, to determine the upper bound, we formulate an appropriate task in the form of binary quadratic programming with constraints. Despite the fact that the results generated by the quantum machine are probabilistic, the hybrid method of algorithm construction proposed in the paper, using alternately a CPU and QPU, guarantees the optimal solution. As a case study we consider the NP -hard single machine scheduling problem with minimizing the weighted number of tardy jobs. The performed computational experiments showed that optimal solutions were already obtained in the root of the solution tree, and the values of the lower and upper bounds differ by only a few percent.