## 1 Introduction
### Job-Shop Scheduling Problem
The requirement \(i\) is served first by the machine \(L_{1}{}^{i}\), then by \(L_{2}{}^{i}\), and so on. Service sequences may be different for different requirements and may contain instrument repetitions. If the requirement \(i\) at stage \(q\) must be serviced by machine \(l\), then the duration \(t_{liq}\) of its servicing by this machine is assumed to be given. The system operation process can be described by setting a schedule (calendar plan), i.e., some set of indications as to whether particular requirements are served at each moment of time. Figure 1 shows a Gantt chart of an example of a JSS problem with jobs \(A\) (blue), \(B\) (green), \(C\) (red), and \(D\) (yellow) and machines \(R\), \(S\), \(T\), and \(Q\). For example, job \(A\) has three stages that require the consistent use of machines \(R\) (8 h), \(S\) (5 h), and \(Q\) (2 h). Figure 1: An example of a JSS problem solution (Gantt chart). Under the assumptions made above, the schedule can be considered a vector \(\{s_{1}(t)\), \(s_{1}(t)\),..., \(s_{m}(t)\}\), whose components are piecewise constant left continuous functions. Each of them is given on the interval \(0\leq t<\infty\) and takes a value of 0, 1,..., \(n\). \[s=\{s_{1}(t),s_{2}(t),\,\ldots\,,\,s_{m}(t)\}. \tag{1}\]  
If \((t^{\prime})=i\), \(l\in M\), \(i\in N\), then at the time \(t^{\prime}\), the device \(l\) serves the requirement \(i\). When setting the schedule, all conditions and restrictions arising from the formulation of the problem under consideration must be observed, which means the schedule must be permissible. If there are several permissible schedules, it is necessary to choose the best of them, which means setting some selection criterion (quality criterion). In the classical scheduling theory, such a criterion is the completion time of all requirements (makespan); that is, the completion time of the last requirement. Each admissible schedule \(s\) uniquely determines the vector of time points for completing the service of all jobs:  
\[T(s)=(T_{1}(s),\,T_{2}(s),\,\ldots\,,\,T_{n}(s)). \tag{2}\]  
If some valid, non-decreasing in each of the variables function \(F(x)\) is given,  
\[F(x)=F(x_{1},\,x_{2},\,\ldots\,,\,x_{n}), \tag{3}\]  
then the quality of the schedule \(s\) is estimated by the value of this function at \(x=T(s)\):  
\[F(x)=\max\{x_{i}\},\,i=1,2,\,\ldots\,,\,n. \tag{4}\]  
In this case,  
\[F(T(s))=T_{\max}(s),\,\text{where}\,\,T_{\max}(s)=\max\{T_{i}(s)\},\,i=1,\,2, \,\ldots\,,\,n, \tag{5}\]  
From this statement of the problem, the main difficulties are noticeable:  
* Discreteness;
* Multivariance;
* Multifactorialism;
* The inability to construct an objective function in the form of an algebraic expression, since the objective function is calculated only algorithmically. Mathematically, the JSS problem can be divided into several subtypes according to their constrictions, criteria, and other features. The review [6] identifies 37 subtypes of the JSS problem. It also provides mathematical formulations for various subtypes and a review of solution methods. A variety of tasks and methods and the fact that research on this issue does not stop indicate both the relevance and high complexity of the JSS problem.