What the study found
The study found that the Series-Parallel Workflow Decomposition (SPWD) algorithm can help a hybrid quantum solver handle workflow scheduling instances that would otherwise exceed its capacity. It also found that this comes with a relatively low cost increase compared with a reference solver.
Why the authors say this matters
The authors suggest that SPWD may make it possible to use low-capacity solvers on larger workflow scheduling problems. They also conclude that, under a hypothetical cloud pay-as-you-go billing model, reducing solver runtime while shifting extra work locally may be beneficial.
What the researchers tested
The researchers introduced SPWD, a heuristic for workflow scheduling that maps a workflow to a Two-Terminal Series-Parallel graph, builds a binary decomposition tree, and prunes it into smaller subworkflows. These subworkflows are then solved independently and merged into a final schedule using the hybrid D-Wave Constrained Quadratic Model (CQM) solver. They tested the approach on real-world workflows from the WfCommons standardization initiative repository.
What worked and what didn't
SPWD enabled the CQM solver to solve instances beyond its native capacity. The reported cost increase was up to 17.5% compared with the reference Gurobi solver, and the optimization subroutine runtime was reduced. At the same time, the decomposition increased local computational load.
What to keep in mind
The available summary does not describe detailed limitations beyond the trade-off between lower solver runtime and higher local computation. The cost comparison is reported against Gurobi on the tested real-world workflows, so the result is scoped to that setting.
- SPWD is a heuristic for decomposing workflow scheduling problems into smaller parts.
- The approach let a hybrid D-Wave CQM solver handle instances beyond its native capacity.
- Reported cost increase versus Gurobi was up to 17.5%.
- The optimization subroutine ran faster, but local computational load increased.
- The authors note possible benefit under a cloud pay-as-you-go billing model.
