Proceedings of the Tomsk Order of the October Revolution and Order of the Red Banner of Labor Polytechnic Institute named after S. M. Kirov

Volume 290　　　　　　　　　　　　　　　　　　　　　　　　　1974

RANKING OF PART FLOWS BETWEEN ENTERPRISE DEPARTMENTS

L. V. PERFILIEV

(Presented by the scientific and technical seminar of the Department of Automated Control Systems and the Control Laboratory)

In a mathematical study of the functioning of the main production of an instrument-making enterprise with a large nomenclature of parts (up to several thousand) used for manufacturing the output product, an important task is the analysis of the flows of parts and assemblies between the enterprise departments (between blank-production shops, machining shops, and assembly shops). In this connection, solving the problem of evaluating or ranking the importance of these flows may be of considerable interest.

Information on flows between departments can be represented in the form of a graph $\Gamma$. The vertices of the graph are shops; the directed arcs are flows of parts and assemblies. Each arc is understood to mean the total flow of parts and assemblies of all types for a single direction that exists between two departments. The volume of this flow can be represented by the expression

\[ Y_{\kappa s}=\sum_{l\in L} Z_{\kappa s}^{l}, \tag{1} \]

where $L$ is the set of types of parts and assemblies,

$\kappa = 1, 2, \ldots, m$ is the number of a department,

$s = 1, 2, \ldots, m$ is the number of a department,

$\kappa \ne s$,

$l$ is the number of the type of part or assembly,

$Z_{\kappa s}^{l}$ is the number of parts and assemblies of the $l$-th type arriving from the $\kappa$-th department to the $s$-th.

The problem consists in ranking, by degree of importance, the total flow between each pair of vertices of the graph $\Gamma$.

For each type of parts and assemblies, a graph $\Gamma_e$ can be constructed that reflects the sequence in which the parts pass through the shops. By superimposing the graphs $\Gamma_e$, the above-described aggregate graph $\Gamma$ can be obtained.

Each $\kappa$-th shop is characterized by the quantity $P_{\kappa s}^{l}$—the resources of the $\kappa$-th shop required for processing one part of the $l$-th type arriving from the $\kappa$-th shop to the $s$-th shop. We denote the entire set of vertices of the aggregate graph by $\kappa$. Within this set one can distinguish subsets $\kappa_l$, whose vertices correspond to shops processing parts of the $l$-th type. Then the ordered sequence-

of arcs \((ks)\) for which the vertices \(k, s \in K_l\) form a path along which parts of the \(l\)-th type pass, being processed successively in the corresponding shops.

Obviously, a disruption in the operation of any shop leads, first of all, to a disruption in the operation of those shops to which the output of this shop is supplied. Consequently, the operation of each shop depends on the operation of the preceding shops through which the part passed during processing. In this sense, each arc \((k_1 s_1)\) depends, with respect to the parameter \(l\) (where \(l\) is the type of part), on the preceding arcs of an ordered sequence consisting of arcs \((ks)\) for which the condition \(k, s \in K_l\) is satisfied. We shall express this dependence by dominance. That is, if, among the ordered sequence of arcs \((ks)\) for which \(k, s \in K_l\), the arc \((k_1 s_1)\) precedes the arc \((k_2, s_2)\), then we shall consider that the arc \((k_1 s_1)\) dominates the arc \((k_2, s_2)\) with respect to the parameter \(l\), and we shall denote this as \((k_1 s_1) > (k_2 s_2)\). It should be noted that in another concrete case other considerations may be used to establish dominance of flows.

As noted, the total flow between two shops is a collection of individual flows characterized by the parameter \(l\). Some of these flows may, with respect to the parameter \(l_1 \in L\), dominate the flows between other shops; for another part there may exist flows that dominate the flows of this part with respect to the parameter \(l_2 \in L,\ l_1 \ne l_2\). In this connection there arises the problem of constructing a method that, taking into account dominance with respect to individual parameters \(l\), makes it possible to rank the flows between departments.

It should be noted that such a method must take into account the fact that dominances with respect to different parameters \(l \in L\) are not equivalent. This non-equivalence, in the case under consideration, is determined by the difference in the total resources expended by the departments for processing parts of each of the types \(l \in L\). That is, a disruption in the operation of some department affects the whole system the more appreciably (and, consequently, the more essential the dominance), the larger the quantity of resources that cannot be realized on time because of this disruption. The resources necessary for processing all parts of the \(l\)-th type can be calculated from the expression

\[ P_l=\sum_{p,s\in K_l} Z_{ks}^{\,l} P_{ks}^{\,l}. \tag{2} \]

The total resources of the whole system are equal to

\[ P=\sum_{l\in L}\sum_{k\in K} Z_{ks}^{\,l} P_{ks}^{\,l}. \tag{3} \]

As a method that makes it possible to rank flows between departments, one may use a method based on the scheme of constructing a graph of pairwise dominance of objects according to given parameters and choosing a solution on this graph by means of one of the known procedures.

The ranking problem can be solved in stages. At the first stage, the order of preference of objects is established for each of the parameters (ranking of objects by parameter). One way of solving the problem at the first stage is pairwise comparison of objects [1, 2] and construction of the graph of pairwise dominance. At the second stage, weight coefficients of the parameters \(l \in L\), reflecting their importance, are determined. At the third stage, ranking or evaluation is carried out—

ranking of objects on the basis of the results of combining the preferences of the objects for each parameter.

The pairwise-dominance graph \(\Gamma'_l\) for each type of parts \(l\) can be obtained on the basis of the graph \(\Gamma_l\) using the relations in the following way.

The vertices of the graph \(\Gamma'_l\) are the arcs of the graph \(\Gamma_l\). Vertices \(i\) and \(j\) of the graph \(\Gamma'_l\) are connected by an arc directed from \(i\) to \(j\) if the arc of the graph \(\Gamma_l\) corresponding to vertex \(i\) in the graph \(\Gamma'_l\) dominates, with respect to parameter \(l\), the arc of the graph \(\Gamma_l\) corresponding to vertex \(j\) in the graph \(\Gamma'_l\).

The union of the graphs \(\Gamma'_l\) forms a pairwise-dominance multigraph, which can be reduced to a unigraph or to a probabilistic graph.

In the pairwise-dominance multigraph, each arc corresponding to one of the values of parameter \(l\) is put into correspondence with \(V_l\)—the weight of parameter \(l\), computed from the expression

\[ V_l= \frac{ \sum_{\kappa,\,s\in K_l} z^l_{\kappa s} p^l_{\kappa s} }{ \sum_{l\in L}\sum_{\kappa,\,s\in K} z^l_{\kappa s} p^l_{\kappa s} }, \tag{4} \]

where \(K_l\) is the set of shops processing parts and assemblies of the \(l\)-th type;
\(K\) is the set of shops;
\(L\) is the set of types of parts and assemblies.

Denote by \(\sum_l V_l^{(ij)}\) the sum of the weights corresponding to all arcs between two vertices \(i\) and \(j\) of the transformed multigraph, and by \(\sum_{l\in D} V_l\) the sum of the weights of the parameters belonging to the set \(D\), for all elements of which the condition \(i > j\) is satisfied.

The transition from the multigraph to a unigraph is carried out by drawing an arc \((ij)\) if the condition

\[ \frac{ \sum_{l\in D} V_l }{ \sum_l V_l^{(ij)} }>1 \tag{5} \]

is satisfied.

If in expression (5) the less-than sign holds, then the arc \((ji)\) is drawn; in the case of equality, two arcs \((ij)\) and \((ji)\) are drawn.

It is not difficult to construct the adjacency matrix of such a graph. The elements of this matrix are equal to

\[ a_{ij}= \begin{cases} 1, & \text{if the arc }(ij)\text{ exists},\\ 0 & \text{otherwise}. \end{cases} \]

A probabilistic graph can be obtained if each arc \((ij)\) and \((ji)\) is assigned a probability value computed from the expressions

\[ P(i,j)= \frac{ \sum_{l\in D} V_l }{ \sum_l V_l^{(i,j)} }, \tag{6} \]

\[ P(j,i)=1-P(i,j), \tag{7} \]

With such a graph, the dominance relation is characterized by the square matrix \(P=\|P_{ij}\|\).

The method for ranking flows of parts and assemblies is determined to a considerable extent by the form in which information on dominance is represented. To solve the ranking problem when using information from a probabilistic graph, the method proposed in [3] may be used; it is based on ideas from the theory of Markov processes.

For ranking flows using information from a unigraph, a method based on ideas of discrete programming [4] may be used.

In this case the problem of ranking objects is solved as a problem of minimizing the total amount of losses, if the ranking is carried out by degree of increasing preference of the objects. The total losses in ranking may be determined from the expression

\[ C=\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{\mu=1}^{n-1}\sum_{\nu>\mu}^{n} x_{i\mu} a_{ij} x_{j\nu}, \tag{8} \]

where \(a_{ij}\) are the elements of the adjacency matrix of the pairwise-dominance graph of size \(n \times n\);

\(\mu,\nu=\overline{1,n}\) are the numbers of the ranks of the objects being ranked;

\(x_{i\mu}\) and \(x_{j\nu}\) are the sought Boolean variables.

\[ x_{i\mu}= \begin{cases} 1, & \text{if object } i \text{ is assigned rank } \mu,\\ 0 & \text{otherwise.} \end{cases} \]

Analogously for \(x_{j\nu}\).

Minimization of expression (8) is carried out subject to the constraints

\[ \sum_{i=1}^{n} x_{i\mu}=1; \tag{9} \]

\[ \sum_{\mu=1}^{n-1} x_{i\mu}=1. \tag{10} \]

Constraint (9) means that in any \(\mu\)-th position there can be only one object \(i\); constraint (10) means that any \(i\)-th object can be located in only one position.

It should be noted that when ranking objects in the case where quantitative information about the objects is available (for example, a matrix \(\|P_{ij}\|\) is specified), this information can be used to evaluate the objects.

The above formulation of the discrete-programming problem can also be used in the case where information on the dominance of objects is given in the form of a probabilistic graph.

REFERENCES

1. K. L. Gofman, N. B. Russman. Some applications of the priority-arrangement problem. “Economics and Mathematical Methods,” vol. V, No. 3, 1969.

2. O. I. Larichev. Human–machine decision-making procedures. “Automation and Telemechanics,” No. 12, 1971.

3. I. A. Ushakov. The problem of choosing the preferable object. Izvestiya of the Academy of Sciences of the USSR, “Engineering Cybernetics,” No. 4, 1971.

4. V. Z. Yampolsky, I. P. Makarov, V. A. Suchkov. A method for making a complex decision on the basis of pairwise comparison of alternatives. Proceedings of the VI Symposium on Cybernetics, part III, Tbilisi, 1972.