On the Optimization of Equipment Operation Scheduling
Abstract Generated abstract
This paper addresses operational production scheduling for sequencing part processing on machines under specified start and completion time constraints, with particular attention to minimizing equipment idle time. Building on a previously described heuristic schedule construction method, it proposes an iterative procedure that repeatedly adjusts the latest completion time in the current schedule, reconstructs the schedule, and retains variants that reduce total machine idle time. The method continues until feasible schedules can no longer be obtained within the time bounds, with smaller iteration steps offering closer approximations to an optimum at greater computational cost. An implementation on a Ural-11B computer for 100 parts reportedly reduced equipment idle time by nearly half relative to the earlier method and shortened the production cycle, while allowing priority to be given to scarce or costly equipment.
Full Text
On the Optimization of Equipment Operation Scheduling
V. M. Reider, Yu. N. Efimov
(Presented by the scientific seminar of the Department of Computer Engineering)
One of the most important tasks in systems of operational production control is the construction of schedules for the optimal sequence of processing parts on machines, with minimization of equipment idle time.
In [1] a heuristic algorithm is described for constructing a schedule for parts, in which it was assumed that the processing of parts must not go beyond the specified start and completion times. The solution of the scheduling problem was based on the use of a preference function—the time reserve
\[ \tau_{\mathrm{res}} = (t_{\mathrm{v}} - t_{\mathrm{z}}) - T_{\mathrm{m}} - t_{\mathrm{pr}}, \]
where
\(t_{\mathrm{v}}\) is the completion time of processing of the part;
\(t_{\mathrm{z}}\) is the start time of processing of the part;
\(T_{\mathrm{m}}\) is the time of processing the part in the shop;
\(t_{\mathrm{pr}}\) is the idle time of the part due to equipment being occupied.
Within the framework of the problem stated above, the question of minimizing equipment idle time is highly relevant. This paper describes a method for solving the problem of constructing a schedule for a quasi-optimal sequence of processing parts on machines, whose objective function is the minimization of equipment idle time.
The essence of the method is as follows.
- A schedule of the sequence of processing parts is constructed and stored using the method of [1]. For the obtained schedule, the total equipment idle time is computed,
\[ T_q^{\mathrm{pr}} = \sum_{\varphi=1}^{m} T_{k\varphi}^{\mathrm{pr}}, \]
where \(T_{k\varphi}^{\mathrm{pr}}\) is the idle time of the \(k\)-th machine;
\(m\) is the number of machines.
-
In the obtained schedule, the part whose processing completion time is maximal is selected.
-
For the selected part, the processing completion time is changed by the amount
\[ t_{\mathrm{v}} := t_{\mathrm{v}} - \Delta t, \]
where \(\Delta t\) is the iteration step.
-
The schedule for processing the parts is constructed again. A new value of the total equipment idle time \(T^{\mathrm{pr}}_{q+1}\) is estimated and compared with the idle time from the previously constructed schedule. If \(T^{\mathrm{pr}}_{q+1} < T^{\mathrm{pr}}_q\), then the previously constructed schedule is replaced by the new one, and the value \(T^{\mathrm{pr}}_{q+1}\) is recorded instead of \(T^{\mathrm{pr}}_q\).
-
In the newly constructed schedule, the part whose processing completion time is maximal is again selected, item 3 is carried out, and so on.
The iterative procedure described continues until reducing the processing time of the parts no longer makes it possible to construct a schedule within the specified bounds on the start and end times of processing. Obviously, as the iteration step is decreased, a schedule variant closest to the optimum can be found. However, the time required to search for the best variant increases significantly.
The algorithm was implemented on the Ural-11B computer for 100 parts, each of which could have from 1 to 50 operations. Equipment idle time, in comparison with the scheduling variant constructed according to the method of [1], was reduced almost by half. At the same time, the production cycle was significantly shortened.
The optimization method described makes it possible to construct a schedule for processing parts in such a way as to minimize the idle time of costly or scarce equipment, at the expense of a possible increase in the idle time of cheaper or more widely available equipment.
REFERENCES
- Yu. N. Efimov, V. M. Reider. On a heuristic algorithm for constructing a schedule for processing parts. This collection.