ON AN ALGORITHM FOR AUTOMATING CALCULATIONS OF PROCESSES FOR MANAGING THE DEVELOPMENT OF COMPLEX SYSTEMS

V. M. Razin, Yu. N. Efimov, V. I. Kizev

(Presented by the scientific seminar of the Faculty of Automation and Computer Engineering)

Recently, the literature [1] has increasingly raised the question of introducing fundamentally new methods of comprehensive operational planning and management of the development of complex systems. The essence of planning by these methods is reduced to the development of network models of processes, the analysis of these models with the aid of electronic digital computing machines (EDCM), with their subsequent use as a management tool at all stages of project execution. One variety of the above-mentioned methods is a system that takes into account only the duration of development. In such a system, known abroad under the name “pert-time,” the processing of information represented by a network schedule is reduced to finding the “critical path,” thereby concentrating the attention of managers on areas of potential difficulty in the course of the work. To solve problems of finding the “critical path,” it is proposed to use high-speed three-address EDCMs with a large amount of random-access memory [2]. At present, two-address EDCMs with a limited amount of random-access memory are becoming widely used. In this connection, it is of interest to consider the question of algorithmizing and programming problems of finding the “critical path” with respect to EDCMs of the class mentioned.

The analysis of a network schedule is usually reduced to the following problem. There is a network schedule without closed loops, containing \(M\) events and \(N\) jobs. To each job \(R_{ij}\), leading from event \(i\) to event \(j\), there corresponds a number \(l_{ij} \geqslant 0\), which we shall call the length of the job. The length of a job is nothing other than its duration in time. A path in the graph will be understood as a sequence of jobs from the initial event to the final one, where, for this sequence, the end of each preceding job coincides with the beginning of the following one. By the length of a path we shall understand the sum of the lengths of all jobs belonging to the given path. For such a graph it is required to determine the “critical path,” i.e., the path with the greatest length among all possible paths, having no time reserve, and several “subcritical” paths having a minimal time reserve.

The method we have developed for solving the stated problem is based on the principle of a complete enumeration of all possible paths in the network schedule.

The network schedule is specified by a list of jobs and their lengths, arranged in any sequence, in the form

\[ k)\ ijl_{ij_n}, \]

where \(k\) is the number of a memory cell, i.e. \(k=m, m+1, m+2,\ldots\)

\(i, j_n\) are the numbers of the events determining the beginning and end of the job \(R_{ij_n}\),

\(l_{ij_n}\) is the length of the job \(R_{ij_n}\),

\(n=1,2,3,\ldots\) are the indices of jobs issuing from one and the same event \(i\).

Processing information of this kind is carried out in two stages. At the first stage, all jobs are ordered by the code of their beginnings; at the second, passage through all possible paths is ensured and the “critical” and “subcritical” ones are selected from them.

Ordering the list of jobs by the code of their beginnings consists in placing the information about the job \(R_{ij_n}\) in the machine memory cell whose address is equal to the number of the event at which the job begins, \(i\). At the same time special indicators \(r\) and \(a\) are generated, so that information of the form is obtained

\[ i)\ r,a\ j_n,\ l_{ij_n}, \]

where \(i\) is the number of the memory cell,

\(j_n\) is the number of the end of a job issuing from event \(i\),

\(r\) is a quantity equal to the number of remaining jobs issuing from event \(i\); if there is no branching, \(r=0\),

\(a\) is a quantity characterizing the location in memory of information about another job issuing from this same event \(i\). Information about this job is placed in the cell with address \((a+c)\), where \(c=\mathrm{const}\). It is convenient to take the constant \(c\) equal to the largest event number of the network schedule.

The ordering of jobs is performed in a single pass through the initial information. When each line of the initial list of jobs is examined, \(i\) is singled out, and the information about this job is written at address \(i\). If, however, an entry has already been made in this cell, then in the information at address \(i\) the quantity \(r\) is increased by 1, \(a\) is formed, and the entry is made at address \(a+c\), etc.

Below is given an example of ordering the initial information and a block diagram of the program implementing the ordering algorithm (Figs. 1 and 2).

Fig. 1. Example of ordering information.

In cell \(i\) is placed one of the jobs which, when the initial information is examined, is encountered first. Let this be the job \(R_{ij_1}\); then the ordered arrangement of information (Fig. 1) will be as follows:

\[ i)\ r_1,\ a_1,\ l_{ij_1}\quad (r_1=3), \]

\[ \cdots\cdots\cdots \]

\[ c+a_1)\ r_2,\ a_2,\ l_{ij_2}\quad (r_2=2), \]

\[ c+a_2)\ r_3,\ a_3,\ l_{ij_3}\quad (r_3=1,\ a_3=0). \]

Thus, the attribute \(r\) is the number of as-yet-unexamined jobs issuing from one and the same event, increased by one.

The attribute \(a\) is formed as follows. Each time that, in ordering the information, events are encountered from which more than one job among the unordered jobs issues, one is added to a special counter. The value of the parameter \(a\) for the job under consideration is taken to be the number accumulated in the counter by the time the job issuing from the event that is the beginning of the unexamined jobs is examined.

The parameter \(a\) is taken equal to zero in two cases:

1) when the job being examined is the only one issuing from the given event;

2) when the job being examined is the last of all the jobs issuing from the given event.

The formation of the attributes \(a\) and \(r\) is illustrated by the block diagram of the program for ordering the initial information in Fig. 2.

After ordering the list of jobs, it is easy to select all possible paths on the network graph. The analysis of the network graph is carried out according to a program whose block diagram is presented in Fig. 3.

Having specified the initial event, it is necessary to read the information from the memory cell having the number of the initial event, select event \(j\), take it as the initial event, etc., until the process reaches the terminal event. The selected completed jobs are written successively into \(z\) cells. Thus we obtain the traversed path in the form of the following information table

\[ r_n,\ a_n,\ j_n,\ l_n, \]

\[ \ldots\ldots \]

\[ r_k,\ a_k,\ j_k,\ l_k, \]

\[ 0,\ 0,\ 0,\ L_k, \]

where \(n = 1, 2, 3,\ldots,k\).

\(k\) is the number of jobs comprising the selected path,

\(L_k\) is the length of the selected path.

In this case the length of the selected path \(L_k\) is obtained as the result of summing all the lengths of the jobs of the given path. Information about one job that enters the selected path and is written in one memory cell will be called a path row. After one of the paths has been selected, the attribute \(r\) is analyzed in the rows of the information table, beginning with the last. If the row contains the attribute \(r > 1\) (we shall call this row a boundary row), a reference is formed to the memory cell with the number

Fig. 2. Block diagram for ordering the initial information.
1 — restoration; 2 — extraction of \(i\) from the row of initial information and sending it to cell \(f\); 3 — reading information from the cell whose address is in \(f\); 4 — extraction of \(r\); 5 — writing information into the cell with the address stored in cell \(f\); 6 — redirection of the examination of the initial information and comparison for the end of examination; 7 — end; 8 — extraction and analysis of \(a\); 9 — adding one to the counter; 10 — formation of the value of \(a\), equal to the contents of the counter; 11 — formation of the address \((a+c)\) and sending it to cell \(f\).

\(a+c\). Taking event \(j\) in this cell as the initial one, a path is selected according to the algorithm described above. Information about the path is entered in the cells \(z\), beginning with the boundary row. A new path is obtained, whose information table differs from the preceding one only in the boundary row. The process is repeated until \(r=1\) in all rows of the path. In this way all possible paths of the network schedule will be selected.

Thanks to the preliminary ordering, the process of selecting all possible paths proceeds comparatively quickly. The selection of all possible paths ends with the storage of \(m\) lengths of “critical” and “subcritical” paths (\(m\) is any integer less than \(p\), where \(p\) is the number of all possible paths). In this case the selection and storage of the \(m\) longest paths is organized by programming as follows. At the initial stage, \(m\) different path lengths, computed first, are stored. All subsequently computed path lengths are compared with the minimum of the stored lengths. If the length being compared is greater and if among the stored ones there is no value equal to it, then it is written into the memory cell in place of the previously stored minimum length. During the secondary pass, information tables are printed for those paths whose lengths coincide with the previously stored ones.

It should be noted that the method considered does not include the possibility of automatically finding circuits.

If it is necessary to obtain only one critical path, it is recommended that the algorithm described be modified somewhat in order to increase speed. The selection of paths proceeds as in the first case, but when analyzing the signs \(r\) in the information table for each event having several outgoing operations, only one operation is left—the one along which the “critical path” would pass if this event were taken as the initial one. The process ends with the finding of the “critical path,” and no secondary pass is required.

According to the algorithm described, a program was compiled and tested on the “Minsk-1” digital computer. With a machine random-access memory capacity of 1024 words, the program can analyze a network schedule having up to 800 operations and no more than 512 events, in view of limitations due to the machine’s small digit grid. In principle, it is possible to analyze a network schedule of any size, after first dividing it appropriately into sections.

Fig. 3. Flowchart of the main program.
1 — loading the initial event into cell \(f\); 2 — writing the cell with address \(B\) from \(f\) into cell \(z\); 3 — selecting \(j\) in \(f\); 4 — comparison for end of path; 5 — finding \(L\) and comparison with \(min\); 6 — analysis of \(r\); 7 — comparison for end; 8 — selecting \(a\) and forming new addresses; 9 — stop.

REFERENCES

1. G. S. Pospelov, A. I. Teiman. Automation of the processes of managing developments of large systems or complex complexes. Izvestiya AN SSSR, Technical Cybernetics, No. 4, 1963.

2. Computing Systems, Publishing House of the Siberian Branch of the Academy of Sciences of the USSR, Novosibirsk, 1964, issue No. 11.