ON THE ANALYSIS OF CALENDAR PLANS

A. I. GUDZENKO, L. V. KOCHNEV, L. V. PERFIL'EV

(Presented by the scientific-technical seminar of the Department of Automated Control Systems and the Control Laboratory)

Problems of calendar planning for complex sets of operations are a very difficult aspect of optimal planning. They form the basis of the mathematical support of such subsystems of automated control systems as preparation of new production, operational-calendar planning of main production (especially unit and small-batch production), and others. Known works on calendar planning consider only questions of the synthesis of plans, including optimal ones \([1, 2]\). In the present work an attempt is made to analyze a calendar plan, making it possible to assess the influence of individual parameters of the system on the quality of the plan.

In solving practical problems of calendar planning, situations arise quite often in which a calendar plan constructed by some method, even an optimal one, does not satisfy certain constraints, i.e., is infeasible. Analysis of the plan in this case may prove to be a very effective means of improving it.

Let us consider the calendar planning of the execution of \(M\) products on \(N\) machines. The manufacturing technology of each \(m\)-th product, \(m = 1, M\), is described in the most general case by a network graph \(\Gamma_m\), \(\Gamma_m = (U_m, V_m)\). Here \(U_m\) is the set of vertices of the graph \(\Gamma_m\), and \(V_m\) is the set of directed arcs of the graph—\(V_m = \{(ij)\}_m\). Moreover, the graph is colored, i.e., the indexing of the vertices is carried out with allowance for the precedence order specified by \(V_m\).

In terms of network planning, each vertex \(j\) is an event consisting in the completion of all operations (arcs) \((ij)\) having \(j\) as their terminal vertex. Each operation \((ij)_m\) is characterized by the parameters: \(\tau^{-}(ij)_m\) and \(\tau^{+}(ij)_m\)—respectively the “optimistic” and “pessimistic” estimates of the time required to perform the operation; \(n(ij)_m\)—the index of the machine servicing the operation. It is more convenient to specify not time estimates, but volume estimates of the operation—\(Q^{-}(ij)_m\) and \(Q^{+}(ij)_m\). Then

\[ \tau^{-}(ij)_m = \frac{Q^{-}(ij)_m}{x_n}; \tag{1} \]

\[ \tau^{+}(ij)_m = \frac{Q^{+}(ij)_m}{x_n}, \tag{2} \]

where \(x_n\) is the capacity of the \(n\)-th device.

Using one of the known algorithms \([1, 2, 3]\), we construct a calendar plan for carrying out the set of requests \(G=\{\Gamma_1,\Gamma_2,\ldots,\Gamma_M\}\), taking into account the arrival times of the requests \(t_m^{s}\). For definiteness, we shall take the execution time of the operations \(\tau(ij)_m\) to be equal to the mathematical expectation (for example, for a beta distribution of \(\tau\)).

Suppose that the algorithm used is sufficiently efficient and, consequently, that the constructed calendar plan \(R=(A,\{t^{s}(ij)_m\})\) is close to optimal. The plan \(R\) consists of its structure \(A\), i.e., the sequence in which the operations are carried out, and the set of start times of the operations \(t^{s}(ij)_m,\ (ij)_m\subset V_m,\ m=\overline{1,M}\).

As the measure of the plan’s efficiency we shall use the most widespread form

\[ F(R)=\max t_m^{f}\to \min . \tag{3} \]

Suppose that some plan \(R^*\), optimal with respect to criterion (3), has been found; however, it may fail to satisfy the specified constraints, for example:

\[ t_m^{f}\leq t_m^{\mathrm{dir}},\quad m=\overline{1,M}, \tag{4} \]

where \(t_m^{\mathrm{dir}}\) is the directive deadline for completing the \(m\)-th request. The problem arises of determining the reasons that do not allow the indicated conditions to be met; in other words, the problem of analyzing the plan and finding its “bottlenecks.”

We introduce the necessary definitions.

Definition 1. By a path \(L\) of the calendar plan \(R\) we shall mean such a sequence of operations \((ij)_m^n,\ m=\overline{1,M};\ n=\overline{1,N}\), that each adjacent pair of operations in the path satisfies one of the following two conditions, or both of them together:

a) the operations \((ij)_m\) and \((il)_m\) belong to the same request, and one of the operations directly precedes the other in the structure \(\Gamma_m\), while the completion time of the first operation and the start time of the second coincide:

\[ t^{f}(ij)_m=t^{s}(il)_m; \tag{4'} \]

b) the preceding operation in the path \((i_1j_1)_{m_1}^n\), according to the adopted service discipline \(P\), precedes the operation \((i_2j_2)_{m_2}^n\), i.e.,

\[ t^{f}(i_1j_1)_{m_1}^n=t^{s}(i_2j_2)_{m_2}^n,\quad m_1\ne m_2 \tag{5} \]

and

\[ t^{s}(i_2j_2)_{m_2}^n>t(i_2)_{m_2}, \tag{6} \]

where \(t(i_2)_{m_2}\) is the time at which event \(i_2\) occurs in the \(m_2\)-th request.

If, when condition (5) is satisfied, instead of inequality (6) we have the equality

\[ t^{s}(i_2j_2)_{m_2}^n=t(i_2)_{m_2}, \tag{7} \]

then the vertex \((i_2)_{m_2}\) is a branching point of paths in the calendar plan. As an elementary path we shall take a sequence of operations satisfying Definition 1, containing one initial and one final operation, and differing from the other paths by at least one element (operation). If, for some node (vertex) of the plan, conditions a) and b) are simultaneously satisfied, or condition a) is satisfied two or more times, then the path \(L\) approaching this node branches into two or more paths. It should be noted that the beginning

the path is considered to be the operation that is last on one of the machines. The construction and analysis of paths is carried out starting from the terminal operations of the plan.

Figure 1 shows the final fragment of a calendar plan for the execution of four orders \(m_1,\ldots,m_4\) on three machines \(n_1,n_2,n_3\). The vertices of the graphs \(\Gamma_{m_1},\ldots,\Gamma_{m_4}\) are denoted respectively by the indices \(i,j,l\), and \(p\) with ordinal numbers. Two paths are distinguished—\(L_1\) and \(L_2\), which merge into one path \(L\) at the point \((n_1,j_5,i_2)\). At the point \((n_2,j_3)\) the path \(L\), by virtue of the simultaneous fulfillment of conditions a) and b), branches into two paths—\(L'\) and \(L''\).

Fig. 1.

Thus, the family of paths in the calendar plan \(\{L\}\) can be represented in the form of a tree with roots, a trunk, and branches. The roots of the tree, or of several trees, are formed by the terminal operations of the set \(G\) on which the plan is constructed, and the branches are formed as a result of branching when moving toward the initial operations of the plan.

If the time estimates of the operations \(\tau(ij)^n_m\) are given, in the general case, by fractional numbers, the probability of branching of paths is very small. However, in practice \(\tau(ij)^n_m\) are quite often specified by integers, and branching of paths becomes possible. In the analysis of a calendar plan, the path that affects the completion of the entire set of operations \(G\) is of greatest interest. For this purpose we introduce the following.

Definition 2. The limiting path of the calendar plan \(R\) will be called the path \(L^*\) whose terminal operation \([(ij)^n_m]^*\) has

\[ t^0[(ij)^n_m]^*=\max_R t^0(ij)^n_m. \tag{8} \]

From Definitions 1 and 2 follows an algorithm for constructing the limiting path \(L^*\) in the plan \(R\):

\(1^\circ.\) Find the operation \([(ij)^n_m]^*\) satisfying (8).

\(2^\circ.\) The current time \(t\) is determined as

\[ t=t^n[(ij)^n_m]^*. \tag{9} \]

\(3^\circ.\) From the plan \(R=\{t^n(ij)^n_m;\ t^0(ij)^n_m\}\) choose operations \((ij)^n_m\) for which

\[ t^0(ij)^n_m=t, \]

and conditions a) or b) are fulfilled.

These operations form the subset of subsequent operations \(\{(ij)\}_c\).

\(4^0\). If \(\{(ij)\}_c \ne \varnothing\), we choose the operation \([(ij)_m^n]^* \subset \{(ij)\}_c\) to which there corresponds (for definiteness)

\[ t^H[(ij)_m^n]^*=\max_{\Omega_c} t^H(ij)_m^n, \tag{10} \]

where

\[ \Omega_c=(ij)_m^n \subset \{(ij)\}_c . \]

The chosen operation \([(ij)_m^n]^*\) is included in the limiting path \(Z^*\), and the operations remaining in \(\{(ij)\}_c\) are copied into the subset of “branching” operations \(\{(ij)\}_p\), after which the next cycle of forming \(L^*\) begins (transition to \(2^0\)).

\(5^0\). If \(\{(ij)\}_p=\varnothing\), transition to \(6^0\); otherwise \([(ij)_m^n]^*\) is chosen:

\[ t^0[(ij)_m^n]^*=\max_{\Omega_p} t^0(ij)_m^n, \tag{11} \]

this operation is included in \(L^*\), and the formation of a new branch \(Z^*\) begins (transition to \(2^0\)).

\(6^0\). The tree of the limiting path \(L^*\) has been constructed; the results are formed and output for printing.

The limiting path of the calendar plan that has been found makes it possible to analyze the plan in order to identify both the most heavily loaded devices and the most critical operations. Let us consider the problem of redistributing capacities (throughputs) among the service devices of the system using the introduced concept of a limiting path.

It is required to distribute limited homogeneous resources (for example, people, equipment, finances, time, etc.) among \(N\) devices of the system so as to minimize the time required to perform the entire complex of operations \(F(R)\), under conditions of the form

\[ \sum_{n=1}^{N} x_n = S, \tag{12} \]

\[ x_n \ge 0,\quad n=\overline{1,N}. \tag{13} \]

It is obvious that the devices on which a larger number of operations of the limiting path falls are, for the given calendar plan, the most heavily loaded. It appears possible, on the basis of analysis of the calendar plan and the identification in it of the limiting path, to organize an iterative procedure for distributing resources among the devices.

The loading time of the \(n\)-th device \(\beta_n\), as the relative total time spent by this device in performing operations belonging to the limiting path, is

\[ \beta_n=\frac{1}{t_G^0}\sum_{(ij)_m^n \subset L^*}\tau(ij)_m^n,\quad n=\overline{1,N}. \tag{14} \]

Then the adaptive optimization algorithm for \(x_n^*,\ n=\overline{1,N}\), is written as

\[ \widetilde{x}_n^{(s+1)}=x_n^s+\gamma_{ns}(\beta_n^s-\bar{\beta}^{\,s})x_n^s. \]

Here

\[ \bar{\beta}^{\,s}=\frac{1}{N}\sum_{n=1}^{N}\beta_n^s; \]

$\gamma_{ns}$ is an element of the matrix $\|\gamma\|$, which, in the first approximation, should be taken as the identity diagonal matrix.

Condition (12) is taken into account by the formula

\[ x_n^s=\frac{\tilde{x}_n^s}{\sum_{n=1}^{N}\tilde{x}_n^s}. \tag{16} \]

The termination of the search is determined by the usual methods [4].

An experimental study of the proposed algorithm on an electronic digital computer showed its sufficiently rapid monotone convergence. Optimization of the parameters $x_n$, carried out on a mathematical model of a real research organization, made it possible to reduce the duration of the planned work by 7%.

The algorithm described above for computing the limiting path is an effective tool for analyzing calendar plans for the purpose of controlling some production process. Below we consider several questions concerning the use of this algorithm in controlling the process of preparing new production. As already noted, the basis of the mathematical support of the subsystem for preparing new production is a mathematical model of the process, making it possible to obtain an optimal calendar plan for carrying out the entire complex. Such a calendar plan establishes the sequence of execution of operations, described by the vector $\vec{A}^{*}$, as well as the optimal values of the service durations of operations, determined by the vector $\vec{t}^{*}$.

Control of the process of preparing new production on the basis of an optimal calendar plan consists in forming control actions in order to eliminate deviations of the actual course of the process from the planned one. One such control action [5] is the intensification of the performance of individual operations within departments. When using the indicated control action, it is advisable to determine a set of priority departments, intensification of whose activity, in comparison with the others, leads to a more substantial reduction in the time required for preparing new production. As such priority departments it is proposed to consider those departments for which $P$—the probability of disruption of the plan through their fault—has the maximum value. Below an algorithm is given that makes it possible to compute the indicated probability. The basis of the algorithm for computing $P$ is the following machine experiment.

1. With the aid of the model of the process of preparing new production, for a fixed value of the sequence vector $\vec{A}^{*}$, $K$ plans $[\vec{A}^{*},\vec{t}^{\,\nu}]$, $\nu=\overline{1,K}$, are formed, whose completion time $(t^{0})$ is greater than $t^{0*}$.

2. For these plans the limiting paths $L_\nu^{*}$ are determined.

3. For each $\nu$-th plan, $\{s\}_n^\nu$ is formed—the set of operations serviced by the $n$-th apparatus and lying on the limiting path. For each operation of the set $\{s\}_n^\nu$, the quantity $d_n^\nu$ is computed—the difference between the optimal value of the time for performing this operation, determined by the vector $\vec{t}^{*}$, and the value of the time determined by the vector—

by the vector $\vec t^{\,v}$. Then the values $a_n^{v}$ are summed over all operations of the set $\{s\}_n^{v}$, i.e., $\sum_{\{s\}_n^{v}} a_n^{v}$.

4. $p_n$ is computed—the number of plans for which $\sum_{\{s\}_n^{v}} a_n^{v}<0$, and the quantity $P$ is defined as the ratio of $r_n$ to the number of generated plans $K$.

It is necessary to note certain features of the algorithm that make it possible to substantially simplify the computational procedure. As noted above, the generation of plans is carried out for a fixed vector $\vec A^{*}$. In this connection, the corresponding paths $L$ of all calendar plans do not differ from one another in terms of the type and sequence of operations of which they consist. These paths differ only in the durations of the operations. In this case, the limiting path $L^{*}$ is the one for which the sum of the execution times of all operations is maximal. Consequently, there is no need at each successive realization to generate the plan $[\vec A^{*}, \vec t^{*}]$ and compute its limiting path. It is advisable, for the plan $[\vec A^{*}, \vec t^{*}]$, to determine all paths $L$; then to compute the length of each path in the $v$-th plan of the sample $[\vec A^{*}, \vec t^{\,v}]$, $v=1,\overline{K}$, as the sum of the execution times of the corresponding operations (the value of this time is a realization of the random vector $\vec t^{\,v}$); and, finally, to determine the limiting path $L^{*}$ as the one of maximum length.

REFERENCES

1. V. V. Shkurba et al. Problems and Methods of Calendar Planning. Kiev, “Naukova dumka,” 1966.

2. D. I. Golenko, Yu. Ya. Tarnopolsky. Optimization of calendar plans by directed-search methods. Kibernetika, 1970, No. 6.

3. L. V. Kochnev. Optimization of a priority system in scheduling problems. In: Cybernetics and the Higher Educational Institution, issue 3, Tomsk, 1970.

4. Ya. Z. Tsypkin. Adaptation and Learning in Automatic Systems. Moscow, “Nauka,” 1968.

5. A. I. Gudzenko, L. V. Perfiliev. Control of the process of preparing a new production facility. Izv. TPI (the present collection).