# Optimal Control Algorithms and Their Analysis for Short-Term Scheduling in Manufacturing Systems
## 4 Combined Method and Algorithm for Short-Term Scheduling in MSs  
The basic _technical idea_ of the presented approach on the basis of previous works ([13; 19; 33; 34; 41]) is the combination of optimal control and mathematical programming. Optimal control is not used for solving the combinatorial problem, but to enhance the existing mathematical programming algorithms regarding non-stationarity, flow control, and continuous material flows. As the control variables are presented as binary variables, it might be possible to incorporate them into the assignment problem. We apply methods of discrete optimization to combinatorial tasks within certain time intervals and use the optimal program control with all its advantages (i.e., accuracy of continuous time, integration of planning and control, and the operation execution parameters as time functions) for the flow control within the operations and for interlinking the decomposed solutions. The basic computational idea of this approach is that operation execution and machine availability are dynamically distributed in time over the planning horizon. As such, not all operations and machines are involved in decision-making at the same time. Therefore, it becomes natural to transit from large-size allocation matrices with a high number of binary variables to a scheduling problem that is dynamically decomposed. The solution at each time point for a small dimensionality is calculated with mathematical programming. Optimal control is used for modeling the execution of the operations and interlinking the mathematical programming solutions over the planning horizon with the help of the maximum principle. The maximum principle provides the necessary conditions such that the optimal solutions of the instantaneous problems give an optimal solution to the overall problem ([21; 27; 42]). We describe the proposed method and algorithm for two classes of models below:  
* models \(M_{<\
u>}\) of operation program control;
* models \(M_{<\
u>}\) of auxiliary operations program control. These models were described in [13; 19; 33; 34; 35; 36; 37; 38]. Along with the initial problem of program control (marked by the symbol \(\Gamma\)), we consider a relaxed one (marked by P). The latter problem has no constraints of interruption disability operations \(D_{\ae}^{(i)}\) (where \(D_{\ae}^{(i)}\) is an operation \(\ae\) with object \(i\). See, for example, [36; 37]). Let the goal function of problem \(\Gamma\) be:  
\[J_{p}=\left\{J_{ob}+\sum_{i=1}^{n}\sum_{\ae=1}^{s_{i}}\sum_{j=1}^{m}\sum_{ \lambda=1}^{l}\left[z_{\ae j\lambda}^{(\alpha,1)}z_{\ae j\lambda}^{(\alpha,3)}+ \frac{(a_{\ae})^{2}}{2}-z_{\ae j\lambda}^{(\alpha,2)}\right]^{2}\left(z_{\ae j \lambda}^{(\alpha,1)}\right)^{2}\right\}\right|_{t=T_{f}} \tag{23}\]  
where the auxiliary variables \(z_{\ae j\lambda}^{(\alpha,1)}(t)\), \(z_{\ae j\lambda}^{(\alpha,2)}(t)\), \(z_{\ae j\lambda}^{(\alpha,3)}(t)\) are used for operations with interruption prohibition. More detailed information about these auxiliary variables and the methods of their utilization can be found in [20]. The following theorem expresses the characteristics of the relaxed problem of MS OPC construction. Let \(P\) be a relaxed problem for the problem \(\Gamma\). Then  
1. If the problem \(P\) does not have allowable solutions, then this is true for the problem \(\Gamma\) as well. 2. The minimal value of the goal function in the problem \(P\) is not greater than the one in the problem \(\Gamma\). 3. If the optimal program control of the problem \(P\) is allowable for the problem \(\Gamma\), then it is the optimal solution for the problem \(\Gamma\) as well. The proof of the theorem follows from simple considerations. **Proof. **  
1. If the problem P does not have allowable solutions, then a control \(\mathbf{u}(t)\) transferring dynamic system (1) from a given initial state \(\mathbf{x}(T_{0})\) to a given final state \(\mathbf{x}(T_{f})\) does not exist. The same end conditions are violated in the problem \(\Gamma\). 2.