On Scheduling the Processing of Parts in a Stamping Section
Abstract Generated abstract
This paper addresses operational scheduling for a stamping section within an automated enterprise management system, where shop-level plans must be refined to part-operation schedules. It formulates the problem for groups of interchangeable presses processing batches according to known technological routes, setup times, and launch dates, with the objective of reducing equipment idle time while maintaining the required flow of parts to subsequent production divisions. The authors propose a discrete dynamic modeling algorithm that constructs the schedule step by step, using a preference function based on remaining processing-time reserve to assign priorities, handle idle machines, continue batches, and mark urgent jobs. The paper also discusses practical tradeoffs in choosing critical priority thresholds and planning-period length, noting their effects on equipment utilization, deadline reliability, and schedule robustness.
Full Text
ON SCHEDULING THE PROCESSING OF PARTS IN A STAMPING SECTION
V. M. Reider, Yu. N. Efimov
(Presented by the scientific seminar of the computing laboratory of the Research Institute of AEM)
In [1] an automated enterprise management system (AEMS) with a discrete character of production is described. The economic-mathematical model developed in this system distinguishes the state of production only down to the level of the inter-shop route of each element of the design of the enterprise’s commercial products. The operational-calendar plans generated by the system guarantee the synchronous operation of all divisions of the enterprise in the interests of fulfilling the directive plan for the output of commercial products within established deadlines, with the simultaneous provision of proportional backlogs and minimization of work in process. However, further operational control over the implementation of operational “machine” plans makes it necessary to have a more detailed schedule of the work of a division at the level of part-operations. The present paper is devoted to one possible variant of solving this problem for the stamping section of a machine shop.
Problem statement. A production section (stamping) is considered, on whose equipment \(Q=\{q_1, q_2, q_3, \ldots, q_f\}\) the set of parts \(I=\{i_1, i_2, i_3, \ldots, i_n\}\) is processed. Each group of equipment \(q=\{s_1, s_2, s_3, \ldots, s_r\}\) contains \(r\) similar machines (presses) with identical productivity. For each \(i\in I\), the technological route within the section is known, consisting of the list of operations \(i\), the processing time of the \(i\)-th part in the \(j\)-th operation \(\tau_{ij}\), and the setup time of the machine for the given part-operation \(t_{ij}^{\text{n}}\). Let the parts \(i\in Iq\), assigned by their technological route to some equipment group \(q\), be capable of being processed with the same economic efficiency on any of the machines belonging to the given group. At any moment of time, on any \(s\in Q\), only one \(i\in Iq\) may be processed. The processing of parts in the section may be carried out from one batch up to the quarterly program. This specificity is explained by the fact that the stamping section is among the production divisions that are first in the technological route of the parts being processed.
A launch plan \(P_i^{\text{з}}(t)\) is specified for sending parts into processing, indicating the calendar dates (days) for launching \(i\in I\) in a quantity equal to one batch \(m_i\).
It is required to construct such a schedule for processing parts that would minimize production costs associated with equipment idle time, under the condition of ensuring the specified rate of arrival of parts into the subsequent production divisions along the technological route.
subdivision. Thus, as the objective function one takes the quantity
\[ F=\min \sum_{q=1}^{f}\sum_{s=1}^{r} T_s^q, \]
where \(T_s^q\) is the idle time of the \(s\)-th machine of the \(q\)-th equipment group.
It should be noted that in the problem under consideration the production costs associated with the holding of interoperation work-in-process inventory are not minimized, since for this section they are insignificant in comparison with the costs arising in connection with failure to meet product-output deadlines, equipment idle time, and its readjustment.
Assumptions
-
Parts that, according to their technological route, return from other sections are not considered.
-
For all \(q \in Q\), \(q_f \cap q_p = \varnothing\) for \(f \ne p\).
-
Interchangeability of machines of different groups is prohibited, i.e.,
\[ I^{q_f}\cap I^{q_p}=\varnothing . \]
- The processing of parts is carried out in quantities that are multiples of \(m_i\).
Algorithm. The proposed algorithm for solving the scheduling problem is constructed by discrete dynamic modeling of the operation of the section, using a preference function that gives priority, when establishing the sequence, to candidates having a smaller reserve of processing time \([2, 3]\). In compiling the schedule, a procedure of step-by-step construction of the optimal variant is used, consisting of seven stages.
1st stage. For each part, according to the specified calendar launch plan, the number of batches \(k_i^{\max}\) to be processed during the planned period is calculated, as well as the total operation time required for processing each \(m_i\) over the entire technological route,
\[ T_i^{m}=\sum_{j=1}^{k}\left(\tau_{ij}^{m}+t_{ij}^{n}\right), \]
where \(k\) is the number of operations of the technological route; \(\tau_{ij}^{m}=\tau_{ij}\cdot m_i\) is the processing time of one batch of parts. The duration of the production cycle for processing a batch of each part in the section is determined as \(T_i=\beta_i T_i^{y}\), where \(T_i^{y}\) is the duration of the production cycle for processing \(i\in I\) in the shop; \(\beta_i\) is the share of the duration of the production cycle for processing the part in the section relative to the shop-wide cycle, determined by expert estimates.
Introduce the following variables: \(t\) is the current time, \(0<t<T\), where \(T\) is the duration of the planned period; \(n_t^i\) is the number of batches requiring launch within the duration of the production cycle; \(v\) is the current number of the working day; \(k_{ij}\) is the number of batches of the \(i\)-th part subject to processing at the \(j\)-th operation.
Set: \(n_t^i=0\) for all \(i\in I\); \(t:=0\); \(v=1\); \(k_{ij}=0\) for all \(j\ne 1\); \(:=k_i^{\max}\).
2nd stage. We form the subset \(I^{v}\subset I\) of parts that have a launch on the \(v\)-th day. For each \(i\in I\) not being processed at the given time, the preference function is calculated
\[ f_i=\frac{T_i}{T_i^{m}}. \]
If some \(i\in I\) have already been put into processing at some opera-
the possibility is determined of processing one more part on this same operation; if the part-operation being processed is tracked by the preference function, then \(n_{\tau}^{i} := n_{\tau}^{i}+1\) is performed; otherwise the value of the preference function is corrected by the following formula:
\[ f_{ij}=\frac{T_i}{T_i^{m}-\sum_{j=1}^{\gamma}\tau_{ij}^{m}+t_{ij}^{n}}, \]
where \(\gamma\) is the number of operations through which the part has already passed in processing.
3rd stage. The workload of each equipment group is analyzed. If in some \(q\in Q\) there are idle \(s\in q\), then \(I_q\subset I\) are assigned for processing, satisfying the following condition:
\[ f_{ij}=\min_{i\in I_q}\left[\frac{T_i}{T_i^{m}}\right]. \]
4th stage. For some time instant \(t+\delta t\), a subset \(I^q\subset I\) is formed, consisting of parts whose processing at the current operation \(j\) has been completed. Obviously, for these parts the inequality must hold:
\[ \tau_{ij}^{m}:=\tau_{ij}^{m}-\delta t\leq 0. \]
For the formed set \(I^q\) the following is performed:
\[ k_{ij}:=k_{ij}-1, \]
and, in addition:
a) if \(k_{ij}^{\max}=0\) and \(j+1=\varnothing\), then the fact of completion of the quarterly program for the \(i\)-th part is recorded;
b) if \(k_{ij}>0\), then processing of the next batch on the same operation is continued and the value is computed
\[ \tau_{ij}^{m}:=\tau_{ij}^{m}-(\delta t-\tau_{ij}^{c}), \]
where \(\tau_{ij}^{c}\) is the time required to finish processing the part-operation after the preceding cutoff \(\delta t\); moreover, for \(n_{\tau}^{i}\ne 0\) the preference function is computed
\[ f_{ij}=\frac{T_i-T_{\kappa}}{T_{ij}^{m}}, \]
where \(T_{\kappa}\) is the lag in launching the given batch relative to the planned date;
c) if \(j+1=\varnothing\), then \(k_{ij+1}:=k_{ij+1}+1\) is performed.
It should be noted that machines released after processing and not loaded again are recorded as idle.
5th stage. For parts having \(f_{ij}\ne 0\), the preference function is corrected
\[ f_{ij} \begin{cases} \displaystyle \frac{T_i}{T_i^{m}-\delta t} & \text{if the part was processed during the time;}\\[6pt] \displaystyle \frac{T_i-\delta t}{T_i^{m}} & \text{otherwise.} \end{cases} \]
Parts not processed during \(\delta t\) and having \(f_{ij}\geq f_{ij}^{k}\), where \(f_{ij}^{k}\) is the critical value of the preference function, are assigned an “emergency” mark. The marked parts are taken by idle equipment, if there is any; otherwise, among the occupied equipment, the machine on which the largest stock of parts for the subsequent operation has been created is released.
6th stage. \(t:=t+\delta t\) is performed. If \(t<t_d\), where \(t_d\) is the duration of the working day, we proceed to the 3rd stage.
7th stage. A check is made for completion of the planned period, compris-
of schedule composition, \(\nu \ge T\). If the indicated inequality is satisfied, the composition of the schedule ends. Otherwise \(\nu=\nu+1\) is performed and a transition is made to stage 2.
Remark. The value \(f_{ij}^k\) can be determined unambiguously in the process of practical implementation of the algorithm. The closer \(f_{ij}^k\) is to unity, the higher the probability of processing one more batch of parts without setting up the machine, and hence the higher the efficiency of equipment utilization. However, \(f_{ij}^k \to 1\) increases the probability of disrupting the release date for parts for the next production subdivision.
In conclusion, it should be noted that the duration of the planning period \(T\) for which the schedule is drawn up is subject to investigation on the basis of experimental testing of the algorithm. It is obvious that the smaller \(T\) is, the more accurately the dynamics of production will be tracked; however, too small a \(T\) excludes preliminary information about upcoming jobs, which in turn makes it impossible to prepare the tooling and tools in advance. In addition, for small values of \(T\) the compiled schedule becomes weakly protected against disturbances.
REFERENCES
-
Yu. N. Efimov, V. I. Kizev, V. I. Nevraev, P. A. Sedelnikov. Basic principles of the construction and functioning of ASUP-TOMSK. Izvestiya TPI (in press).
-
S. A. Dumler. A modeling algorithm for compiling a calendar schedule. Mathematical Methods in the Organization and Economics of Production. “Mashinostroenie,” 1966.
-
V. M. Reider, Yu. N. Efimov, A. I. Zaitsev. A modeling algorithm for compiling a schedule for processing parts. Collection of reports of the VI Scientific and Technical Conference on Problems of Production Automation. Tomsk, 1969.