OPTIMIZATION OF THE WORK DISTRIBUTION PLAN IN A NETWORK PLANNING AND MANAGEMENT SYSTEM WITH LIMITED RESOURCES

Yu. N. Efimov

(Presented by the scientific seminar of the Computing Laboratory)

In creating unique prototypes of new equipment, large systems, and complex facilities, the most convenient instrument for planning and management is a method based on the analysis of network graphs [1]. Network planning and management (NPM) methods make it possible to identify “bottlenecks” in a project already at the planning stage. At the second stage—the management stage—the NPM system helps concentrate the attention of managers on “critical” activities, delays in the execution of which entail a corresponding shift in the completion date of the entire complex. By using high-speed electronic computers (ECM), the NPM system becomes an operational management system that reacts quickly to any change in the initially accepted parameters (the graphical model and the time characteristics of activities).

At present, algorithms have been developed for the time [2, 3] and logical [4] analysis of network graphs, and some experience has been accumulated in the application of NPM systems in industry and construction. However, in analyzing network graphs, the available resources (labor, equipment, etc.) are usually not taken into account; that is, the resources are regarded as unlimited. But since, in practice, resources are always limited, such an analysis leads to an understatement of the total estimated time for completing all activities of the complex \((t_{\mathrm{cr}})\) and gives incorrect dates for the execution of individual activities. In the literature there are attempts to take resource constraints into account by including in the concept of the critical path criticality not only with respect to time, but also with respect to resources [5]. In practice, limited resources are also taken into account when drawing up network graphs by the very topology of the network (parallelization of activities, introduction of dummy activities, etc.). Naturally, such accounting is carried out in a far from optimal manner. Thus, the problem arises of the optimal distribution of resources among activities, i.e., of compiling such a work schedule, taking into account their technological relationships, which, under given limited resources, would ensure completion of the project in minimum time. Often it is of interest to solve the inverse problem, that is, to find the optimal required resource for completing the project by a given deadline. Up to the present time, no complete solution of these problems has been found; however, heuristic algorithms [6] are being developed that lead to sufficiently good,

practically satisfactory solutions. We shall describe one such algorithm for solving the inverse problem, as well as a program implementing the algorithm on the Minsk-1 computer.

Let a loop-free network graph \(G=(I, U)\) be given by a set of jobs \((U)\), their durations \(t_{ij}\geq 0\), and the intensities of resource consumption on each job \(v_{ij}>0(ij\in U)\). We shall assume that all jobs consume a resource of one kind, for example labor. Moreover, the intensity of resource consumption on each job remains constant throughout the entire time of the job’s execution, i.e. \(v_{ij}=\operatorname{const}\) on \((0,t_{ij})\). Let the labor-motion graph (equipment-load graph) be a step function \(R(t)\) having at least one maximum in the time interval \((0,t_{\mathrm{cr}})\). The problem consists in arranging the jobs in such a way that the quantity \(\max_{t\in(0,t_{\mathrm{cr}})} R(t)\) is minimal. In other words, it is required to determine the minimum number of workers (machines) needed to perform the entire complex of jobs no later than \(t_{\mathrm{cr}}\), where \(t_{\mathrm{cr}}\) is the value calculated without taking resource constraints into account.

An optimal arrangement of jobs within the time interval \((0,t_{\mathrm{cr}})\) can be achieved by delaying the start time of certain jobs that do not lie on the critical path. Such jobs, called “noncritical,” possess a certain time reserve for their execution. As is known [7], four kinds of reserves of noncritical jobs can be distinguished: total, free, and two kinds of partial reserves. The total time reserve \(P_{\mathrm{n}}(ij)\) of a job is the maximum possible time by which the completion of the given job may be postponed by delaying its start, without postponing the time of the final event of the complex of operations, i.e. without increasing the duration of the critical path.

\[ P_{\mathrm{n}}(ij)=t_{\mathrm{n}}(j)-t_{\mathrm{p}}(i)-t_{ij}, \]

where

\(t_{\mathrm{n}}(j)\) is the latest of the admissible times of occurrence of the final event \((j)\) of job \((ij)\),

\(t_{\mathrm{p}}(i)\) is the earliest of the possible times of occurrence of the initial event \((i)\) of job \((ij)\),

\(t_{ij}\) is the duration (length) of job \((ij)\).

The total time reserve of job \((ij)\) is the time reserve of the longest of the paths passing through this job. Using part of a job’s total time reserve to delay the start of its execution changes the total time reserves of all subsequent jobs and requires their recalculation. In addition, it may happen that the entire time reserve will be spent on the initial jobs, while the final jobs will no longer be able to be delayed, which significantly worsens the distribution plan. Consequently, the use of \(P_{\mathrm{n}}(ij)\) for optimizing the arrangement of jobs for a specified project completion time \((t_{\mathrm{cr}})\) is associated with computational difficulties and does not always lead to satisfactory results. For purposes of optimization it is preferable to use such time reserves whose expenditure on initial jobs has no effect on the magnitude of the reserves of subsequent jobs. Such a reserve can be the free time reserve of a job—the maximum time by which the start of the job can be delayed without changing the occurrence times of its initial \((i)\) and final \((j)\) events.

\[ P_{\mathrm{c}}(ij)=\max\{0,[t_{\mathrm{p}}(j)-t_{\mathrm{n}}(i)-t_{ij}]\}. \]

However, as experience with calculations has shown, the overwhelming majority of jobs in real network schedules have \(P''(ij)=0\). Shifts of the start of jobs only within their \(P_{\mathrm{c}}\) give, in most cases, an insignificant reduction in the value \(\max_{t\in(0,t_{\mathrm{cr}})} R(t)\). Therefore it seems expedient to us, for optimizing the placement of jobs with a given project completion time, to use the partial float of the second kind. The partial float of the second kind \([P_{\mathrm{p}}(ij)]\) is formed for jobs immediately preceding an event at which paths of different lengths intersect. This float indicates what part of the total time float of a job can be used to shift the start of this job and of the jobs preceding it that belong to the segment of the path lying between the two nearest points of its intersection with paths of greater length, provided that this shift does not cause a reduction in the float of any of the subsequent jobs.

\[ P_{\mathrm{p}}'''(ij)=t_{\mathrm{p}}(j)-t_{\mathrm{p}}(i)-t_{ij}=P_{\mathrm{p}}(ij)-p(j), \tag{1} \]

\(P(j)\) is the time float of event \(j\), determined by the formula

\[ p(j)=t_{\mathrm{l}}(j)-t_{\mathrm{p}}(j). \]

As is seen from (1), the use of \(P_{\mathrm{p}}'''(ij)\) changes only the values \(P_{\mathrm{p}}(ij)\) for preceding jobs, while the values \(P_{\mathrm{p}}''(ij)\) of all jobs do not change; therefore no recalculation of time floats is required.

The initial information about each job, evidently, must include:

1) \(t_{\mathrm{rn}}\) — early start time of the job,
2) \(P_{\mathrm{p}}''\) — time float,
3) \(N\) — designation of the job (two-index or one-index),
4) \(t_{ij}\) — duration of the job,
5) \(v_{ij}\) — intensity of resource consumption.

Consequently, the initial information is a matrix \(M\) of dimensions \((n\times 5)\), where \(n\) is the number of jobs. Then the optimization problem being solved can be formulated as follows.

By increasing \(t_{\mathrm{rn}}\) of some jobs \((ij)\in U\) by an amount \(\delta\leq P_{\mathrm{p}}''(ij)\), find a plan for placing jobs in time \((0,t_{\mathrm{cr}})\) that minimizes

\[ \max_{t\in(0,t_{\mathrm{cr}})} R(t). \]

Obviously, the desired \(\min \max R(t)\geq R_{\mathrm{av}}\), where

\[ R_{\mathrm{av}}=\frac{\sum_{ij\in U} v_{ij}t_{ij}}{t_{\mathrm{cr}}}, \]

is the average amount of resource consumed per unit time. Consider the following subsets of the set \(U\).

\[ A(t)=\{(ij)\in U/t_{\mathrm{rn}}(ij)=t\}, \tag{2} \]

\[ C(t)=\{(ij)\in U/t_{\mathrm{rn}}(ij)+t_{ij}=t\}, \tag{3} \]

\[ B(t)=\{ij\in U/t_{\mathrm{rn}}(ij)<t<t_{\mathrm{rn}}(ij)+t_{ij}\}. \tag{4} \]

These subsets may be regarded as single-valued functions of the independent variable \(t\) (time). It follows from (2–4) that \(A(t)\) includes jobs that begin at time \(t\), \(C(t)\) jobs that end at time \(t\), and \(B(t)\) jobs that began earlier and continue at time \(t\). We shall call the front of work \(F(t)\) the subset of jobs being performed at time \(t\).

\[ F(t)=\{(ij)\in U/t_{\mathrm{rn}}(ij)+t_{ij}>t\}. \tag{5} \]

Obviously, \(F(t)=A(t)\cup B(t)\).

For \(t=0\), \(B(0)=\varnothing;\ F(0)=A(0)\).

For

\[ t=t_{\mathrm{cr}}\quad B(t_{\mathrm{cr}})=\varnothing;\quad A(t_{\mathrm{cr}})=\varnothing;\quad F(t_{\mathrm{cr}})=\varnothing . \]

The function \(R(t)\) can be defined as the sum of the resource-consumption intensities of all jobs in the front \(F(t)\).

\[ R(t)\sum_{(ij)\in F(t)} v_{ij}. \tag{6} \]

Therefore, in order to find \(R(t)\) it is sufficient to form the job front for each \(t\) in the interval \((0,t_{\mathrm{cr}})\) and to sum the \(v_{ij}\) of the jobs belonging to \(F(t)\). Then the minimization algorithm reduces to the following.

1. The function \(R_0(t)\) and the value \(\max R_0(t)\) are found, i.e., the graph of labor-force movement without optimization is constructed.

Let, for some time \(t_k\), the job front \(F(t_k)\) have already been formed; then the function \(R_0(t)\) is constructed as follows:

a) The resource-consumption intensities for these jobs are summed and the point \(R_0(t_k)\) is found.

\[ R_0(t_k)=\sum_{(ij)\in F(t_k)} v_{ij}. \]

b) The quantities \(R(t_k)\) and \(\max R_0(t_k)\) are compared; the larger of them is taken as \(\max R_0(t_k)\).

c) The durations of all jobs \((ij)\in F(t_k)\) are decreased by one.

d) From the jobs whose duration becomes equal to zero, a subset \(C(t_{k+1})\) is formed; from the remaining jobs, a subset \(B(t_{k+1})\) is formed.

\[ B(t_{k+1})=F(t_k)/C(t_{k+1}). \]

e) From the set of jobs \(U\), the jobs beginning at the time \(t_{k+1}\) are selected, and the subset \(A(t_{k+1})\) is formed.

f) The new job front \(F(t_{k+1})\) is found.

\[ F(t_{k+1})=A(t_{k+1})\cup B(t_{k+1}). \]

g) If \(t<t_{\mathrm{cr}}\), go to a); if \(t=t_{\mathrm{cr}}\), the function \(R_0(t)\) has been constructed and the value \(\max R_0(t)\) has been found.

1. An attempt is made to construct the function \(R_1(t)\), setting the limit

\[ \max R_1(t)\leq \max R_0(t)-1. \]

Let, for some time \(t_k\), the job front \(F(t_k)\) have already been formed; then the construction of \(R_1(t)\) is carried out as follows:

a) The jobs of the front are ordered in increasing order of the value \(P_{\mathrm{n}}''(ij)\) (i.e., priority is given to jobs with a smaller time reserve).

b) \(R(t_k)=\sum_{(ij)\in F(t_k)} v_{ij}\) is found, with the summation being carried out until the obtained sum exceeds the value \([\max R_0(t)-1]\). The job whose resource-consumption intensity makes the sum greater than \([\max R_0(t)-1]\) is shifted to the right, i.e., excluded from \(F(t_k)\) and transferred to \(F(t_{k+1})\). In this case its start time is increased, and the time reserve is decreased by one. However, a shift to the right is possible only if the reserve of the shifted job is greater—

than zero. Otherwise, further improvement of the plan is impossible, and one should proceed to 3. After the shift of the activity, the summation of the resource-consumption intensities of the remaining activities of the front is continued.

c) From the durations of all unshifted activities of the front, one unit is subtracted, and all these activities are assigned the value \(P_{\text{p}}^{\text{i}}=0\), since it is assumed that the activities do not allow interruption.

d) The remaining steps in constructing \(R_1(t)\) are analogous to the construction of \(R_0(t)\). After constructing \(R_1(t)\), an attempt is made to construct \(R_2(t)\), taking into account the constraint

\[ \max R_2(t)\leq \max R_1(t)-1 \]

and so on, until after constructing \(R_{\text{p}}(t)\) further improvement of the plan is impossible.

1. The improvement coefficient is found:

\[ K_{\text{ul}}=\frac{\max R_{\text{p}}(t)}{\max R_0(t)}. \]

This coefficient gives a quantitative characteristic of the degree of improvement of the initial work-distribution plan. Obviously, \(K_{\text{ul}}\leq 1\).

Below is a formal description of the algorithm in terms of the ALGOL-60 language [8].

begin integer r, Ct 1, CtF, n, no, max S, max 1 S;
    procedure forwarding (u, d, A, B);
        integer u, d; integer array A, B;
        begin integer j; for j:=1 step 1 until 5 do
            B[d, j]:=A[u, j] end;
input (n, no); r:=0; max S:=0;
    begin integer A_n, f; integer array N [no:no+n, 1:5];

input (N);
        L1: Ct1:=0; CtF:=1; A_n:=no; f:=0;
        L2: begin integer i, Ct4; integer array F [1:CtF, 1:5];
            Ct4:=0; for i:=1 step 1 while Ct4=CtF do
            begin go to if F [i, 3]>0 then M2 else M1
                M1: CtF:=CtF−1; if F [CtF, 3]>0 then
                    forwarding (CtF, i, F, F) else go to M1;
                M2: Ct4:=Ct4+1 end
            end;
            go to if f=0 then formation F else
            if CtF>0 then L3 else L5;
        formation F: begin integer i;
            for i:=A_n step 1 while N[i, 1]>Ct1 ∨ A_n>no+n do
            if N[i, 3]>0 then begin CtF:=CtF+1;
                forwarding (i, CtF, N, F) end; A_n:=A_n+1;
            if A_n=no+n then f:=f+1 end;
        L3: begin integer i, ro; integer array F [1:CtF, 1:5],
            r[1:5];
            if CtF=1 then begin CtF:=CtF+1; print <0>;
            go to L4 end;

M1: ro:=0; for i:=1 step 1 until CtF−1 do
 begin if F[1, 2]>F[i+1, 2] then begin
  transfer (i, 1, F, r); transfer (i+1, i, F, F);
  transfer (i, i+1, r, F); ro:=ro+1 end
 end;
 go to if ro>0 then M1 else M2;
M2: end;
begin integer S, i; S:=0; i:=0;
 MO: i:=i+1; if i>CtF then go to M4;
 if F[i, 5]=0 then go to M3; S:=S+F[i, 5];
 if S≤max S then go to M2 else if r=0
 then go to M1; S:=S−F[i, 5]; if F[i, 2]>0
 then begin F[i, 2]:=F[i, 2]−1; F[i, 1]:=
 F[i, 1]+1; go to MO end else go to L8;
 M1: max S:=S;
 M2: F[i, 2]:=0; F[i, 4]:=F[i, 4]−1;
  go to if F[i, 4]=0 then M3 else MO;
 M3: F[i, 3]:=0−F[i, 3]; print (F[i, 3], F[i, 1]);
  go to MO;
 M4: end; print (S);
L5: interval; go to if r=0 then L6 else L7;
L6: max 1S:=max S;
L7: max S:=max S−1; go to L1
end;
L8: begin real \(K_{\text{ul}}\); \(K_{\text{ul}}\):=max S/max 1S;
print (\(K_{\text{ul}}\)) end;

The described algorithm was tested on the “Minsk-1” electronic digital computer. The initial information about one job was written into one cell of the machine’s random-access memory in the form

\[ (m)\ t_n\ P\ N\ t\ v, \tag{7} \]

where

\(m\) — memory-cell number,
\(N\) — single-index job number.

The program occupies 233 “8” cells of the machine’s random-access memory and can optimize network schedules containing up to 770 jobs. Moreover, information on jobs may be specified with omissions; in that case the omitted cell must contain the standard word—zeros in all digits.

At the operator’s request the program prints:

1) the function \(R_0(t)\),
2) the function \(R_n(t)\) and \(K_{\text{ul}}\),
3) all intermediate functions \(R_k(t)\).

In all three cases, the start time may be printed for each job or only for shifted jobs. The program makes it possible to improve the job-distribution plan of large network schedules for multitheme developments that consume several types of resources. To do this, from all jobs of the time-calculated network schedule, jobs consuming only one type of resource are selected. These jobs constitute the initial information about some subgraph \(G_1 \subset G(I, U)\), to which the described algorithm is applied. Similar calculations must be applied for each type of resource. Optimization should be carried out after the complete time analysis of the network schedule, since then it is sufficiently simple to form, by program means, the initial information in the form (7).

References

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

2. G. M. Adelson-Velsky, F. M. Filler. A program for computing network schedules. Zh. Vychisl. Mat. i Mat. Fiziki, vol. 5, No. 1, 1965.

3. A. G. Petrova, N. N. Karnaukhova. On one algorithm for finding the critical path of a network schedule. In: Computing Systems, issue 11, Novosibirsk, Publishing House of the Institute of Mathematics, Siberian Branch, USSR Academy of Sciences, 1964.

4. L. Ya. Leifman, A. T. Petrova. Some algorithms for the analysis of oriented graphs. In: Computing Systems, issue 11, Novosibirsk, Publishing House of the Institute of Mathematics, Siberian Branch, USSR Academy of Sciences, 1964.

5. I. D. Wiest. Operations Research, 12, 1964.

6. S. I. Zukhovitskii, I. A. Radchik. Mathematical Methods of Network Planning. Moscow, 1965.

7. Basic Provisions for the Development and Application of NPM. Moscow, “Ekonomika,” 1965.

8. M. I. Ageev. Fundamentals of the ALGOL-60 Algorithmic Language. Computing Center, USSR Academy of Sciences, Moscow, 1965.