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 computer science

Determination of the Lower Bounds of the Goal Function for a Single-Machine Scheduling Problem on D-Wave Quantum Annealer

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

Published Jan 1, 2023• 2 citations
Publisher
DOI
10.1007/978-3-031-36030-5_16

Related papers

Distributed Quantum Annealing on D-Wave for the Single Machine Total Weighted Tardiness Scheduling Problem

Wojciech Bożejko, Jarosław Pempera, Mariusz Uchroński +1 more

Lecture notes in computer science•Jan 1, 2022•7 citations

Quantum annealing-driven branch and bound for the single machine total weighted number of tardy jobs scheduling problem

Wojciech Bożejko, Jarosław Pempera, Mariusz Uchroński +1 more

Future Generation Computer Systems•Feb 19, 2024•22 citations

Quantum Annealing to Solve the Unrelated Parallel Machine Scheduling Problem

Francisco José Orts, Antonio Manuel Puertas, Ester Martín Garzón +1 more

Lecture notes in computer science•Jan 1, 2023•3 citations

Solving Two-Machine Sum-Cost Flow Shop Problem on D-Wave Quantum Annealer

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

Lecture notes in computer science•Jan 1, 2025•1 citation

Performance of Quantum Annealers on Hard Scheduling Problems

Bibek Pokharel, Davide Venturelli, Eleanor Gilbert Rieffel

Bulletin of the American Physical Society•Mar 13, 2017•1 citation

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
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.