Realizing distributed architectures for quantum computing is crucial to scaling up computational power. A key component of such architectures is a scheduler that coordinates operations over a short-range quantum network required to enable the necessary non-local entangling gates between quantum processing units (QPUs). It is desirable to determine schedules of minimum make span, which in the case of networks with constrained resources hinges on their efficient usage. Here we compare and contrast two approaches to solving the make span minimization problem, an approach based on the resource constrained project scheduling (RCPSP) framework, and another based on a greedy heuristic algorithm. The workflow considered is as follows. Firstly, the computational circuit is partitioned and assigned to different QPUs such that the number of nonlocal entangling gates acting across partitions is minimized while the qubit load is nearly uniform on the individual QPUs, which can be accomplished using, e.g., the METIS solver. Secondly, the nonlocal entangling gate requirements with respect to the partitions are identified, and mapped to network operation sequences that deliver the necessary entanglement between the QPUs. Finally, the network operations are scheduled such that the make span is minimized. As illustrative examples, we analyze the implementation of a small instance of the Quantum Fourier Transform algorithm over instances of a simple hub and spoke (star) network architecture comprised of a quantum switch as the hub and QPUs as spokes, each with a finite qubit resource budget. In one instance, our results show the RCPSP approach outperforming the greedy heuristic. In another instance, we find the two performing equally well. Our results thus illustrate the effectiveness of the RCPSP framework, while also underlining the relevance and usefulness of greedy heuristics.
Quantum annealing emerges as a promising approach for tackling complex scheduling problems such as the resource-constrained project scheduling problem (RCPSP). This study represents the first application of quantum annealing to solve the RCPSP, analyzing 12 well-known mixed integer linear programming (MILP) formulations and converting the most qubit-efficient one into a quadratic unconstrained binary optimization (QUBO) model. We then solve this model using the D-wave advantage 6.3 quantum annealer, comparing its performance against classical computer solvers. Our results indicate significant potential, particularly for small to medium-sized instances. Further, we introduce time-to-target and Atos Q-score metrics to evaluate the effectiveness of quantum annealing and reverse quantum annealing. The paper also explores advanced quantum optimization techniques, such as customized anneal schedules, enhancing our understanding and application of quantum computing in operations research.
Overview This deposition provides the theoretical framework, mathematical formulations, and benchmarking protocol for the Refinery Turnaround Activity Scheduling Problem with Spatial Hazards (RTASP-SH). The research formally evaluates the performance of Superconducting Quantum Annealing (D-Wave QPU), Hybrid Classical-Quantum Solvers (D-Wave Leap CQM), and state-of-the-art classical Constraint Programming (Google OR-Tools CP-SAT) under strict semantic symmetry. A central contribution of this work is addressing prevalent methodological deficiencies in quantum optimization literature—specifically asymmetric constraint modeling (e.g., omitting hard cumulative resource limits in QUBO/Ising models while retaining them in classical baselines) and the conflation of model compilation latency with computational execution time. Core Scientific Contributions Formal Problem Characterization (RTASP-SH): An industrial extension of the strongly
NP-hard Resource-Constrained Project Scheduling Problem (RCPSP), incorporating renewable cumulative resources and pairwise disjunctive spatial hazards (e.g., co-located hot work and explosive hydrocarbon atmospheres). Graph-Theoretic Sanitization: Algorithmic preprocessing pipeline establishing provable minimum/maximum makespan horizons (
Hmin=CPM(V,E0),
Hmax=∑di), computing transitive reductions
TR(E0) to eliminate topological redundancies, and filtering out pseudo-disjunctive spatial conflicts between transitively reachable nodes via the reachability closure
TC(E0). Semantically Symmetrical Dual Formulations: Constraint Programming (CP-SAT): Native non-preemptive interval variables utilizing Lazy Clause Generation (LCG), global energetic reasoning (Cumulative), and disjunctive propagation (NoOverlap). Time-Indexed Constrained Quadratic Model (CQM): Exact binary time-indexed representation enforcing execution uniqueness, makespan bounding on DAG sink tasks
Tsink, discrete-time cumulative capacity constraints, and time-step disjunctive spatial conflicts. Analytical Proof of Physical QPU Limitations (Proposition 1): Mathematical demonstration of why binary slack variable expansions for cumulative constraints induce quadratic coupling coefficients
Jij∝λCr2. This dynamic range expansion forces the coupling ratio below the physical Intrinsic Control Error (
σICE≈10−2Jmax) and DAC resolution limits of physical flux qubits, proving that un-decomposed pure QPU annealing fails to yield feasible ground states. Slack-Free Hybrid Decomposition (LNS-MWIS): A decomposition-based Large Neighborhood Search (LNS) paradigm where the classical CP-SAT master problem manages global temporal constraints and cumulative resource ceilings, delegating congested, conflict-free Maximum Weight Independent Set (MWIS) subproblems to the quantum annealer without introducing slack variables. Methodological Protocol and Metrics To support reproducible benchmarking, the artifacts define rigorous evaluation criteria: Feasibility Ratio (
Rfeas): Strict verification of 100% compliance across cumulative and disjunctive constraints across all generated samples. Time-to-Target (TTT): Exact wall-clock solving trajectories required to reach certified bounds within 2% of
Hmin. Overhead Separation: Granular profiling separating Python SDK instantiation/graph construction time from actual QPU/hybrid cloud solver execution time. Citation & Metadata @article{usai2026benchmarking, title = {Benchmarking Quantum and Hybrid Annealing on Refinery Turnaround Scheduling: A Rigorous Assessment against Constraint Programming and Mixed-Integer Formulations}, author = {Usai, Luigi}, year = {2026}, doi = {10.5281/zenodo.XXXXXXX}, publisher = {Zenodo}, note = {ORCID: 0009-0003-3001-717X} } Keywords: Quantum Annealing, D-Wave CQM, Turnaround Scheduling, RCPSP, CP-SAT, Constraint Programming, Maximum Weight Independent Set, Intrinsic Control Error, Operations Research, Mathematical Optimization.