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.
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.
Heterogeneous HPC workflow scheduling under multiple hard constraints poses a challenging combinatorial optimization problem. Classical exact solvers provide optimal solutions but often face scalability limitations, motivating interest in quantum-inspired Quadratic Unconstrained Binary Optimization (QUBO) formulations as alternative optimization paradigms. This work presents a systematic and reproducible empirical evaluation of QUBO-based scheduling methods against established classical baselines, including MILP, CP-SAT, GA, and HEFT. We evaluate three QUBO variants, single-run simulated annealing, multi-attempt annealing, and a layered QAOA-inspired schedule, together with hybrid enhancement strategies on both ground-truth validation workflows (3–4 tasks) and synthetic scaling instances (5–20 tasks). All solvers are assessed through a unified evaluation pipeline that explicitly tracks feasibility, makespan, and resource utilization under progressive constraint activation and controlled penalty sweeps. Results show that all approaches recover the expected optimal makespan on validation instances, confirming formulation correctness. However, feasibility degradation emerges for specific QUBO variants as constraint interactions intensify, particularly when communication costs are introduced. Penalty sensitivity analysis reveals a sharp feasibility threshold for QUBO-SA, where insufficient penalties consistently fail and moderate-to-strong penalties restore feasibility. Scaling experiments delineate the regimes in which classical solvers and heuristics remain robust across all tested sizes, while QUBO-SA loses feasibility beyond 15 tasks and the QAOA-inspired variant beyond 10 tasks. Overall, the study provides a clear empirical characterization of the reliability boundaries of quantum-inspired QUBO formulations for heterogeneous HPC scheduling and identifies the regimes where classical approaches remain preferable under current formulations and solver capabilities.
Heterogeneous HPC workflow scheduling under multiple hard constraints poses a challenging combinatorial optimization problem. Classical exact solvers guarantee optimality but face scalability limits, motivating interest in quantum-inspired Quadratic Unconstrained Binary Optimization (QUBO) as an alternative optimization paradigm. This work presents a systematic empirical evaluation of QUBO-based scheduling methods against classical baselines including MILP, CP-SAT, GA, and HEFT. We evaluate three QUBO variants, single-run simulated annealing, multi-attempt annealing, and a layered QAOA-inspired schedule, with hybrid enhancement strategies on validation workflows (3-4 tasks) and synthetic scaling instances (5-20 tasks). All solvers are assessed through a unified pipeline tracking feasibility, makespan, and resource utilization under progressive constraint activation and controlled penalty sweeps. All approaches recover the expected optimal makespan on validation instances, confirming formulation correctness. However, feasibility degradation emerges for specific QUBO variants as constraint interactions intensify, particularly when communication costs are introduced. Penalty analysis reveals a sharp feasibility threshold for QUBO-SA, where insufficient penalties consistently fail and moderate-to-strong penalties restore feasibility. Scaling experiments show that classical solvers remain robust across all tested sizes, while QUBO-SA loses feasibility beyond 15 tasks and the QAOA-inspired variant beyond 10 tasks. The study provides a clear empirical characterization of the reliability boundaries of quantum-inspired QUBO formulations for HPC scheduling and identifies regimes where classical approaches remain preferable under current solver capabilities.
The Multi-Knapsack Problem (MKP) is a fundamental challenge in operations research and combinatorial optimization. Quantum computing introduces new possibilities for solving MKP using Quadratic Unconstrained Binary Optimization (QUBO) models. However, a key challenge in QUBO formulations is the selection of penalty parameters, which directly influence solution feasibility and algorithm performance. In this work, we develop QUBO formulations for two MKP variants—the Multidimensional Knapsack Problem (MDKP) and the Multiple Knapsack Problem (MUKP)—and provide an algebraic characterization of their penalty parameters. We systematically evaluate their impact through quantum simulation experiments and compare the performance of the two leading quantum optimization approaches: Quantum Approximate Optimization Algorithm (QAOA) and quantum annealing, alongside a state-of-the-art classical solver. Our results indicate that while classical solvers remain superior, careful tuning of penalty parameters has a strong impact on quantum optimization outcomes. QAOA is highly sensitive to parameter choices, whereas quantum annealing produces more stable results on small to mid-sized instances. Further, our results reveal that MDKP instances can maintain feasibility at penalty values below theoretical bounds, while MUKP instances show greater sensitivity to penalty reductions. Finally, we outline directions for future research in solving MKP, including adaptive penalty parameter tuning, hybrid quantum-classical approaches, and practical optimization strategies for QAOA, as well as real-hardware evaluations.
This paper investigates the use of Quantum Annealing (QA) devices for optimizing unit scheduling in renewable energy systems, addressing the challenge of energy balancing with intermittent generation. We compare two approaches for encoding inequality constraints in Quadratic Unconstrained Binary Optimization (QUBO) formulations: (a) the conventional slack-variable-based method and (b) a novel soft-encoding technique called unbalanced penalization. This first application of unbalanced penalization in the energy and power systems domain, aims to disseminate knowledge about near-term applications of quantum-computing and how to make best use of it within the community. Through computational experiments, we find thatUnbalanced Penalizationconsistently outperforms the conventional method of using slack variables by reducing the number of variables in the QUBO formulation. Despite this, its inherent nature penalizes feasible solutions unevenly, preventing the ability to handle much larger problem sizes. More broadly, we observe that both methods-like most pure quantum approaches-struggle with scalability on current QA hardware, as solution quality declines with increasing problem size. In light of these limitations, we assess the feasibility of purely quantum solutions and argue that hybrid approaches remain the most practical path forward.
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.
Constrained knapsack variants are well-suited for QUBO-based quantum optimization, but adding logical relations can inflate the binary model and complicate penalty selection. This work examines the multi-dimensional knapsack problems augmented with conflict, forcing, and precedence (CFP) constraints using Quadratic Unconstrained Binary Optimization (QUBO) models across classical and quantum platforms. The additional logical constraints are incorporated through quadratic penalty terms that modify existing QUBO coefficients without introducing additional binary variables beyond the slack variables used for the capacity constraints. Computational studies are conducted to assess how each of the three constraint types affects solution behavior, including solution quality, computation time, and sensitivity to penalty parameter magnitudes. The approach is demonstrated on representative small-scale instances using QAOA on IBM Quantum gate-based device and quantum annealing on a D-Wave Advantage processor, with results compared with Gurobi as classical solver. The experiments show that the proposed QUBO formulations achieve optimal or near-optimal solutions for small instances, while showing the sensitivity of current quantum hardware to penalty selection, and scaling. Overall, CFP penalties are variable-neutral relative to the slack-based capacity representation, while the capacity terms dominate logical-qubit count and coupling density. Future work may target more compact or hardware-aware capacity modeling.