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

arXiv:2209.13712

A Quantum Optimization Algorithm for Single Machine Total Weighted Tardiness Minimization

Youhao Steve Wang, Julian Cheng

Published Sep 27, 2022• 0 citations
arXivHTMLPDF

Abstract

A single machine total weighted tardiness minimization (TWTM) problem in operational planning is considered. The problem is formulated as an NP-hard constrained combinatorial problem, which has no known deterministic polynomial complexity solution using classical computing. Based on efficient Grover's quantum search and Trugenberger's quantum optimization algorithms, a novel efficient quantum optimization algorithm is proposed to solve the NP-hard single machine TWTM problem, which makes the desired solution satisfying the searching constraints and showing the minimal TWT value be measured with the highest probability.

DOI
10.48550/arxiv.2209.13712

Related papers

Quantum Speed-ups for Single-machine Scheduling Problems

Camille Grange, Eric Bourreau, Michaël Poss +1 more

Grover search is currently one of the main approaches to obtain quantum speed-ups for combinatorial optimization problems. The combination of Quantum Minimum Finding (obtained from Grover search) with dynamic programming has proved particularly efficient to improve the worst-case complexity of several NP-hard optimization problems. Specifically, for these problems, the classical dynamic programming complexity (ignoring the polynomial factors) in O* (cn) can be reduced by a bounded-error hybrid quantum-classical algorithm to O* (cnquant) for cquant < c. In this paper, we extend the resulting hybrid dynamic programming algorithm to three examples of single-machine scheduling problems: minimizing the total weighted completion time with deadlines, minimizing the total weighted completion time with precedence constraints, and minimizing the total weighted tardiness. The extension relies on the inclusion of a pseudo-polynomial term in the state space of the dynamic programming as well as an additive term in the recurrence.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 15, 2023•2 citations

Grover Algorithm-based Quantum Scheduling Framework for Constrained Graph Coloring

Lutfiana Sausan, Hyunsoo Lee

Quantum computing holds significant promise for solving NP-hard combinatorial problems by leveraging quantum properties such as superposition, entanglement, and interference. In this study, we apply Grover’s algorithm to a constrained scheduling problem modeled as a graph coloring task with an added complexity: ensuring that the total processing time of all jobs assigned to a machine does not exceed its capacity. This additional constraint increases the problem’s difficulty beyond traditional graph coloring. Our proposed quantum framework demonstrates the ability to generate valid schedules that satisfy both coloring and capacity constraint, highlighting the practical potential of quantum computing for addressing complex scheduling challenges.

Journal of Korean Institute of Industrial Engineers•Dec 15, 2025•0 citations

Solving two-machine flow shop scheduling problem with total weighted number of on-time tasks maximization criterion on D-Wave quantum computer

Wojciech Bożejko, Ryszard Klempous, Mariusz Uchroński +1 more

The work deals with the NP-hard problem of scheduling tasks on two machines with the sum-cost criterion. In this problem, each task must be performed sequentially on the first and then on the second machine. Each task is associated with: execution time, due date, and weight (revenue) related to completing the task on-time (i.e. before the due date). The goal is to determine the order of task execution, the same on both machines, that maximizes the total weighted number of on-time tasks (maximum profit). We propose a hybrid algorithm combining quantum and classical methods based on the branch and bound method. We propose to formulate the problem under consideration as a Constrained Quadratic Model (CQM), due to which we can compute upper bounds (using Lagrange relaxation) and lower bounds on the D-Wave quantum machine. Although the D-Wave quantum computer performs probabilistic calculations, the solution determined by the proposed algorithm is optimal.

IEEE International Symposium on Computational Intelligence and Informatics (CINTI)•Nov 20, 2023•4 citations

Quantum Approximation for Wireless Scheduling

Jaeho Choi, Seunghyeok Oh, Joongheon Kim

This paper proposes an application algorithm based on a quantum approximate optimization algorithm (QAOA) for wireless scheduling problems. QAOA is one of the promising hybrid quantum-classical algorithms to solve combinatorial optimization problems and it provides great approximate solutions to non-deterministic polynomial-time (NP) hard problems. QAOA maps the given problem into Hilbert space, and then it generates the Hamiltonian for the given objective and constraint. Then, QAOA finds proper parameters from the classical optimization loop in order to optimize the expectation value of the generated Hamiltonian. Based on the parameters, the optimal solution to the given problem can be obtained from the optimum of the expectation value of the Hamiltonian. Inspired by QAOA, a quantum approximate optimization for scheduling (QAOS) algorithm is proposed. The proposed QAOS designs the Hamiltonian of the wireless scheduling problem which is formulated by the maximum weight independent set (MWIS). The designed Hamiltonian is converted into a unitary operator and implemented as a quantum gate operation. After that, the iterative QAOS sequence solves the wireless scheduling problem. The novelty of QAOS is verified with simulation results implemented via Cirq and TensorFlow-Quantum.

arXiv:2004.11229•Applied Sciences•Oct 13, 2020•47 citations

Quantum Computing-Based Real-Time Optimization Method for Large-Scale Single-Machine Scheduling

Lixiang Zhang, Qing Gao, Yu Pan +1 more

Large-scale single-machine scheduling has become increasingly critical in modern intelligent manufacturing, where real-time optimization is essential for efficient resource utilization and rapid decision-making. However, existing methods often struggle to balance optimization quality and computational responsiveness when facing high-dimensional scheduling scenarios. To address this challenge, this paper proposes a quantum computing-based real-time optimization framework for large-scale single-machine scheduling problems. The approach first formulates the scheduling process as an integer programming model and transforms it into a quadratic unconstrained binary optimization representation to enable quantum computation. To efficiently explore the exponentially growing solution space, a scalable problem decomposition mechanism is developed, allowing the parallel optimization of subproblems on quantum devices under hardware constraints. Furthermore, a decoding and correction mechanism is introduced to ensure the feasibility of scheduling solutions. Experimental results verify that the proposed framework achieves superior real-time performance, effectively shortens the total earliness and tardiness, and guarantees feasible schedules for large-scale problems, demonstrating significant advantages over classical heuristic and exact algorithms.

IEEE International Conference on Cybernetics (CYBCONF)•Apr 1, 2026•0 citations

A Quantum Global Optimization Algorithm: Application to the Knapsack Problem

Mohamed Yassine Cherif, Wided Lejouad Chaari, Olfa Belkahla Driss

Abstract Solving combinatorial optimization problems represents a challenge for researchers, especially hard NP-complete problems that are commonly handled through heuristic methods providing approximate solutions. The emergence of quantum computing, which enables performing parallel computation, raises hope for solving such problems within a reasonable time frame. This paper proposes a quantum global optimization algorithm for solving combinatorial optimization problems with improved performance and runtime approaching Grover’s optimal time of quantum search. The algorithm determines the global optimum of the objective function defining the addressed problem using an enhanced application of Grover’s search by simultaneously exploring all comparison cases of possible solutions without requiring iterative operations, unlike previous approaches, which affect performance and runtime. The paper also introduces a version of the proposed algorithm for solving the knapsack problem, along with its execution results and a comparison with other competing algorithms.

•Jan 12, 2026•0 citations
A single machine total weighted tardiness minimization (TWTM) problem in operational planning is considered. The problem is formulated as an NP-hard constrained combinatorial problem, which has no known deterministic polynomial complexity solution using classical computing. Based on efficient Grover's quantum search and Trugenberger's quantum optimization algorithms, a novel efficient quantum optimization algorithm is proposed to solve the NP-hard single machine TWTM problem, which makes the desired solution satisfying the searching constraints and showing the minimal TWT value be measured with the highest probability.
Grover search is currently one of the main approaches to obtain quantum speed-ups for combinatorial optimization problems. The combination of Quantum Minimum Finding (obtained from Grover search) with dynamic programming has proved particularly efficient to improve the worst-case complexity of several NP-hard optimization problems. Specifically, for these problems, the classical dynamic programming complexity (ignoring the polynomial factors) in O* (cn) can be reduced by a bounded-error hybrid quantum-classical algorithm to O* (cnquant) for cquant < c. In this paper, we extend the resulting hybrid dynamic programming algorithm to three examples of single-machine scheduling problems: minimizing the total weighted completion time with deadlines, minimizing the total weighted completion time with precedence constraints, and minimizing the total weighted tardiness. The extension relies on the inclusion of a pseudo-polynomial term in the state space of the dynamic programming as well as an additive term in the recurrence.
Quantum computing holds significant promise for solving NP-hard combinatorial problems by leveraging quantum properties such as superposition, entanglement, and interference. In this study, we apply Grover’s algorithm to a constrained scheduling problem modeled as a graph coloring task with an added complexity: ensuring that the total processing time of all jobs assigned to a machine does not exceed its capacity. This additional constraint increases the problem’s difficulty beyond traditional graph coloring. Our proposed quantum framework demonstrates the ability to generate valid schedules that satisfy both coloring and capacity constraint, highlighting the practical potential of quantum computing for addressing complex scheduling challenges.
The work deals with the NP-hard problem of scheduling tasks on two machines with the sum-cost criterion. In this problem, each task must be performed sequentially on the first and then on the second machine. Each task is associated with: execution time, due date, and weight (revenue) related to completing the task on-time (i.e. before the due date). The goal is to determine the order of task execution, the same on both machines, that maximizes the total weighted number of on-time tasks (maximum profit). We propose a hybrid algorithm combining quantum and classical methods based on the branch and bound method. We propose to formulate the problem under consideration as a Constrained Quadratic Model (CQM), due to which we can compute upper bounds (using Lagrange relaxation) and lower bounds on the D-Wave quantum machine. Although the D-Wave quantum computer performs probabilistic calculations, the solution determined by the proposed algorithm is optimal.
This paper proposes an application algorithm based on a quantum approximate optimization algorithm (QAOA) for wireless scheduling problems. QAOA is one of the promising hybrid quantum-classical algorithms to solve combinatorial optimization problems and it provides great approximate solutions to non-deterministic polynomial-time (NP) hard problems. QAOA maps the given problem into Hilbert space, and then it generates the Hamiltonian for the given objective and constraint. Then, QAOA finds proper parameters from the classical optimization loop in order to optimize the expectation value of the generated Hamiltonian. Based on the parameters, the optimal solution to the given problem can be obtained from the optimum of the expectation value of the Hamiltonian. Inspired by QAOA, a quantum approximate optimization for scheduling (QAOS) algorithm is proposed. The proposed QAOS designs the Hamiltonian of the wireless scheduling problem which is formulated by the maximum weight independent set (MWIS). The designed Hamiltonian is converted into a unitary operator and implemented as a quantum gate operation. After that, the iterative QAOS sequence solves the wireless scheduling problem. The novelty of QAOS is verified with simulation results implemented via Cirq and TensorFlow-Quantum.
Large-scale single-machine scheduling has become increasingly critical in modern intelligent manufacturing, where real-time optimization is essential for efficient resource utilization and rapid decision-making. However, existing methods often struggle to balance optimization quality and computational responsiveness when facing high-dimensional scheduling scenarios. To address this challenge, this paper proposes a quantum computing-based real-time optimization framework for large-scale single-machine scheduling problems. The approach first formulates the scheduling process as an integer programming model and transforms it into a quadratic unconstrained binary optimization representation to enable quantum computation. To efficiently explore the exponentially growing solution space, a scalable problem decomposition mechanism is developed, allowing the parallel optimization of subproblems on quantum devices under hardware constraints. Furthermore, a decoding and correction mechanism is introduced to ensure the feasibility of scheduling solutions. Experimental results verify that the proposed framework achieves superior real-time performance, effectively shortens the total earliness and tardiness, and guarantees feasible schedules for large-scale problems, demonstrating significant advantages over classical heuristic and exact algorithms.
Abstract Solving combinatorial optimization problems represents a challenge for researchers, especially hard NP-complete problems that are commonly handled through heuristic methods providing approximate solutions. The emergence of quantum computing, which enables performing parallel computation, raises hope for solving such problems within a reasonable time frame. This paper proposes a quantum global optimization algorithm for solving combinatorial optimization problems with improved performance and runtime approaching Grover’s optimal time of quantum search. The algorithm determines the global optimum of the objective function defining the addressed problem using an enhanced application of Grover’s search by simultaneously exploring all comparison cases of possible solutions without requiring iterative operations, unlike previous approaches, which affect performance and runtime. The paper also introduces a version of the proposed algorithm for solving the knapsack problem, along with its execution results and a comparison with other competing algorithms.