A METHOD AND HEURISTIC ALGORITHM FOR OPERATIONAL SCHEDULING OF PRODUCTION

P. L. STEPANOV, A. M. REVIN, V. Z. YAMPOLSKY

(Presented by the Scientific and Technical Seminar of the Research Institute of Automatic Electric Machines)

The introduction of electronic computers into the practice of production management increasingly demands the use of mathematical methods in planning, above all in one-off and small-batch production. Enterprises of one-off and small-batch production are characterized by frequent changes in the range of products planned for manufacture; by the absence of any similarity in the duration of technological operations, cycles, and technological routes.

Analyzing the existing practical methods of calendar planning at enterprises of one-off and small-batch production, it is not difficult to see that the main difficulties are posed by the formation of monthly production programs, the determination of the optimal variant of launching and releasing parts, the preparation of operational production assignments, and the calculation of uniform equipment loading for each calendar-planning period.

Below, one of the possible solutions to these basic tasks of calendar planning under the conditions of one-off and small-batch production is proposed.

Selection and Justification of Criteria

The increasing rates of scientific and technological progress in industry and the conditions of the new economic reform have sharply raised the requirements for the quality and speed of solving problems of production planning and management.

For making optimal decisions in the planning of a complex production process, rigorous mathematical methods were required for investigating management processes, with a solid scientific foundation provided by the relatively young scientific field of “operations research.”

The following elements are characteristic of methods for solving management problems in “operations research” [1]:

1. Construction of a mathematical model of the object of management.
2. Formation of the set of variables whose values are selected from the overall management strategy.
3. Selection of the objective function from the chosen variables.
4. Selection and application of a computational method for determining the value of the objective function for the chosen variant of the values of the variables.

Thus, the first thing with which research begins is, as it were, the construction of a model. However, this is not entirely correct. Let us consider the definition of a mathematical model for solving management problems,

most clearly formulated by M. K. Starr [2]. “A model is a representation of reality. It is constructed in such a way as to explain some, but not all, aspects of the totality of phenomena in this reality. The reason a model is used is that it is always simpler than the actual situation in the real world. It must be a good representation of those dimensions that are relevant to the purposes of the system.”

It follows from this that, before undertaking the construction of a model, it is necessary to choose a quantity that would serve as the optimality criterion for the system’s objective function.

In the present article an attempt is made to propose a correct method for selecting optimality criteria for constructing a mathematical model of production suitable for solving problems of operational scheduling. The system of operational scheduling of production at a socialist enterprise must, obviously, contribute as much as possible to the enterprise’s fulfillment of the indicators of the state plan. The most important of these indicators, characterizing the activity of the enterprise as a whole, are: profit, profitability level, and volume of sold output. It is reasonable to take these indicators as optimality criteria when organizing the activity of the enterprise as a whole. It does not appear possible to take them as optimality criteria when constructing the system of operational scheduling (OSP), owing to the absence of a direct connection between it and these indicators.

In this case it is necessary to select factors that are directly dependent on the OSP system and that influence, albeit indirectly, the principal indicators of the enterprise’s activity. Then, having determined the strength of the influence of these factors on the principal indicators, one can choose those among them whose influence is maximal. In such a case, obviously, the optimality criterion for constructing the OSP system (and, consequently, the mathematical model as well) must be taken to be the attainment of the maximum (or minimum, depending on the direction of influence) with respect to these factors.

The mathematical apparatus for determining the magnitude and direction of the influence of various factors may be the method of multiple correlation analysis [3, 4, 5]. However, the application of this method to linear dependencies is limited by the requirement that the distribution of the set of quantities under study be normal. Economic indicators, as a rule, have an asymmetric distribution [6]. Thus, processing the initial statistical information may require transition to another system of variables distributed normally. This transition can be carried out by one of the simple methods described in [3].

Description of the Method and Algorithm

The proposed method and algorithm should be used for planning the production of products whose production cycle is shorter than the planned period. However, at the end a number of conditions will be given that make it possible to remove this restriction.

First of all, it is necessary to choose the criteria of the operational scheduling method.

The activity of an enterprise is evaluated by a number of indicators which, in turn, are determined by a large number of factors. Such indicators are, for example: profit, profitability level, volumes of commodity and sold output, cost per 1 ruble of commodity output, etc.

By applying methods of statistical analysis, one can construct a system of regression equations showing the dependence of these indicators on various factors characterizing the activity of the enterprise and

compute the coefficients of partial correlation. Among the large number of factors one can single out a group directly connected with the planning system existing at the enterprise. By the magnitude of the partial-correlation coefficients found, some of them—namely those with the maximum correlation coefficient—may be regarded as optimality criteria in constructing the method and developing the algorithm for operational scheduling. Such criteria were: the rhythmicity of work, equipment utilization, and observance of directive deadlines for the output of products.

The proposed method is optimal precisely in the sense of obtaining the maximum values of these criteria.

One month is taken as the planning period. However, at the beginning it is convenient to consider two adjacent periods as well: the preceding and the following months.

Thus, we consider 3 months.

The plan is drawn up for the 2nd month. The nomenclature and quantity of products that the plant must manufacture in the 2nd and 3rd months are given.

Let \(n_{i2}\) be the quantity of the \(i\)-th product that must be manufactured in the 2nd month, and \(n_{i3}\), respectively, in the 3rd. It is obvious that, for uniform operation of the assembly shops of the plant in the 3rd month, in the 2nd month it is necessary to prepare such a number of the \(j\)-th part for the \(i\)-th product that there will be enough of it until the arrival of these parts manufactured in the 3rd month. That is, if the duration of the production cycle of the \(j\)-th part is equal to \(t_j\), then, assuming its consumption to be uniform, we obtain

\[ N_{ij}=(n_{i2}\cdot d_{ij})+\frac{(n_{i3}\cdot d_{ij})}{T}t_j =d_{ij}\left(n_{i2}+\frac{t_j}{T}n_{i3}\right), \]

where \(N_{ij2}\) is the quantity of the \(j\)-th part for the \(i\)-th product that must be manufactured in the 2nd month;

\(d_{ij}\) is the applicability of the \(j\)-th part in the \(i\)-th product;

\(T\) is the planned period, in this case a month.

However, it must be taken into account that, when the plan for the 1st month was being compiled, it included a similarly calculated number of \(j\)-parts ensuring uniform operation of the assembly shops in the 2nd month, that is,

\(\dfrac{t_{ij}}{T}n_{i2}\); consequently, this part must be subtracted from the program of the 2nd month, that is,

\[ N_{ij2}=d_{ij}\left(n_{i2}+\frac{t_j}{T}n_{i3}-\frac{t_j}{T}n_{i2}\right). \tag{1} \]

It is obvious that in the case \(n_{i3}=n_{i2}=n\), we obtain the necessity of the existence of a once-created reserve for each part, \(\dfrac{t_j\cdot n\cdot d_{ij}}{T}\), with their uniform output during any month \((d_{ij}n)\).

In what follows, the general case (1) will be considered.

With such a method, applied continuously, it is obvious that a part entering the plan from the term \((d_{ij}\cdot n_{i2})\) does not differ in any way, in terms of manufacturing priority, from a part from the term \(\left(d_{ij}n_{i2}\dfrac{t_j}{T}\right)\).

Below is given a method for compiling a weekly plan for the output and launching of parts, assemblies, and products broken down by shops or sections. (In what follows, a section will mean a subdivision of the plant performing a definite technological operation with the given part, assembly, or product.)

Let \(P_1, P_2, \ldots, P_N\) be the set of products whose manufacture must be carried out within the established directive period (quarter, month). A five-day week is adopted as the planning-and-accounting period; it is assumed that the entire program period is divided into \(j\) five-day weeks. It is required to form a calendar plan for the work of the enterprise that ensures

the output of the entire specified product nomenclature and providing for uniform loading of the available groups of equipment within each five-day period of the entire planning period.

It is assumed that, for all products \(P_1, P_2, \ldots, P_N\), whose manufacture is scheduled during the specified directive period, standard network schedules \(\Gamma_1, \Gamma_2, \ldots, \Gamma_N\) [7] have been constructed. For each component part \(d_{ij}\) of the given product \(P_i\) \((i=1,2,\ldots,N)\), using the constructed network schedules, a quantity \(K_{\text{н}}^{ij}\) is introduced, called the coefficient of intensity of work execution and defined by the following rule:

\[ K_{\text{н}}^{ij}=\frac{t(L_{ij})}{t(L_{\max})}, \qquad \begin{pmatrix} i=1,2,\ldots,N\\ j=1,2,\ldots \end{pmatrix}, \tag{2} \]

where

\(t(L_{ij})\) is the duration of the path \(L_{ij}\) connecting the event \(x_{ij}\), consisting in the manufacture of the component part \(d_{ij}\) of the given product \(P_i\), with the event \(x_k\)—the completion of manufacture of product \(P_i\);

\(t(L_{\max})\) is the duration of the maximum of the critical paths of the network schedules \(\Gamma_1, \Gamma_2, \ldots, \Gamma_N\).

As follows from (2), the value of the intensity coefficient for the various component parts and assemblies of the products \(P_1, P_2, \ldots, P_N\) lies within the limits

\[ 0<K_{\text{н}}^{ij}\leqslant 1. \]

The intensity coefficient is one of the most important parameters of the proposed method of calendar planning. The value of the intensity coefficient gives an idea of the degree of urgency of the work, makes it possible to establish the order in which work should be performed under multi-project conditions, that is, when the work being performed belongs to different networks; and makes it possible to estimate how freely the time reserves available to them may be used.

With the aid of the intensity coefficient introduced above, the entire set of parts and assemblies constituting the given products \(P_1, P_2, \ldots, P_N\) is divided into \(f\) arrays \(M_1, M_2, \ldots, M_f\) (\(f\) is the number of five-day periods in the planning period). Moreover, the manufacture of parts and assemblies falling into one or another array \(M_1, M_2, \ldots, M_f\) must be carried out respectively in the 1st, 2nd, ..., \(f\)-th five-day period of the directive period. The inclusion of part \(d_{ij}\) in one or another array \(M_s\) \((s=1,2,\ldots,f)\) is carried out on the basis of an estimate, by means of the intensity coefficient, of the degree of urgency of manufacturing this part and of the presence, for this five-day period \(s\), of the corresponding time reserve for it.

Thus, the purpose of the first stage of the calculations is to form production assignments for each calendar-planning period while satisfying two basic criteria of calendar planning:

1) fulfillment of the nomenclature plan of the directive period by 100% (in full);

2) observance of the directive deadlines for manufacturing individual products.

The next important stage in the development of the calendar plan is the organization and achievement of rhythmic work of all divisions of the enterprise, which is achieved by uniformly loading the equipment, with attainment, as far as possible, of the maximum value of the latter.

Let us introduce the notation:

\[ d_1^{(s)},\ d_2^{(s)},\ \ldots,\ d_M^{(s)} \tag{3} \]

— the set of parts whose manufacture must be carried out in the \(s\)-th five-day period of the directive period \((s=1,2,\ldots,f)\);

\(n_1^{(s)}, \ldots, n_M^{(s)}\) — the corresponding quantities of parts (3);

\(F_1^{(s)}, \ldots, F_r^{(s)}\) — the weekly time funds for the work of each group of equipment, in norm-hours;

\(j\) is the code of the equipment group on which the operation of the \(i\)-th part must be performed \((i = 1, 2, \ldots, M)\);

\(t_{ij}\) is the standard duration of the \(j\)-th operation of the \(i\)-th part.

The criterion according to which all parts from (3) will be unconditionally included in the plan for the \(s\)-th five-day period consists in requiring that the total labor input of the operations for processing these parts, for each type of work, correspond to the available time funds of the equipment operation \(F_j^{(s)}\).

In accordance with this, all parts from (3) will be included in the plan for the \(s\)-th five-day period if

\[ \sum_{ij} t_{ij}^{(s)} n_i^{(s)} \leq F_j^{(s)}, \quad \begin{pmatrix} j = 1, 2, \ldots, r \\ i = 1, 2, \ldots, M \end{pmatrix}. \tag{4} \]

Let us denote by \(\Delta F_j^{(s)}\) the part of the calendar time fund that remains after the parts from (3) have been included in the plan for the \(s\)-th five-day period:

\[ \Delta F_j^{(s)} = F_j^{(s)} - \sum_{ij} t_{ij}^{(s)} n_i^{(s)} . \]

The remaining fund \(\Delta F_j^{(s)}\) must be reduced to a minimum by adding parts from other arrays \(M_1, \ldots, M_{s-1}, M_{s+1}, \ldots, M_f\).

Let \(d_1^*, d_2^*, \ldots, d_m^*\) (5) be the set of parts produced at the expense of this remaining time. The set (5), according to (4), must satisfy the condition

\[ \sum_{\hat{i}j} n_{\hat{i}}^* t_{\hat{i}j}^* \leq \Delta F_j^{(s)} \]

\[ (j = 1, 2, \ldots, r;\ s = 1, 2, \ldots, f;\ \hat{i} = 1, 2, \ldots, m). \]

Let us consider the question of forming the set of parts (5). Under the conditions of real production, carrying out the launch—release of parts of each type-size in the form of batches is one of the most important factors affecting the economy and organization of an enterprise’s work.

The batch size is determined by economic and technical considerations. When distributing the production program among calendar-planning periods, one should first of all be guided by the product release dates stipulated by the state plan. Within the established directive period, the launch—release of a part of the \(i\)-th type-size may be carried out in the form of a series with batch size \(n_i\) and \(n_i^{\mathrm{opt}}\), where \(n_i\) is determined on the basis of the need for parts of the \(i\)-th type-size in assembly, and \(n_i^{\mathrm{opt}}\) is the batch size based on economic considerations.

From the foregoing follows the criterion according to which the array (5) is formed of parts and assemblies produced at the expense of the remaining fund \(\Delta F^{j(s)}\).

A part \(d_{\hat{i}}^*\) in the quantity \(n_{\hat{i}}^*\) units will be included in array (5) if, with the aid of these parts, it is possible to bring the batch \(\{n_i;\ d_i\}\) of parts \(d\) (where \(d_i\) is a part of the same type-size as \(d_{\hat{i}}^*\)), planned for manufacture in the \(s\)-th five-day period, up to the optimal size, that is, if

\[ n_i + n_{\hat{i}}^* = n_i^{\mathrm{opt}}, \]

where \(n_{\hat{i}}^*\) must be a multiple of the applicability of the parts in one of the products \(P_i\).

In a similar manner, the load is leveled across all calendar-planning periods.

As a result of the calculations performed by the proposed method, the output information is issued in the form of two lists for each five-day period: in the first, the parts whose manufacture begins in the given five-day period are presented; in the second, the parts whose manufacture is completely completed in the given five-day period.

The production assignment obtained for each five-day period and the initial technological information on the manufacture of parts make it possible to proceed with drawing up a calendar plan for the output—launch of parts within the five-day period.

REFERENCES

1. K. J. Arrow, S. Karlin, H. Scarf, Studies in the Mathematical Theory of Inventory and Production, Stanford University Press, 1958.

2. M. K. Starr, “Production Management Research,” Operation Research, 6, 1958.

3. Ya. P. Lukomskii, The Theory of Correlation and Its Application to the Analysis of Production, Statistika, Moscow, 1958.

4. F. M. Borodkin, Statistical Assessment of Relationships among Economic Indicators, Statistika, Moscow, 1968.

5. G. V. Osipov, Methods and Techniques of Statistical Processing of Primary Sociological Information, Nauka, Moscow, 1968.

6. Collection of articles, Economic-Statistical Studies of Industrial Production, Statistika, Moscow, 1969.

7. P. L. Stepanov, A. M. Revin, A. I. Gudzenko, V. Z. Yampol’skii, “Preparation of Information for Solving Problems of Operational-Calendar Planning on a Computer,” article in the present collection.