On an Algorithm for Calculating the Calendar Plan of Launch and Output

Yu. N. Efimov, V. I. Kizev, V. I. Nevraev, P. A. Sedelnikov

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

In [1] an algorithm is proposed for calculating the calendar plan of launch and output, using a network model and minimizing work in progress. Practical implementation of the developed planning system showed that the first attempt to implement this algorithm, described in the same work, was not entirely successful.

The representation of the output plan for each vertex of the graph*) in the form of the set

\[ P_j^{\mathrm{в}}(t)=\{q_\lambda^{\mathrm{в}}, t_\lambda^{\mathrm{в}}\}_{\lambda=\overline{1,\mu};\ j\in I} \]

is very cumbersome. This leads to large volumes of fields for storing plans, to irrational use of the external memory and RAM, which, in turn, entails considerable machine-time expenditures for analyzing the network model. The unequal number of elements in the plans of different vertices of the graph complicated the service program and required the introduction of an information table (IT) stored in external memory.

An experimentally established power-law dependence of computation time on the number of vertices of the model being analyzed was found. The accumulated experience of using this algorithm for calendar planning on the “Ural-11B” computer showed that, on machines of this class, network models not exceeding 1000 vertices can be calculated. The need to analyze graphs of larger dimension requires the development of another machine algorithm for calculating launch-output plans, free of the shortcomings indicated above. It seems to us that the solution of the posed problem should be sought along the path of a more compact recording of plans and the development of a more perfect system for their storage and search in the machine memory.

Proceeding from the foregoing, we propose another variant of the algorithm for calculating plans, differing from [1] both in the form in which the graph is specified and in the method of analysis.

The network model is represented in the form of a graph \(G=(I,\Gamma)\), so that the information about one vertex has the form

\[ \begin{aligned} &i,\ x_i,\ T_i,\ y_i,\ m_i,\ \rho_i;\\ &j_1,\ R_{i,1};\\ &j_2,\ R_{i,2};\\ &\ldots \end{aligned} \tag{1} \]

*) Here and below, the terminology and notation are taken from [1].

\[ j_{\rho},\ R_{i,\rho}, \]

where \(j_k \in \Gamma^i\), with \(i > j\), and \(j_k < j_{k+1}\);
\(\rho_i\) is the number of arcs leaving vertex \(i\) (the local degree of \(G\) at \(i\)).

Let us note that such information is easy to obtain from the summary specification for the product. If the information is taken from component specifications or from technological documentation (where-used lists), it is not difficult to transform it to the form (1) using the algorithm [2]. In this case the initial information must be ordered by layers, and within a layer in increasing order of the vertex numbers \(i\). The ordering is carried out by algorithm [3].

Output plans are formed in the form of a finite ordered set

\[ P_j^{\mathrm{o}}(t)=\{q_\lambda^{\mathrm{o}}\}_{\lambda=\overline{1,\nu}}, \]

where \(\nu\) is the number of elements of the plan. The value \(q_\lambda^{\mathrm{o}} \ge 0\) characterizes the quantity to be output, and its location (position) in the ordered set \(P_j^{\mathrm{o}}(t)\) is the output time. It is necessary to emphasize that, in contrast to [1], here it is possible that \(q_\lambda^{\mathrm{o}} = 0\), which makes it possible to apply the positional form of recording plans. With this form of recording, no more than \(Z^{\mathrm{o}}\) cells of the computer’s operative memory are required to represent one output plan.

\[ Z^{\mathrm{o}}=\frac{T^{\mathrm{p}}+t_{\mathrm{c}}}{h}\cdot \psi_q, \]

where \(T^{\mathrm{p}}\) is the planning period;
\(t_{\mathrm{c}}\) is the duration of the production cycle for manufacturing the output products;
\(h\) is the quantization step of the directive-plan function;
\(\psi_q\) is the ratio of the number of digits required to record \(q_\lambda^{\mathrm{o}}\) to the number of digits of one NF cell.

Similarly, launch plans are represented in the following positional form:

\[ P_j^{\mathrm{l}}(t)=\{n_\lambda\}_{\lambda=\overline{1,\nu}}, \tag{2} \]

where \(n_\lambda\) is the number of batches \(m_j\) launched at the time determined by the position \(n_\lambda\) in \(P_j^{\mathrm{l}}(t)\). In this case each launch plan requires \(Z^{\mathrm{l}}\) cells of operative memory.

\[ Z^{\mathrm{l}}=\frac{T^{\mathrm{p}}+t_{\mathrm{c}}}{h}\cdot \psi_n, \]

where \(\psi_n\) is the ratio of the number of digits required to record the value \(n_\lambda\) to the number of digits of one NF cell.

In practice, for most production operations, products are launched one batch \(m_j\) at a time. In this case, at each fixed moment of time in \(P_j^{\mathrm{l}}(t)\) only the fact of launch itself is recorded, for which one binary digit is used. Such a form of recording launch plans is sufficiently compact; moreover, it can be made of constant length.

The operation of the proposed algorithm is as follows: first, on the basis of directive plans for the output products, launch plans are formed. Then the ordered initial information is scanned, and for each \(i \in \Gamma_j^{-1}\) the output plan is formed by the formula

\[ P_i^{\mathrm{o}}(t)=\sum_{j\in \Gamma_i^1} P_j^{\mathrm{l}}(t)\cdot R_{ij}. \]

The obtained output plan is transformed into a launch plan for this same vertex according to the algorithm [1], but is represented in the machine in the form (2). The transformed output plan does not participate in subsequent calculations and is not stored in memory. Thus, as a result of the operation of the algorithm, only launch plans are stored for all \(j \in I\). For the operation of the algorithm it is necessary that, by the time \(P_i^2(t)\) is calculated, the plans \(P_j^3(t)\) for all \(j \in \Gamma_i\) have already been calculated. This requirement is satisfied by the ordered initial information.

The records of the launch plans are made of constant length, which has simplified their search in the AF and in the MLD. At the beginning of the counting process, the launch plans are written into the AF in the plan field until it is filled; after this the plans are written into the working field of the MLD. Subsequently, only newly obtained launch plans are copied into the working field of the MLD, since they will not be needed for forming the plans of all the remaining vertices of the analyzed layer. When proceeding to the analysis of the next layer of the graph \(G\), the plans from the working fields of the AF and the MLD are copied into the plan field of the MLD, while the plans obtained last remain in the AF. The number of these plans is determined by the size of the AF plan field. In a special cell of main memory, the upper \(i_{\mathrm{v}}\) and lower \(i_{\mathrm{n}}\) boundaries of the subset \(I_{\mathrm{nf}} \subset I\) of vertices of the graph \(G\), whose plans are located in the AF, are formed. Then the search for the plans needed for the calculation can be carried out as follows:

a) If \(j \in I_{\mathrm{nf}}\), then
\[ A_j^{\mathrm{n}} = A_0 + (j - i_{\mathrm{n}})\cdot Z^3, \]
where \(A_j^{\mathrm{n}}\) is the initial address of the record of the plan \(P_j^3(t)\);
\(A_0\) is the initial address of the plan field.

b) If \(j \notin I_{\mathrm{nf}}\), then
\[ N_z = N_z^0 + E'\left(\frac{j}{\Theta}\right), \]
where \(N_z\) is the number of the MLD zone in which the required plan is recorded;
\(N_z^0\) is the initial number of the MLD plan-field zone;
\(\Theta\) is the number of launch plans stored in one zone;

\[ E'\left(\frac{j}{\Theta}\right) \]
is the integer part of the ratio. The remainder of this ratio determines the location of the plan within the zone.

Thus, as a result of the operation of the algorithm, we obtain in the MLD the launch plans for the entire set of vertices of the analyzed network model. This information serves as the basis for forming on the computer the following output documents:

the calendar launch–output plan, broken down by subdivisions; the summary output plan in labor and cost terms for the product as a whole and broken down by subdivisions; the planned demand for basic and auxiliary materials, components, tools, energy expenditures, etc., in physical and cost terms; and various limit cards by subdivision.

The proposed algorithm was implemented on the “Ural-11B” computer. The time required to analyze a network model containing 4000 vertices with complexity coefficient 3 was approximately 30 min.

REFERENCES

1. Yu. N. Efimov, V. I. Kizev, V. I. Nevraev, P. A. Sedelnikov. Algorithm for solving the problem of operational calendar planning of discrete production. In the present collection.

2. Yu. N. Efimov, P. A. Sedelnikov. On one algorithm for transforming the form of representation of a graph. Izv. TPI, vol. 243. TSU Press, 1972.

3. Yu. N. Efimov, P. A. Sedelnikov. Algorithm for ordered recoding of graph vertices. In the present collection.