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

Lecture notes in networks and systems

On Quantum Computing Formulations for the Total Weighted Tardiness and Total Weighted Earliness Optimization

Mikołaj Bożejko, Igor Janiak, Hubert Siewiera, Mikołaj Wysocki, Jarosław Rudy

Published Jan 1, 2026• 1 citation
Publisher
DOI
10.1007/978-3-032-14163-7_26

Related papers

Time Optimization in Quantum Computing

Anonymous

Physics•Oct 19, 2016•0 citations

A Quantum Optimization Algorithm for Single Machine Total Weighted Tardiness Minimization

Youhao Steve Wang, Julian Cheng

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.

arXiv:2209.13712•Sep 27, 2022•0 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

Quantum Algorithms for Optimization

Ansh Bansal

IOSR Journal of Computer Engineering•Oct 1, 2025•0 citations

Quantum annealing‐driven branch and bound for the total weighted tardiness traveling salesman problem on the D‐Wave quantum computer

Wojciech Bożejko, Mariusz Uchroński, Mieczysław Wodecki

Abstract The transportation problem considered in this work consists of minimizing the sum of penalties for tardiness in the delivery of the product from the base to clients. We propose an innovative method for constructing hybrid algorithms using quantum annealing that guarantees the optimality of the solution. The hybrid algorithm alternately performs calculations on a classical computer equipped with a silicon CPU and a quantum annealer with a QPU processor. The entire method is based on the branch and bound scheme. The lower and upper bounds are calculated on the QPU, while the CPU is responsible for organizing the calculations, recalling the solution tree. The problem under consideration is of great practical importance because it is a component of many complex issues related to solving the traveling repairmen problem, which are very difficult or even impossible to solve today using classical methods. Undoubtedly, an important application of quantum computers in the future is NP‐hard optimization tasks related to transportation scheduling and logistics.

International Transactions in Operational Research•Jan 21, 2026•1 citation

Total Quantum Search of Optimal Solution in Quantum Computing

Tomah Sogabe

The Japanese Society for Artificial Intelligence•Apr 8, 2019•1 citation
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.
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 The transportation problem considered in this work consists of minimizing the sum of penalties for tardiness in the delivery of the product from the base to clients. We propose an innovative method for constructing hybrid algorithms using quantum annealing that guarantees the optimality of the solution. The hybrid algorithm alternately performs calculations on a classical computer equipped with a silicon CPU and a quantum annealer with a QPU processor. The entire method is based on the branch and bound scheme. The lower and upper bounds are calculated on the QPU, while the CPU is responsible for organizing the calculations, recalling the solution tree. The problem under consideration is of great practical importance because it is a component of many complex issues related to solving the traveling repairmen problem, which are very difficult or even impossible to solve today using classical methods. Undoubtedly, an important application of quantum computers in the future is NP‐hard optimization tasks related to transportation scheduling and logistics.