PREPARATION OF INFORMATION FOR SOLVING OPERATIONAL SCHEDULING PROBLEMS ON A COMPUTER

A. I. Gudzenko, P. L. Stepanov, A. M. Revin, V. Z. Yampolsky

(Presented by the Scientific-Technical Seminar of the Research Institute of AEN)

Among the various parts of the complex process of managing the activity of an industrial enterprise, a special place belongs to operational scheduling of production, which must provide for the coordinated work of all subdivisions of the enterprise for the timely and complete output of finished products in accordance with the enterprise’s directive plan.

The difficulty of drawing up operational schedules is connected with the fact that one has to deal with a large number of objects of labor, a large number of technological operations, and technological units of equipment. The subdivision of an enterprise engaged in operational scheduling has to work with a large amount of initial information located in various services of the enterprise and concentrated in a large number of documents.

This process is made still more complicated at enterprises that have a considerable and frequently changing nomenclature of products manufactured as individual items or in small batches.

A qualitatively new step in operational scheduling has been the use of electronic computers for these purposes. However, for this it is necessary to prepare the diverse initial information in a definite form, which in itself is a complex task. This article proposes a method for preparing initial information in the form of network graphs of product manufacture for solving operational scheduling problems on a computer. The proposed method has been introduced at the Mathematical Machines Plant (Tomsk) for calculating schedules on computers of the M-20 type (M-220, BESM-4).

The initial information for drawing up schedules for the work of enterprise subdivisions is divided into several parts: directive information (the nomenclature, quantity, and due dates for the output of finished products in the planned period), normative information (the quantity and nomenclature of materials used, labor-time standards, etc.), design information (the composition of the product), and technological information (the technological sequence of operations, routing, etc.).

All this information is contained in various documents and in a form unsuitable for computer calculations, for example, in a process chart.

To combine the greater part of the normative-reference information, a so-called “normative card” has been developed (Figs. 1, 2). It is based on the normative card developed by the Computing Center of the Siberian Branch of the USSR Academy of Sciences [1].

Ex. cycle, ser. no.:

Standard Card No. ______

reason for change

duration

Fig. 1. Front side of the standard card.

The form of the standard card meets the requirements for preparing input information for an M-20 type computer, i.e., it is taken into account that the representation of a number is 45-digit and therefore the maximum line length of each field is twelve digits.

The card consists of 6 fields.

The first field. Into it is entered the drawing number of the item for which the card is being opened. Since drawing numbers consist of 12 decimal digits, this field occupies one cell.

The second field. In the case of export execution, a 1 is entered in the column “Ex”; in all other cases a 0 is entered; in the column “Cycle” the production cycle for manufacturing the part (assembly) is recorded in days. In the column

Fig. 2. Reverse side of the normative card.

In “Lead time” the time (in days) by which the release of a part (assembly) is to be advanced is recorded.

In the third item, labor standards are recorded. In the column “Operation No.” the ordinal number of the technological operation is entered in the sequence specified by the technological process.

In the column “Characteristic of the standard” the characteristic of the issued standards (experimental-statistical, time-study, or calculated-technical) must be recorded by the designations (++ , +−, −+).

In the column “Time” the time is written in hours in the usual form with decimal places (in the mantissa column). The column “order” is intended for perforation. Next, the numbers of the grid, grade, and shop are recorded. In the column “Code

the code of the technological operation is entered in accordance with the adopted coding of technological operations.

In the fourth field, information is entered on the applicability of the part (assembly unit) for which the given standard card has been opened in other assemblies (products).

The fifth field. In the column “Operation No.”, the serial number of the operation to which the given material or component product has gone is recorded. In the column “Item number,” the code number adopted for the given material or component product is entered.

In the sixth field, the parts and assemblies included in the assembly of the given assembly unit (product) are entered; the number of the operation to which the parts (assemblies) go, the number of pieces, and the drawing number of the included parts (assemblies) are indicated in accordance with the entry of the first field for each of them.

The information contained in the standard cards is the initial information for constructing, with the aid of a computer, network schedules for product manufacture, which are already the direct initial information for operational-calendar production planning.

The network model, which is constructed with the aid of the developed algorithm, is a network oriented toward events, where each event consists in the manufacture of the next component product, assembly unit, or part. For the desired network model, whose analogue is the directed graph $G(X; U)$, let us divide the set of all events $X$ into the following subsets:

$X_1$ is the set of those events $x_j^1$ for which there is no preceding event in the network;

$X_2$ is the set of those events $x_i^2$ for which the aggregate of all adjacent events preceding the events $x_i^2$ belongs to the set $X_1$;

$X_3$ is the set of those events $x_i^3$ for which the aggregate of adjacent events preceding the events $x_i^3$ belongs to the union of the sets $X_1$, $X_2$;

$X_k$ is the set of those events $x_i^k$ for which the aggregate of adjacent events preceding the events $x_i^k$ belongs to the union of the sets $X_1$, $X_2$, ..., $X_{k-1}$. It should be noted that we consider the case where the set $X_k$ consists of only one event $x^k$, consisting in the completion of the manufacture of a certain product.

The process of constructing the desired network model consists in forming the subsets described above, $X_1$, $X_2$, ..., $X_k$, and establishing the topological connection between the events $x_j^i$ ($j = 1, 2, \ldots, m_i$, where $m_i$ is the number of events of the set $X_i$), of each of the introduced subsets, with the construction proceeding in the direction from $X_k$ to $X_1$.

In the course of the algorithm’s operation, a certain auxiliary array is constructed—the array of codes. The array of codes is constructed as follows.

During the formation of the next link of the network schedule, the code of the next event $x_j^i$ (at the first stage, $x^k$) is selected from the array of codes; all events immediately preceding it, $x_{j_1}^{i_1}$, $x_{j_2}^{i_2}$, ..., $x_{j_n}^{i_n}$ (the indices $i_1, i_2, \ldots, i$ take values from the set $1, 2, \ldots, i-1$; $j_s = 1, \ldots, m_{i_s}$), are determined; the codes of these events are entered into the array of codes and are written immediately after the code of the next event.

The process of constructing the network model proceeds according to the following scheme:

1) from the array of codes, the code of the next event $x_j^i$, belonging to the subset $X_i$ ($i = 1, 2, \ldots, k$), is selected;

2) the codes of all events immediately preceding the event $x_j^i$, namely $x_{j_1}^{i_1}$, $x_{j_2}^{i_2}$, ..., $x_{j_n}^{i_n}$, are determined;

3) all time characteristics of the events identified at the preceding stage are determined;

4) according to the selected data, the next link of the network schedule is printed.

Algorithm

In what follows, we shall replace the term “event \(x_j^i\)” by “standard card corresponding to event \(x_j^i\).”

\[ AL\ (\text{construction of the network model}) = G_1G_2G_3\Pi_4G_5G_6G_7G_8\Pi_9G_{10}\Pi_{11}G_{12}. \]

Fig. 3. Network schedule for manufacturing a product.

\(G_1\) — selection, from the entire array of standard cards, of the main standard card and entry of its code into the array of codes;

\(G_2\) — selection, from the array of codes, of the code of the next standard card and search, by this code, for the corresponding standard card;

\(G_3\) — from item No. 2 of the standard card selected at the preceding stage, the duration of the production cycle for manufacturing the corresponding product is selected;

\(\Pi_4\) — check: whether item No. 6 of the selected standard card is empty (It should be noted that for a part, item No. 6 is not filled in).

\(G_5\) — selection from item No. 6 of the selected standard card, selected

by operator \(G_2\), of the code of the immediately preceding standard card, and the number of parts of this code.

\(G_6\)—for the code selected by operator \(G_5\), the corresponding standard card is sought in the array of standard cards; from it the duration of the production cycle is determined.

\(G_7\)—recording, in the array of codes, of the code selected by operator \(G_5\);

\(G_8\)—printing of the code selected by operator \(G_5\), the number of parts of this code, and the duration of the production cycle;

\(P_9\)—check: whether all codes from requisite No. 6 of the standard card selected by operator \(Z_2\) have been examined;

\(G_{10}\)—printing of the code of the standard card selected by operator \(G_2\), and of the duration of the production cycle;

\(P_{11}\)—check: whether all codes from the array of codes have been examined;

\(G_{12}\)—end of computations.

The output information has the following form.

Product code 00160

. . . . . . . . . . . . . . . 4 5 4 5 0 0 0 0 0
. . . . . . . . . . . . . . . 8 6 6 5 2 0 6 0 0
. . . . . . . . . . . . . . . 0 0 0 0 0 0 0 1 3
. . . . . . . . . . . . . . . 4 5 4 0 0 0 0 0 0
No. of the head job 0 0 1 1
. . . . . . . . . . . . . . . 7 7 5 5 0 3 9 0 0
. . . . . . . . . . . . . . . 0 0 0 0 0 0 0 1 4
. . . . . . . . . . . . . . . 2 4 0 0 0 0 0 0 0
numbers of initial jobs 0 0 0 3
0 0 0 7
0 0 0 8
0 0 1 0
0 0 1 2
0 0 1 3
0 0 1 4

The form of the network schedule for manufacturing product 00160, constructed according to this list, is shown in Fig. 3.

REFERENCES

1. B. V. Doktorov, I. M. Bobko, I. M. Vladovskii, V. V. Kolmogorov, N. P. Peregudova, V. G. Sharapov. Automated control system for the Barnaul Radio Plant. Publishing House “Nauka,” Siberian Branch. Novosibirsk, 1968.