W zależności od ilości danych do przetworzenia generowanie pliku może się wydłużyć.

Jeśli generowanie trwa zbyt długo można ograniczyć dane np. zmniejszając zakres lat.

Artykuł

Pobierz BibTeX

Tytuł

Application of Quantum Approximate Optimization Algorithm to Job Shop Scheduling Problem

Autorzy

[ 1 ] Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | [ 2 ] Instytut Informatyki, Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | [ SzD ] doktorant ze Szkoły Doktorskiej | [ P ] pracownik

Dyscyplina naukowa (Ustawa 2.0)

[2.3] Informatyka techniczna i telekomunikacja

Rok publikacji

2023

Opublikowano w

European Journal of Operational Research

Rocznik: 2023 | Tom: vol. 310 | Numer: no. 2

Typ artykułu

artykuł naukowy

Język publikacji

angielski

Słowa kluczowe
EN
  • Scheduling
  • Computing science
  • Heuristics
  • Job Shop Scheduling Problem
  • Quantum Approximate Optimization Algorithm
Streszczenie

EN The Job Shop Scheduling Problem (JSSP) has always been considered as one of the most complex and industry essential scheduling problems. Optimizing the makespan of a given schedule generally involves using dedicated algorithms, local search strategies, or metaheuristics. These approaches, however, heavily rely on classical computational power, which is bounded by the physical limits of microcontrollers and power issues. Inspired by the promising results achieved for Quantum Annealing (QA) based approaches to solve JSSP instances, we propose a new approach that uses gate-model quantum architecture as an alternative to QA. We find that we can make use of the time-indexed JSSP instance representation to build a cost Hamiltonian, which can be embedded into Quantum Approximate Optimization Algorithm (QAOA) to find an optimal solution to a basic JSSP instance. We demonstrate the use of QAOA to solve the JSSP, and we evaluate its efficiency and accuracy for this problem from experimental results, as there is an increased urgency to demonstrate the applicability of quantum optimization algorithms. We also find that optimal variational parameters form patterns that can facilitate computation in bigger quantum circuits. Additionally, we compare the obtained noiseless simulation results of gate-model quantum circuits demonstrating the relationship between two evaluation criteria - makespan and energy. Finally, we analyze and present the overall performance of our approach with the increasing deadline and simulated depth of QAOA circuits.

Data udostępnienia online

12.03.2023

Strony (od-do)

518 - 528

DOI

10.1016/j.ejor.2023.03.013

URL

https://www.sciencedirect.com/science/article/pii/S0377221723002072

Typ licencji

CC BY (uznanie autorstwa)

Tryb otwartego dostępu

czasopismo hybrydowe

Wersja tekstu w otwartym dostępie

ostateczna wersja opublikowana

Czas udostępnienia publikacji w sposób otwarty

przed opublikowaniem

Punktacja Ministerstwa / czasopismo

140

Impact Factor

6

Ta strona używa plików Cookies, w celu zapamiętania uwierzytelnionej sesji użytkownika. Aby dowiedzieć się więcej przeczytaj o plikach Cookies i Polityce Prywatności.