# Intelligent Scheduling with Reinforcement Learning
## 2 Literature Review
### Job Shop Problem  
In this section, the essential components for understanding the _Job Shop_ problem are presented, describing in detail the formalization of the problem, the complexity of reaching a solution and the problems with its optimization and, finally, how the quality of these solutions and the corresponding plans is measured. Multi-operation _Job Shop_ scheduling problems consist of processing n manufacturing orders (known as jobs), \(J_{1},J_{2},J_{3},\cdots,J_{n}\) in \(m\) machines, \(M_{1},M_{2},M_{3},\cdots,M_{m}\)  
These machines are located in an industrial environment, such as a factory or workshop. The name _Job Shop_ is derived, precisely, from the combination of English language terms for manufacturing orders and machines. Each task (also known as manufacturing order) is characterized by a certain number of operations. Each one of these operations is represented by \(o_{ij}\), where the \(i\) represents the task number that the operation belongs to and \(j\) the processing order on the task (e.g., \(o_{15}\) represents the fifth operation of the first task). A _Job Shop_ problem P is thus defined by the set of machines, tasks and operations, establishing \(P=(M,J,O)\). Each operation also has an associated \(p_{ij}\) processing time that is known, representing the number of time units that is required to fully execute the operation \(o_{ij}\). This set and its relations are illustrated in Figure 1.  
Obtaining a scheduling plan is, after all, a relatively uncomplicated task. However, a scheduling plan by itself is not particularly valuable. What is sought, then, is an optimized scheduling plan that presents the optimal solution. Unfortunately, there is no simple way to determine an optimized plan given its high complexity. According to the computational complexity theory [16], problems can be classified according to the computational power requirements of algorithms into easy or hard. A problem is easy (or of polynomial class P) when there is an algorithm that can obtain the optimal solution of a problem in polynomial time, being only limited in execution time by the size of the problem (in this case the number of jobs). A hard (or NP) problem is characterized by not having algorithms capable of producing optimal solutions in a timely manner. Within these, there is also a subdivision: NP-hard and NP-complete problems. The set of NP-complete problems is a subset of NP problems that has the particularity that if an algorithm is found that solves one of these problems, that algorithm can be applied to any NP problem [17]. Scheduling problems are considered to be of very complex resolution. Not only do they belong to the \(NP\)-difficulty category, they actually are one of the worst problems in it due to the difficulty in calculating solutions [18]. From a large set of possible plans, it is necessary to choose the one that offers the best performance (according to the metric chosen). The possible combinations are quite high: considering \(n\) tasks in \(m\) machines, the number of possible plans will be \((n!)^{m}\). A problem of 5 machines with 5 tasks generates 24 billion possible combinations; a problem (still small) of 10 tasks with 10 different machines quickly reaches an intractable number of plans: \((10!)^{10}=3.959^{65}\). Most of these solutions might end up invalid (e.g., violations of constraints) but, nevertheless, it would not be possible to validate such a large number of solutions. Given the inherent complexity, there is no algorithm to obtain optimal solutions to large _Job Shop_ problems in a timely manner. It is therefore necessary to resort to approximate approaches to solve this problem, so that satisfactory solutions can be found in a timely manner. When the optimization of something is mentioned, it usually refers to the choice of an option (from a diversified range) that will minimize or maximize a certain objective function. This objective function is a mathematical equation that translates the objectives to be achieved with this process and its constraints.