A quantum genetic algorithm for a parallel machine scheduling problem

Schwenzow T, Lehnert A, Liebrecht C, Franke J, Reitelshöfer S (2025)

Publication Type: Journal article

Publication year: 2025

Journal

Journal of Combinatorial Optimization Springer Verlag (Germany)

Book Volume: 50

Article Number: 33

Journal Issue: 4

DOI: 10.1007/s10878-025-01347-7

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.

Authors with CRIS profile

Jörg Franke Lehrstuhl für Fertigungsautomatisierung und Produktionssystematik (FAPS) Sebastian Reitelshöfer Lehrstuhl für Fertigungsautomatisierung und Produktionssystematik (FAPS)

Involved external institutions

Karlsruhe Institute of Technology (KIT) DE Germany (DE)

How to cite

APA:

Schwenzow, T., Lehnert, A., Liebrecht, C., Franke, J., & Reitelshöfer, S. (2025). A quantum genetic algorithm for a parallel machine scheduling problem. Journal of Combinatorial Optimization, 50(4). https://doi.org/10.1007/s10878-025-01347-7

MLA:

Schwenzow, Tilmann, et al. "A quantum genetic algorithm for a parallel machine scheduling problem." Journal of Combinatorial Optimization 50.4 (2025).

BibTeX: Download