QUBO Resolution of the Job Reassignment Problem

Iñigo Perez Delgado; Beatriz García Markaida; Alejandro Mata Ali; Aitor Moreno Fdez. de Leceta

doi:10.1109/ITSC57777.2023.10422467

paper

QUBO Resolution of the Job Reassignment Problem

arXiv:2309.16473 · doi:10.1109/ITSC57777.2023.10422467

Abstract

We present a subproblemation scheme for heuristical solving of the JSP (Job Reassignment Problem). The cost function of the JSP is described via a QUBO hamiltonian to allow implementation in both gate-based and annealing quantum computers. For a job pool of $K$ jobs, $O (K^{2})$ binary variables -- qubits -- are needed to solve the full problem, for a runtime of $O (2^{K^{2}})$ . With the presented heuristics, the average variable number of each of the $D$ subproblems to solve is $O (K^{2} /2 D)$ , and the expected total runtime $O (D 2^{K^{2} /2 D})$ , achieving an exponential speedup.

Accepted for publication in in 2023 IEEE Symposium Series on Computational Intelligence (SSCI)