Zapraszamy na Krakow Quantum Informatics Seminar organizowane wspólnie przez Katedrę Informatyki AGH i IBM Software Lab Kraków. Spotkanie odbędzie się we wtorek 7.07.2020 w godzinach 9:30-11:00 via Internet, Webex
W programie:
Krzysztof Kurowski, Poznań Supercomputing and Networking Centre, Poznań, PL
Temat: Hybrid quantum annealing heuristic method for solving job shop scheduling problem
PrezentacjaAbstract:
Scheduling problems have attracted the attention of researchers and practitioners for several decades. The quality of different methods developed to solve these problems on classical computers have been collected and compared in various benchmark repositories. Recently, quantum annealing has appeared as promising approach to solve some scheduling problems.
The goal of this talk is to show and discuss results of performed experiments to demonstrate how this new quantum-based approach can be applied for solving a well-known benchmark of the classical Job Shop Scheduling Problem. I will present the existing capabilities provided by the D-Wave 2000Q quantum annealing system in the light of this benchmark as we have tested the quantum annealing system features experimentally, and proposed a new hybrid classical-quantum heuristic method as a proof-of-concept.
In our approach we decompose the considered scheduling problem into a set of smaller optimization problems which fit better into a limited quantum hardware capacity. We have tuned experimentally various parameters of limited fully-connected graphs of qubits available in the quantum annealing system for the heuristic published in our recent paper. In my presentation, I will elaborate also on how new improvements in the upcoming D-Wave quantum processor might potentially impact the performance of our generic approach applicable for scheduling problems.