Investigating the Variational Quantum Eigensolver to solve scheduling for identical parallel machines with sequence-dependent setup-times

Scheduling jobs on parallel identical machines with sequence-dependent setup times is a well-known NP-hard problem, which can be found in various industries such as the printed circuit board industry. We compare the performance of a classical exact solver and a hybrid quantum algorithm for solving this problem. As the classical exact solver, we introduce a Branch and Bound algorithm tailored to the problem. As for the quantum algorithm, we employ the Variational Quantum Eigensolver (VQE) and develop a dense encoding scheme that efficiently uses the limited number of qubits in a noise-free quantum computer simulation. For small problem instances, our results reveal that VQE shows a convergence behavior regarding the time to solution which is comparable to classical solvers. This initial approach for VQE solving the specific scheduling problem and its critical reflection lay the groundwork for identifying areas of inquiry for future research. Moreover, this work underscores the potential of quantum computing for solving complex optimization problems, which cannot be solved with classical solvers.