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

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)

Enhanced QUBO Formulations for The Flow Shop Scheduling Problem

Yousra Farhani, Malak Saiem, Taha Arbaoui, Faicel Hnaien

Published Jul 14, 2024• 4 citations
Publisher

Abstract

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.

DOI
10.1145/3638530.3664150

Related papers

Manual vs. Automated QUBO Formulations for Flow Shop Scheduling: A Comparative Study on D-Wave and InfinityQ

Yousra Farhani, Taha Arbaoui, Karima Benatchba

Flow Shop Scheduling Problems (FSP) represent a challenging class of combinatorial optimization tasks with significant relevance across diverse domains ranging from manufacturing and logistics to service operations. Recent advances in quantum annealing and quantum-inspired approaches have opened avenues for tackling such problems via Quadratic Unconstrained Binary Optimization models. However, their performance depends strongly on how the problem is encoded as a QUBO. In this study, we perform a comparative evaluation of manually formulated QUBOs versus those automatically produced by the AutoQUBO framework. We test both formulations on D-Wave's hybrid and qbsolv solvers and the InfinityQ solver, exploring the effect of QUBO-solver-specific behaviors and sensitivity, and fine-tuning strategies on the quality of the solution. While carefully crafted manual QUBOs typically yield stronger solution fidelity, they demand greater domain expertise and computational overhead. In contrast, automated approaches greatly expedite modeling at the cost of certain performance trade-offs. We further observe that solver fine-tuning and hardware selection substantially shape outcomes, with certain solvers favoring domain-tailored encodings. These insights demonstrate the necessity of solver-aware QUBO design, offering practical guidance on QUBO construction and solver choice to solve the FSP using quantum and quantum-inspired hardware.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 14, 2025•1 citation

QUBO Model Formulation for Flow-shop Scheduling Problems with Changeover based on Timed Colored Petri Nets

Takuya Shinjo, Morikazu Nakamura, Norihiko Itani

Quadratic unconstrained binary optimization (QUBO) and Ising models are standard formats for the problem instance formulation of quantum annealing and quantum approximate optimization algorithm. This paper proposes a formulation method of QUBO models for flexible flow-shop scheduling problems with resource changeover based on timed colored Petri nets. The proposed method generates QUBO models for such practical flow-shop scheduling problems from Petri net firing rules, problem-specific constraints, and optimization criteria. The proposed method requires us to use only the domain knowledge of the target optimization problem and simple rules of Petri nets. Our method provides a low-cost formulation and reduces the hurdle to increasing the usability of quantum annealing and QAOAs.

International Symposium on Computing and Networking Workshops (CANDARW)•Nov 1, 2022•4 citations

Quantum solution for solving the Bin Packing problem

Samuel Deleplanque, Amélia Durbec, Amina El Yaagoubi

Quantum optimization shows significant potential in tackling complex combinatorial challenges, prompting our research exploration into the domain of quantum computing to address the Bin Packing Problem (BPP) through Quadratic Unconstrained Binary Optimization (QUBO) formulations. This work-in-progress paper outlines our proposal for a thorough study that encompasses classical bin packing formulations, initiating with the Mixed Integer Linear Program, followed by a comparative analysis of the corresponding QUBO representations, and adopting a structured approach of Quantum Annealing on the D-Wave machine. While our work is still in progress, continuous comparative analyses are being conducted to evaluate various QUBO formulations, derived from diverse classical bin packing models, aiming to identify the most efficient QUBO for addressing the BPP. On another front, efforts are dedicated to refining the solution process further, with a focus on enhancing the precision of the selected QUBO formulation.

International Conference on Control, Decision and Information Technologies (CoDIT)•Jul 1, 2024•1 citation

A Hybrid Framework Using a QUBO Solver For Permutation-Based Combinatorial Optimization

Siong Thye Goh, Sabrish Gopalakrishnan, Jianyuan Bo +1 more

In this paper, we propose a hybrid framework to solve large-scale permutation-based combinatorial problems effectively using a high-performance quadratic unconstrained binary optimization (QUBO) solver. To do so, transformations are required to change a constrained optimization model to an unconstrained model that involves parameter tuning. We propose techniques to overcome the challenges in using a QUBO solver that typically comes with limited numbers of bits. First, to smooth the energy landscape, we reduce the magnitudes of the input without compromising optimality. We propose a machine learning approach to tune the parameters for good performance effectively. To handle possible infeasibility, we introduce a polynomial-time projection algorithm. Finally, to solve large-scale problems, we introduce a divide-and-conquer approach that calls the QUBO solver repeatedly on small sub-problems. We tested our approach on provably hard Euclidean Traveling Salesman (E-TSP) instances and Flow Shop Problem (FSP). Optimality gap that is less than $10\%$ and $11\%$ are obtained respectively compared to the best-known approach.

arXiv:2009.12767•Sep 27, 2020•4 citations

Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware

Jiachen Zhang, Giovanni Lo Bianco, J. Christopher Beck

The emergence of specialized hardware, such as quantum computers and Digital/CMOS annealers, and the slowing of performance growth of general-purpose hardware raises an important question for our community: how can the high-performance, specialized solvers be used for planning and scheduling problems? In this work, we focus on the job-shop scheduling problem (JSP) and Quadratic Unconstrained Binary Optimization (QUBO) models, the mathematical formulation shared by a number of novel hardware platforms. We study two direct QUBO models of JSP and propose a novel large neighborhood search (LNS) approach, that hybridizes a QUBO model with constraint programming (CP). Empirical results show that our LNS approach significantly outperforms classical CP-based LNS methods and a mixed integer programming model, while being competitive with CP for large problem instances. This work is the first approach that we are aware of that can solve non-trivial JSPs using QUBO hardware, albeit as part of a hybrid algorithm.

Proceedings of the International Conference on Automated Planning and Scheduling•Jun 13, 2022•14 citations

Solving Scheduling Problems with Quantum Computing: a Study on Flexible Open Shop

Marco Baioletti, Angelo Oddi, Riccardo Rasconi

Despite quantum computing is revealing an increasingly promising technology that has the potential to introduce a significant speed-up in many areas of computation, the number of problems that it can represent and solve is currently rather limited. Therefore, one of the current challenges faced by the quantum computing community is to broaden the class of problems that can be tackled. Among these problems, scheduling problems are a class of particularly interesting and hard combinatorial problems; in this paper, we present a novel solution for representing and solving the Flexible Open Shop Scheduling Problem (FOSSP) to optimality by minimizing the makespan. We firstly present a compact formulation of this problem as a Quadratic unconstrained binary optimization (QUBO), which can be used to solve this problem with a quantum annealer. Then, we proceed to the Quantum Approximate Optimization Algorithm (QAOA) problem formulation, thus producing both the cost and mix Hamiltonians related to the problem. From the Hamiltonians, we provide the complete description of the quantum circuit that can be used to tackle the FOSSP within the QAOA framework. This second approach can be used to solve the optimization problem with a general-purpose quantum gate-based hardware.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 15, 2023•3 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.
Flow Shop Scheduling Problems (FSP) represent a challenging class of combinatorial optimization tasks with significant relevance across diverse domains ranging from manufacturing and logistics to service operations. Recent advances in quantum annealing and quantum-inspired approaches have opened avenues for tackling such problems via Quadratic Unconstrained Binary Optimization models. However, their performance depends strongly on how the problem is encoded as a QUBO. In this study, we perform a comparative evaluation of manually formulated QUBOs versus those automatically produced by the AutoQUBO framework. We test both formulations on D-Wave's hybrid and qbsolv solvers and the InfinityQ solver, exploring the effect of QUBO-solver-specific behaviors and sensitivity, and fine-tuning strategies on the quality of the solution. While carefully crafted manual QUBOs typically yield stronger solution fidelity, they demand greater domain expertise and computational overhead. In contrast, automated approaches greatly expedite modeling at the cost of certain performance trade-offs. We further observe that solver fine-tuning and hardware selection substantially shape outcomes, with certain solvers favoring domain-tailored encodings. These insights demonstrate the necessity of solver-aware QUBO design, offering practical guidance on QUBO construction and solver choice to solve the FSP using quantum and quantum-inspired hardware.
Quadratic unconstrained binary optimization (QUBO) and Ising models are standard formats for the problem instance formulation of quantum annealing and quantum approximate optimization algorithm. This paper proposes a formulation method of QUBO models for flexible flow-shop scheduling problems with resource changeover based on timed colored Petri nets. The proposed method generates QUBO models for such practical flow-shop scheduling problems from Petri net firing rules, problem-specific constraints, and optimization criteria. The proposed method requires us to use only the domain knowledge of the target optimization problem and simple rules of Petri nets. Our method provides a low-cost formulation and reduces the hurdle to increasing the usability of quantum annealing and QAOAs.
Quantum optimization shows significant potential in tackling complex combinatorial challenges, prompting our research exploration into the domain of quantum computing to address the Bin Packing Problem (BPP) through Quadratic Unconstrained Binary Optimization (QUBO) formulations. This work-in-progress paper outlines our proposal for a thorough study that encompasses classical bin packing formulations, initiating with the Mixed Integer Linear Program, followed by a comparative analysis of the corresponding QUBO representations, and adopting a structured approach of Quantum Annealing on the D-Wave machine. While our work is still in progress, continuous comparative analyses are being conducted to evaluate various QUBO formulations, derived from diverse classical bin packing models, aiming to identify the most efficient QUBO for addressing the BPP. On another front, efforts are dedicated to refining the solution process further, with a focus on enhancing the precision of the selected QUBO formulation.
In this paper, we propose a hybrid framework to solve large-scale permutation-based combinatorial problems effectively using a high-performance quadratic unconstrained binary optimization (QUBO) solver. To do so, transformations are required to change a constrained optimization model to an unconstrained model that involves parameter tuning. We propose techniques to overcome the challenges in using a QUBO solver that typically comes with limited numbers of bits. First, to smooth the energy landscape, we reduce the magnitudes of the input without compromising optimality. We propose a machine learning approach to tune the parameters for good performance effectively. To handle possible infeasibility, we introduce a polynomial-time projection algorithm. Finally, to solve large-scale problems, we introduce a divide-and-conquer approach that calls the QUBO solver repeatedly on small sub-problems. We tested our approach on provably hard Euclidean Traveling Salesman (E-TSP) instances and Flow Shop Problem (FSP). Optimality gap that is less than 10%10\%10% and 11%11\%11% are obtained respectively compared to the best-known approach.
The emergence of specialized hardware, such as quantum computers and Digital/CMOS annealers, and the slowing of performance growth of general-purpose hardware raises an important question for our community: how can the high-performance, specialized solvers be used for planning and scheduling problems? In this work, we focus on the job-shop scheduling problem (JSP) and Quadratic Unconstrained Binary Optimization (QUBO) models, the mathematical formulation shared by a number of novel hardware platforms. We study two direct QUBO models of JSP and propose a novel large neighborhood search (LNS) approach, that hybridizes a QUBO model with constraint programming (CP). Empirical results show that our LNS approach significantly outperforms classical CP-based LNS methods and a mixed integer programming model, while being competitive with CP for large problem instances. This work is the first approach that we are aware of that can solve non-trivial JSPs using QUBO hardware, albeit as part of a hybrid algorithm.
Despite quantum computing is revealing an increasingly promising technology that has the potential to introduce a significant speed-up in many areas of computation, the number of problems that it can represent and solve is currently rather limited. Therefore, one of the current challenges faced by the quantum computing community is to broaden the class of problems that can be tackled. Among these problems, scheduling problems are a class of particularly interesting and hard combinatorial problems; in this paper, we present a novel solution for representing and solving the Flexible Open Shop Scheduling Problem (FOSSP) to optimality by minimizing the makespan. We firstly present a compact formulation of this problem as a Quadratic unconstrained binary optimization (QUBO), which can be used to solve this problem with a quantum annealer. Then, we proceed to the Quantum Approximate Optimization Algorithm (QAOA) problem formulation, thus producing both the cost and mix Hamiltonians related to the problem. From the Hamiltonians, we provide the complete description of the quantum circuit that can be used to tackle the FOSSP within the QAOA framework. This second approach can be used to solve the optimization problem with a general-purpose quantum gate-based hardware.