Development of software package based on the mathematical graph theory for more efficient project management.

Majstorovic, Vlado ; Rakic, Kresimir ; Glavas, Marijana Bandic 等

1. INTRODUCTION

In terms of the increasing division of labor and specialization, planning and management projects becoming more complex. Coordination of the participants in performing the business task is of great importance and decisive impact on the efficiency of its execution. Integrated observing of execution of business project provides significantly better planning of implementation process and increases the efficiency of managing these projects. Network planning methods have the advantage compared to other methods which have complete look at the process of business project realization, because they provide a clear enough view of realization of the entire work, unambiguous view of logical course of mutual dependence of parts and processes, more precisely and more accurately determine parts of the project deadlines and the project as a whole as well as they determine the most burdened path from time aspect (Andrijic, 1982).

Recognizing the need for continued specialized software solutions for computer-aided project management, we are going to create an comprehensive software package that will enable us faster and more efficient operation in the future. Despite the existence of similar software packages, we decided for this step because of the need for concrete customizing software solutions to real problems that we encounter every day.

2. MAIN IDEA

Noticing a strong correlation between the concepts of network planning and concepts of mathematical graph theory, along with a detailed study of the many algorithms used in graph theory, we concluded that the mentioned algorithms can very effectively used to solve specific problems encountered in project management.

The basis of network planning is the network diagram that consists of activities, or parts of projects, which can be considered as separate entities from the feasibility and economic point of view, and events, or moments of time where one or more activities begin or end. Each activity, as well as the entire project, has a initial event and final event. An activity which initial event is i, and final event is j we will mark as [A.sub.ij] (Majstorovic, 2001). Each network diagram must meet the following requirements:

* there is only one initial and one final event of the project;

* there is at least one path from the initial to the final event of the project;

* for each event there is at least one path to the final event of the project;

* the existence of cycles is not allowed.

In terms of graph theory, graph vertices represent the events, and its edges represent project activities. Due to the lack of multiple arcs and loops, the network diagram is a strict, directed graph D (Veljan, 2001). Therefore, in our analysis, we can apply all the known algorithms from mathematical graph theory that will help us in solving our tasks.

To illustrate the usability of these algorithms in this paper we describe the application of well-known Floyd-Warshall algorithm for finding the critical path (CPM--Critical Path Method) in project time analysis. In this analysis, each activity is associated with a numeric value that represents its duration. From the standpoint of graph theory, these numerical values can be interpreted as a weight value of edges, so in this case, the network diagram is an strict weighted directed graph D, which is very suitable for performing the aforementioned Floyd-Warshall's algorithm

3. MODIFIED FLOYD-WARSHALL ALGORITHM

Original Floyd-Warshall algorithm compares all possible paths through the strict weighted directed graph D between each pair of vertices (Cormen et al., 2001). If we assume that a strict weighted directed graph has no negative cycles, and network diagram for time analysis is just such a graph, Floyd-Warshall algorithm finds the shortest path between each pair of vertices in a single passage.

Considering that the longest path between initial and final vertex of network diagram, as well as paths between all pairs of internal vertices (due to possible multiple critical paths between any pairs of nodes), is crucial for determination of critical path, we will modify the Floyd-Warshall algorithm to find the longest paths between vertices instead of the shortest ones. First we will describe modified Floyd-Warshall algorithm for finding critical paths in the network diagram.

Let D be strict weighted directed graph and let [V.sub.D] = {[v.sub.1], [v.sub.2], ..., [v.sub.n]} be set of n vertices of graph D, insome order. We will define an recursive function LongestPath(i, j, k):

LongestPath(i, j, k) = Maximal(LongestPath(i, j, k-1), LongestPath(i, k, k-1) + LongestPath(k, j, k-1)); LongestPath(i, j, 0) = ArcWeight(i, j);

for which we claim that, as a result, returns the longest possible path starting at the vi and ending at the [v.sub.j], using only the vertices [v.sub.1], ..., [v.sub.k] as an intermediate points along the path.

The basis of the algorithm is an adjacency matrix W(D) of weighted directed graph D, which gives us the value of the function ArcWeight(i, j) for all vertices pairs ([v.sub.i], [v.sub.j]). Algorithm for finding the longest path between each pair of peaks is carried out in n steps.

The proof of correctness of the basics of Floyd-Warshallovog algorithm, that is the above recursive formula LongestPath(i, j, k), is carried out with an mathematical induction, according to the cardinal number k of vertices set {[v.sub.i], [v.sub.2], [v.sub.k]} e VD, which are used as an intermediate points along the path.

Basis: For k = 0 set of vertices that we use as an intermediate points along the path is an empty set. Thus, the longest path beginning at the [v.sub.i] and ending at the [v.sub.j], which does not contain any vertex as an intermediate point, is either equal to the weight of arc starting at the [v.sub.i] and ending at the [v.sub.j], if this arc exists, or it is not defined (i.e. has value [infinity]) if there is no such arc. Those are the exact values that we can find in adjacency matrix W(D), or, in other words, the return values of function ArcWeight(i, j). This proves induction basis.

Assumption: We assume that the recursive function LongestPath (i, j, k) returns the longest possible path starting at the vi and ending at the vj, using only vertices [v.sub.i], ..., [v.sub.k] as an intermediate points along the path.

Inductive step: Let us prove the claim for k+1. Therefore, we are looking for the longest possible path starting at the v' and ending at the [v.sub.j], using only the vertices from the set {[v.sub.1], [v.sub.2], ..., [v.sub.k], [v.sub.k+i]} as an intermediate points along the path. There are two candidates for this path: it's either the path which uses only the vertices from the set {[v.sub.1], [v.sub.2], ..., [v.sub.k]} and [v.sub.k+i] is not used, or there is an longer path that goes from [v.sub.1] to [v.sub.k+i], and further from [v.sub.k+i] to [v.sub.j]. We know that the longest possible path from [v.sub.i] to [v.sub.j] that uses only vertices [v.sub.i], ..., [v.sub.k] is determined by function LongestPath(i, j, k). It is also obvious that, if there is a longer path from [v.sub.i] to [v.sub.j] through the vertex [v.sub.k+i], then its length is the sum of the longest paths from [v.sub.i] to [v.sub.k+1] and from [v.sub.k+1] to [v.sub.j] (using only the set of vertices {[v.sub.1], [v.sub.2], [v.sub.k]}). Therefore:

LongestPath(i, j, k+1) = Maximal(LongestPath(i, j, k), LongestPath(i, k+1, k) + LongtestPath(k+1, j, k));

which proves the inductive step.

Since both the basis and the inductive step have been proved, it has now been proved by mathematical induction that our formula holds for all natural n. Q.E.D.

4. IMPLEMENTATION EXAMPLE

Functioning of the Floyd-Warshallov algorithm for finding critical times in the project time analysis we will show using the following network diagram.

[FIGURE 1 OMITTED]

The final results of modified Floyd-Warshall algorithm are the longest paths between each pair of vertices of strict weighted directed graph D. In the terminology of network planning these numerical values represent the earliest beginnings of the project activities.

The next step is to determine the latest beginnings of project activities. For this purpose, we observe the network diagram starting from the final event and all the activities in the reverse direction, which is achieved by transforming the adjacency matrix.

[FIGURE 2 OMITTED]

We get the values of the latest beginnings by detracting the results of Floyd-Warshall algorithm from the value of the earliest start of the final event. Final results will be as the following figure:

[FIGURE 3 OMITTED]

Critical project activities are those activities in which have the same earliest and latest start (Heldman & Cram, 2004). In our example, those activities are [A.sub.13], [A.sub.36], [A.sub.67] and [A.sub.78] (marked with thicker arrows), and they form a critical path in time analysis of observed project.

5. CONCLUSION

The presented problem is a simple example of finding unique critical path in project time analysis. Used the modified Floyd-Warshall algorithm also allows the determination of multiple critical paths, due to the fact that it determines the longest paths between each pair of vertices, not only between the initial and final vertex. Once we determine the critical project activities, we can determine all the critical paths in a way that for every internal vertex of critical path (excluding initial and final vertex), verify the existence of an alternative critical paths from the initial vertex to the observed one, which does not pass all previously tested internal vertices of critical path.

This way of finding the critical path will be a basis of software package, which we plan to develop. In this direction we face our further work.

6. REFERENCE

Andrijic, S. (1982). Matematicke metode programiranja u organizacijama udruzenog rada (Mathematical Methods of Programming in Organizations of Associated Labor) Svjetlost, ISBN, Sarajevo

Cormen, T.H.; Leiserson, C.E.; Rivest R.L. & Stein C. (2001). Introduction to Algorithms, 2nd Edition, The MIT Press, ISBN 0-262-03293-7, Cambridge

Heldman, W. & Cram, L. (2004). IT Project +, Sybex, ISBN 07821-4318-0, San Francisco-London

Majstorovic, V. (2001). Production and Project Management, DAAAM, ISBN 3-901 509-23-2, Mostar-Wien

Veljan, D. (2001). Kombinatorna i diskretna matematika (Combinatorial and Discrete Mathematics), Algoritam, ISBN 953-6450-74-7, Zagreb