Algorithm for Solving the Problem of Operational Scheduling in Discrete Manufacturing
Abstract Generated abstract
This paper presents an algorithm for operational scheduling in discrete manufacturing systems represented by an acyclic directed network model. Given directive output plans for finished products, batch sizes, production cycle durations, initial stock and work in progress, and product applicability coefficients on graph arcs, the method computes launch and output plans for all products by processing graph vertices in layered order and maintaining sufficient availability over each reproduction cycle. The authors describe the formation of plan elements, propagation of derived demand to predecessor products, required planning horizons, and an implementation on the Ural-11B computer using memory management procedures for storing and retrieving intermediate plans. The resulting program produces calendar launch and completion plans for all vertices, with a reported computation and printing time of about two hours for a 700-vertex network model.
Full Text
An Algorithm for Solving the Problem of Operational Scheduling in Discrete Manufacturing
Yu. N. Efimov, V. I. Kizev, V. I. Nevraev, P. A. Sedelnikov
(Presented by the scientific seminar of the Department of Computer Engineering)
In automated systems for planning and control of discrete manufacturing that use a network model in forming the calendar plan for launching and output, the following problem arises.
There is a directed graph \(G=(I,U)\) without circuits [1], containing \(|I|\) vertices and \(|U|\) arcs. To each arc \((i,j)\in U\), leading from vertex \(i\) to vertex \(j\), there corresponds a number \(R_{ij}>0\), which has the meaning of the applicability of product \(i\) in one batch of product \(j\). To each vertex \(j\in I\) of the graph \(G\) there are assigned the numbers
\[ m_j>0,\quad T_j>0,\quad \Delta_j>0,\quad \sigma_j>0, \]
where: \(m_j\) is the size of the output batch of product \(j\);
\(T_j\) is the duration of the production cycle for manufacturing product \(j\);
\(\Delta_j\) is the quantity of product \(j\) available at time \(T_0\), corresponding to the beginning of the planned period;
\(\sigma_j\) is the quantity of product \(j\) that is in production at time \(T_0\).
It is obvious that the set
\[ S=\{S_j\}_{j=\overline{1,|I|}}, \]
where \(S_j=\Delta_j+\sigma_j\), determines the volume of work in progress in quantitative terms.
For the vertices of the graph \(G\) corresponding to output products (finished products), directive output plans are specified in the form of discrete functions \(f_j(t)\). We note that the directive plan may also be specified by any continuous function, which is then quantized. Thus, the introduction of the discrete function \(f_j(t)\) of the directive plan does not restrict the generality of the subsequent reasoning.
On the basis of the data listed above, it is required to transform the directive plans of the graph vertices corresponding to output products into particular plans for all the remaining vertices (products).
Let \(q_\lambda^{\mathrm{B}}\) denote the quantity of product \(j\) output at time \(t_\lambda^{\mathrm{B}}\). Then by the output plan of the product corresponding to vertex \(j\) we shall understand a finite set of pairs
\[ P_j^{\mathrm{B}}(t)=\{q_\lambda^{\mathrm{B}},\, t_\lambda^{\mathrm{B}}\}_{\lambda=1,\mu}. \]
Each pair
\[ p^b_\lambda = q^b_\lambda,\ t^b_\lambda \]
constitutes an element of the output plan. Similarly, for the launch plan,
\[ P^z_j(t)=\{q^z_\lambda,\ t^z_\lambda\}_{\lambda=1,\nu}; \]
\[ p^z_\lambda=q^z_\lambda,\ t^z_\lambda;\qquad p^z_\lambda\in P^z_j(t). \]
Let \(I'\) be the set of those vertices of the graph \(G\) for which directive output plans are specified. Then, for \(j\in I'\),
\[ P^b_j(t)=f_j(t). \]
Therefore, the main problem in forming the schedule is the calculation of \(P^z_j(t)\) for each \(j\in I\) and of \(P^b_j(t)\) for \(j\in I/I'\). To compute \(P^z_j(t)\) from the known \(P^b_j(t)\), we shall use the relation [1]
\[ P^z_j(t-T_j)\geq P^b_j(t)-s_j, \]
which expresses the basic principle of maintaining the synchronous operation of all divisions of the enterprise. In order to satisfy this relation for all \(j\in I\), it is necessary to launch the \(j\)-th product in the quantity \(q^z_\lambda=km\) (\(k\) is a positive integer) if and only if its available quantity becomes less than the planned demand over the period \(T_j\) required for its reproduction. The output plans are calculated by the formula
\[ P^b_i(t)=\sum_{j\in \Gamma_i} P^z_j(t)\cdot R_{ij}. \]
It follows from this that \(P^b_i(t)\) for \(i\in \Gamma_j^{-1}\) can be calculated only after all launch plans have been calculated for \(j\in \Gamma_i\). Therefore, the initial information characterizing the vertices of the graph should be ordered by layers, using, for example, the method of [2]. Then the operation of the proposed algorithm for calculating the plans is reduced to the following.
- Set
\[ \{P^b_j(t)\}_{j\in I/I'}:=\varnothing . \]
Take the first vertex \(j\in I\) from the ordered initial information.
- Set \(Q:=s_j\).
Take the first element of the plan \(P^b_j(t)\).
-
Set \(Q:=Q-q_\lambda\).
-
Check whether \(Q\geq 0\). Yes: perform step 5.
No: perform step 11.
-
Check whether all elements of the plan \(P^b_j(t)\) have been considered. Yes: perform step 7. No: perform step 6.
-
Take the next element of the plan \(P^b_j(t)\) and perform step 3.
-
The plan
\[ P^z_j(t)=\{q^z_\lambda,\ t^z_\lambda\}_{\lambda=1,\nu} \]
has been formed.
For each \(i\in \Gamma_j^{-1}\), find the partial output plan
\[ P^{pc}_i(t):=P^{pc}_i(t)+P^z_j(t)\cdot R_{ij}. \]
Since the initial information is ordered by layers, by the time \(P^b_i(t)\) is used to calculate \(P^z_i(t)\), the plan being formed is
\[ P^{pc}_i(t)=P^b_i(t). \]
-
Check whether all vertices \(j \in I\) have been processed. Yes. Perform step 10. No. Perform step 9.
-
Take the next vertex \(j\) from the ordered initial information and perform step 2.
-
Terminate the computations, since all plans have been calculated.
-
Form the next element of the launch plan
\[ t_{\lambda}^{3}=t_{\lambda}^{\mathrm{в}}-T_j; \]
\[ q_{\lambda}^{3}=E\left(\frac{|Q|}{m_j}\right)\cdot m_j, \]
where \(E\left(\frac{|Q|}{m_j}\right)\) is the smallest integer exceeding the ratio \(\frac{|Q|}{m_j}\).
- Set \(Q := Q+q_{\lambda}^{3}\) and go to 5.
It is not hard to see that, when calculating the plan \(P_i^{3}(t)\) for some vertex \(i \in I\) of the graph \(G\) for the planning period \(T^{\mathrm{п}}\), it is necessary to have \(P_{\lambda}^{\mathrm{в}}(t)/j \in \Gamma_i\) for the period \((T^{\mathrm{п}}+T_j)\). Hence the plan \(P_v^{\mathrm{в}}(t)\) for any vertex \(v \in I\) must be calculated for the period \((T^{\mathrm{п}}+t_v)\), where
\[ t_v=\max_{l_v\in L_v}\sum_{j\in l_v}T_j, \]
\(l_v\) is the set of vertices of the graph \(G\) that constitute a path preceding vertex \(v\), and the maximum is taken over the entire set of preceding paths \(L_v\). The directive release plans for finished products are specified correspondingly; for these (plans), \(t_v\) is equal to the duration of the production cycle for manufacturing these products.
The algorithm described has been implemented on the Ural-11B computer. The ordered initial information for each \(j \in I\) was represented in the following form:
\[ \begin{gathered} j,\ x_j,\ T_j,\ y_j,\ m_j,\ \rho_j;\\ i_1,\ R_{1j};\\ i_2,\ R_{2j};\\ \ldots\ldots\ldots\\ i_\rho,\ R_{\rho j}; \end{gathered} \]
where \(i \in \Gamma_j^{-1}\);
\(\rho_j\) is the number of arcs entering vertex \(j\) (the local degree of the graph at vertex \(j\) [2]);
\(x_j,\ y_j\) are the addresses to which the corresponding output documents are sent.
The calculation of launch plans and release plans is organized in the form of the corresponding standard subroutines, the connection between which is carried out by a service program. The service program also performs all the necessary preparation for plan calculation (sequential scanning of the initial ordered information, writing the obtained plans to NF or NML, searching in NF or NML for the plans needed for the subsequent computation. The search for plans is carried out as follows: by the address \((a+j)\) (\(a\) = const, \(j\) is the octal number of the graph vertex), a row is found in the information table (TI) in which, from the contents of the sign digit, the location of the required plan is determined—NF or NML; the next 7 binary digits contain the number of elements of the plan, and the remaining 5 digits contain the initial address of the plan if it is located in NF, or the zone number if it is recorded in NML.
The \(P_i^{\mathrm{в}}(t)\) obtained in the course of the calculation is entered either in NF, if there is sufficient space in the operational field of plans, or in NML. In any
In this case, information on the location of the recorded plan and the number of its elements is entered into the IT in address form.
Let us note that the plan \(P_j^{v}(t)\), according to which the plans \(P_i^{z}(t)\) for \(i \in \Gamma_j^{-1}\) have already been calculated, does not participate in further computations under the algorithm and is excluded from the field of plans. The freed memory space of the machine is used to store the newly obtained plans \(P_i^{v}(t)\).
In the service program, a table of operative zones (TOZ) is formed, making it possible to reduce the time spent working with the NML. When reading plans \((P_j^{v} t)\) from the NML, the corresponding zone numbers are entered into the TOZ so that the subsequently obtained plans are recorded precisely in these zones. Such repeated reference to a small number of zones reduces the time required to find the necessary information in the NML.
Thus, as a result of the program’s operation, launch–completion plans are formed for all vertices of the graph. The relative time \(t_\lambda\) is converted into calendar dates; a calendar launch–completion plan, distributed by the addresses \(x_j, y_j\), is printed. The plan obtained from the computer is a document that is approved and accepted for execution.
The total time for calculating the plans and printing the input documents for a network model having 700 vertices and complexity coefficient 3, with the number of elements in the directive plan \(\mu = 150\), was about 2 hours.
References
- P. A. Sedelnikov, Yu. N. Efimov. Algorithm for ordered recoding of a graph. In the present collection.
- O. Ore. Graph Theory. Moscow, Nauka Publishing House, 1968.