2022/05/10 by A. I. Pakhomchik, S. Yudin, Pakhomchik, A. I. +9 · 1 citation
Computer Science · Physics and Astronomy · #Cloud Computing and Resource Management #Parallel Computing and Optimization Techniques #Quantum Computing Algorithms and Architecture #quant-ph
paper · pdf · doi:10.48550/arxiv.2205.04844
10 pages, 6 figures
arxiv created 2022/05/10 · arxiv updated 2022/05/11
In this paper we investigate the workflow scheduling problem, a known NP-hard class of scheduling problems. We derive problem instances from an industrial use case and compare against several quantum, classical, and hybrid quantum-classical algorithms. We develop a novel QUBO to represent our scheduling problem and show how the QUBO complexity depends on the input problem. We derive and present a decomposition method for this specific application to mitigate this complexity and demonstrate the effectiveness of the approach.