# Optimal Control Algorithms and Their Analysis for Short-Term Scheduling in Manufacturing Systems
## 4 Combined Method and Algorithm for Short-Term Scheduling in MSs
It can be seen that the difference between the functional \(J_{p}\) in (23) and the functional \(J_{ob}\) in the problem P is equal to losses caused by interruption of operation execution. 3. Let \(\mathbf{u}_{p}^{*}(t)\), \(\forall\)\(t\in\) (\(T_{0}\), \(T_{f}\)) be an MS optimal program control in P and an allowable program control in \(\Gamma\); let \(\mathbf{x}_{p}^{*}(t)\) be a solution of differential equations of the models \(M_{<\infty}\), \(M_{<\
u>}\) subject to \(\mathbf{u}(t)\)=\(\mathbf{u}_{p}^{*}(t)\). If so, then \(\mathbf{u}_{p}^{*}(t)\) meets the requirements of the local section method (maximizes [PERSON]'s function) for the problem \(\Gamma\). In this case, the vectors \(\mathbf{u}_{p}^{*}(t)\), \(\mathbf{x}_{p}^{*}(t)\) return the minimum to the functional (1). The scheme of computation can be stated as follows. Step 1. An initial solution \(\mathbf{u}_{g}(t)\), \(t\in\) (\(T_{0}\), \(T_{f}\)) (an arbitrary allowable control, in other words, allowable schedule) is selected. The variant \(\mathbf{u}_{g}(t)\equiv 0\) is also possible. Step 2. The main system of Equation (1) is integrated subject to \(\mathbf{h}_{0}(\mathbf{x}(T_{0}))\leq 0\) and \(\mathbf{u}(t)\)=\(\mathbf{u}_{g}(t)\). The vector \(\mathbf{x}^{(o)}(t)\) is received as a result. In addition, if \(t=T_{f}\), then the record value \(J_{p}=J_{p}^{(o)}\) can be calculated, and the transversality conditions (5) are evaluated. Step 3. The adjoint system (2) is integrated subject to \(\mathbf{u}(t)\)=\(\mathbf{u}_{g}(t)\) and (5) over the interval from \(t=T_{f}\) to \(t=T_{0}\). For time \(t=T_{0}\), the first approximation \(\Psi_{i}^{(o)}(T_{0})\) is received as a result. Here the iteration number \(r=0\) is completed. Step 4. From the point \(t=T_{0}\) onwards, the control \(u^{(r+1)}(t)\) is determined (\(r=0\), \(1\), \(2\), \(\dots\) is the number of iteration) through the conditions (19). In parallel with the maximization of the Hamiltonian, the main system of equations and the adjoint system are integrated. The maximization involves the solving of several mathematical programming problems at each time point. The branching of the problem \(\Gamma\) occurs during the process of Hamiltonian maximization at some time \(\widetilde{t}\in\) (\(T_{0}\), \(T_{f}\)) if the operation \(D_{\boldsymbol{x}}^{(i)}\) is being interrupted by the priority operation \(D_{\xi}^{(\omega)}\). In this case, the problem \(\Gamma\) is split into two sub-problems (\(\mathrm{P}_{\boldsymbol{x}}^{(i)}\),\(\mathrm{P}_{\xi}^{(\omega)}\)). Within the problem \(\mathrm{P}_{\boldsymbol{x}}^{(i)}\), the operation \(D_{\boldsymbol{x}}^{(i)}\) is executed in an interrupt-disable mode. For other operations, this restriction is removed and the relaxed scheduling problem is solved via the method of successive approximations. Let us denote the received value of the goal function (23) by \(J_{p0}^{(1)}\). Within the problem \(\mathrm{P}_{\xi}^{(\omega)}\), the previously started operation \(D_{\boldsymbol{x}}^{(i)}\) is terminated, and \(D_{\xi}^{(\omega)}\) begins at time \(\widetilde{t}\). The resources released by the operation \(D_{\boldsymbol{x}}^{(i)}\) and not seized by \(D_{\xi}^{(\omega)}\) can be used for other operations if any are present. Reallocation of resources should be performed according to (19). Subsequently, after completion of operation \(D_{\xi}^{(\omega)}\), the relaxed scheduling problem is solved. In this case, the value of the goal function (23) is denoted by \(J_{p1}^{(1)}\). The record \(J_{p}\) is updated if \(J_{p0}^{(1)}<J_{p}\) or/and \(J_{p1}^{(1)}<J_{p}^{(1)}\) [we assume that the functional (23) is minimized]. If only \(J_{p0}^{(1)}<J_{p}^{(1)}\), then \(J_{p}=J_{p0}^{(1)}\). Similarly, if only \(J_{p1}^{(1)}<J_{p}^{(1)}\), then \(J_{p}=J_{p1}^{(1)}\). If both inequalities are true, then \(J_{p}=\min\{J_{p0}^{(1)}\), \(J_{p1}^{(1)}\}\).