ON A HEURISTIC ALGORITHM FOR SCHEDULING THE PROCESSING OF PARTS

Yu. N. EFIMOV, V. M. REIDER

(Presented by the scientific seminar of the Department of Computational Mathematics)

Technical progress up to the present time has been observed mainly in the area of broad automation of individual sections of production and the improvement of technological processes.

At the same time, the development of the science of production management has lagged sharply behind the needs of production. This disproportion in the development of the national economy, which has become especially apparent recently, between technical progress in the sphere of production and the level of scientific organization of labor in production, is a serious brake on the further development of the socialist economy. Large reserves in the development of production exist in the sphere of operational calendar planning. Small-batch and single-piece production is the most complex from the point of view of the organization of operational planning and management. An intuitive approach to solving this problem is, of course, not the best one. With 50–60 orders differing in their structure, each of which includes the manufacture of about 600 different part names, and if each part undergoes on average 6–8 machining operations, then every month a volume of work amounting to 300 thousand part-operations is introduced into production [1]. Another feature of operational-calendar planning, characteristic of small-batch and single-piece production with a relatively long manufacturing cycle, is that, when determining equipment loading and constructing plans, it is necessary to distribute the volumes of work among each production subdivision in a definite calendar sequence. Therefore, one of the basic requirements for operational planning and production management is the distribution of volumes of work in a definite calendar sequence, taking into account the optimal and uniform loading of equipment throughout the entire period of order manufacture.

An important feature of small-batch and single-piece production is that thousands of parts with different technological routes are constantly in manufacture. Their timely arrival for assembly must be ensured with minimal economic losses.

At present there are no rigorous mathematical solutions for the problems of forming plans. Attempts to use linear programming, as a rule, do not give appreciable results because of the inexpediency—

numerical solutions, the large size of the matrix, and the length of the calculation [1]. Therefore, various heuristic algorithms are proposed for solving such problems. It is clear that they do not give strictly optimal solutions; nevertheless, the results of the solutions are sufficiently close to the optimal ones.

Below we present a heuristic algorithm for constructing an optimal work schedule for a section or shop having \(m\) machines, on which \(n\) types of parts are processed. A number of publications [2, 3] present various heuristic algorithms for constructing optimal work schedules in which the objective function is taken to be the minimization of equipment idle time. Since the shop (section) for which the work schedule is being compiled is an inseparable link in the production system, the construction of the calendar schedule must be based on an objective function that minimizes deviations from the specified delivery times of parts to the next section or shop. Minimization of equipment idle time, although important, is less essential than manufacturing products by the specified due date.

The initial elements for solving the problem are the specified times: the time at which parts (batches of parts) are launched into the given shop, \(t_z\); the time at which parts are released, \(t_v\); the number of parts entering processing with individual route sheets, \(n\); and the equipment pool, \(m\) machines of the given production unit. The problem is solved for the case when each type of equipment includes only one machine. Let the parts entering processing be denoted by \(j\). In the route sheets of the parts, the operations \(i\) for processing the parts are given, as are the processing time of the \(j\)-th part in the \(i\)-th operation, \(\tau^{\mathrm{op}}_{ij}\), and the setup time for it for each \(i\)-th operation, \(t^{\mathrm{n}}_{ij}\). Let \(p\) denote the number of operations of the \(j\)-th part.

The developed heuristic algorithm is based on the following main points.

1. On the basis of the specified launch and release times of the part (batch of parts) to be processed in the given shop, the preference function is determined

\[ \tau_{\mathrm{res}} = (t_v - t_z) - T_m - t_{\mathrm{pr}}, \tag{1} \]

where \(t_{\mathrm{pr}}\) is the time the part waits before the next operation; \(T_m\), the processing time of the part in the shop, is determined by

\[ T_m = \sum_{i=1}^{p} \left(\tau^{\mathrm{op}}_{ij} + t^{\mathrm{n}}_{ji}\right). \tag{2} \]

At the initial moment of time \(t_{\mathrm{pr}}\) is equal to zero. Obviously, this function determines the degree of urgency of manufacturing the \(j\)-th part. As the part passes through the given shop, \(\tau_{\mathrm{res}}\) continuously decreases because of the parts lying between operations owing to the occupation of the equipment.

1. From all route sheets of the parts, their initial operations are selected and assigned to the corresponding equipment. If there are several contenders among the parts for a given type of equipment, the priority of processing is established according to the preference rule—the minimum value of \(\tau_{\mathrm{res}}\) of the part. Thus, all available parts are assigned to the existing equipment pool. The remaining parts are entered into the list of contenders for the corresponding type of equipment.

2. Among all the parts launched for processing, the part having the minimum processing time on the given machine is determined; this time is defined as

\[ \tau_{j \min} = \min_{j \in n} \left(\tau^{\mathrm{op}}_{ji} + t^{\mathrm{n}}_{ji}\right). \]

Over the time interval from the start of launching parts for processing, the value of \(\tau_{\mathrm{res}}\) is changed for the candidates and the operation time for the parts being processed:

for the candidates \(\tau_{\mathrm{res}} := \tau_{\mathrm{res}} - \tau_{j\min}\),

for the parts being processed \(\tau_{ji}^{\mathrm{op}} = \tau_{ji}^{\mathrm{op}} - \tau_{j\min}\).

1. The candidates for the freed equipment are evaluated, and the part with the minimum value of the preference function is assigned to this type of equipment. It is deleted from the list of candidates.

2. For a part that has undergone processing in the \(i\)-th operation, the \((i+1)\)-st operation is analyzed. The type of equipment for the \((i+1)\)-st operation is found; if the equipment is free, the given part is assigned to the type of equipment found. If the equipment is occupied, a comparison is made according to the preferential criterion \(\tau_{\mathrm{res}}\), taking into account the time of completion of processing of the part on the occupied type of equipment. Obviously, it is not always advisable to remove a part from equipment if it is close to the end of processing, even when its \(\tau_{\mathrm{res}}\) is greater than that of the candidate. The evaluation is performed by comparing the quantities

\[ k t_{ji}^{\mathrm{n}} < \tau_{ji}^{\mathrm{op}}, \]

where \(k\) is a coefficient. The part is removed in the case where the remaining processing time is greater than \(k t_{ji}^{\mathrm{n}}\). It is clear that, as the coefficient \(k\) increases, the probability of removing an unprocessed part from the equipment decreases. As \(k\) tends to infinity, this probability tends to zero. At the next stage of the algorithm, all parts launched into production are again reviewed, the part with the minimum processing time is found, and so on until all parts have been assigned for all operations.

If, in the obtained schedule for processing the parts, some parts do not fit into the specified time \(t = t_{\mathrm{v}} - t_{\mathrm{z}}\), then by decreasing the coefficient \(k\) it is possible, by changing the schedule that has been drawn up, to place the processing of all parts within the specified time. In this case the total time of equipment utilization correspondingly increases, since each replacement of an unprocessed part on the equipment increases the total processing time of all parts by the amount of the setup time \(t_{ji}^{\mathrm{n}}\) of the \(j\)-th part for the \(i\)-th operation. If the number of replacements of unprocessed parts is denoted by \(j\), then the value of the total time of equipment utilization will take the form

\[ T = \sum_{j=1}^{n} \sum_{i=1}^{p} \left(\tau_{ji}^{\mathrm{op}} + t_{ji}^{\mathrm{n}}\right) + \sum_{k=1}^{f} t_k^{\mathrm{n}} . \]

As the preference function in establishing the launch order of the part in the problem being solved, the time reserve possessed by each part was taken. In principle, it is possible to choose any other criterion, according to which the launch order of parts may be established.

REFERENCES

1. S. A. Dumler, R. S. Sedegov, L. P. Karp. A system of operational control using SPM and computers at enterprises of unit and small-batch production. Automated Control Systems, ed. S. A. Dumler, Minsk, 1965.

2. V. N. Reznichenko. Solution of one problem of scheduling theory by a heuristic method. Proceedings of the seminar “Algorithmization of Production Processes.” Academy of Sciences of the Ukrainian SSR, issue I, Kiev, 1968.

3. V. V. Shkurba. Computational schemes for solving scheduling-theory problems. Kibernetika, No. 3, Moscow, 1965.