Depending on the amount of data to process, file generation may take longer.

If it takes too long to generate, you can limit the data by, for example, reducing the range of years.

Article

Download BibTeX

Title

Application of Quantum Approximate Optimization Algorithm to Job Shop Scheduling Problem

Authors

[ 1 ] Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | [ 2 ] Instytut Informatyki, Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | [ SzD ] doctoral school student | [ P ] employee

Scientific discipline (Law 2.0)

[2.3] Information and communication technology

Year of publication

2023

Published in

European Journal of Operational Research

Journal year: 2023 | Journal volume: vol. 310 | Journal number: no. 2

Article type

scientific article

Publication language

english

Keywords
EN
  • Scheduling
  • Computing science
  • Heuristics
  • Job Shop Scheduling Problem
  • Quantum Approximate Optimization Algorithm
Abstract

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.

Date of online publication

12.03.2023

Pages (from - to)

518 - 528

DOI

10.1016/j.ejor.2023.03.013

URL

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

License type

CC BY (attribution alone)

Open Access Mode

czasopismo hybrydowe

Open Access Text Version

final published version

Date of Open Access to the publication

in press

Ministry points / journal

140

Impact Factor

6

This website uses cookies to remember the authenticated session of the user. For more information, read about Cookies and Privacy Policy.