Institute of Computer Science AGH and IBM Software Laboratory in Krakow invite to
Krakow Quantum Informatics Seminar (KQIS)
(KQIS is an official seminar of the Quantum Computing Section of the Computer Science Committee of the Polish Academy of Sciences)
https://www.informatyka.agh.edu.pl/en/kqi-seminars/
Tuesday, 19 November 2024, 9.35-11.00 via Teams
Marcin Kroczek
Faculty of Computer Science, AGH Krakow, PL
Decomposing algorithm for solving big workflow scheduling problems on D-Wave hybrid sampler
Abstract
Recent research has shown that solving Workflow Scheduling Problems (WSP) on both quantum [1] and hybrid (quantum-classical) [2] solvers is possible, but limited to small problem instances by solver capacity. During this seminar, we will present a graph decomposition algorithm that is based on the series-parallel graph concept [3] and utilizes its tree representation to divide workflow into independent parts. We will explain the process of obtaining decomposed subproblems, examining its advantages, limitations, and performance, with results from experiments conducted on the CQM hybrid solver using real-world workflow instances from the WFCommons repository.
References
[1] Dawid Tomasiewicz et al. “Foundations for Workflow Application Scheduling on D-Wave System”. In: Computational Science – ICCS 2020. Ed. by Valeria V. Krzhizhanovskaya et al. Cham: Springer International Publishing, 2020, pp. 516–530.
[2] Mateusz Hurbol. “Selected aspects of adapting the D-Wave annealer solutions to Workflow Management Systems”. MA thesis. AGH UST, 2022.
[3] Jacobo Valdes, Robert E. Tarjan, and Eugene L. Lawler. “The recognition of Series Parallel digraphs”. In: Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing. STOC ’79. Atlanta, Georgia, USA: Association for Computing Machinery, 1979, pp. 1–12.
Bio Marcin Kroczek is a graduate of the Faculty of Computer Science AGH Krakow, currently working as a software engineer in the airline travel industry.