{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T21:08:45Z","timestamp":1777064925661,"version":"3.51.4"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,10,18]],"date-time":"2025-10-18T00:00:00Z","timestamp":1760745600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,10,18]],"date-time":"2025-10-18T00:00:00Z","timestamp":1760745600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001652","name":"Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001652","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2025,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>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.<\/jats:p>","DOI":"10.1007\/s10878-025-01347-7","type":"journal-article","created":{"date-parts":[[2025,10,18]],"date-time":"2025-10-18T21:57:35Z","timestamp":1760824655000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A quantum genetic algorithm for a parallel machine scheduling problem"],"prefix":"10.1007","volume":"50","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-4913-9834","authenticated-orcid":false,"given":"Tilmann","family":"Schwenzow","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Annika","family":"Lehnert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"Liebrecht","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00f6rg","family":"Franke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Reitelsh\u00f6fer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,10,18]]},"reference":[{"key":"1347_CR1","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1016\/j.ins.2021.06.049","volume":"575","author":"G Acampora","year":"2021","unstructured":"Acampora G, Vitiello A (2021) Implementing evolutionary optimization on actual quantum processors. Inf Sci 575:542\u2013562. https:\/\/doi.org\/10.1016\/j.ins.2021.06.049 (https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S002002552100640X)","journal-title":"Inf Sci"},{"key":"1347_CR2","doi-asserted-by":"publisher","unstructured":"Ambainis A (2017) Understanding quantum algorithms via query complexity. https:\/\/doi.org\/10.48550\/arXiv.1712.06349","DOI":"10.48550\/arXiv.1712.06349"},{"key":"1347_CR3","doi-asserted-by":"publisher","DOI":"10.7717\/peerj-cs.2210","volume":"10","author":"SM Ardelean","year":"2024","unstructured":"Ardelean SM, Udrescu M (2024) Hybrid quantum search with genetic algorithm optimization. PeerJ Computer Sci 10:e2210. https:\/\/doi.org\/10.7717\/peerj-cs.2210 (https:\/\/peerj.com\/articles\/cs-2210D)","journal-title":"PeerJ Computer Sci"},{"issue":"4","key":"1347_CR4","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P","volume":"46","author":"M Boyer","year":"1998","unstructured":"Boyer M, Brassard G, Hoeyer P, Tapp A (1998) Tight bounds on quantum searching. Fortschr Phys 46(4):493\u2013505. https:\/\/doi.org\/10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P. arXiv:quant-ph\/9605034","journal-title":"Fortschr Phys"},{"key":"1347_CR5","doi-asserted-by":"publisher","unstructured":"Draper TG (2000) Addition on a quantum computer https:\/\/doi.org\/10.48550\/ARXIV.QUANT-PH\/0008033","DOI":"10.48550\/ARXIV.QUANT-PH\/0008033"},{"key":"1347_CR6","unstructured":"Durr C, Hoyer P (1999) A quantum algorithm for finding the minimum. arXiv:quant-ph\/9607014"},{"key":"1347_CR7","doi-asserted-by":"publisher","unstructured":"Grover LK (1996) A fast quantum mechanical algorithm for database search https:\/\/doi.org\/10.48550\/ARXIV.QUANT-PH\/9605043. publisher: arXiv Version Number: 3","DOI":"10.48550\/ARXIV.QUANT-PH\/9605043"},{"key":"1347_CR8","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/j.cie.2017.02.013","volume":"106","author":"A Hamzadayi","year":"2017","unstructured":"Hamzadayi A, Yildiz G (2017) Modeling and solving static m identical parallel machines scheduling problem with a common server and sequence dependent setup times. Comput Ind Eng 106:287\u2013298. https:\/\/doi.org\/10.1016\/j.cie.2017.02.013","journal-title":"Comput Ind Eng"},{"key":"1347_CR9","unstructured":"IBM (2024) IntegerComparator (latest version) | IBM Quantum Documentation. https:\/\/docs.quantum.ibm.com\/api\/qiskit\/qiskit.circuit.library.IntegerComparator"},{"key":"1347_CR10","doi-asserted-by":"crossref","unstructured":"Karger D, Stein C, Wein J (2010) Scheduling algorithms p\u00a020","DOI":"10.1201\/9781584888215-c20"},{"issue":"5","key":"1347_CR11","doi-asserted-by":"publisher","first-page":"8091","DOI":"10.1007\/s11042-020-10139-6","volume":"80","author":"S Katoch","year":"2021","unstructured":"Katoch S, Chauhan SS, Kumar V (2021) A review on genetic algorithm: past, present, and future. Multimed Tools Appl 80(5):8091\u20138126. https:\/\/doi.org\/10.1007\/s11042-020-10139-6 (http:\/\/link.springer.com\/10.1007\/s11042-020-10139-6)","journal-title":"Multimed Tools Appl"},{"key":"1347_CR12","doi-asserted-by":"publisher","unstructured":"Korte B, Vygen J (2018) Combinatorial optimization: theory and algorithms, algorithms and combinatorics, vol 21. Springer, Berlin. https:\/\/doi.org\/10.1007\/978-3-662-56039-6","DOI":"10.1007\/978-3-662-56039-6"},{"issue":"12","key":"1347_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0895-7177(97)00236-7","volume":"26","author":"S Kravchenko","year":"1997","unstructured":"Kravchenko S, Werner F (1997) Parallel machine scheduling problems with a single server. Math Comput Model 26(12):1\u201311. https:\/\/doi.org\/10.1016\/S0895-7177(97)00236-7","journal-title":"Math Comput Model"},{"issue":"4","key":"1347_CR14","doi-asserted-by":"publisher","first-page":"24","DOI":"10.3390\/computers5040024","volume":"5","author":"R Lahoz-Beltra","year":"2016","unstructured":"Lahoz-Beltra R (2016) Quantum genetic algorithms for computer scientists. Computers 5(4):24. https:\/\/doi.org\/10.3390\/computers5040024 (https:\/\/www.mdpi.com\/2073-431X\/5\/4\/24)","journal-title":"Computers"},{"key":"1347_CR15","doi-asserted-by":"publisher","unstructured":"Lawler EL, Lenstra JK, Rinnooy\u00a0Kan AH, Shmoys DB (1993) Chapter 9 sequencing and scheduling: Algorithms and complexity. In: Handbooks in Operations Research and Management Science, vol\u00a04, Elsevier, pp 445\u2013522, https:\/\/doi.org\/10.1016\/S0927-0507(05)80189-6","DOI":"10.1016\/S0927-0507(05)80189-6"},{"key":"1347_CR16","doi-asserted-by":"publisher","unstructured":"Almufti MS, Ahmad Shaban A, Arif Ali Z, Ismael Ali RA, Dela Fuente J (2023) Overview of metaheuristic algorithms. Polaris Global J Schol Res Trends 2(2), 10\u20133. https:\/\/doi.org\/10.58429\/pgjsrt.v2n2a144","DOI":"10.58429\/pgjsrt.v2n2a144"},{"issue":"2","key":"1347_CR17","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1109\/TEVC.2007.905006","volume":"12","author":"A Malossini","year":"2008","unstructured":"Malossini A, Blanzieri E, Calarco T (2008) Quantum genetic optimization. IEEE Trans Evol Comput 12(2):231\u2013241. https:\/\/doi.org\/10.1109\/TEVC.2007.905006 (http:\/\/ieeexplore.ieee.org\/document\/4358783\/)","journal-title":"IEEE Trans Evol Comput"},{"key":"1347_CR18","volume-title":"Quantum computation and quantum information","author":"MA Nielsen","year":"2010","unstructured":"Nielsen MA, Chuang IL (2010) Quantum computation and quantum information, 10th edn. Cambridge University Press, Cambridge","edition":"10"},{"key":"1347_CR19","doi-asserted-by":"publisher","unstructured":"Phillipson F (2024) Quantum computing in logistics and supply chain management an overview. https:\/\/doi.org\/10.48550\/arXiv.2402.17520, arXiv:2402.17520 [quant-ph]","DOI":"10.48550\/arXiv.2402.17520"},{"issue":"3","key":"1347_CR20","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1007\/s11128-013-0686-6","volume":"13","author":"A SaiToh","year":"2014","unstructured":"SaiToh A, Rahimi R, Nakahara M (2014) A quantum genetic algorithm with quantum crossover and mutation operations. Quantum Inf Process 13(3):737\u2013755. https:\/\/doi.org\/10.1007\/s11128-013-0686-6 (http:\/\/link.springer.com\/10.1007\/s11128-013-0686-6)","journal-title":"Quantum Inf Process"},{"issue":"5","key":"1347_CR21","first-page":"1484","volume":"26","author":"PW Shor","year":"1997","unstructured":"Shor PW (1997) Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev 26(5):1484\u20131509","journal-title":"SIAM Rev"},{"key":"1347_CR22","doi-asserted-by":"publisher","unstructured":"Thakoor N, Devarajan V, Gao J (2009) Computation complexity of branch-and-bound model selection. In: 2009 IEEE 12th international conference on computer vision, IEEE, Kyoto, pp 1895\u20131900, https:\/\/doi.org\/10.1109\/ICCV.2009.5459420","DOI":"10.1109\/ICCV.2009.5459420"},{"key":"1347_CR23","doi-asserted-by":"publisher","unstructured":"Theradapuzha Mathew N, Johansson B (2023) Production planning and scheduling challenges in the engineer-to-order manufacturing segment-a literature study. Int J Innov Manage Technol 14:80\u201387. https:\/\/doi.org\/10.18178\/ijimt.2023.14.3.942","DOI":"10.18178\/ijimt.2023.14.3.942"},{"key":"1347_CR24","unstructured":"Thula (2023) Efficient quantum comparator circuit. https:\/\/egrettathula.wordpress.com\/2023\/04\/18\/efficient-quantum-comparator-circuit\/"},{"key":"1347_CR25","doi-asserted-by":"publisher","unstructured":"Udrescu M, Prodan L, Vladutiu M (2006) Implementing quantum genetic algorithms: a solution based on Grover\u2019s algorithm. In: Proceedings of the 3rd conference on computing frontiers, ACM, Ischia Italy, pp 71\u201382, https:\/\/doi.org\/10.1145\/1128022.1128034, https:\/\/dl.acm.org\/doi\/10.1145\/1128022.1128034","DOI":"10.1145\/1128022.1128034"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01347-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-025-01347-7","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01347-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T15:03:15Z","timestamp":1767193395000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-025-01347-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,18]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["1347"],"URL":"https:\/\/doi.org\/10.1007\/s10878-025-01347-7","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,18]]},"assertion":[{"value":"5 August 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 October 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"33"}}