A mathematical model for synthesizing an algorithm for parallel solving of interconnected organizational problems is proposed. According to this model, the synthesis process consists of two stages. In the first stage, the main solution options for the entire set of problems are formed as graph structures. Also, for the main variants that use intermediate results of solving other problems, additional variants are formed based on the separation of the corresponding vertices. Then the expected execution time of the algorithms is calculated using the PERT method. In this case, the optimistic and pessimistic times are specified by fuzzy linguistic estimates, and the Golenko β-distribution is used to calculate the most probable time. In the second stage, the option with the minimum time expenditure is selected. For this purpose, a graph of primary and additional options is formed, and the selection problem is reduced to finding the shortest path in this graph.
Organizational tasks represent a set of management and coordination activities that arise in the functioning of organizations and their structural units [1]. They cover activity planning, resource allocation, coordination of performers’ work, monitoring of task execution, and integration of the obtained results into a unified managerial decision. A distinguishing feature of such tasks is their complexity and interdependence, which necessitates the application of methods for their efficient solution [2].
In general, 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 [3]. 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, the nature of the parallel solution process depends on the type of interdependencies involved. 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 [4, 5]. At present, there exist many approaches (methods) to distributed/parallel graph computation, which can be grouped as follows: • • •
computational resources among system nodes and reducing workload imbalance. The foundation lies in graph partitioning algorithms that ensure an even distribution of vertices and edges across processes while minimizing interprocessor communications [6, 7].
of parallel graph algorithms by providing ready-to-use high-level abstractions and efficient data structures. The core idea is to supply developers with libraries that conceal the low-level details of parallelism (task distribution, load balancing, synchronization) while ensuring high performance [8–10].
In addition, one can note the vertex separation method [4, 14], which consists in partitioning the set of graph vertices into subsets in such a way that the internal connections within each group are preserved, while the intergroup connections are minimized or eliminated. This allows parallel task solving within each group using resources of different structural units or computing systems. The dependencies between groups then determine the order of combining partial solutions into an overall result.
Summarizing, the mentioned groups of methods are characterized by different strategies of scaling graph computations, which are mainly focused on solving problems linked by final results, while tasks connected by intermediate results have received comparatively little scholarly attention.
This article proposes a mathematical model for one possible approach to parallel solutions for interrelated organizational problems, which may be linked by both final and intermediate results. This approach also further develops the ideas behind the vertex separation method in graph models, which, overall, will reduce the time it takes of receiving decisions and create the preconditions for improving the efficiency of management processes. 2. Problem statement of algorithm synthesis for solving organizational tasks the solution variants of different tasks ( ≠ ′). procedure independent of the solutions of other tasks.
One of the characteristic features of organizational tasks is their informational interdependence at the level of both final and intermediate results of their solution. Based on this, the essence of the problem of determining an algorithm for solving the tasks of an organizational structure lies in selecting such an algorithm for solving the entire set of tasks, taking into account the interrelations between them, so that the overall execution time of their solution is minimized.
At present, the most common methods for solving problems of this class are graph theory methods.
Let ={ | =1, } be the set of tasks of the organizational structure, ={ = 1, } – the set of basic solution variants for the i-th task, and = ′ ′ – the information dependency matrix between
=
=1,
Let each set be represented by a directed graph ( , )), where = =1, is the set of vertices representing information-processing operations of the solution variants of task , and is the set of edges that determine the execution order of these operations. Each combination Е=( 1, 2, . . . , ) is minimized: variant corresponds to a path in graph , which is associated with an execution time denoted as . The objective is to identify, in each graph , such a path that the total execution time T of their = ∑ =1 ,
where is the execution time of the chosen variant of task .
variants of task ′ associated with it must also be selected. That is, connected with several variants of task ′, then when solving task i by this variant, exactly one of the if ′ ′ ≠ 0 & ∈ , then ′ ′ ∈
Thus, the solution of this problem is carried out in two stages: first, a graph structure of solution variants of tasks is constructed, taking into account their interdependencies, and then, in this graph structure, the shortest path is found, which determines the algorithm for solving the organizational tasks.
At the beginning, for each problem , algorithms (options) for its solution are determined (j=1, ). Such variants can be constructed efficiently using the method [15], which is a development of
Next, using the (PERT) method [16], a network schedule for its implementation is constructed for each option. First, the execution time of variant
is determined as: = ∑ =1
,
= ′ +4 * + ″
, 6 ( ) = - · , = + · ( )
is
(
in variant .
The expected time is defined as:
is the expected execution time of the k -th operation, and n is the number of operations where ′ is the optimistic estimate of the execution time, * is the most probable estimate, and ″ is the pessimistic estimate.
The optimistic estimate is the minimum execution time under the most favorable conditions, whereas the pessimistic estimate is the maximum execution time under the least favorable conditions. The most probable time corresponds to the median of the probability distribution (cumulative probability 0.5).
Practical experience with network planning demonstrates that it is generally difficult to reliably estimate the minimum (maximum) execution time of a task in conditions of uncertainty, and even more so to provide a reliable estimate of the most probable time. In order to improve the objectivity of such estimates, the following approaches are proposed.
execution time interval, i.e., the minimum and maximum time.
We will define the minimum and maximum time for completing the job using fuzzy statements of the type “the time for completing the job is approximately in the range from a to b,” which are natural for a person under conditions of uncertainty. The above statement represents a fuzzy trapezoidal number ( , , , ),, where α and β are fuzziness coefficients that define the boundaries of the possible
where
≈ 2.55, and ( ) and ( ) are the distances between the transition points for numbers approximately equal to a and b. The error of the approximate calculation Δ<0.5, which is fully acceptable in practice.
To calculate the distances between transition points, the mechanism proposed in [18] is used. This compute the distances between their transition points (see Table 1). mechanism is based on expert data, which allows, for numbers approximately equal to ∈ [1,99], to
Using this table, for numbers >99, the distance between their transition points is calculated according to the following algorithm. numbers , ∈ {0, 1, 2}, where =
3. Then: Let the least significant digit of the number have order . Let be the least significant digit of this number, and +1 be its digit whose order is one higher than the order of . Define classes of ∈ 0, then ( )= ( ) ⋅ 10 -2, where = ⋅ 10⋅and ( ) is calculated from Table 1. 1. If 2. If
∈ 1, there are two possible cases: a) if +1=0, then ( )= ( ) ⋅ 10 -1, where = ;
b) if +1 ≠ 0, then ( )= ( ) ⋅ 10 -1, where = +1 ⋅ 10+ . 3. If
∈ 2, there are also two possible cases: a) if +1=0, then = ⋅ 10; ( )= ( ) ⋅ 10 -2; b) if +1 ≠ 0, then = +1 ⋅ 10+ ; ( )= ( ) ⋅ 10 -1.
As a result, the value ( ) is obtained.
point 3(b), we have x=12, b(120) = b(12)·10. According to the table:
Example. Let's represent the statement "the completion time for the k-th work is approximately in
the range from 90 to 120 minutes" as a fuzzy trapezoidal number. As noted, a fuzzy trapezoidal number
has the form ( , , , ), where in this case a=90, b=120, and α and β are the minimum and maximum
work completion times, which are calculated using formulas (
For the number 120 we have =2, =2, +1=1, d=2mod3=2, i.e. its class is 2. Then, according to b(12) = 1 2 12 10 ⋅ 10+5 +
= 12 (6.48+0.92)=3.7, and b(120) = 37.
Then, according to (
be the estimate of the execution time of the -th operation of variant , where is the optimistic and pessimistic time. Since any value within the given interval can be considered a possible execution time, a probability ( ) is introduced that the operation will be * is then taken as the median of the probability ( ) distribution over completed by time ( ′
≤ ≤ ″ ).
The most probable time the given interval, i.e., ( *
)=0,5.
To describe random variables that are bounded within a finite interval, the beta distribution is typically used. Various stochastic network models have been developed [19–21]. Among them, the simplest is the model by D. Golenko [21]. This model requires specifying two estimates: an optimistic estimate (a) and a pessimistic estimate (b) of the task duration. and =3, having the probability density function:
The Golenko model is based on the beta distribution over the interval [ , ] with parameters =2 and the cumulative distribution function: ( | , )=
12 ( - )4 ∙ ( - )( - )2
1
( )= (
( )=12 ∫0 ⋅ (1- )2 .
= -1(0.5).
As a result, each variant is represented by a network graph , in which the vertices correspond to operations
with their execution times Figure 1 shows an example of a network schedule variant of solving task .
, and the edges define the order of their execution.
In the constructed network graph
, the execution time of variant is determined using the critical path method. The critical path is calculated from the initial vertex of the network to the terminal vertex using the formula = + }, where is the current vertex , and is the set of vertices that have a direct connection to . The longest path in the corresponding graph of the entire set of operations: = ∑ =1 , where is
determines the execution time the number of vertices in the path . performed. For this purpose, each operation
is described by an aggregate:
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. To account for the possibility of using intermediate results of task solutions , an information linkage between the solute on variants is = ( , ), where =( 1
, 2 , . . . , ) and =( 1 , 2 , . . . , ) are vectors of input and output data of the operation, the elements of which are represented by the corresponding information categories, and
is the execution time of the -th operation.
Next, the input and output categories categories coincide and the execution of operation and ℎ ( ≠ ) are considered. If the names of these ℎ completes earlier than operation , i.e., ℎ < , then a connection is established from the source vertex ℎ in the graph ℎ to the consumer vertex in the graph
.
separation of the consumer vertex [22]. results from another task, i.e., as an alternative information source for operation . This, in turn, leads to an additional solution variant ′ for task . The formation of this variant is based on the Let
be the consumer vertex in graph introducing a new vertex
into the graph data from an alternative information source. The new vertex vertex ℎ , as well as to vertices input data for (see Fig. 2). Fig. 2 shows the separation of the consumer vertex .
. The separation of this vertex is performed by , which represents the operation of obtaining input
is then connected to the source and to the vertex that immediately precedes the preparation of
As a result of linking task variants and separating consumer vertices, additional solution variants ′ for the task are formed, for which the execution times are also determined. As a result, the main and additional options for solving organizational problems are represented by a set of interconnected graphs of their solution (Fig. 3).
In the figure, the connections between variants based on the use of final results are labeled as “A,” while those based on the use of intermediate results are labeled as “B.”
In the given graph structure, finding the shortest path using conventional algorithms is not directly possible. Therefore, the structure is first transformed into a standard form graph . The construction of such a graph is carried out as follows [22].
Let =( 1, 2, . . . , ) be the vector of solution variants for task .
Step 1. The vectors are ordered according to the task numbers. The elements of the vectors correspond to the vertices of the graph . Fig. 4 shows an example of vector ordering.
Step 2. According to the graph structure (see Fig. 3), the connectivity matrices = ℎ of the solution variants and ℎ for tasks and (including unconnected tasks) are constructed. Next, adjacent tasks and +1 ( =1, -1) are considered, and based on the corresponding matrices ( +1), connections between their variants are established. Additionally, connections are created between all variants of task and the main variants ( +1) of task +1, as well as between unconnected additional variants ( +1) ′ of task +1 and all main variants of task . An example of linking solution options for related problems is shown in Fig. 5.
Step 3. The graph constructed in this way is supplemented with initial and terminal vertices, which are connected to all variants of tasks 1 and , respectively. Figure 6 shows an example of such a graph for three problems.
Step 4. Each edge , which connects variants and , is assigned a weight (corresponding to its execution time for the variant ). Edges connecting the initial vertex are assigned zero weight, whereas edges leading from variants to the terminal vertex are assigned weights .
Since the graph has a standard structure, the minimum path E={eij}, where is the task number and is the algorithm for solving it, can be found using known algorithms. This path will be an algorithm for solving the entire set of tasks of the organizational system, taking into account their interrelations. For example, in the graph in Figure 6, such a path could be ( 11, 25, 33). That is, task 1 is solved by algorithm 11, task 2 by algorithm 25, and task 3 by algorithm 33.
While preparing this work, the authors used the AI programs Grammarly Pro to correct text grammar and Strike Plagiarism to search for possible plagiarism. After using this tool, the authors reviewed and edited the content as needed and took full responsibility for the publication’s content.
A mathematical model for synthesizing an algorithm for parallel solution of interconnected organizational problems is considered. According to this model, the main solution options for the entire set of problems are first generated as graph structures. For the main options, which use intermediate results other problems, additional options are generated based on the separation of the corresponding vertex of the graph. The expected execution time for all algorithms is then calculated using the PERT method. Moreover, the optimistic and pessimistic completion times for each task are specified by fuzzy interval linguistic estimates, which are natural for humans under uncertainty. The Golenko β-distribution, which uses such estimates, is used to calculate the most probable time. The option with the minimum time expenditure is then selected. The problem of choosing such an option is equivalent to finding the shortest path in a graph. If a variant of one task is re lated to a variant of another task, both variants are selected. In general, the approach considered does not claim to be complete and can be used as a pilot for creating algorithms for optimal solutions to organizational problems, and the given examples of its main stages demonstrate the practical feasibility of the proposed model. [4] T. H. Davenport and J. Kirby, Designing Intelligent Organizations: AI, Analytics, and the Future of Work. Harper Business, 2023. [5] J. A. Bondy and U. S. R. Murty, Graph Theory. Springer, 2008. [6] S. Even, Graph Algorithms. Cambridge University Press, 2012. [7] L. Meng, Z. Huang, Q. Zhang, L. Chen, and J. Yu, "A Survey of Distributed Graph Algorithms on
Massive Graphs," ACM Computing Surveys, vol. 56, no. 4, 2024, doi: 10.1145/3659969. [8] D. Q. Nguyen and K. Pingali, "Galois: A C++ Library for Parallel Graph Analytics," SIGPLAN
Notices, 2018, doi: 10.1145/3276483.3276491. [9] V. Kovalchuk, S. Ivanov, and M. Pavlenko, "Parallel Graph Processing in Multicore Systems: Data Structures and Libraries," Information Technologies and Computer Engineering, no. 2, pp. 45–53, 2023. [10] O. Shevchenko and M. Tymoshenko, "GPU Libraries for Scalable Graph Algorithms in Scientific
Research," Scientific Works of KhNURE, no. 58, pp. 112–120, 2022. [11] G. Malewicz et al., "Pregel: A System for Large-Scale Graph Processing," in Proc. SIGMOD, 2010. [12] J. E. Gonzalez et al., "PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs," in Proc. OSDI, 2012. [13] R. Xiang, Y. He, Q. Sun, and J. Yu, "Adaptive Distributed BFS and PageRank for Skewed Graphs," in Proc. IEEE BigData, 2022. [14] E. Turban, C. Pollard, and G. Wood, Information Technology for Management: On-Demand
[15] Y. Y. Samokhvalov, "Development of the Prediction Graph Method Under Incomplete and Inaccurate Expert Estimates," Cybern Syst Anal, vol. 54, pp. 75–82, 2018, doi: 10.1007/s10559-0180008-1. [16] "Program Evaluation and Review Technique (PERT)," Available: http://www.referenceforbusiness.com/encyclopedia/Per-Pro/Program-Evaluation-and-Review
[17] Y. Samokhvalov, "Risk Assessment of Innovative Projects Based on Fuzzy Modeling," in Lecture Notes in Computational Intelligence and Decision Making. ISDMCI 2020, S. Babichev, V.
10.1007/978-3-030-54215-3_17. [ [18] A. Borisov, O. Krumberg, and I. Fedorov, Decision Making Based on Fuzzy Models: Examples of
[19] L. Huang, "The Stochastic Network Model," in Learning for Decision and Control in Stochastic Networks. Synthesis Lectures on Learning, Networks, and Algorithms. Springer, Cham, 2023, doi: 10.1007/978-3-031-31597-8_2. [20] Ya. D. Gelrud, "Generalized Stochastic Network Models for
[20] D. I. Golenko-Ginzburg, Stochastic Network Models for Planning and Management of
[21] Y. Samokhvalov and O. Burba, Pre-Design of Automated Systems. Kyiv, 2013.