Indirect Flow-Shop Coding Using Rank: Application to Indirect QAOA

The Flow-Shop Scheduling Problem (FSSP) is one of the most famous scheduling problems. The Flow-Shop scheduling problem is a disjunctive problem, meaning that a solution is fully described by an oriented disjunctive graph where the earliest starting times are computed with a longest path algorithm. We propose a new approach based on Quantum Approximate Optimization Algorithm (QAOA) to find high quality solutions to FSSP instances using a vector representation. This approach permits to solve the well-known Carlier’s instances with 64 operations to schedule. All the experiments have been achieved using the Qiskit library and carried on the IBM simulator. Presently, quantum methods cannot compete with classical ones because we lack quantum computers capable of solving large instances, and we have yet to figure out how to integrate the vast body of research results accumulated in flow-shop resolution over the last few decades into quantum algorithms. The ability of quantum approaches to effectively solve optimization problems in the future depends both on technical advancements in quantum machines and on the capacity to incorporate theoretical findings from scheduling into quantum optimization strategies.