{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T03:34:40Z","timestamp":1777952080816,"version":"3.51.4"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T00:00:00Z","timestamp":1777852800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T00:00:00Z","timestamp":1777852800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1007\/s10732-026-09594-5","type":"journal-article","created":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T11:38:40Z","timestamp":1777894720000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Quantum annealing heuristics for the job shop scheduling problem with availability constraints"],"prefix":"10.1007","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4119-6006","authenticated-orcid":false,"given":"Samuel","family":"Deleplanque","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3680-2377","authenticated-orcid":false,"given":"Luis Fernando","family":"P\u00e9rez Armas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2622-7097","authenticated-orcid":false,"given":"Riad","family":"Aggoune","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,5,4]]},"reference":[{"issue":"3","key":"9594_CR1","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1287\/mnsc.34.3.391","volume":"34","author":"J Adams","year":"1988","unstructured":"Adams, J., Balas, E., Zawack, D.: The shifting bottleneck procedure for job shop scheduling. Manage. Sci. 34(3), 391\u2013401 (1988)","journal-title":"Manage. Sci."},{"issue":"3","key":"9594_CR2","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1016\/S0377-2217(03)00261-3","volume":"153","author":"R Aggoune","year":"2004","unstructured":"Aggoune, R.: Minimizing the makespan for the flow shop scheduling problem with availability constraints. Eur. J. Oper. Res. 153(3), 534\u2013543 (2004)","journal-title":"Eur. J. Oper. Res."},{"key":"9594_CR3","doi-asserted-by":"publisher","unstructured":"Aggoune, R. and Deleplanque, S. A Quantum Annealing Solution to the Job Shop Scheduling Problem. International Conference on Computational Science and Its Applications, LNCS, vol. 14104, Springer, 2023. https:\/\/doi.org\/10.1007\/978-3-031-37105-9_28","DOI":"10.1007\/978-3-031-37105-9_28"},{"key":"9594_CR4","doi-asserted-by":"publisher","unstructured":"Aggoune, R. and Deleplanque, S. Addressing Machine Unavailability in Job Shop Scheduling: A Quantum Computing Approach. Metaheuristics, Lecture Notes in Computer Science, Springer Nature, Switzerland, 2024.https:\/\/doi.org\/10.1007\/978-3-031-62912-9_23.","DOI":"10.1007\/978-3-031-62912-9_23."},{"issue":"1\u20132","key":"9594_CR5","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1016\/j.ijpe.2004.12.002","volume":"99","author":"R Aggoune","year":"2006","unstructured":"Aggoune, R., Portmann, M.-C.: Flow shop scheduling problem with limited machine availability: A heuristic approach. Int. J. Prod. Econ. 99(1\u20132), 4\u201315 (2006)","journal-title":"Int. J. Prod. Econ."},{"key":"9594_CR6","doi-asserted-by":"crossref","unstructured":"Amaro, D. and Rosenkranz, M. and Fitzpatrick, N. and Hirano, K. and M. Fiorentini. A case study of variational quantum algorithms for a job shop scheduling problem. EPJ Quantum Technol, 9 : 100\u2013114, 2022","DOI":"10.1140\/epjqt\/s40507-022-00123-4"},{"issue":"2","key":"9594_CR7","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1287\/ijoc.3.2.149","volume":"3","author":"D Applegate","year":"1991","unstructured":"Applegate, D., Cook, W.: A computational study of the job-shop scheduling problem. ORSA J. Comput. 3(2), 149\u2013156 (1991)","journal-title":"ORSA J. Comput."},{"key":"9594_CR8","doi-asserted-by":"publisher","first-page":"48","DOI":"10.3389\/fphy.2019.00048","volume":"7","author":"M Aramon","year":"2019","unstructured":"Aramon, M., Rosenberg, G., Valiante, E., Miyazawa, T., Tamura, H., Katzgraber, H.G.: Physics-inspired optimization for quadratic unconstrained problems using a digital annealer. Frontiers in Physics 7, 48 (2019)","journal-title":"Frontiers in Physics"},{"key":"9594_CR9","doi-asserted-by":"crossref","unstructured":"Blazewicz and J. Breit and P. Formanowicz and W. Kubiak and G. Schmidt. Heuristic algorithms for the two-machine flowshop problem with limited machine availability. Omega Journal, 29 : 599\u2013608, 2001","DOI":"10.1016\/S0305-0483(01)00048-2"},{"key":"9594_CR10","doi-asserted-by":"publisher","first-page":"6539","DOI":"10.1038\/s41598-022-10169-0","volume":"12","author":"C Carugno","year":"2022","unstructured":"Carugno, C., Ferrari Dacrema, M., Cremonesi, P.: Evaluating the job shop scheduling problem on a D-wave quantum annealer. Sci. Rep. 12, 6539 (2022). https:\/\/doi.org\/10.1038\/s41598-022-10169-0","journal-title":"Sci. Rep."},{"key":"9594_CR11","doi-asserted-by":"publisher","unstructured":"Creemers, S. and P\u00e9rez Armas, L. F. Discrete optimization: A quantum revolution? European Journal of Operational Research, 2024, In Press. https:\/\/doi.org\/10.1016\/j.ejor.2024.12.016","DOI":"10.1016\/j.ejor.2024.12.016"},{"key":"9594_CR12","doi-asserted-by":"crossref","unstructured":"Da Col, G. and E. C. Teppan. Industrial-size job shop scheduling with constraint programming. Operations Research Perspectives, 9, 2022","DOI":"10.1016\/j.orp.2022.100249"},{"key":"9594_CR13","doi-asserted-by":"crossref","unstructured":"Deleplanque, S. and P\u00e9rez Armas, L. F. and Creemers, S. solQHealer: Quantum Procedures for Rendering Infeasible Solutions Feasible: A Proof of Concept with the Maximum Independent Set Problem and 3-SAT. Journal of Heuristics, 31(3):30, 2025","DOI":"10.1007\/s10732-025-09564-3"},{"key":"9594_CR14","doi-asserted-by":"crossref","unstructured":"Denkena B. and Schinkel F. and Pirnay J. and S. Wilmsmeier. Quantum algorithms for process parallel flexible job shop scheduling. CIRP Journal of Manufacturing Science and Technology, 12142 , 2020","DOI":"10.1016\/j.cirpj.2021.03.006"},{"key":"9594_CR15","unstructured":"Farhi, E. and Goldstone, J. and Gutmann, S. A Quantum Approximate Optimization Algorithm. 10.48550\/arxiv.1411.4028, 2014"},{"issue":"3","key":"9594_CR16","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1287\/mnsc.13.3.167","volume":"13","author":"WS Gere Jr","year":"1966","unstructured":"Gere, W.S., Jr.: Heuristics in job shop scheduling. Manage. Sci. 13(3), 167\u2013190 (1966)","journal-title":"Manage. Sci."},{"key":"9594_CR17","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., USA (1979)"},{"key":"9594_CR18","doi-asserted-by":"crossref","unstructured":"Grover, L. K. A Fast Quantum Mechanical Algorithm for Database Search. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, 212\u2013219, 1996","DOI":"10.1145\/237814.237866"},{"issue":"5","key":"9594_CR19","doi-asserted-by":"publisher","first-page":"5355","DOI":"10.1103\/PhysRevE.58.5355","volume":"58","author":"T Kadowaki","year":"1998","unstructured":"Kadowaki, T., Nishimori, H.: Quantum annealing in the transverse ising model. Phys. Rev. E 58(5), 5355 (1998)","journal-title":"Phys. Rev. E"},{"key":"9594_CR20","doi-asserted-by":"publisher","first-page":"4598","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, S., Gelatt, C.D., Jr., Vecchi, M.: P. Optimization by simulated annealing. Science 220, 4598 (1983)","journal-title":"Science"},{"key":"9594_CR21","doi-asserted-by":"publisher","first-page":"518","DOI":"10.1016\/j.ejor.2023.03.013","volume":"310","author":"K Kurowski","year":"2023","unstructured":"Kurowski, K., Pecyna, T., Slysz, R., R\u00f3\u017ccki, R., Walig\u00f3ra, G., W\u0229glarz, J.: Application of quantum approximate optimization algorithm to job shop scheduling problem. Eur. J. Oper. Res. 310, 518\u2013528 (2023). https:\/\/doi.org\/10.1016\/j.ejor.2023.03.013","journal-title":"Eur. J. Oper. Res."},{"key":"9594_CR22","doi-asserted-by":"crossref","unstructured":"Kurowski, K., W\u0229glarz, J., Subocz, M., R\u00f3\u017ccki, R. and Walig\u00f3ra, G. Hybrid Quantum Annealing Heuristic Method for Solving Job Shop Scheduling Problem. ICCS,: Lecture Notes in Computer Science. Springer 33(100\u2013114), 2021 (2020)","DOI":"10.1007\/978-3-030-50433-5_39"},{"key":"9594_CR23","volume-title":"Resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques (Supplement)","author":"S Lawrence","year":"1984","unstructured":"Lawrence, S.: Resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques (Supplement). Carnegie-Mellon University, Graduate School of Industrial Administration (1984)"},{"issue":"2","key":"9594_CR24","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1287\/opre.8.2.219","volume":"8","author":"AS Manne","year":"1960","unstructured":"Manne, A.S.: On the Job-Shop Scheduling Problem. Oper. Res. 8(2), 219\u2013223 (1960). https:\/\/doi.org\/10.1287\/opre.8.2.219","journal-title":"Oper. Res."},{"key":"9594_CR25","volume-title":"Probabilistic learning combinations of local job-shop scheduling rules","author":"J Muth","year":"1963","unstructured":"Muth, J.: Probabilistic learning combinations of local job-shop scheduling rules. Prentice Hall, Industrial Scheduling (1963)"},{"key":"9594_CR26","doi-asserted-by":"publisher","unstructured":"Or\u00fas, R. and Mugel, S. and Lizaso, E. Quantum computing for finance: Overview and prospects. Reviews in Physics, 4, 2019. https:\/\/doi.org\/10.1016\/j.revip.2019.100028","DOI":"10.1016\/j.revip.2019.100028"},{"key":"9594_CR27","doi-asserted-by":"crossref","unstructured":"P\u00e9rez Armas, L. F. and Creemers, S. and Deleplanque, S. Solving the resource constrained project scheduling problem with quantum annealing. Scientific Reports, 14(1):16784, 2024","DOI":"10.1038\/s41598-024-67168-6"},{"key":"9594_CR28","doi-asserted-by":"crossref","unstructured":"Perez Armas, L. F. and Deleplanque, S. and Aggoune, R. and Creemers, S. A hybrid column generation-based heuristic for solving the parallel machine scheduling problem with sequence-dependent set-up times. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 383(2310), 2025","DOI":"10.1098\/rsta.2024.0380"},{"key":"9594_CR29","doi-asserted-by":"crossref","unstructured":"Rao, P.U., Sodhi, B., Scheduling with Multiple Dispatch Rules: A Quantum Computing Approach. ICCS,: Lecture Notes in Computer Science. Springer 13353(233\u2013246), 2022 (2022)","DOI":"10.1007\/978-3-031-08760-8_20"},{"issue":"1","key":"9594_CR30","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1287\/ijoc.2021.1065","volume":"34","author":"T Serra","year":"2022","unstructured":"Serra, T., Huang, T., Raghunathan, A.U., Bergman, D.: Template-based minor embedding for adiabatic quantum optimization. INFORMS J. Comput. 34(1), 427\u2013439 (2022)","journal-title":"INFORMS J. Comput."},{"key":"9594_CR31","doi-asserted-by":"publisher","unstructured":"Schworm, P., Wu, X., Glatt, M. and J. C. Aurich. Solving flexible job shop scheduling problems in manufacturing with Quantum Annealing. Prod. Eng. Res. Devel., 17: 105-115, 2023. https:\/\/doi.org\/10.1007\/s11740-022-01145-8","DOI":"10.1007\/s11740-022-01145-8"},{"key":"9594_CR32","doi-asserted-by":"crossref","unstructured":"Shimada, D. and T. Shibuya and T. Shibasaki. A Decomposition Method for Makespan Minimization in Job-Shop Scheduling Problem Using Ising Machine. 2021 IEEE 8th International Conference on Industrial Engineering and Applications, 307\u2013314, 2021","DOI":"10.1109\/ICIEA52957.2021.9436798"},{"key":"9594_CR33","doi-asserted-by":"crossref","unstructured":"Tasseff, B., Albash, T., Morrell, Z., Vuffray, M., Lokhov, A. Y., Misra, S., and Coffrin, C. On the emerging potential of quantum annealing hardware for combinatorial optimization. Journal of Heuristics, 30(5) 325\u2013358, 2024. Springer","DOI":"10.1007\/s10732-024-09530-5"},{"key":"9594_CR34","unstructured":"Venturelli, D. and Marchand, D. J. and Rojo, G. Quantum annealing implementation of job-shop scheduling. arXiv preprint:1506.08479, 2015"},{"key":"9594_CR35","unstructured":"Weise, T. jsspInstancesAndResults: Results, Data, and Instances of the Job Shop Scheduling Problem. Institute of Applied Optimization, Hefei University, Hefei, Anhui, China, 2019\u20132020. https:\/\/github.com\/thomasWeise\/jsspInstancesAndResults"},{"issue":"1","key":"9594_CR36","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1609\/icaps.v32i1.19826","volume":"32","author":"J Zhang","year":"2022","unstructured":"Zhang, J., Lo Bianco, G., Beck, J.C.: Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware. Proceedings of the International Conference on Automated Planning and Scheduling 32(1), 404\u2013412 (2022)","journal-title":"Proceedings of the International Conference on Automated Planning and Scheduling"}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-026-09594-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10732-026-09594-5","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-026-09594-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T11:38:47Z","timestamp":1777894727000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10732-026-09594-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,4]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["9594"],"URL":"https:\/\/doi.org\/10.1007\/s10732-026-09594-5","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,4]]},"assertion":[{"value":"17 February 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 April 2026","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 April 2026","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 May 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}},{"value":"The authors declare that this research was conducted in compliance with ethical standards. This study does not involve human participants or animals, and no ethical approval was required.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval"}}],"article-number":"19"}}