Workflow decomposition algorithm for scheduling with quantum annealer-based hybrid solver Journal: Journal of Parallel and Distributed Computing
Marcin Kroczek, Justyna Zawalska, Katarzyna Rycerz · 2025
Read Workflow decomposition algorithm for scheduling with quantum annealer-based hybrid solver Journal: Journal of Parallel and Distributed Computing by Marcin Kroczek, Justyna Zawalska, Katarzyna Rycerz (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-01567.txt.
Introduction
Marcin Kroczek, Justyna Zawalska, and Katarzyna Rycerz split big scheduling problems so a quantum device can chew them piece by piece. Their 2025 paper addresses workflow scheduling, the assigning of linked task chains to machines. A hybrid solver that pairs a D-Wave quantum device with classical machinery has size limits, and real workflows blow past them.
Their heuristic, built for series-parallel workflows, decomposes an oversized problem into pieces the solver can accept, then reassembles a schedule. Tests used real workflow descriptions from a public standardization repository, run in an execution environment the authors describe alongside the algorithm. The claim is practical: the split extends the hybrid solver's reach to jobs that would otherwise not fit. The authors present the method as infrastructure for a period when quantum hardware helps at the margins of classical scheduling.
Catalog record
| CREATOR | Marcin Kroczek, Justyna Zawalska, Katarzyna Rycerz |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 35 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-01567
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Workflow decomposition algorithm for scheduling with quantum annealer-based hybrid solver Journal: Journal of Parallel and Distributed Computing Marcin Kroczek, Justyna Zawalska, Katarzyna Rycerz Abstract We introduce the Series-Parallel Workflow Decomposition (SPWD) heuristic algorithm for the Workflow Scheduling Problem (WSP) decomposition. We demonstrate that the SPWD algorithm facilitates the scheduling of large WSP instances with the hybrid D-Wave Constrained Quadratic Model solver, enabling the scheduling of instances that would otherwise exceed its capacity limitations. We also describe the accompanying execution environment used to obtain the results of the experiments with real-life workflow instances available in the WfCommons standardization initiative repository. † † graphicalabstract: † † highlights: proposition of a new SPWD algorithm that enhances the capacity of the hybrid classical-quantum CQM solver when solving a workflow scheduling optimization problem; experimental analysis of the algorithm with real-life workflows data from the WfCommons repository; a fully functional execution environment for performing aforementioned experiments. 1 Introduction A scientific workflow is an application model expressed as a Directed Acyclic Graph (DAG) of many tasks. Important problems in the field of astronomy [ 1 ] , bioinformatics [ 2 ] , high-energy physics [ 3 ] or computational medicine [ 4 ] can be expressed this way. The model is popular, so initiatives like the WfCommons framework [ 5 ] have been proposed to standardize the description of various real-life workflow applications. WfCommons is also a repository for execution logs, which can be used as a reliable data source in research on the quality of workflow scheduling. Over the past few years, there have been several scientific publications focusing on the application of quantum computing to solve the problem of assigning workflow tasks to machines in a cloud environment, i.e., the Workflow Scheduling Problem. The foundations for research in this field were established in [ 6 ] , where schedules for small examples of WSP were successfully found using the D-Wave 2000Q pure quantum annealer. However, the proposed approach struggled to solve larger problem instances. Since the publication of this research, the capacity and architecture of quantum annealers have been improved. Furthermore, the supporting software has been expanded, in particular with the hybrid solver set provided by D-Wave [ 7 ] . This led to further research [ 8 ] on solving WSPs using D-Wave’s hybrid solver designed for problems expressed as a Constrained Quadratic Model (CQM) [ 9 ] . The results were promising, but also indicated capacity limitations for larger problems. In this paper, we investigate the limitations of the hybrid CQM solver in more detail and propose a solution to overcome them and obtain meaningful results. To achieve this goal, we designed a new heuristic algorithm for the WSP decomposition called the Series-Parallel Workflow Decomposition (SPWD). The algorithm is based on the concept of series-parallel DAGs [ 10 ] and is applied to produce reduced-size problems that are then solved independently by an external solver of choice, and finally the results are combined into the final schedule. Moreover, we integrated our algorithm with the QHyper library [ 11 ] . This allowed us to build a flexible environment for experiments that gets WfCommons workflow data and transforms it into a problem description that is accepted by both the hybrid classical-quantum CQM solver and the classical Gurobi optimizer [ 12 ] , which we used as a reference method [ 11 ] . Experimental results on the most popular families of real-life workflows available in the WfCommons repository show that the proposed SPWD algorithm combined with CQM finds schedules that were previously unattainable through the exclusive use of CQM. Additionally, we present the impact of both the number of binary variables and the amount of constraints on scheduling quality. Since the CQM solver is available for independent researchers as a black-box solution, such experiments are also important to investigate its implicit behavior. Apart from the main research objective, the presented algorithm can also be used in strictly classical scenarios when the workflow scheduling problem is too large to be solved in a single attempt. To summarize, our paper offers the following contributions: 1. proposition of a new SPWD algorithm that enhances capacity of hybrid classical-quantum CQM solver when solving workflow scheduling optimization problem; 2. experimental analysis of the algorithm with real-life workflows data from WfCommons repository; 3. fully functional execution environment for performing aforementioned experiments. The paper is organized as follows: the necessary basic concepts can be found in Section 2 and the overview of the related work is described in Section 3 . Section 4 explains the SPWD algorithm in detail and Section 5 presents its time complexity analysis. The execution environment is shown in Section 6 . The results are presented in Section 7 . Section 8 contains the conclusion. 2 Preliminaries In this Section, we provide an overview of the key concepts necessary for understanding the solution presented in this paper. Definition 1 (Workflow Scheduling Problem (WSP)) The WSP [ 6 ] is defined with the following input data: 1. DAG G with t nodes (tasks) and e edges that defines the structure of a workflow including the paths set P of p paths between the workflow’s roots and leaves. 2. Time matrix \mathnormal{T}=[\tau_{i,j}]_{t\times m} , where t is the number of tasks and m is the number of machines. This matrix contains information about the execution time of each task on each available machine. 3. Machine cost vector K=[k_{i}]_{m} . Contains the price of using each machine for a unit of time. This vector, in connection with the time matrix, allows one to calculate the cost of running a task on a given machine, which can be represented as the matrix \mathnormal{C}=[c_{i,j}]_{t\times m} . 4. Deadline d is an integer that imposes the time limit for the execution of the workflow. The goal is to assign tasks to machines in a way that minimizes the overall cost of running the workflow, given deadline restrictions. The common requirement when using pure quantum devices is to express optimization problems as Quadratic Unconstrained Binary Optimization (QUBO) functions [ 13 ] . To formulate QUBO for WSP, a cost function and its constraints have to be combined using the so-called penalty weights [ 6 ] . Setting that hyperparameter for an arbitrary WSP is a nontrivial problem. Therefore, for our experiments, we chose a different solution, that is, the aforementioned CQM, a hybrid classical-quantum version of the D-Wave solver, since it allows us to provide constraints and the cost function separately, in the form of quadratic and linear functions of binary, integer, or continuous variables [ 9 ] . Unfortunately, due to the proprietary implementation, the details of using a quantum processing unit by the D-Wave’s CQM solver are hidden from the users. The solution presented in this paper allows for investigation of the black-box CQM solver properties. Definition 2 (WSP formulation for CQM) For each possible pair (task, machine), we set the binary variable x_{i,j}=1 if task i is assigned to machine j , and 0 otherwise. 1. The goal is to minimize the overall cost of a schedule: \sum_{t}\sum_{m}c_{t,m}\cdot x_{t,m} (1) 2. In order to assure that each task is run on exactly one machine, the set of one-hot constraints is defined: