2020

rozdział w monografii naukowej / referat

angielski

EN 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 paper is to check experimentally if and how this approach can be applied for solving a well-known benchmark of the classical Job Shop Scheduling Problem. We present the existing capabilities provided by the D-Wave 2000Q quantum annealing system in the light of this benchmark. We have tested the quantum annealing system features experimentally, and proposed a new 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. We also indicate how new improvements in the upcoming D-Wave quantum processor might potentially impact the performance of our approach.

502 - 515

10.1007/978-3-030-50433-5_39

https://link.springer.com/chapter/10.1007%2F978-3-030-50433-5_39

Computational Science – ICCS 2020: 20th International Conference, Amsterdam, The Netherlands, June 3–5, 2020, Proceedings, Part VI

20th International Conference on Computational Science, 3-5.06.2020, Amsterdam, Netherlands

inne

ostateczna wersja opublikowana

15.06.2020

w momencie opublikowania

140