A Quantum Annealing Solution to the Job Shop Scheduling Problem

被引：0
作者：
Aggoune, Riad [1 ]
Deleplanque, Samuel [2 ]
机构：
[1] Luxembourg Inst Sci & Technol, ITIS Dept, 5 Av Hauts Fourneaux, L-4362 Esch Sur Alzette, Luxembourg
[2] Univ Valenciennes, Univ Lille, UMR 8520 IEMN, CNRS,Cent Lille,JUNIA, 41 Blvd Vauban, F-59046 Lille, France
来源：
COMPUTATIONAL SCIENCE AND ITS APPLICATIONS-ICCSA 2023 WORKSHOPS, PT I | 2023年 / 14104卷
关键词：
quantum computing; optimisation; QUBO; job shop scheduling;
D O I：
10.1007/978-3-031-37105-9_28
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
We consider in this paper the job shop scheduling problem. We first present a mathematical formulation of the problem, namely a disjunctive model. Then, we show how the model can be reformulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, that can be solved by an analog quantum computer.
引用
收藏
页码：421 / 428
页数：8
相关论文
共 16 条
[1]  
Aggoune R., 2023, 21 EU ME M EM OPT ME
[2]   A case study of variational quantum algorithms for a job shop scheduling problem [J].
Amaro, David ;
Rosenkranz, Matthias ;
Fitzpatrick, Nathan ;
Hirano, Koji ;
Fiorentini, Mattia .
EPJ QUANTUM TECHNOLOGY, 2022, 9 (01)
[3]   Evaluating the job shop scheduling problem on a D-wave quantum annealer [J].
Carugno, Costantino ;
Dacrema, Maurizio Ferrari ;
Cremonesi, Paolo .
SCIENTIFIC REPORTS, 2022, 12 (01)
[4]   Industrial-size job shop scheduling with constraint programming [J].
Da Col, Giacomo ;
Teppan, Erich C. .
OPERATIONS RESEARCH PERSPECTIVES, 2022, 9
[5]   Quantum algorithms for process parallel flexible job shop scheduling [J].
Denkena, Berend ;
Schinkel, Fritz ;
Pirnay, Jonathan ;
Wilmsmeier, Soren .
CIRP JOURNAL OF MANUFACTURING SCIENCE AND TECHNOLOGY, 2021, 33 :100-114
[6]  
Farhi E, 2014, Arxiv, DOI [arXiv:1411.4028, 10.48550/arXiv.1411.4028]
[7]  
Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness
[8]  
Grover L. K., 1996, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, P212, DOI 10.1145/237814.237866
[9]   Quantum annealing in the transverse Ising model [J].
Kadowaki, T ;
Nishimori, H .
PHYSICAL REVIEW E, 1998, 58 (05) :5355-5363
[10]   Hybrid Quantum Annealing Heuristic Method for Solving Job Shop Scheduling Problem [J].
Kurowski, Krzysztof ;
Weglarz, Jan ;
Subocz, Marek ;
Rozycki, Rafal ;
Waligora, Grzegorz .
COMPUTATIONAL SCIENCE - ICCS 2020, PT VI, 2020, 12142 :502-515
12