## 1 Introduction  
### Job-Shop Scheduling Problem  
In all cases of human activity to achieve the desired result, as a rule, plans and schedules are drafted. The complexity of task scheduling along with the continuous improvement of automation tools for such activities has led to increased interest in scheduling synthesis theory and calendar planning. The tasks of calendar planning reflect the process of the distribution over time of a limited number of resources assigned to the project, which includes a list of related works. Problems of scheduling theory belong to the class of problems of combinatorial optimization or ordering. The active research and development of scheduling theory began in the 1950s. One of the main issues of scheduling theory was the classification of tasks and the establishment of their complexity. Reviews of problems in scheduling theory are presented in the works of [PERSON] [PERSON], [PERSON], [PERSON], [PERSON], [PERSON], and [PERSON], et al. [1, 2, 3, 4, 5, 6]. The scheduling problem of the \"job-shop\" class is NP-hard if there are more than two devices [5, 7]. The survey [6] shows that the job-shop scheduling (JSS) problem is one of the most difficult among all NP-class problems even from the point of view of task formulation. As shown in [8], the number of combinations for a job-shop task with \(n\) jobs and \(m\) devices (each job contains \(m\) stages) is proportional to the value \((n!)^{m}\). At the same time, JSS problems are important for many fields: manufacturing, semiconductors, pharmaceuticals, supply chains, rail-bound transportation, mining, healthcare, etc. [6]. Since planning tasks are very important in practice and have high complexity and variety, a wide variety of methods are used to solve them, including artificial intelligence methods [5; 9; 10]. Although classical optimization methods are also used, such as the branch and bound method [11; 12], dynamic programming [7], and methods based on heuristics and rules [13; 14; 15; 16]. Among the methods of artificial intelligence, the most commonly used is the genetic algorithm (GA) [5; 17; 18; 19] and other population-based algorithms such as the Particle Swarm Optimization [20; 21] and ant colony optimization (ACO) algorithms [22]. All these stochastic population optimization algorithms (evolutionary or swarm) provide high flexibility and solve scheduling problems not with 100% accuracy but with sufficient accuracy in a reasonable time. In addition, population algorithms can be used to create hybrids with other, deterministic approaches [7; 17; 18; 19; 23]. Additionally worthy of note is the use of stochastic algorithms that are faster than population algorithms and based on Simulated Annealing [10; 24]. Despite a large number of solution methods, none of them can be called dominant. Besides the usual reasons typical for NP-hard problems [25], the variability of planning problems even within the same class should also be noted. Most scheduling tasks are associated with the concept of multi-stage service systems. These include systems in which servicing requirements consist of several stages. Despite the diversity of production systems, the formalized description of the JSS problem can be considered basic for a large class of multi-stage systems. The job-shop problem can be formulated as follows. 1. There is a finite set \(N=\{1,2,\ldots,n\}\) of requirements (works, jobs, orders) and a finite set \(M=\{1,2,\ldots,m\}\) of devices (machines, executors, workstations, etc.). The service process for requirement \(i\) includes \(r_{i}\) stages. At the same time, each requirement \(i\) and each stage \(q\) (\(1\leq q\leq r_{i}\)) of its service is associated with some subset of machines \(M^{i}q\) from the set \(M\). It is assumed that each machine can simultaneously serve no more than one requirement. In such systems with successive servers, each job \(i\) is assigned its own, characterizing for this job the sequence \(L_{i}\) of its servicing by machines: \(L_{i}=(L_{1}{}^{i},\)\(L_{2}{}^{i},\)\(\ldots,L_{m}{}^{i})\).