Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Conference on Quantum Computing and Engineering (QCE)

Iterative Quantum Annealing for Job Shop Scheduling with a Directed Graph Representation

Rebecca Casati, Thomas Giudici, Pietro Torta, Enrico Prati

Published Aug 30, 2025• 1 citation
Publisher

Abstract

A promising use of quantum computers lies in the logistics and scheduling of industrial problems, such as space mission planning, maritime management, and many others. This field is expected to provide useful applications for quantum computing at the current stage of hardware development. Quantum annealing techniques have been proposed to solve scheduling problems, along with many other optimization problems. In this work, we test quantum annealing and hybrid techniques based on the D-Wave hardware to solve scheduling problems in the framework of job shop scheduling (JSP), which consists of optimally assigning operations to certain resources, while satisfying specific constraints and minimizing the total scheduling time, known as timespan. We devised an iterative algorithm that produces valid schedules for decreasing timespan values. We implemented a refined iterative variable pruning technique, which significantly reduces the number of spin variables in the corresponding Ising model, whose low-energy configurations are sampled by using the D-Wave Hybrid Solver Service. Our novel iterative algorithm leverages a directed acyclic graph (DAG) representation of partial or complete solutions of the JSP instance, which enables an efficient update of the feasible processing time windows for each operation. This approach leads to significantly improved results compared to the standard state-of-the-art applications of quantum annealing for the JSP. Remarkably, we can often prove the absolute optimality of the obtained solution, namely that a more efficient schedule within a shorter timespan can not exist.

DOI
10.1109/qce65121.2025.00236

Related papers

Quantum Annealing Implementation of Job-Shop Scheduling

Davide Venturelli, D. J. J. Marchand, Galo Rojo

A quantum annealing solver for the renowned job-shop scheduling problem (JSP) is presented in detail. After formulating the problem as a time-indexed quadratic unconstrained binary optimization problem, several pre-processing and graph embedding strategies are employed to compile optimally parametrized families of the JSP for scheduling instances of up to six jobs and six machines on the D-Wave Systems Vesuvius processor. Problem simplifications and partitioning algorithms, including variable pruning and running strategies that consider tailored binary searches, are discussed and the results from the processor are compared against state-of-the-art global-optimum solvers.

arXiv:1506.08479•Jun 29, 2015•135 citations

Quantum-classical hybrid algorithm using quantum annealing for multi-objective job shop scheduling

Kenta Sawamura, Kensuke Araki, Naoki Maruyama +2 more

Efficient production planning is essential in modern manufacturing to improve performance indicators such as lead time and to reduce reliance on human intuition. While mathematical optimization approaches, formulated as job shop scheduling problems, have been applied to automate this process, solving large-scale production planning problems remains computationally demanding. Moreover, many practical scenarios involve conflicting objectives, making traditional scalarization techniques ineffective in finding diverse and useful Pareto-optimal solutions. To address these challenges, we developed a quantum-classical hybrid algorithm that decomposes the problem into two subproblems: resource allocation and task scheduling. Resource allocation is formulated as a quadratic unconstrained binary optimization problem and solved using annealing-based methods that efficiently explore complex solutions. Task scheduling is modeled as a mixed-integer linear programming problem and solved using conventional solvers to satisfy detailed scheduling constraints. We validated the proposed method using benchmark instances based on foundry production scenarios. Experimental results demonstrate that our hybrid approach achieves superior solution quality and computational efficiency compared to traditional monolithic methods. This work offers a promising direction for high-speed, multi-objective scheduling in industrial applications.

quant-pharXiv:2511.03257•Nov 6, 2025•0 citations

Exploiting adiabatic quantum computing in deep space missions

Rebecca Casati, Enrico Prati

Abstract Several fundamental questions demand space exploration, posing tremendous computational tasks to address modelling and data processing. Quantum computing has been proposed to address deep space-related problems from quantum gravity, nuclear processes and many-body field theory simulation to artificial intelligence and related space mission planning. Adiabatic quantum computers have been proposed for solving optimization problems, such as space mission scheduling. The problem of assigning jobs to resources in a scientific mission, while satisfying certain constraints, can be tackled with the help of D-Wave’s quantum annealer, which exploits the adiabatic theorem to find the minimum energy solutions of a given system, encoded as the Hamiltonian of a quadratic unconstrained binary optimization (QUBO) problem. In its simplest em-bodiement, the scheduling can be implemented as a graph coloring (GC) problem, where the goal is to assign different colors (out of a given set) to connected nodes of an input graph, while respecting given constraints. The feasibility of our methods and the performance of quantum annealers are studied on randomly generated GC instances. A second framework studied is the job shop scheduling problem (JSP) that encodes more real-like scheduling problems of interest to agencies and industries. By implementing the problems with a QUBO formulation, we are able to find the optimal solution to three JSP instances present in the literature. The biggest one is solved with a quantum computation approach here for the first time.

Journal of Physics Conference Series•Jun 1, 2025•0 citations

Evaluating the job shop scheduling problem on a D-wave quantum annealer

Costantino Carugno, Maurizio Ferrari Dacrema, Paolo Cremonesi

Job Shop Scheduling is a combinatorial optimization problem of particular importance for production environments where the goal is to complete a production task in the shortest possible time given limitations in the resources available. Due to its computational complexity it quickly becomes intractable for problems of interesting size. The emerging technology of Quantum Annealing provides an alternative computational architecture that promises improved scalability and solution quality. However, several limitations as well as open research questions exist in this relatively new and rapidly developing technology. This paper studies the application of quantum annealing to solve the job shop scheduling problem, describing each step required from the problem formulation to the fine-tuning of the quantum annealer and compares the solution quality with various classical solvers. Particular attention is devoted to aspects that are often overlooked, such as the computational cost of representing the problem in the formulation required by the quantum annealer, the relative qubits requirements and how to mitigate chain breaks. Furthermore, the impact of advanced tools such as reverse annealing is presented and its effectiveness discussed. The results indicate several challenges emerging at various stages of the experimental pipeline which bring forward important research questions and directions of improvement.

Scientific Reports•Apr 21, 2022•69 citations

Application of quantum approximate optimization algorithm to job shop scheduling problem

Krzysztof Kurowski, Tomasz Pecyna, Mateusz Slysz +3 more

The Job Shop Scheduling Problem (JSSP) has always been considered as one of the most complex and industry essential scheduling problems. Optimizing the makespan of a given schedule generally involves using dedicated algorithms, local search strategies, or metaheuristics. These approaches, however, heavily rely on classical computational power, which is bounded by the physical limits of microcontrollers and power issues. Inspired by the promising results achieved for Quantum Annealing (QA) based approaches to solve JSSP instances, we propose a new approach that uses gate-model quantum architecture as an alternative to QA. We find that we can make use of the time-indexed JSSP instance representation to build a cost Hamiltonian, which can be embedded into Quantum Approximate Optimization Algorithm (QAOA) to find an optimal solution to a basic JSSP instance. We demonstrate the use of QAOA to solve the JSSP, and we evaluate its efficiency and accuracy for this problem from experimental results, as there is an increased urgency to demonstrate the applicability of quantum optimization algorithms. We also find that optimal variational parameters form patterns that can facilitate computation in bigger quantum circuits. Additionally, we compare the obtained noiseless simulation results of gate-model quantum circuits demonstrating the relationship between two evaluation criteria - makespan and energy. Finally, we analyze and present the overall performance of our approach with the increasing deadline and simulated depth of QAOA circuits.

European Journal of Operational Research•Mar 12, 2023•62 citations

An Empirical Study of Quantum Annealing Methods for Robust Time Dependent Job Shop Scheduling Optimization

V.R.R Lakshmi Kumari, Animoni Nagaraju

A Robust Time Dependent Job Shop Scheduling Problem (RTDJSSP) is a complicated optimization problem for simulating real-world process scheduling tasks with competing objectives. To address RTDJSSPs, approximation approaches are used to ensure solutions are completed within acceptable timelines with varying sectional durations. Quantum Annealing, a metaheuristic that uses quantum mechanical effects, produces better solution quality in less time than conventional algorithms. However, due to hardware restrictions in quantum annealers, hybrid methods are required for solving bigger RTDJSSPs. This work explores the threshold issue sizes for which quantum annealers are sufficient and when hybrid algorithms are necessary, focusing on the distribution of computing resources in hybrid approaches.

International Journal of Drug Delivery Technology•Apr 23, 2026•0 citations
A promising use of quantum computers lies in the logistics and scheduling of industrial problems, such as space mission planning, maritime management, and many others. This field is expected to provide useful applications for quantum computing at the current stage of hardware development. Quantum annealing techniques have been proposed to solve scheduling problems, along with many other optimization problems. In this work, we test quantum annealing and hybrid techniques based on the D-Wave hardware to solve scheduling problems in the framework of job shop scheduling (JSP), which consists of optimally assigning operations to certain resources, while satisfying specific constraints and minimizing the total scheduling time, known as timespan. We devised an iterative algorithm that produces valid schedules for decreasing timespan values. We implemented a refined iterative variable pruning technique, which significantly reduces the number of spin variables in the corresponding Ising model, whose low-energy configurations are sampled by using the D-Wave Hybrid Solver Service. Our novel iterative algorithm leverages a directed acyclic graph (DAG) representation of partial or complete solutions of the JSP instance, which enables an efficient update of the feasible processing time windows for each operation. This approach leads to significantly improved results compared to the standard state-of-the-art applications of quantum annealing for the JSP. Remarkably, we can often prove the absolute optimality of the obtained solution, namely that a more efficient schedule within a shorter timespan can not exist.
A quantum annealing solver for the renowned job-shop scheduling problem (JSP) is presented in detail. After formulating the problem as a time-indexed quadratic unconstrained binary optimization problem, several pre-processing and graph embedding strategies are employed to compile optimally parametrized families of the JSP for scheduling instances of up to six jobs and six machines on the D-Wave Systems Vesuvius processor. Problem simplifications and partitioning algorithms, including variable pruning and running strategies that consider tailored binary searches, are discussed and the results from the processor are compared against state-of-the-art global-optimum solvers.
Efficient production planning is essential in modern manufacturing to improve performance indicators such as lead time and to reduce reliance on human intuition. While mathematical optimization approaches, formulated as job shop scheduling problems, have been applied to automate this process, solving large-scale production planning problems remains computationally demanding. Moreover, many practical scenarios involve conflicting objectives, making traditional scalarization techniques ineffective in finding diverse and useful Pareto-optimal solutions. To address these challenges, we developed a quantum-classical hybrid algorithm that decomposes the problem into two subproblems: resource allocation and task scheduling. Resource allocation is formulated as a quadratic unconstrained binary optimization problem and solved using annealing-based methods that efficiently explore complex solutions. Task scheduling is modeled as a mixed-integer linear programming problem and solved using conventional solvers to satisfy detailed scheduling constraints. We validated the proposed method using benchmark instances based on foundry production scenarios. Experimental results demonstrate that our hybrid approach achieves superior solution quality and computational efficiency compared to traditional monolithic methods. This work offers a promising direction for high-speed, multi-objective scheduling in industrial applications.
Abstract Several fundamental questions demand space exploration, posing tremendous computational tasks to address modelling and data processing. Quantum computing has been proposed to address deep space-related problems from quantum gravity, nuclear processes and many-body field theory simulation to artificial intelligence and related space mission planning. Adiabatic quantum computers have been proposed for solving optimization problems, such as space mission scheduling. The problem of assigning jobs to resources in a scientific mission, while satisfying certain constraints, can be tackled with the help of D-Wave’s quantum annealer, which exploits the adiabatic theorem to find the minimum energy solutions of a given system, encoded as the Hamiltonian of a quadratic unconstrained binary optimization (QUBO) problem. In its simplest em-bodiement, the scheduling can be implemented as a graph coloring (GC) problem, where the goal is to assign different colors (out of a given set) to connected nodes of an input graph, while respecting given constraints. The feasibility of our methods and the performance of quantum annealers are studied on randomly generated GC instances. A second framework studied is the job shop scheduling problem (JSP) that encodes more real-like scheduling problems of interest to agencies and industries. By implementing the problems with a QUBO formulation, we are able to find the optimal solution to three JSP instances present in the literature. The biggest one is solved with a quantum computation approach here for the first time.
Job Shop Scheduling is a combinatorial optimization problem of particular importance for production environments where the goal is to complete a production task in the shortest possible time given limitations in the resources available. Due to its computational complexity it quickly becomes intractable for problems of interesting size. The emerging technology of Quantum Annealing provides an alternative computational architecture that promises improved scalability and solution quality. However, several limitations as well as open research questions exist in this relatively new and rapidly developing technology. This paper studies the application of quantum annealing to solve the job shop scheduling problem, describing each step required from the problem formulation to the fine-tuning of the quantum annealer and compares the solution quality with various classical solvers. Particular attention is devoted to aspects that are often overlooked, such as the computational cost of representing the problem in the formulation required by the quantum annealer, the relative qubits requirements and how to mitigate chain breaks. Furthermore, the impact of advanced tools such as reverse annealing is presented and its effectiveness discussed. The results indicate several challenges emerging at various stages of the experimental pipeline which bring forward important research questions and directions of improvement.
The Job Shop Scheduling Problem (JSSP) has always been considered as one of the most complex and industry essential scheduling problems. Optimizing the makespan of a given schedule generally involves using dedicated algorithms, local search strategies, or metaheuristics. These approaches, however, heavily rely on classical computational power, which is bounded by the physical limits of microcontrollers and power issues. Inspired by the promising results achieved for Quantum Annealing (QA) based approaches to solve JSSP instances, we propose a new approach that uses gate-model quantum architecture as an alternative to QA. We find that we can make use of the time-indexed JSSP instance representation to build a cost Hamiltonian, which can be embedded into Quantum Approximate Optimization Algorithm (QAOA) to find an optimal solution to a basic JSSP instance. We demonstrate the use of QAOA to solve the JSSP, and we evaluate its efficiency and accuracy for this problem from experimental results, as there is an increased urgency to demonstrate the applicability of quantum optimization algorithms. We also find that optimal variational parameters form patterns that can facilitate computation in bigger quantum circuits. Additionally, we compare the obtained noiseless simulation results of gate-model quantum circuits demonstrating the relationship between two evaluation criteria - makespan and energy. Finally, we analyze and present the overall performance of our approach with the increasing deadline and simulated depth of QAOA circuits.
A Robust Time Dependent Job Shop Scheduling Problem (RTDJSSP) is a complicated optimization problem for simulating real-world process scheduling tasks with competing objectives. To address RTDJSSPs, approximation approaches are used to ensure solutions are completed within acceptable timelines with varying sectional durations. Quantum Annealing, a metaheuristic that uses quantum mechanical effects, produces better solution quality in less time than conventional algorithms. However, due to hardware restrictions in quantum annealers, hybrid methods are required for solving bigger RTDJSSPs. This work explores the threshold issue sizes for which quantum annealers are sufficient and when hybrid algorithms are necessary, focusing on the distribution of computing resources in hybrid approaches.