Algorithm for Constructing a Network Model of Development

Yu. N. Efimov

(Presented by the scientific seminar of the Department of Computer Engineering, TPI)

The automated system of network planning and control (SPU), which has become widespread, is based on the analysis of network schedules, which are dynamic models of complex developments. Representing the development process in the form of a network formalizes the operational plan to the greatest extent, which makes it possible to use electronic computers (ECMs) to perform procedures for processing information on the progress of work and preparing data for decision-making. However, if the analysis of network schedules is performed with the aid of an ECM, the process of constructing them (linking the jobs) still remains manual. This leads to the fact that, in the terminology of SPU, the work of compiling the network schedule becomes critical in the overall set of tasks involved in introducing an SPU system for some development. Obviously, automating the construction of network schedules will make the SPU system still more operational.

This article presents an algorithm for constructing network models of developments described by means of a certain set of jobs and the links between them. It is assumed here that the following conditions are satisfied:

1) the development contains only one final job;
2) the network model has only one initial event $i_0$;
3) any job $(i, j)$ may be started only after all jobs preceding it have been completed; that is, every event of the model realizes the elementary logical function “AND” (conjunction). In practice, for almost any single-purpose development that permits the use of network methods of planning and control, it is possible to compile a set of jobs satisfying the conditions listed above.

As is known, the initial data for constructing a primary network schedule are taken from the list of jobs of the development being modeled, which is compiled by the responsible executors of the jobs. The mentioned jobs are “linked” to one another by events on the basis of the logical interrelation and technological sequence of performing the jobs. In doing so, it is necessary to take into account the basic rules for constructing networks [1], which reduce to the following.

1. One and the same event number must not be used twice; this ensures an unambiguous definition of any job of the network. (The code of a job is composed of the codes of its initial and final events.)

1. The network must be simple, without unnecessary intersections; the directions of activities should, as far as possible, be shown from left to right.

2. In the network there must not be a single event, except the initial one, into which no activity enters; all events, except the terminal one, must have at least one subsequent activity. The presence of discontinuities of the first or second kind [2] indicates a logical error made in constructing the network.

3. The network diagram must not contain closed contours (cycles), which likewise indicate a logical error.

Fig. 1. Examples of introducing dummy links in the case of differentially dependent activities

The constructed network, in addition to the principal activities indicated in the list, may obviously contain some number of so-called dummy links, necessary for the correct representation of differentially dependent activities. For example, if some activity \(A\) can be started after completion of activities \(B\), \(C\), and \(D\), while activity \(E\) only after completion of \(C\) and \(D\), then it is necessary to introduce the dummy activity \(F\) (Fig. 1a). If activity \(A\) may be started after completion of activities \(B\), \(C\), and the start of activity \(D\) depends only on completion of \(B\), while the start of \(E\) depends on completion of activity \(C\), then two dummy links \(F_1\) and \(F_2\) must be introduced into the network diagram (Fig. 1b).

Fig. 2. Example of introducing dummy links for parallel activities

In practice, cases are often encountered in which one event serves as the start for two or more activities that also end in the same event. (We shall call such activities parallel.) To show that parallel activities proceed independently, it is necessary to introduce additional events and dummy activities (Fig. 2).

Thus, the main task in drawing up a network diagram is to find the necessary number of events and dummy activities. Moreover, this number must be minimal in the sense that it is impossible to describe the development being modeled with a smaller number of events and dummy activities. The events found must be numbered in increasing order of the values of the ordering function \(\varphi(i)\) [3], defined on these events; that is, for any activity (both principal and dummy) the relation

\[ i < j, \]

must hold, where \(i\) and \(j\) are, respectively, the numbers of the initial and terminal events of activity \((i,j)\).

Such numbering significantly simplifies the drawing of the resulting network and accelerates the subsequent process of its analysis. For example, when the iteration method is used, ordered coding of events makes it possible to carry out the time analysis of a network in two mutually opposite passes through the list of jobs, whereas in the general case \([\varphi(i)_{\max}+1]\) passes are required.

As the initial information for constructing the network we use the data of Table 1, where the second column contains the list of all development jobs, the third contains the job parameters (duration, cost, etc.), and the fourth contains information on the links between jobs in the form of rows of preliminary codes of preceding jobs.

Table 1

It is convenient to take as the preliminary code of a job its ordinal number in the initial list (the first column). For the initial development jobs, a zero or a dash is entered in the fourth column of Table 1. It is obvious that the initial information in this form can very easily be obtained from the responsible performers, who know after the completion of which jobs they can begin “their” job.

Let the jobs immediately preceding some job \(k\) of the initial list constitute the subset \(\Gamma_k^{-1}\) (one row of the fourth column of Table 1) with number of elements \(\omega_k^0\). Denote by \(\omega_k'\) the number of elements of the subset \(\Gamma_k^{-1}\) not yet considered. Obviously, before the algorithm begins, \(\omega_k'=\omega_k^0\). The jobs of the initial list that have been considered will be marked with a sign and written into the one-dimensional array \(s[m]\), which will be continually augmented in the course of the solution by new members. Then the operation of the algorithm solving the main tasks of constructing a network schedule reduces to the following.

1. Execute the restoration commands:

\[ C_4 := 1;\quad s[m] := 0. \]

1. Assign to the starts of all initial jobs a code equal to the value \(C_4\). Mark the initial development jobs with a sign and write them into the array \(s[m]\). Execute \(C_4 := C_4+1\).

2. Take the first element of the array \(s[m]\).

3. Examine all jobs in the initial table not marked with the sign and execute \(\omega_k' := \omega_k' - 1\) if the element of the array \(s[m]\) under consideration is a member of the subset \(\Gamma_k^{-1}\).

4. Determine whether there are jobs that have obtained \(\omega_k'=0\) in performing step 4. Yes. Execute step 6. No. Execute step 19.

5. Arrange the jobs that have obtained \(\omega_k'=0\) in increasing order of \(\omega_k^0\). Jobs with identical \(\omega_k^0\) form a group of jobs. Obviously, the list of preceding jobs for any job of the group will be the same. We shall call this list the subset \((\Gamma_q^{-1})\) preceding the group \((q)\).

6. Consider the first group of jobs.

1. Write out all activities \((i,j)\in \Gamma_q^{-1}\) and arrange them in increasing order of the codes of their beginnings.

2. From the ordered sequence obtained, exclude activities whose terminal events already have codes \((j)\) assigned. Take the largest of the codes of the ends of the excluded activities as the code of the beginning of the next dummy activity. Divide the activities remaining in the sequence into subgroups of activities with identical codes \((i)\) of their beginnings. Mark the first activities of all subgroups in the sequence.

3. Take the first unmarked activity in the sequence.

4. Assign to the end of this activity a code equal to the value \(C_4\). Take this same code as the beginning of the next dummy activity.

5. Perform \(C_4 := C_4+1\).

6. Check whether all unmarked activities in the sequence have been considered. Yes: perform step 15. No: perform step 14.

7. Take the next unmarked activity in the sequence and perform step 11.

8. Assign a code equal to the value \(C_4\):

a) to the beginnings of all activities in the group;

b) to the ends of all activities \((i,j)\in \Gamma_q^{-1}\) that still do not have a code for the terminal event;

c) to the ends of dummy activities (these activities received the code of the beginning when steps 9 and 11 were performed).

1. Mark all activities of the considered group with the attribute and write them into the array \(s[m]\), placing them after the last element of the array.

2. Check whether all groups of activities have been considered. Yes: perform step 19. No: perform step 18.

3. Consider the next group of activities and perform step 8.

4. Check whether all elements of the array \(s[m]\) have been considered. Yes: perform step 21. No: perform step 20.

5. Take the next element of the array \(s[m]\) and perform step 4.

6. Check whether all activities of the original list are marked with the attribute. Yes: perform step 22. No: perform step 25.

7. Take as the code of the end of the final activity the value \(C_4+1\).

8. Check whether all activities have end codes. Yes: perform step 24. No: perform step 26.

9. Order the list of real and dummy activities by the code of their beginnings and finish the computations.

The ordered list thus obtained is the solution of the problem posed.

1. Stop the computations, since the network model contains a cycle. The corresponding corrections must be made in the original information.

2. Stop the computations and write out the activities that do not have a terminal-event code. The results of these activities are not needed for carrying out other development activities. Consequently, these activities are either superfluous, or an error has been made in the original information.

As an example of the operation of the algorithm, we present the construction of a network model of development, the initial data for which are specified by the left-hand side of Table 2 (here the names and parameters of the activities are absent, since they are not needed for the operation of the algorithm). The right-hand side of this table shows the change in the value \(\omega_k'\) and gives the obtained codes of the initial \(i\) and terminal \(j\) events of the activities of the original list. Below is given the obtained

Table 2

\(S[m]\) 5, 11, 13, 15, 19, 1, 4, 16, 17, 10, 12, 14, 20, 7, 2, 6, 18, 8, 3, 9.

ny as a result of the operation of the algorithm, the array $s[m]$, and in Table 3—the list of dummy operations. Table 4 gives the complete list of real and dummy operations (dummy operations are marked with an asterisk, *), ordered by the code of their beginnings. From this list the network model of the development shown in Fig. 3 was constructed. It is not difficult to verify that the constructed network model fully corresponds to the initial data and to all the rules for constructing a network.

Fig. 3. Network model constructed from the results of the operation of the algorithm

It should be noted that the information obtained about the network model (Table 4) is usually used as the initial information for network analysis. Thus, the algorithm described makes it possible, without fully developing the network graph (without drawing the network and without coding the events), to proceed to its analysis on the basis of the information given in Table 1.

Table 3

List of dummy operations

Table 4

In the initial information obtained after analysis of the network graph and intended for the executors, the machine codes of the operations may be replaced by the sequential numbers of these operations in the initial list or by their actual names (if alphanumeric output is available), taken from the second column of Table 1.

References

1. Basic provisions for the development and application of SPM, Moscow, “Ekonomika,” 1965.

2. Yu. N. Efimov. A program for preliminary analysis of a complex network schedule with localization of logical errors. Izv. TPI. Collection “Proceedings of the Computing Laboratory,” No. 168, 1969.

3. Yu. N. Efimov. An algorithm for finding the ordinal function of a network schedule. Izv. TPI. Collection “Proceedings of the Computing Laboratory,” No. 168, 1969.