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.
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.
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.
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.
Quantum annealing is an emerging new platform for combinatorial optimization, requiring an Ising model formulation for optimization problems. The formulation can be an essential obstacle to the permeation of this innovation into broad areas of everyday life. Our research is aimed at the proposal of a Petri net modeling approach for an Ising model formulation. Although the proposed method requires users to model their optimization problems with Petri nets, this process can be carried out in a relatively straightforward manner if we know the target problem and the simple Petri net modeling rules. With our method, the constraints and objective functions in the target optimization problems are represented as fundamental characteristics of Petri net models, extracted systematically from Petri net models, and then converted into binary quadratic nets, equivalent to Ising models. The proposed method can drastically reduce the difficulty of the Ising model formulation.
Quantum optimization which is the use of quantum computers and algorithms for solving complex optimization problems, is one of the topics in quantum computing with the highest potential. Two types of approaches are generally used to solve combinatorial optimization problems with quantum computers: exact methods such as the Grover’s search algorithm, and meta-heuristics such as the Quantum Annealing and the Quantum Approximate Optimization Algorithm (QAOA). Exact methods and variational methods like QAOA make use of universal gate-based quantum computers, such as the ones developed by the IBM company.Quantum annealing is designed for analogic quantum computers developed by D-Wave. Solving a combinatorial optimization problem with heuristics generally requires a transformation of the problem to a format suitable for the quantum computer. While some existing frameworks can cope with Constrained Quadratic Models (CQM), Quadratic Unconstrained Binary Optimization (QUBO) is the best option to map an optimization problem to a quantum computer or simulator. We consider in this paper the job shop scheduling problem.
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.
Large-scale combinatorial scheduling problems -- job-shop scheduling, flow-shop scheduling, and vehicle routing among them -- remain NP-hard at practically relevant scale, and quantum computing has entered this space along two related tracks: genuinely quantum solvers, principally quantum annealers and gate-based devices running the quantum approximate optimization algorithm (QAOA), and quantum-inspired classical solvers, such as coherent Ising machines and digital annealers, that borrow the same Ising/QUBO problem structure without requiring quantum hardware. This article synthesizes both tracks as applied specifically to scheduling. We trace the theoretical foundations from quantum and simulated annealing through the QUBO formulation techniques that make scheduling problems solver-ready, then review direct applications to job-shop, flow-shop, and vehicle-routing problems, reporting the concrete, verified numbers the underlying studies provide. The consistent finding is that quantum hardware remains constrained by qubit connectivity, embedding overhead, and shallow achievable circuit depth to small benchmark instances, while quantum-inspired classical solvers, unconstrained by qubit count, already reach scheduling-relevant problem sizes with reported performance competitive with or exceeding classical heuristics. We close by identifying benchmarking rigor, hardware connectivity, and the near-total absence of work on dynamic, online scheduling as the field's clearest open problems.