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

Optimal solving of a scheduling problem using quantum annealing metaheuristics on the D-Wave quantum solver

Wojciech Bożejko, Ryszard Klempous, Jarosław Pempera, Jerzy W. Rozenblit, Czesław Smutnicki, Mariusz Uchroński, Mieczysław Wodecki

Published Apr 26, 2023• 0 citations
Publisher

Abstract

This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible. The main disadvantage of calculations on quantum computers is their non-determinism. For optimization problems, of course, it is possible to get surprisingly good results but without a guarantee of the actual optimality of the result, i.e, an assurance that there exists no better solution which could potentially be found by the quantum machine. In this paper, we propose an novel approach that provides such a guarantee of optimality. We generate a solution that is optimal in the strict mathematical sense, without probabilistic considerations. To accomplish this, we use the D-Wave quantum machine working as a sampler implementing quantum annealing -- an approach considered a hardware metaheuristic -- to obtain upper and lower bounds on the value of the objective function of the problem under consideration. Then, we use the Branch and Bound scheme controlled by quantum annealing. This allows us to obtain very quickly -- in constant time -- the boundaries of the considered subproblems. Our approach is a combination of calculations realized on a quantum machine controlled by procedures implemented on a classical computer, allowing us to generate optimal solutions to the NP-hard problems of task scheduling on a single machine with a total weighted tardiness criterion. The proposed quantum algorithm shows a significant advantage over the classical CPU approach both in terms of calculation time and the number of generated solution tree nodes.

DOI
10.36227/techrxiv.22677721

Related papers

Optimal Solving of a Scheduling Problem Using Quantum Annealing Metaheuristics on the D-Wave Quantum Solver

Wojciech Bożejko, Ryszard Klempous, Jarosław Pempera +4 more

Accurately solving discrete optimization problems is still a serious challenge for classical computing systems. Despite significant progress, it is still impossible to optimally solve examples of the size found in real-world applications. This article examines the problem of scheduling tasks on one machine. Each task has an associated execution time, desired completion date, and a late penalty feature weight. The order of executing tasks should be determined in a manner that minimizes the sum of delay costs. Despite the simplicity of the formulation, this problem is NP-hard and is representative of optimization challenges encountered in the practice of production control, management, and logistics.In this work, we propose using a quantum computing environment to solve it. The main disadvantage of calculations on quantum computers is their nondeterminism. Therefore, there is no guarantee of optimality of solutions to discrete optimization problems determined on a quantum computer.We propose a novel approach to constructing hybrid algorithms that guarantee the optimality of the solution. The algorithm for solving the task scheduling problem considered here is based on the branch and bound method. Calculations are performed alternately on a classical computer and a quantum computer. The lower and upper bounds of the criterion function are determined on a quantum computer. Computational experiments were performed on the D-Wave quantum computer. In small examples, the algorithm runs faster and generates significantly fewer solution tree vertices than its counterpart running on a classic computer. For larger examples, the proposed runtime-constrained method, acting as a heuristic, is an interesting alternative to using quantum computing hardware in relation to classical approaches based on silicon computers.

IEEE Transactions on Systems Man and Cybernetics Systems•Oct 2, 2024•22 citations

Using Quantum Annealing to Solve Large-Scale Optimization Problems in Logistics and Scheduling

Sandeep Kumar

In planning and scheduling, large-scale optimization problems often have complex limits and a lot of factors, which makes them hard to answer with standard methods. Quantum annealing has become a hopeful way to deal with these problems because it can quickly look into a lot of possible solutions. This essay looks into how quantum annealing might be used to solve optimization problems in transportation and scheduling, with a focus on how it could be used for route planning, inventory management, and arranging workers. To do these optimization jobs, quantum annealing is used. This is a quantum computing method that gets the global minimum of a cost function. We use the D-Wave quantum annealer in this method. It turns the problem's limits and objective function into a quadratic unconstrained binary optimization (QUBO) model. The quantum annealer then works on this model to find the best answers. The suggested method combines traditional preparation methods with quantum annealing to get the best results for big schedule and transportation issues. We use quantum annealing to solve difficult multi-objective optimization problems, like reducing shipping time, cost, and resource use all at the same time. Preliminary results show that quantum annealing can make solutions much better and use computers much more efficiently than traditional methods for optimizing supplies and schedules. Quantum annealing works especially well with problems that have a lot of dimensions. It can provide scalable answers that sometimes work better than standard methods.

International Conference on Emerging Smart Computing and Informatics (ESCI)•Mar 5, 2025•0 citations

Quantum annealing for vehicle routing and scheduling problems

Alex Syrichas

Metaheuristic approaches to solving combinatorial optimization problems have many attractions. They sidestep the issue of combinatorial explosion; they return good results; they are often conceptually simple and straight forward to implement. There are also shortcomings. Optimal solutions are not guaranteed; choosing the metaheuristic which best fits a problem is a matter of experimentation; and conceptual differences between metaheuristics make absolute comparisons of performance difficult. There is also the difficulty of configuration of the algorithm - the process of identifying precise values for the parameters which control the optimization process. Quantum annealing is a metaheuristic which is the quantum counterpart of the well known classical Simulated Annealing algorithm for combinatorial optimization problems. This research investigates the application of quantum annealing to the Vehicle Routing Problem, a difficult problem of practical significance within industries such as logistics and workforce scheduling. The work devises spin encoding schemes for routing and scheduling problem domains, enabling an effective quantum annealing algorithm which locates new solutions to widely used benchmarks. The performance of the metaheuristic is further improved by the development of an enhanced tuning approach using fitness clouds as behaviour models. The algorithm is shown to be further enhanced by taking advantage of multiprocessor environments, using threading techniques to parallelize the optimization workload. The work also shows quantum annealing applied successfully in an industrial setting to generate solutions to complex scheduling problems, results which created extra savings over an incumbent optimization technique. Components of the intellectual property rendered in this latter effort went on to secure a patent-protected status.

•May 28, 2026•2 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•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

What Is the Optimal Annealing Schedule in Quantum Annealing

Oscar Galindo, Владик Крейнович

In many real-life situations in engineering (and in other disciplines), we need to solve an optimization problem: we want an optimal design, we want an optimal control, etc. One of the main problems in optimization is avoiding local maxima (or minima). One of the techniques that helps with solving this problem is annealing: whenever we find ourselves in a possibly local maximum, we jump out with some probability and continue search for the true optimum. A natural way to organize such a probabilistic perturbation of the deterministic optimization is to use quantum effects. It turns out that often, quantum annealing works much better than non-quantum one. Quantum annealing is the main technique behind the only commercially available computational devices that use quantum effects-D-Wave computers. The efficiency of quantum annealing depends on the proper selection of the annealing schedule, i.e., schedule that describes how the perturbations decrease with time. Empirically, it has been found that two schedules work best: power law and exponential ones. In this paper, we provide a theoretical explanation for these empirical successes, by proving that these two schedules are indeed optimal (in some reasonable sense).

IEEE Symposium Series on Computational Intelligence (SSCI)•Dec 1, 2020•11 citations
This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible. The main disadvantage of calculations on quantum computers is their non-determinism. For optimization problems, of course, it is possible to get surprisingly good results but without a guarantee of the actual optimality of the result, i.e, an assurance that there exists no better solution which could potentially be found by the quantum machine. In this paper, we propose an novel approach that provides such a guarantee of optimality. We generate a solution that is optimal in the strict mathematical sense, without probabilistic considerations. To accomplish this, we use the D-Wave quantum machine working as a sampler implementing quantum annealing -- an approach considered a hardware metaheuristic -- to obtain upper and lower bounds on the value of the objective function of the problem under consideration. Then, we use the Branch and Bound scheme controlled by quantum annealing. This allows us to obtain very quickly -- in constant time -- the boundaries of the considered subproblems. Our approach is a combination of calculations realized on a quantum machine controlled by procedures implemented on a classical computer, allowing us to generate optimal solutions to the NP-hard problems of task scheduling on a single machine with a total weighted tardiness criterion. The proposed quantum algorithm shows a significant advantage over the classical CPU approach both in terms of calculation time and the number of generated solution tree nodes.
Accurately solving discrete optimization problems is still a serious challenge for classical computing systems. Despite significant progress, it is still impossible to optimally solve examples of the size found in real-world applications. This article examines the problem of scheduling tasks on one machine. Each task has an associated execution time, desired completion date, and a late penalty feature weight. The order of executing tasks should be determined in a manner that minimizes the sum of delay costs. Despite the simplicity of the formulation, this problem is NP-hard and is representative of optimization challenges encountered in the practice of production control, management, and logistics.In this work, we propose using a quantum computing environment to solve it. The main disadvantage of calculations on quantum computers is their nondeterminism. Therefore, there is no guarantee of optimality of solutions to discrete optimization problems determined on a quantum computer.We propose a novel approach to constructing hybrid algorithms that guarantee the optimality of the solution. The algorithm for solving the task scheduling problem considered here is based on the branch and bound method. Calculations are performed alternately on a classical computer and a quantum computer. The lower and upper bounds of the criterion function are determined on a quantum computer. Computational experiments were performed on the D-Wave quantum computer. In small examples, the algorithm runs faster and generates significantly fewer solution tree vertices than its counterpart running on a classic computer. For larger examples, the proposed runtime-constrained method, acting as a heuristic, is an interesting alternative to using quantum computing hardware in relation to classical approaches based on silicon computers.
In planning and scheduling, large-scale optimization problems often have complex limits and a lot of factors, which makes them hard to answer with standard methods. Quantum annealing has become a hopeful way to deal with these problems because it can quickly look into a lot of possible solutions. This essay looks into how quantum annealing might be used to solve optimization problems in transportation and scheduling, with a focus on how it could be used for route planning, inventory management, and arranging workers. To do these optimization jobs, quantum annealing is used. This is a quantum computing method that gets the global minimum of a cost function. We use the D-Wave quantum annealer in this method. It turns the problem's limits and objective function into a quadratic unconstrained binary optimization (QUBO) model. The quantum annealer then works on this model to find the best answers. The suggested method combines traditional preparation methods with quantum annealing to get the best results for big schedule and transportation issues. We use quantum annealing to solve difficult multi-objective optimization problems, like reducing shipping time, cost, and resource use all at the same time. Preliminary results show that quantum annealing can make solutions much better and use computers much more efficiently than traditional methods for optimizing supplies and schedules. Quantum annealing works especially well with problems that have a lot of dimensions. It can provide scalable answers that sometimes work better than standard methods.
Metaheuristic approaches to solving combinatorial optimization problems have many attractions. They sidestep the issue of combinatorial explosion; they return good results; they are often conceptually simple and straight forward to implement. There are also shortcomings. Optimal solutions are not guaranteed; choosing the metaheuristic which best fits a problem is a matter of experimentation; and conceptual differences between metaheuristics make absolute comparisons of performance difficult. There is also the difficulty of configuration of the algorithm - the process of identifying precise values for the parameters which control the optimization process. Quantum annealing is a metaheuristic which is the quantum counterpart of the well known classical Simulated Annealing algorithm for combinatorial optimization problems. This research investigates the application of quantum annealing to the Vehicle Routing Problem, a difficult problem of practical significance within industries such as logistics and workforce scheduling. The work devises spin encoding schemes for routing and scheduling problem domains, enabling an effective quantum annealing algorithm which locates new solutions to widely used benchmarks. The performance of the metaheuristic is further improved by the development of an enhanced tuning approach using fitness clouds as behaviour models. The algorithm is shown to be further enhanced by taking advantage of multiprocessor environments, using threading techniques to parallelize the optimization workload. The work also shows quantum annealing applied successfully in an industrial setting to generate solutions to complex scheduling problems, results which created extra savings over an incumbent optimization technique. Components of the intellectual property rendered in this latter effort went on to secure a patent-protected status.
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.
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.
In many real-life situations in engineering (and in other disciplines), we need to solve an optimization problem: we want an optimal design, we want an optimal control, etc. One of the main problems in optimization is avoiding local maxima (or minima). One of the techniques that helps with solving this problem is annealing: whenever we find ourselves in a possibly local maximum, we jump out with some probability and continue search for the true optimum. A natural way to organize such a probabilistic perturbation of the deterministic optimization is to use quantum effects. It turns out that often, quantum annealing works much better than non-quantum one. Quantum annealing is the main technique behind the only commercially available computational devices that use quantum effects-D-Wave computers. The efficiency of quantum annealing depends on the proper selection of the annealing schedule, i.e., schedule that describes how the perturbations decrease with time. Empirically, it has been found that two schedules work best: power law and exponential ones. In this paper, we provide a theoretical explanation for these empirical successes, by proving that these two schedules are indeed optimal (in some reasonable sense).