aqora

Hybrid Quantum Annealing Heuristic Method for Solving Job Shop Scheduling Problem

Krzysztof Kurowski, Jan Węglarz, Marek Subocz +2 more

Lecture notes in computer scienceJan 1, 202037 citations

Adaptive Hybrid Quantum Annealing with Dynamic Scheduling and Chain Repair for Combinatorial Optimization Problems

Asmaa Hussein Alwan, Nuha Sami Mohsin, Abdullah Hasan Ali

Ingénierie des systèmes d informationJul 31, 20260 citations

Optimizing quantum annealing schedules with Monte Carlo tree search enhanced with neural networks

Yuqin Chen, Yu Chen, Chee‐Kong Lee +2 more

arXiv:2004.02836Nature Machine IntelligenceMar 14, 202238 citations

Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware

Jiachen Zhang, Giovanni Lo Bianco, J. Christopher Beck

The emergence of specialized hardware, such as quantum computers and Digital/CMOS annealers, and the slowing of performance growth of general-purpose hardware raises an important question for our community: how can the high-performance, specialized solvers be used for planning and scheduling problems? In this work, we focus on the job-shop scheduling problem (JSP) and Quadratic Unconstrained Binary Optimization (QUBO) models, the mathematical formulation shared by a number of novel hardware platforms. We study two direct QUBO models of JSP and propose a novel large neighborhood search (LNS) approach, that hybridizes a QUBO model with constraint programming (CP). Empirical results show that our LNS approach significantly outperforms classical CP-based LNS methods and a mixed integer programming model, while being competitive with CP for large problem instances. This work is the first approach that we are aware of that can solve non-trivial JSPs using QUBO hardware, albeit as part of a hybrid algorithm.The emergence of specialized hardware, such as quantum computers and Digital/CMOS annealers, and the slowing of performance growth of general-purpose hardware raises an important question for our community: how can the high-performance, specialized solvers be used for planning and scheduling problems? In this work, we focus on the job-shop scheduling problem (JSP) and Quadratic Unconstrained Binary Optimization (QUBO) models, the mathematical formulation shared by a number of novel hardware platforms. We study two direct QUBO models of JSP and propose a novel large neighborhood search (LNS) approach, that hybridizes a QUBO model with constraint programming (CP). Empirical results show that our LNS approach significantly outperforms classical CP-based LNS methods and a mixed integer programming model, while being competitive with CP for large problem instances. This work is the first approach that we are aware of that can solve non-trivial JSPs using QUBO hardware, albeit as part of a hybrid algorithm.

Proceedings of the International Conference on Automated Planning and SchedulingJun 13, 202214 citations

Quantum Annealing to Solve the Unrelated Parallel Machine Scheduling Problem

Francisco José Orts, Antonio Manuel Puertas, Ester Martín Garzón +1 more

Lecture notes in computer scienceJan 1, 20233 citations

A Hybrid Quantum-Classical Approach to Solving Scheduling Problems

Tony T. Tran, Minh Do, Eleanor Gilbert Rieffel +5 more

An effective approach to solving complex problems is to decompose them and integrate dedicated solvers for those subproblems. We introduce a hybrid decomposition that incorporates: (1) a quantum annealer that samples from the configuration space of a relaxed problem to obtain strong candidate solutions, and (2) a classical processor that maintains a global search tree and enforces constraints on the relaxed components of the problem. Our framework is the first to use quantum annealing as part of a complete search. We consider variants of our approach with differing amounts of guidance from the quantum annealer. We empirically test our algorithm and compare the variants on problems from three scheduling domains: graph-coloring-type scheduling, simplified Mars Lander task scheduling, and airport runway scheduling. While we were only able to test on problems of small sizes, due to the limitation of currently available quantum annealing hardware, the empirical results show that results obtained from the quantum annealer can be used for more effective search node pruning and to improve node selection heuristics when compared to a standard classical approach.An effective approach to solving complex problems is to decompose them and integrate dedicated solvers for those subproblems. We introduce a hybrid decomposition that incorporates: (1) a quantum annealer that samples from the configuration space of a relaxed problem to obtain strong candidate solutions, and (2) a classical processor that maintains a global search tree and enforces constraints on the relaxed components of the problem. Our framework is the first to use quantum annealing as part of a complete search. We consider variants of our approach with differing amounts of guidance from the quantum annealer. We empirically test our algorithm and compare the variants on problems from three scheduling domains: graph-coloring-type scheduling, simplified Mars Lander task scheduling, and airport runway scheduling. While we were only able to test on problems of small sizes, due to the limitation of currently available quantum annealing hardware, the empirical results show that results obtained from the quantum annealer can be used for more effective search node pruning and to improve node selection heuristics when compared to a standard classical approach.

Proceedings of the International Symposium on Combinatorial SearchSep 1, 202173 citations

Hybrid Quantum Annealing Approach for Huge Neighborhoods Searching in Application to Task Scheduling

Related papers

Hybrid Quantum Annealing Approach for Huge Neighborhoods Searching in Application to Task Scheduling

Related papers