QUBO Resolution of the Job Reassignment Problem

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(K2) binary variables -- qubits -- are needed to solve the full problem, for a runtime of O(2K2). With the presented heuristics, the average variable number of each of the D subproblems to solve is O(K2/2D), and the expected total runtime O(D2K2/2D), achieving an exponential speedup.