Recovery of directed graphs from the matrix of peaks neighborhood

Abstract

The properties of the graph problem of optimal investment of additional resources available to reduce the critical path network project are considered. It was proposed the algorithm in graph structure of the project on a given matrix of precedence works. The specified method of minimizing the required number of fictitious works to simplify the graph of the project is indicated.

Keywords

• problem of network planning and management
• lists of predecessors
• graph of the project
• minimizing of the required number of fictitious works

-

0  

Resource k i1

X can be a real number with a non-negative partitioning xi  X (or 1  ik1 xi  X ), or the set of discrete elements X  yt tL11 with arbitrary partition into subsets U(X)  2 x .

Let optimize the resource allocation xiik1 for minimizing the total time of the project P: k tai, xi  min

i1

2. Reduce the list of predecessors

We describe the relation S of precedence aiSaj of the project jobs ai,aj  P by the matrix of precedence S  si, j ik, j 1 :

def s(i,j)  χ(a(i),s(a(j))), with the characteristic function

def 1  ai sa j,  ai, sa j  

0  ai sa j.

Thus, the unit 1 in the i-th row of the matrix S indicates preceding the job a(i) of the respective columns. Then the transposed matrix S T describes the inverse relation S *1 following ajS–1ai project job: unity 1 in the i-th row of the matrix S T indicates preceding job a(i) by the job of relevant columns. Obviously, the relations S and S T are transitive ( S 2  S, (S 1)2  S 1 ) through the finiteness of the set of project jobs and has the inclusions   S k 1  S k 2    S 3  S 2  S   S 1 k 1  S 1 k 2    S 1 3  S 1 2  S 1 .

We call the job a(i)  P immediate predecessor of the job a(j)  P, if χ(a(i),s(a(j)))=1 and no other job such as a(l)  P: χ(a(i),s(a(l)))=χ(a(l),s(a(j)))=1.

Otherwise, the preceding (following) will be called indirect.

With the immediate predecessors lists s * aiik1 we define the relation S* of immediate precedence by k×k-matrix of direct precedence S*  s * i, j ik, j 1 : def s*(i,j)  χ(a(i),s*(a(j))).

Let the transposed matrix S *T defines the inverse relation S *1 of immediately following project jobs. Wherein the relations S* and S *1 are generally transitive as k1 k 1 S*  S   S t and S *1  S 1   S 1 t .

t2 t 2

We shorten the list of precedence saiik1 to the list of direct precedence s * aiik1 and by permutation of rows and columns of the matrix S for correct precedence order of the project jobs:  a j, s * ai  0 .

i j

In the future, we consider the original numbering of project jobs aiik1 is correct, and the original list of predecessors saiik1 is shorthand. Let matrix A of direct precedence of the properly ordered jobs S=(A[i1×j1],A[i2×j2],…,A[ir×jr]), 2≤r≤k–1, i1=j1=i2, j2=i3, …, jr-1=ir=jr, r r1 t2 it  t1 jt  k , be upper triangular and block-chained with zeros on the main diagonal and has continuous chain it×jt-blocks A[it×jt], 1≤t≤r, of which the first block and the last block are zero and square A[i1×j1]=0, A[ir×jr]=0.

Let the remaining blocks are non-zero: A[it×jt]≠0, 2≤t≤r–1.

Example 1.

The matrix of direct precedence of properly ordered 9 project jobs aii91  P may take the form a1 a2 a3 a4 a5 a6 a7 a8 a9 Ai1  j1

Ai2  j2 

3. Project’s graph

We construct a directed graph G(V,R) of the project P. At first we define the set of vertices V as follows.

Case 1. If block A[it×jt], 2≤t≤r–1, consists only of units, then exists a general conclusion vк(a(α( 1 )))=vк(a(α( 2 )))=…=vк(a(α(it))) and common origins vн(a(β( 1 )))=vн(a(β( 2 )))=…=vн(a(β(jt))) of the project jobs a(α( 1 )),a(α( 2 )),…,a(α(it)),a(β( 1 )),a(β( 2 )),…,a(β(jt))  P with numbers 1  ts11is   1   2     it    1   2      jt   rst 1 js .

Obviously that the resulting subgraph G(A[it×jt]), which connects the project jobs a uiut 1  a uujt1 , is planar, and the number of options for passing full paths through project P unit block A[it×jt] is equal to it×jt.

Case 2. If among the elements of the block A[it×jt], 2≤t≤r–1, there are zeros, then relevant bipartite graph K(it,jt) is not complete and must be added by the fictional jobs, unlike the embodiment of Fig. 1 it can not to connect a it incoming and jt outgoing directed arcs by one vertex.

Example 2.

Consider the 2×2-blocked 5×9-matrix of the immediate preceding project jobs ai1i46 by the jobs aii51 : 1 1 1 1 1 1 1 1 1    1 1 1 1 1 1 1 1 1  A5  9  1 1 1 1 1 1 1 1 1  .

1 1 1 1 0 0 0 0 0   1 1 1 1 0 0 0 0 0

Combining events (Fig. 3) vк(a( 1 ))=vк(a( 2 ))=vк(a( 3 ))=vн(a(10))=vн(a(11))=vн(a(12))=vн(a(13))=vн(a(14)), vк(a( 4 ))=vк(a(5))=vн(a(6))=vн(a(7))=vн(a(8))=vн(a(9)), introduce the additional (fictional) job b( 1 ) to save the immediate preceding of the jobs aii96 by the jobs aii54 , and the preceding of the jobs ai1i410 by the jobs aii31 , and non-immediate preceding of the jobs aii96 by the jobs aii31 . a( 2 ) a( 1 ) a( 3 ) a( 4 ) a(5) b( 1 ) a(10) a(11) a(12) a(13) a(14) a(6) a(7) a(8) a(9)

The permutation of the project jobs aii96 and ai1i410 and the addition of the fictional job b( 1 ) between a(5) and a(10) does not change the other blocks of the matrix of directly precedence S, setting the proper ordering of a united set of jobs b1 ai1i41 and turning the block A[5×9] to the 2×2-blocked 6×10-submatrix b1 a10 a11 a12 a13 a14 a6 a7 a8 a9

Note that the permutation of the project jobs aii51 , as well as ai1i46 , does not change the accuracy of ordering. For example, a permutation of the jobs ai1i46 of the Example 2 can get another 2×2-blocked 5×9-matrix of directly preceding of the jobs ai1i46 by the jobs aii51 of the jobs aii96 by the jobs aii31 , the jobs ai1i410 by the jobs aii54 and non-directly preceding and the jobs ai1i410 by the jobs aii31 corresponds to the following sub-boxes (Fig. 4).

Adding of the fictional job b( 1 ) between a(5) and a(6) does not modify other blocks of the matrix of direct precedence S, establishing the correct sequencing united plurality of the jobs b1 ai1i41 and turning the block A[5×9] to 2×2-blocked 6×10-submatrix

b1 a6 a7 a8 a9 a10 a11 a12 a13 a14 with two 3×5-unit blocks in broken chain of the non-zero blocks above the main diagonal of the matrix S. columns C def auluilji1 , l  tu11iu , 1≤i=it, 1≤j=jt, 2≤t≤r–1, of the project jobs in the continuous chain Ait  jt tr1 blocked chained matrix of directly precedence S. We consider the set of previous project jobs B as the factor-set of the relationship of equality of the rows of the matrix A[i×j]. Then the relationship of direct sequence s*– 1 determines the one-to-one mapping s*^-1: 2^C→2^C on the set of all subsets of C. At the closure D of the image s *1 2C  of her stepintersection subsets ∩ build the oriented tree of the relation

def D1, D2  D (D1→D2  D2  D1 ), excluding the empty set  . Arcs of this tree are the desired fictional jobs you needed to build the subgraph G(A[i×j]), binding the project jobs B  C . Therefore, it completed the construction of sub-graph for non-trivial block in the Case 2.

As is a tree, the subgraph G(A[i×j]) is planar, and the number of passing ways of the project P through the block A[i×j] is equal to i×j.

Thus, the total number M of the full paths of the project P is M  tr11it  tr2 jt .

References

1. Dokuchaev AV , Kotenko AP . Optimization of additional resources in network planning . Vestnik of Samara State Technical University. Series Sci. science , 2010 ; 1 ( 20 ). [In Russian]

2. Dokuchaev AV , Kotenko AP . Transition to the direct precedence matrix for network project graph construction . Abstracts of VIII Conf. “Math. Simulation and Boundary Value Probl.” , 2011 ; part 2. [in Russian]

3. Dokuchaev AV , Kotenko AP . Network project graph construction on the basis of jobs precedence table . Groups and Graphs , Algorithms and Automata-2015. Abstracts of the International Conf . Yekaterinburg: UrFU Publishing house, 2015 .

4. Dokuchaev AV , Kotenko AP . Necessary conditions to complement the graph of project by fictitious arcs . Information Technology and Nanotechnology-2015. Abstracts of the International Conf. Samara: SSAU , 2015 . [in Russian]