A quantum genetic algorithm for a parallel machine scheduling problem

Tilmann Schwenzow (), Annika Lehnert, Christoph Liebrecht, Jörg Franke and Sebastian Reitelshöfer
Additional contact information
Tilmann Schwenzow: Siemens AG
Annika Lehnert: Karlsruher Institut für Technologie (KIT)
Christoph Liebrecht: Siemens AG
Jörg Franke: Friedrich-Alexander-Universitaet Erlangen-Nuernberg (FAU)
Sebastian Reitelshöfer: Friedrich-Alexander-Universitaet Erlangen-Nuernberg (FAU)

Journal of Combinatorial Optimization, 2025, vol. 50, issue 4, No 2, 22 pages

Abstract: Abstract Scheduling problems are a common challenge across various industries. This paper addresses a specific problem arising in printed circuit board (PCB) assembly: the parallel machines scheduling problem with sequence-dependent setup times. To address this challenge, we propose a hybrid quantum genetic algorithm (QGA) designed to solve this problem on an error-free quantum computer. The development focuses on three key aspects: efficient adaptability of the quantum circuit to different problem instances, feasibility of the measured circuit outputs, and efficient utilization of qubits. To compare the quantum algorithm with its purely classical counterpart, we introduce a novel key performance indicator to quantify a potential quantum speedup. Furthermore, we evaluate the convergence behavior of the solver across various problem instances. Our results demonstrate that the QGA exhibits strong convergence behavior, resulting in near-optimal solutions. Additionally, we identify a potential quantum advantage for solving this practical problem. The advantage increases as the population size grows.

Keywords: Parallel machines scheduling; Quantum genetic algorithm; Grover’s algorithm; Hybrid quantum algorithm (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01347-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:50:y:2025:i:4:d:10.1007_s10878-025-01347-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01347-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().