A Variational Quantum Algorithm for the Permutation Flow Shop Scheduling Problem

In this paper we present a Variational Quantum Algorithm (VQA) for the Permutation Flow Shop Scheduling Problem (PFSSP). This scheduling problem is challenging to be solved with a quantum algorithm because the objective function is quite difficult to be expressed by means of a Hamiltonian, and a large number of qubits is generally required. For this reason, we propose to use a variational approach where the solution is represented with a limited number of qubits and the objective function can be computed without explicitly synthesizing a Hamiltonian operator. The algorithm has been implemented and tested on a simulator; the preliminary experimental results demonstrate that our solution could represent a viable alternative to solve the PFSSP on real quantum devices.