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

Computer Engineering and Applications Journal

Research of improved hybrid quantum algorithm in Job Shop scheduling problems

Zhao Wei-min

Published Jan 1, 2009• 3 citations
OpenAlex

Abstract

Managers have focused a lot on the aid of computers since the introduction of scientific management concepts into production process.Job Shop scheduling problem(JSP) is a simplified model which results from many exact production scheduling problems.The tremendous solution space brings big challenge.On the basis of Q-bit coding,two types of decoding are designed, quantum angles can be adjusted intelligently with the help of Particle Swarm Optimization algorithm(PSO) and Hybrid Quantum Algorithm(HQA) is constructed.However,when HQA is employed to solve JSP,the effect is not satisfactory.Under the HQA structure,some optimization mechanisms are introduced,which dramatically improve the capability of the algorithm,and the new algorithm is denoted as Improved Hybrid Quantum Algorithm(IHQA).

Related papers

Hybrid quantum algorithm and its application in flow shop problem

Xie Jin-hua

Quantum Evolutionary Algorithm(QEA) is a distinctive type of algorithm for optimization currently,and the theoretical basis of QEA is quantum computation.The algorithm takes advantage of intervention and parallelism of quantum bit thoroughly,which enables QEA to solve combinatorial optimization problems.While solving scheduling problems,QEA has defects that it converges slowly and doesn’t use other immature individual.Hybrid Quantum Algorithm(HQA) is formed and it sucks Particle Swarm Optimization algorithm(PSO) and evolutionary computation into QEA.Classical flow shop problem is employed to test the algorithm,and the result shows that the hybrid algorithm overcomes the defects of QEA and it has universality to solve scheduling problems.

Computer Engineering and Applications Journal•Jan 1, 2008•0 citations

Application study on hybrid quantum algorithm in traveling salesman problem

Chunming Ye

A novel method of coding was brought forward and the essence of evolutionary algorithm(EA) and particle swarm optimization algorithm(PSO) was put into consideration in terms of the characteristics of Traveling Salesman Problem(TSP),and a distinctive hybrid quantum algorithm(HQA) was constructed.The breakthrough was taken as the means of updating the individual to improve the capability of HQA.Still further,the updating of inertial weight was guided dynamically,and the decision that individual would turn out to be attractive or repulsive in the next iteration was made.This new algorithm is called improved hybrid quantum algorithm(IHQA).The result of the test manifests that both two algorithms are of strong capability in optimum-searching,and IAQA performs better.

Journal of the University of Shanghai for Science and Technology•Jan 1, 2009•1 citation

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

Evaluation of Quantum Annealing-based algorithms for flexible job shop scheduling

Philipp Schworm, Xiangqian Wu, Matthias Klar +1 more

A flexible job shop scheduling problem (FJSSP) poses a complex optimization task in modeling real-world process scheduling tasks with conflicting objectives. To tackle FJSSPs, approximation methods are employed to ensure solutions are within acceptable timeframes. Quantum Annealing, a metaheuristic leveraging quantum mechanical effects, demonstrates superior solution quality in a shorter time compared to classical algorithms. However, due to hardware limitations of quantum annealers, hybrid algorithms become essential for solving larger FJSSPs. This paper investigates the threshold problem sizes up to which quantum annealers are sufficient and when hybrid algorithms are required, highlighting the distribution of computing power in hybrid methods.

arXiv:2408.15671•Procedia CIRP•Jan 1, 2026•3 citations

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

Rebecca Casati, Thomas Giudici, Pietro Torta +1 more

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.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•1 citation

Solving Flexible Job-Shop Scheduling Problems Based on Quantum Computing

Kaihan Fu, Jianjun Liu, Miao Chen +1 more

Flexible job-shop scheduling problems (FJSPs) represent one of the most complex combinatorial optimization challenges. Modern production systems and control processes demand rapid decision-making in scheduling. To address this challenge, we propose a quantum computing approach for solving FJSPs. We propose a quadratic unconstrained binary optimization (QUBO) model to minimize the makespan of FJSPs, with the scheduling scheme encoded in the ground state of the Hamiltonian operator. The model is solved using a coherent Ising machine (CIM). Numerical experiments are conducted to evaluate and validate the performance and effectiveness of the CIM. The results demonstrate that quantum computing holds significant potential for solving FJSPs more efficiently than traditional computational methods.

Entropy•Feb 13, 2025•6 citations
Managers have focused a lot on the aid of computers since the introduction of scientific management concepts into production process.Job Shop scheduling problem(JSP) is a simplified model which results from many exact production scheduling problems.The tremendous solution space brings big challenge.On the basis of Q-bit coding,two types of decoding are designed, quantum angles can be adjusted intelligently with the help of Particle Swarm Optimization algorithm(PSO) and Hybrid Quantum Algorithm(HQA) is constructed.However,when HQA is employed to solve JSP,the effect is not satisfactory.Under the HQA structure,some optimization mechanisms are introduced,which dramatically improve the capability of the algorithm,and the new algorithm is denoted as Improved Hybrid Quantum Algorithm(IHQA).
Quantum Evolutionary Algorithm(QEA) is a distinctive type of algorithm for optimization currently,and the theoretical basis of QEA is quantum computation.The algorithm takes advantage of intervention and parallelism of quantum bit thoroughly,which enables QEA to solve combinatorial optimization problems.While solving scheduling problems,QEA has defects that it converges slowly and doesn’t use other immature individual.Hybrid Quantum Algorithm(HQA) is formed and it sucks Particle Swarm Optimization algorithm(PSO) and evolutionary computation into QEA.Classical flow shop problem is employed to test the algorithm,and the result shows that the hybrid algorithm overcomes the defects of QEA and it has universality to solve scheduling problems.
A novel method of coding was brought forward and the essence of evolutionary algorithm(EA) and particle swarm optimization algorithm(PSO) was put into consideration in terms of the characteristics of Traveling Salesman Problem(TSP),and a distinctive hybrid quantum algorithm(HQA) was constructed.The breakthrough was taken as the means of updating the individual to improve the capability of HQA.Still further,the updating of inertial weight was guided dynamically,and the decision that individual would turn out to be attractive or repulsive in the next iteration was made.This new algorithm is called improved hybrid quantum algorithm(IHQA).The result of the test manifests that both two algorithms are of strong capability in optimum-searching,and IAQA performs better.
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.
A flexible job shop scheduling problem (FJSSP) poses a complex optimization task in modeling real-world process scheduling tasks with conflicting objectives. To tackle FJSSPs, approximation methods are employed to ensure solutions are within acceptable timeframes. Quantum Annealing, a metaheuristic leveraging quantum mechanical effects, demonstrates superior solution quality in a shorter time compared to classical algorithms. However, due to hardware limitations of quantum annealers, hybrid algorithms become essential for solving larger FJSSPs. This paper investigates the threshold problem sizes up to which quantum annealers are sufficient and when hybrid algorithms are required, highlighting the distribution of computing power in hybrid methods.
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.
Flexible job-shop scheduling problems (FJSPs) represent one of the most complex combinatorial optimization challenges. Modern production systems and control processes demand rapid decision-making in scheduling. To address this challenge, we propose a quantum computing approach for solving FJSPs. We propose a quadratic unconstrained binary optimization (QUBO) model to minimize the makespan of FJSPs, with the scheduling scheme encoded in the ground state of the Hamiltonian operator. The model is solved using a coherent Ising machine (CIM). Numerical experiments are conducted to evaluate and validate the performance and effectiveness of the CIM. The results demonstrate that quantum computing holds significant potential for solving FJSPs more efficiently than traditional computational methods.