Quantum Integer Programming: an Annealing approach to the Job Shop Scheduling problem

In this thesis i developed a complete workflow to get optimal solutions of the JSS problem. During this work i deeply analized many of the steps required in the usage of quantum annealers. In detail i tested 2 different approaches to the minor-embedding procedure and compared them with the current default euristic implemented by Dwave. I also tested an hybrid algorithm wich extract the elements of the Graver basis of the problem and then augment an initial feasible solution to obtain an optimal one. The obtained results shows that the quantum annealers can get to optimal solutions in a competitive time but, due to the limited numer of working qubits and the sparse connectivity among them, only small instances can be efficiently solved with the current hardware.