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

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

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

Published Jan 1, 2025• 1 citation
Publisher
DOI
10.1007/978-3-031-83885-9_7

Related papers

Hybrid Quantum Annealing Heuristic Method for Solving Job Shop Scheduling Problem

Krzysztof Kurowski, Jan Węglarz, Marek Subocz +2 more

Lecture notes in computer science•Jan 1, 2020•37 citations

Decomposition Algorithms for Solving NP-hard Problems on a Quantum Annealer

Elijah Pelofske, Georg Hahn, Hristo N. Djidjev

arXiv:2009.06726•Journal of Signal Processing Systems•Jun 29, 2020•23 citations

Enhanced QUBO Formulations for The Flow Shop Scheduling Problem

Yousra Farhani, Malak Saiem, Taha Arbaoui +1 more

In recent years, the Flow shop Scheduling Problem (FSP) has gained significant attention, prompting researchers to develop various methods, from conventional to hybrid optimization algorithms. Driven by the rapid growth of quantum computing capabilities, quantum approaches applied to optimization problems have attracted an increasing research effort. This work attempts to solve the permutation flow shop scheduling problem using quantum annealing by formulating the problem as a Quadratic Unconstrained Binary Optimization model (QUBO). Two QUBO formulations tailored to address the FSP are used. The first formulation is based on the position-based modelling while the second is based on five approximations of FSP as a Traveling Salesman Problem (TSP). The QUBO formulations are tested, using D-Wave's quantum annealers, on the well-known Taillard FSP benchmark and compared against each other. Results show that the proposed position-based QUBO reaches better solutions than the TSP-based QUBOs. This work is an attempt to highlight the increasing effectiveness of quantum annealers in addressing complex optimization problems and their limitations compared to conventional classical methods.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 14, 2024•4 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

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 +1 more

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

CINTI 2023 TOC

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

IEEE International Symposium on Computational Intelligence and Informatics (CINTI)•Nov 20, 2023•0 citations
In recent years, the Flow shop Scheduling Problem (FSP) has gained significant attention, prompting researchers to develop various methods, from conventional to hybrid optimization algorithms. Driven by the rapid growth of quantum computing capabilities, quantum approaches applied to optimization problems have attracted an increasing research effort. This work attempts to solve the permutation flow shop scheduling problem using quantum annealing by formulating the problem as a Quadratic Unconstrained Binary Optimization model (QUBO). Two QUBO formulations tailored to address the FSP are used. The first formulation is based on the position-based modelling while the second is based on five approximations of FSP as a Traveling Salesman Problem (TSP). The QUBO formulations are tested, using D-Wave's quantum annealers, on the well-known Taillard FSP benchmark and compared against each other. Results show that the proposed position-based QUBO reaches better solutions than the TSP-based QUBOs. This work is an attempt to highlight the increasing effectiveness of quantum annealers in addressing complex optimization problems and their limitations compared to conventional classical methods.
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.