Iterative Quantum Annealing for Job Shop Scheduling with a Directed Graph Representation

A promising use of quantum computers lies in the logistics and scheduling of industrial problems, such as space mission planning, maritime management, and many others. This field is expected to provide useful applications for quantum computing at the current stage of hardware development. Quantum annealing techniques have been proposed to solve scheduling problems, along with many other optimization problems. In this work, we test quantum annealing and hybrid techniques based on the D-Wave hardware to solve scheduling problems in the framework of job shop scheduling (JSP), which consists of optimally assigning operations to certain resources, while satisfying specific constraints and minimizing the total scheduling time, known as timespan. We devised an iterative algorithm that produces valid schedules for decreasing timespan values. We implemented a refined iterative variable pruning technique, which significantly reduces the number of spin variables in the corresponding Ising model, whose low-energy configurations are sampled by using the D-Wave Hybrid Solver Service. Our novel iterative algorithm leverages a directed acyclic graph (DAG) representation of partial or complete solutions of the JSP instance, which enables an efficient update of the feasible processing time windows for each operation. This approach leads to significantly improved results compared to the standard state-of-the-art applications of quantum annealing for the JSP. Remarkably, we can often prove the absolute optimality of the obtained solution, namely that a more efficient schedule within a shorter timespan can not exist.