On an Algorithm for Optimizing the Operational Production Schedule
Abstract Generated abstract
This paper addresses the correction of computer-generated operational production schedules when calculated launch or output dates fall before the beginning of the planning period. The authors formulate the adjustment as a problem of minimally shortening production-cycle durations across enterprise subdivisions, noting that a direct linear programming solution is impractical for large network models. They propose a heuristic algorithm based on identifying critical paths in the production network, reducing lead times until early orders are eliminated, and then distributing reductions along technological routes. Tests on a Ural-11B computer for a 1000-vertex network reportedly produced practically satisfactory schedules within 2 to 3 minutes.
Full Text
On an Algorithm for Optimizing the Operational Production Schedule
Yu. N. Efimov, V. M. Reider
(Presented by the scientific-technical seminar of the Research Institute of Automated Control Systems at TPI)
If an algorithm is known for constructing an operational production schedule on the basis of a network model \(G = (J,\Gamma)\), a directive plan for the output of commodity products \(f_i(t)\), and data on work in process \((\Delta_i,\sigma_i)^*\), then, using recurrence relations, conditional launch plans \(P_i(t)\) are found, which serve as the basis for forming launch plans \(P_i^{зl}(t)\) and output plans \(P_i^{вl}(t)\) for a particular shop \(y_i^l\) over the entire set of products manufactured by that shop.
Since \(P_i(t)\), and consequently also \(P_i^{зl}(t)\), \(P_i^{вl}(t)\), are functions of several variables \((\Delta_i, m_i, \sigma_i, f_i(t), T_i^k)\), situations are possible in the calculation in which, for \(t < T_0\), where \(T_0\) is the beginning of the planning period, \(P_i(t) > 0\) for some \(i \in J\), and, correspondingly, for some shops,
\[ P_i^{зl}(t) > 0, \qquad P_i^{вl}(t) > 0. \]
As a result, some subdivisions of the enterprise receive information that, in order to fulfill the directive plan, it was necessary at time \(t < T_0\) (i.e., in the past) to launch into production or release certain types of products \(i\). Undoubtedly, this is valuable information, indicating to subdivision managers the most strained areas of work. On its basis, the subdivision takes all measures for the fastest possible fulfillment of “early” orders. However, the appearance of “early” orders and their fulfillment in the present, rather than in the past, leads to the fact that the plan in the subdivision is carried out not in strict accordance with the deadlines calculated on the computer. Thus, because of “early” orders, the launch–output plan obtained from the computer cannot be a strictly working document and requires correction. In the correction it is necessary to reduce certain quantities \(T_i^k\) so that, for \(t < T_0\), the relations are always satisfied:
\[ P_i(t) = 0, \qquad P_i^{зl}(t) = 0, \qquad P_i^{вl}(t) = 0. \]
Moreover, this correction must be optimal in the sense that the total time by which the durations of production cycles in all subdivisions of the enterprise are shortened is minimal. Such correction of the plan guarantees a minimal increase in the tension of the labor process as a whole at the enterprise, provided that it is carried out when forming plans for each type of commodity product.
It is not difficult to show that the problem of optimally adjusting the plan can be reduced to a linear programming problem with the objective function
\[ F=\sum_{i\in I}\sum_{k=1}^{n_i}\Pi_i^k\cdot \delta T_i^k, \]
where
\[
\delta T_i^k
\]
is the amount of time by which the duration of the production cycle for manufacturing product \(i\) in subdivision \(y_i^k\) is reduced;
\[
\Pi_i^k
\]
is the preference coefficient (priority) for reducing \(T_i^k\);
\[
n_i
\]
is the number of subdivisions in the technological route for manufacturing product \(i\).
However, the large number of constraints and the considerable size of \(|J|\) make it impossible to implement the solution of the optimal-adjustment problem in terms of linear programming. Therefore it seems expedient to develop a heuristic algorithm that simplifies the computational procedure of adjustment and leads to a practically satisfactory solution close to the optimum. Below a more precise formulation of the adjustment problem is given, and a heuristic algorithm for solving it is described.
Let us introduce into the network model [1] a new parameter \(T_i^{k*}\), meaning the minimum possible duration of the production cycle for manufacturing product \(i\) in subdivision \(y_i^k\). Sometimes, in order to reduce the volume of initial data, it is expedient to use the parameter
\[ \delta T_i^{k*}=T_i^k-T_i^{k*}, \]
which has the meaning of the maximum possible amount of reduction of \(T_i^k\).
It is not difficult to show that for an individual arc \((i,j)\), according to the algorithm for forming conditional launch plans [1], the lead time for launching the first batch of product \(i\) in \(P_i(t)\) relative to the first batch of product \(j\) in \(P_j(t)\) is
\[ T_i^c=\sum_{k=1}^{n_i}T_i^k-E\left(\frac{\Delta_i}{m_i}\right)+\tau_i, \]
where \(E\left(\dfrac{\Delta_i}{m_i}\right)\) is the integer part of the ratio;
\(\tau\) is the time by which \(T_i^c\) is increased because \(m_i<m_j\) (under the condition that no more than one batch of product can be launched into production per unit time).
If all arcs leaving \(i\) are taken into account, then \(\tau_i\) characterizes the increase in \(T_i^c\) due to the fulfillment, for certain moments of time \(t_0\), of the following inequality:
\[ m_i<\sum_{j\in\Gamma_i}P_j(t_0)\cdot R_{ij}. \]
Exact values of \(\tau_i\) can be formed only simultaneously with the calculation of conditional launch plans.
Let us note that \(T_i^c\) may take negative values, which should be interpreted as a delay in the launch of the first batch in the plan \(P_i(t)\) relative to the launch of the first batch in \(P_j(t)\) because of the considerable magnitude of \(\Delta_i\).
Introduce the following notation:
\(T_0\) — the beginning of the planned period (the moment at which the calculations are performed);
\(T_1\) — the end of the planned period;
\(T_2\) — the minimum time at which the directive-plan function
\[ f_j(T_2)>0. \]
Then the length of the planning period is determined as:
\[ T^{n}=T_{1}-T_{0}. \]
We shall call the quantity
\[ t_{g}=T_{2}-T_{0} \]
the directive deadline. For each \(i \in J\), compute the value of the lead in launching the first batch in \(P_i(t)\) relative to \(T_2\). To do this, we use the following recurrence relation:
\[ T_i^0=\max_{j\in\Gamma_i}\{T_j^0+T_i^c\}, \]
which makes it possible to find the quantities of interest to us in one pass ordered by the layers of the topology of the network model. Obviously, “early” orders will appear only for those \(i\in J\) for which
\[ T_i^0>t_g \tag{*} \]
If, in the process of computing \(T_i^0\), one records the numbers \(j\in\Gamma_i\) having \(\max T_j^0\), then it is not difficult to construct a path from sequences \(i\in L_{\mathrm{cr}}\) forming the value \(T_i^0\) for which inequality \([*]\) is satisfied. We shall call this path critical.
The operation of the proposed algorithm reduces to the following:
- Perform
\[ T_i:=\sum_{k=1}^{n_i} T_i^k . \]
-
Compute \(T_i^c\), for each \(i\in J\).
-
For each vertex, compute \(T_i^0\).
-
Determine
\[ T_{\max}^0=\max\{T_i^0\}_{i=1,|I|} \]
and record \(\gamma\in J\) for which \(T_\gamma=T_{\max}^0\).
-
Check \(T_{\max}^0>t_g\). Yes: go to 6. No: go to 9.
-
Construct the critical path \(L_{\mathrm{cr}}(\gamma,\ldots,i,\ldots,\beta)\), where \(\beta\in J\) and \(\Gamma_\beta=\varnothing\).
-
For \(i\in L_{\mathrm{cr}}\), compute
\[ \delta T_i= \frac{(T_{\max}^0-t_g)\cdot \sum_{k=1}^{n_i} T_i^{k*}} {\sum_{i\in L_{\mathrm{cr}}}\sum_{k=1}^{n_i} T_i^{k*}} . \]
- For \(i\in L_{\mathrm{cr}}\), perform
\[ T_i^c:=T_i^c-\delta T_i \]
\[ T_i:=T_i-\delta T_i \]
go to 3.
- Compute
\[ \delta t_i=\sum_{k=1}^{n_i} T_i^k-T_i . \]
- Distribute \(\delta t_i\ne0\) along the technological route \(y_i^k\):
\[ \delta T_i^k=\frac{\delta t_i\cdot T_i^{k*}}{\sum_{i=1}^{n_i} T_i^{k*}} . \]
- Perform
\[ T_i^k:=T_i^k-\delta T_i^k . \]
- The adjustment algorithm is complete. Proceed to the computation of the operational calendar plan.
The algorithm described was tested on the Ural-11B computer and yielded practically satisfactory results. The optimization time for an operational calendar plan for a network model containing 1000 vertices is 2–3 minutes.