# Intelligent Scheduling with Reinforcement Learning
## 2 Literature Review
### Job Shop Problem
Typically, these functions are interpreted as the value or cost of a plan, and the greater or lesser they are, respectively, the better the solution. Figure 1: Representation of a _Job Shop_ scheduling problem (based on [PERSON] proposal [15]). It is possible to use objective functions that apply only one measurement, but usually several metrics with different degrees of importance are used. Using an industrial production environment as an example, the objective function may correspond mainly to profit maximization, having as secondary objectives the reduction of machine downtime and the minimization of delays. In this case, the best solutions would be those that would bring the greatest profits to the company; but in case of very similar solutions in terms of profits, the best (according to this objective function) would be those that would reduce idle times and delays. In _Job Shop_ problems, the most used metrics in objective functions are divided, mainly, in three subcategories [11]: related to the use of the system, the date of completion of tasks and the task travel time (difference between receiving the task and its delivery). Some examples of these are:  
1. Date of completion * greatest delay; * sum of delays and advances (tasks completed ahead of schedule); * total number of tardy jobs. 2. Travel time * (task) travel time; * average travel time; * maximum travel time;
3. System usage * machine usage; * system usage, i.e., average utilization of each machine. Of all these, the most common criterion to measure the quality of a schedule comparatively is typically related to the makespan (completion time of all operations of a task) and a combination of secondary objectives, e.g., the minimization of the total time needed to perform all operations, while minimizing the sum of earliness and lateness and maximizing the use of the system [2]. Given the complexity of the _Job Shop_ scheduling problem, creating methods to solve it is a great challenge. There are two main approaches [3]: the application of exact methods and the approximation algorithms. Exact methods have a great advantage over other methods: they are the only ones that can guarantee that the optimal solution is found. However, for this to be possible, its implementation is built around an exhaustive search that can solve an optimization problem with effort that grows polynomially in accordance to the size of the solution space (related to the problem complexity), which may lead to a substantial reduction in efficiency. In practice, it takes a large amount of time (in problems of normal dimensions) to navigate that space to find the optimal solution. This makes it so that those solutions might not be ready in time, making them almost impossible to use [19]. The approximation algorithms present an alternative: find satisfactory solutions with the available time. The compromise of this approach is that one is not looking for the optimal solution, but the best solution found until the time when it is necessary to put the plan into production. Of these two approaches, the one that stands out is the one that uses approximation algorithms, given its efficiency and possibility of being used in production environments of real industries. Some examples of successful approaches are presented in [9; 20; 21].