The Operational Fixed Interval Scheduling Problem aims to find an assignment of jobs to machines that maximizes the total weight of the completed jobs. We introduce a new variant of the problem where we consider the additional goal of minimizing the idle time, the total duration during which the machines are idle. The problem is expressed using quadratic unconstrained binary optimization (QUBO) formulation, taking into account soft and hard constraints required to ensure that the number of jobs running at a time point is desirably equal to the number of machines. Our choice of QUBO representation is motivated by the increasing popularity of new computational architectures such as neuromorphic processors, coherent Ising machines, and quantum and quantum-inspired digital annealers for which QUBO is a natural input. An optimization problem that can be solved using the presented QUBO formulation is the music reduction problem, the process of reducing a given music piece for a smaller number of instruments. We use two music compositions to test the QUBO formulation and compare the performance of simulated, quantum, and hybrid annealing algorithms.
The Operational Fixed Interval Scheduling Problem aims to find an assignment of jobs to machines that maximizes the total weight of the completed jobs. We introduce a new variant of the problem where we consider the additional goal of minimizing the idle time, the total duration during which the machines are idle. The problem is expressed using quadratic unconstrained binary optimization (QUBO) formulation, taking into account soft and hard constraints required to ensure that the number of jobs running at a time point is desirably equal to the number of machines. Our choice of QUBO representation is motivated by the increasing popularity of new computational architectures such as neuromorphic processors, coherent Ising machines, and quantum and quantum-inspired digital annealers for which QUBO is a natural input. An optimization problem that can be solved using the presented QUBO formulation is the music reduction problem, the process of reducing a given music piece for a smaller number of instruments. We use two music compositions to test the QUBO formulation and compare the performance of simulated, quantum, and hybrid annealing algorithms.
Resource constrained project scheduling and related allocation tasks can be expressed as Quadratic Unconstrained Binary Optimization (QUBO) models and submitted to quantum annealers. This paper develops the QUBO formulation in detail: choice of binary variables, linear and quadratic objective terms, conversion of precedence and resource constraints into penalty functions, and calibration of penalty weights. The resulting Hamiltonian is embedded onto quantum hardware, annealed, and post-processed. Hybrid classical–quantum workflows that wrap the QUBO solver inside Monte Carlo risk analysis or a digital twin are examined. Supporting process flowcharts and energy-landscape figures illustrate every stage. The treatment remains grounded in construction and logistics applications while remaining transferable to other combinatorial domains such as ULD configuration. Keywords: QUBO formulation; quantum annealing; Ising model; penalty methods; resource-constrained project scheduling; hybrid quantum-classical; minor embedding; Monte Carlo; digital twin.
This paper investigates several Quadratic Unconstrained Binary optimisation (QUBO) formulations for the parallel machine scheduling problem P m | | C max with the goal of assessing their suitability for quantum annealing and related heuristic optimisation methods. Three QUBO models are constructed, ranging from formulations derived from classical integer and one-hot encodings to a more compact load-balancing based representation. Extensive computational experiments using Simulated Annealing (SA) and Quantum Annealing (QA) reveal substantial differences in scalability and solution quality among the formulations. The alternative load-balanced model consistently yields near-optimal makespans, typically within 1%–3% of the theoretical lower bound, highlighting its stability and effectiveness compared to the more penalty sensitive formulations, whose performance deteriorates for larger instances. Sensitivity analyses further reveal that the appropriate selection of penalty weights and problem-specific parameter tuning significantly influences both solution accuracy and computational effort in QUBO formulations. While current quantum hardware limitations restrict experimentation to small problem sizes, the findings illustrate how compact QUBO designs can better exploit quantum optimisation frameworks. The insights gained in this study provide practical modelling guidelines for future quantum scheduling research and lay the groundwork for extending QUBO-based approaches to more complex scheduling environments. • Three QUBO formulations are compared for identical parallel machine scheduling. • A compact load-balancing QUBO avoids auxiliary variables. • Load balancing yields makespans on average within 1–3%. • Both simulated and quantum annealing produce near-optimal schedules. • Penalty selection and encoding strongly affect scalability and solution quality.
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.
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.
Abstract In this paper, a quantum computer-aided approach to job scheduling for automated storage and retrieval systems is introduced. The approach covers application cases, where various objects need to be transported between storage positions and the order of transport operations can be freely chosen. The objective of job scheduling is to arrange the transport operations in a sequence, where the cumulative costs of the transport operations and empty runs between subsequent transport operations are minimized. The scheduling problem is formulated as an asymmetric quadratic unconstrained binary optimization (QUBO) problem, in which the transport operations are modeled as nodes and empty runs are modeled as edges, with costs assigned to each node and each edge. An Quantum Approximate Optimization Algorithm (QAOA) is used to solve the QUBO. Evaluations of the quantum computer-aided job scheduling approach have been conducted on the IBM Q System One quantum computer in Ehningen. In particular, the running time for the solution of the QUBO has been investigated, as well as the scalability of the approach with respect to the required number of qubits.
The problem of finding the maximum weighted cycle in a directed graph maps to optimization problems in NP, implying that approaches in classical computing are inefficient. Here, Quantum computing might be a promising alternative. Many current approaches on the quantum computer are based on a Quadratic Unconstrained Binary Optimization (QUBO) problem formulation. This paper develops four different QUBO approaches to this problem. The first two take the starting vertex and the number of vertices used in the cycle as given, while the latter two loosen the second assumption of knowing the size of the cycle. A QUBO formulation is derived for each approach. Further, the number of binary variables required to encode the maximum weighted cycle problem with one or both assumptions for the respective approach is made explicit. The problem is motivated by finding the maximum weighted debt cycle in a debt graph. This paper compares classical computing versus currently avaiable (hybrid) quantum computing approaches for various debt graphs. For the classical part, it investigated the Depth-First-Search (DFS) method and Simulated Annealing. For the (hybrid) quantum approaches, we utilized direct embedding on the quantum annealer and two types of quantum hybrid solvers. Simulated Annealing and the usage of the hybrid CQM (Constrained Quadratic Model) machine functioned promising. The DFS method, direct QPU, and hybrid BQM (Binary Quadratic Model), on the other hand, performed less, due to memory issues, surpassing the limit of decision variables, and finding the right penalty values, respectively.