# Intelligent Scheduling with Reinforcement Learning
## 3 Problem Formulation
In the approach proposed in this paper, the agent chooses to ignore all the possible permutations, focusing instead on the information of the current state and on perceiving the effect that the chosen action (which will lead to \(s^{\prime}\)) will have. The \(R\) reward function determines the expected reward amount that must be received when making the transition from one specific state to another. In order to define the reward, it is necessary to consider what the agent's objective is. This work suggests that the formulation of the _Job Slop_ scheduling problem should aim at the minimization of the makespan, since this is the most common goal in this type of problem. The reward should be a ratio that estimates the benefit of the chosen action against its cost, considering the chosen objective. The used formula is presented in Equation (2), where the makespan difference indicates the distance from the obtained makespan to the known optimal value [49] (we use the best known upper bound on instances that are not optimally solved). This formula (previously presented in [50]) has undergone a process of fine-tuning the reward limits throughout the work presented here, so that the agent would obtain better results more rapidly. Given that the highest reward considers a difference lower than 250 units, the system might have a tendency to offer just good-enough solutions (and not near-optimal) on very small problems. However, we do not consider this issue as relevant given that extremely small problems would be easier to solve and, as such, the proposed system would not be the best option--that would be the application of an approach that guarantees the optimal solution. \[R= \begin{cases}\text{Invalid operation allocation,}&-1.0\\ \text{Valid operation allocation,}&0.0\\ \text{Complete allocation and makespan diff $<$250},&1.0\\ \text{Complete allocation and makespan diff $<$450},&0.6\\ \text{Complete allocation and makespan diff $<$650},&0.4\\ \text{Complete allocation and makespan diff $<$1500},&0.1\\ \text{Complete allocation and makespan diff $>$1500},&0.0\end{cases}  \tag{2}\]  
It is important to note that this formula has a limitation: it relies on the existence of a reference (the optimal or best known upper bound) value that is used to measure the quality of the obtained makespan. In cases where this value is not known (e.g., a dynamic industry environment) the agent could not apply this reward formula. In that situation the agent would have to be trained beforehand, or a revised formula would have to be applied. Given the way reinforcement learning approaches work and the nature of the _Job Shop_ scheduling problem, the order in which actions are taken will have a significant impact on the total reward obtained. The agent will then have to be able to learn and explore all decision paths in the best possible way, discovering how to achieve his goal. With this proposal to formalize the _Job Shop_ problem environment as a Markov decision process, an agent with good learning abilities should be able to perceive its environment, analyze its state and choose the actions that maximize the total reward gathered, always taking into consideration the goals that have been established.