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

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 Infini-tyQ 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 domaintailored 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. CCS CONCEPTS • Theory of computation → Quantum computation; Quantum algorithms, protocols, and simulations; Design and analysis of algorithms; • Mathematics of computing → Mathematical optimization; Solvers.