Workflow decomposition algorithm for scheduling with quantum annealer-based hybrid solver

Although quantum devices are considered a promising approach to combinatorial optimization problems, their limited capacity remains a serious bottleneck for research in this area. An important scenario in this context concerns the allocation of workflow applications to computational infrastructure resources. To address this limitation, we introduce the Series-Parallel Workflow Decomposition (SPWD) algorithm, a heuristic that maps a workflow structure to a Two-Terminal Series-Parallel graph, constructs its binary decomposition tree, and uses this tree to obtain a global view of workload and deadline distribution. The tree is then pruned to produce subworkflows of bounded size that can be solved independently by low-capacity solvers and subsequently merged into the final schedule. We demonstrate that the SPWD algorithm facilitates solving large workflow scheduling problem instances with the hybrid D-Wave Constrained Quadratic Model (CQM) solver, enabling the handling of instances that would otherwise exceed its capacity limitations. Experiments on real-world workflows from the WfCommons standardization initiative repository show that SPWD enables CQM to solve instances beyond its native capacity with a relatively low cost increase (up to 17.5%) compared to the reference Gurobi solver. Additionally, we demonstrate that the SPWD algorithm reduces the runtime of the solvers optimization subroutine, although this is achieved by increasing the local computational load caused by the decomposition. However, under a hypothetical cloud-based pay-as-you-go billing model, such a trade-off may be beneficial, as it shortens the time charged for solver execution while shifting additional work to the local side.