Department of Computer Science AGH and IBM Software Laboratory in Krakow invite to Krakow Quantum Informatics Seminar (KQIS)
•    understand and discuss current problems in quantum informatics,
•    discuss new quantum computing technologies,
•    exchange ideas and research results,
•    integrate information across different research teams,
•    build a community around quantum informatics.
Venue:  via Internet, Webex

Tuesday, 7th of July, 2020, 9:30-11:00

Krzysztof KurowskiPoznań Supercomputing and Networking Centre, Poznań, PL

Topic: Hybrid quantum annealing heuristic method for solving job shop scheduling problem



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.



  • 1 month ago