IX International scientific and practical conference �“Applied information systems and technologies in the digital society” �(AISTDS-2025) Kyiv, Ukraine 01 October�

1

GRAPH-BASED APPROACH TO THE SYNTHESIS OF AN ALGORITHM FOR PARALLEL SOLVING OF INTERRELATED ORGANIZATIONAL TASKS USING VERTEX SEPARATION

​

Yuri Samokhvalov, Eduard Bovda Viktor Klimenko and Dmytro Ustynov

1. Introduction

Applied information systems and technologies in the digital society, October 01, 2025, Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

Organizational tasks represent a set of management and coordination activities that arise in the functioning of organizations and their structural units. A distinguishing feature of such tasks is their complexity and interdependence, which necessitates the application of methods for their efficient solution. The process of solving an organizational task includes the formulation of the initial task by a manager, its decomposition into subtasks, the distribution of subtasks among performers, their parallel solution, and the integration of results into a single decision. This approach is characteristic both for the entire organization and its individual structural units.

A key aspect of this process is the parallel solution of subtasks. Independent subtasks can be solved simultaneously by different performers, whereas interrelated subtasks require coordination of results or adherence to a specific execution order. At the same time, subtasks may be linked either by their final results or by intermediate results.

To formalize the process of parallel subtask solving, graph models are widely used. The report offers one of the possible approaches to solving interrelated organizational problems using graph models and the vertex separation method.

Applied information systems and technologies in the digital society, October 01, 2025, Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

Problem Statement of Algorithm Synthesis for Solving Organizational Tasks.

Applied information systems and technologies in the digital society, October 01, 2025, Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

Construction of the Graph Structure.

Determination of Minimum and Maximum Time.

A fuzzy statement “the execution time of the task is approximately within the interval from a to b”.

Calculation of Distances Between Transition Points

Applied information systems and technologies in the digital society, October 01, 2025, Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

The algorithm for calculating the distance between transition points for numbers greater than 99.

Determination of the Most Probable Time.

Applied information systems and technologies in the digital society, October 01, 2025, Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

Network graph

As noted, the interdependence of tasks may occur at the level of final results as well as intermediate results of other tasks. Such results can be considered as alternative sources of information, and their use represents additional solution variants for the tasks. The formation of this variant is based on the separation of the consumer vertex.

Applied information systems and technologies in the digital society, October 01, 2025, Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

Separation of the consumer vertex

Applied information systems and technologies in the digital society, October 01, 2025, Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

Graph structure of task solution algorithms

Applied information systems and technologies in the digital society, October 01, 2025, Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

Finding the Shortest Path in the Graph Structure.

Applied information systems and technologies in the digital society, October 01, 2025, Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

Linking solution variants of adjacent tasks.

Step 2. For each pair of related problems, connections between their variants are established.

Applied information systems and technologies in the digital society, October 01, 2025, Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

Graph of solution variants for three tasks.

Applied information systems and technologies in the digital society, October 01, 2025, Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

Conclusions.

The proposed approach allows for the synthesis of an algorithm for the parallel solution of related organizational tasks. First, the main variants of the solution for the entire set of tasks are formed in the form of graph structures, as well as additional variants based on the separation of the corresponding vertices. Then, the expected execution time for all algorithm operations is calculated using the PERT method. To set optimistic and pessimistic estimates of execution time, it is proposed to set these estimates as fuzzy intervals, and to use Golenko's beta distribution model to calculate the most probable time.

Next, the option with the minimum time cost is selected. The task of selecting such an option is equivalent to the task of finding the minimum path in a given graph. The basic and additional options for solving the problems obtained do not allow the use of known algorithms to find the minimum path in this graph. Therefore, this task is reduced to the classical one by bringing the obtained graph to a standard form, in which the vertices will be the options for solving the tasks, and the arcs will indicate their interconnection, taking into account the given constraint.

In general, the approach considered can be used to develop appropriate methods for constructing algorithms for the optimal solution of organizational tasks.

Thank you for your attention!

Applied information systems and technologies in the digital society, October 01, 2025, Taras Shevchenko National University of Kyiv, Kyiv, Ukraine