Hybrid Quantum Annealing Heuristic Method for Solving Job Shop Scheduling Problem
| Autor: | Krzysztof Kurowski, Rafał Różycki, Jan Wȩglarz, Grzegorz Waligóra, Marek Subocz |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
0303 health sciences
Mathematical optimization Optimization problem Job shop scheduling Computer science Heuristic Quantum annealing Job shop scheduling problem 01 natural sciences Scheduling (computing) 03 medical and health sciences Qubit 0103 physical sciences 010306 general physics Quantum 030304 developmental biology Quantum computer |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783030504328 ICCS (6) |
| DOI: | 10.1007/978-3-030-50433-5_39 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|