# Optimal Control Algorithms and Their Analysis for Short-Term Scheduling in Manufacturing Systems
## 4 Combined Method and Algorithm for Short-Term Scheduling in MSs
In the latter case, the conflict resolution is performed as follows: if \(J_{p0}^{(1)}<J_{p1}^{(1)}\), then during the maximization of (19) \(D_{\boldsymbol{x}}^{(i)}\) is executed in an interrupt-disable mode. Otherwise, the operation \(D_{\boldsymbol{x}}^{(i)}\) is entered into the Hamiltonian at priority \(D_{\xi}^{(\omega)}\) at arrival time \(\widetilde{t}\). After conflict resolution, the allocation of resources is continued, complying with (19) and without interruption of operations until a new contention is similarly examined. The considered variant of dichotomous division in conflict resolution can be extended to the case of \(\widetilde{k}\)-adic branching, where \(\widetilde{k}\) is the number of interrupted operations at some time \(\widetilde{t}\). The iterative process of the optimal schedule search is terminated under the following circumstances: either the allowable solution of the problem \(\Gamma\) is determined during the solving of a relaxed problem or at the fourth step of the algorithm after the integration we receive:  
\[\Big{|}J_{p}^{(r+1)}-J_{p}^{(r)}\Big{|}<\varepsilon_{1} \tag{24}\]  
where \(\varepsilon_{1}\) is a given value, \(r=0\), \(1\),... If the condition (24) is not satisfied, then the third step is repeated, etc. The developed algorithm is similar to those considered in [20; 37]. Here, the set of time points in which the Hamiltonian is to be maximized is formed on the previous iteration. These are points of operations interruption. Computational investigations of the proposed algorithm showed that the rate of convergence is predominantly influenced by the choice of the initial adjoint vector \(\psi(t_{0})\). In its turn, \(\psi(t_{0})\) depends on the first allowable control that is produced at the first step. During the scheduling process, the machines are primarily assigned to operations of high dynamic priority. To illustrate the main ideas of the algorithm, let us consider a simple example of a scheduling problem with two jobs, three operations, and a single machine, (\(T_{0}\), \(T_{f}\)) = (0, 14), \(a_{i\text{ae}}^{(o)}\) = 2 (\(I\) = 1,2; \(\ae=1\), 2, 3); \(\Theta_{i\text{ae}}(t)\) = 1 \(\forall\)\(t\); \(\varepsilon_{11}(t)\) = 1 at \(t\in(0,14]\), \(\varepsilon_{21}(t)\) = 0 for \(0\leq t<1\), \(\varepsilon_{21}(t)\) = 1 for \(t\geq 1\). In this case, the model can be described as follows:  
\[ \begin{array}{c}M=\Big{\{}\overset{\rightarrow}{u}\Big{|}\dot{x}_{i\text{ae }}^{(o)}=\varepsilon_{11}u_{i\text{ae}1}^{(o)};\dot{z}_{i\text{ae}1}^{(o,1)}=u _{i\text{ae}1}^{(o)};\dot{z}_{i\text{ae}1}^{(o,2)}=z_{i\text{e}1}^{(o,1)};\\ \dot{z}_{i\text{e}1}^{(o,3)}=&w_{i\text{e}1}^{(o)};u_{i\text{e}1}^{(o)}(t),w_{ i\text{e}}^{(o)}(t)\in\{0,1\},\sum\limits_{\ae=1}^{3}\sum\limits_{i=1}^{2}u_{i \text{e}1}^{(o)}(t)\leq 1;u_{i21}^{(o)}\Big{(}a_{i\text{}}^{(o)}-x_{i\text{ }1}^{(o)}\Big{)}=0;u_{i31}^{(o)}\Big{(}a_{i2}^{(o)}-x_{i2}^{(o)}\Big{)}=0;\\ w_{i\text{e}1}^{(o)}\Big{(}a_{i\text{ae}}^{(o)}-z_{i\text{ae}}^{(o,1)}\Big{)}= 0;T_{0}=0:\;x_{i\text{ae}}^{(o)}(t_{0})=z_{i\text{e}1}^{(o,1)}(t_{0})=z_{i\text {e}1}^{(o,2)}(t_{0})=z_{i\text{e}1}^{(o,3)}(t_{0})=0;T_{f}=14:\;x_{i\text{ae}}^ {(o)}(t_{f})=2;\\ \dot{z}_{i\text{e}1}^{(o)}(t_{f})\in\mathbb{R}^{1},\,l=1,2,3\Big{\}}.\end{array}  \tag{25}\]  
The scheduling quality measure is defined by the expression:  
\[ \begin{array}{c}J_{p}=\sum\limits_{i=1}^{2}\sum\limits_{\ae=1}^{3}\left[ \Big{(}a_{i\text{ae}}^{(o)}-x_{i\text{ae}}^{(o)}\Big{)}^{2}+\left(z_{i\text{ ae}1}^{(o,1)}z_{i\text{e}1}^{(o,3)}+\frac{\big{(}a_{i\text{ae}}^{(o)}\big{)}^{2}}{2 }-z_{i\text{e}1}^{(o,2)}\right)^{2}\Big{(}z_{i\text{e}1}^{(o,1)}\Big{)}^{2} \right]\Bigg{|}_{t=T_{f}}\\ -\sum\limits_{i=1}^{2}\sum\limits_{\ae=1}^{3}\int\limits_{0}^{14}\gamma_{i \text{ae}}(\tau)u_{i\text{ae}1}^{(o)}(\tau)d\tau,\end{array}