# Intelligent Scheduling with Reinforcement Learning
## 3 Problem Formulation  
This section explains the characteristics that make the _Job Shop_ scheduling problem so interesting and unique and what should be done so that it can be solved with learning techniques. A _Job Shop_ scheduling problem consists of N tasks that must be processed on M machines at a given moment, as detailed in Section 2. Traditionally, the most common goal of scheduling optimization is the minimization of the makespan [2]. The conditions that allow us to define a reinforcement learning problem are the specification of an objective to achieve, a set of possible actions and states that the environment may have, and the policy of the agent. To define this problem, and as typically used in reinforcement learning approaches (Section 2.4), it is proposed here to formulate the _Job Shop_ problem as a Markov decision process. The mathematical formulation of a Markov process consists of a finite set of \(S\) states (where \(s\in S\)), a set of possible \(A(s)\) actions in each state, a \(R(s^{\prime}|s,a)\) function that represents the reward when applying action \(a\) in state \(s\) which leads to the state \(s^{\prime}\) and the probability of transition between state \(s\) and \(s^{\prime}\), knowing that action \(a\) has been chosen. This probability is defined in Equation (1). \[p(s^{\prime}|s,a) \tag{1}\]  
Most real problems are quite complex, making it impossible to know in advance all the probabilities of transition between all states. That is where the learning mechanism of a reinforcement learning agent comes into play in order to solve the problem. Thus, the mathematical formulation of the _Job Slop_ problem in the form of a Markov decision process requires only the definition of the set of states \(S\), possible actions \(A\) and the reward function \(R\). At first glance, the definition of the set of actions \(A\) seems to be relatively simple. At any given time, there is only one type of action that can be done, and that is assigning an operation to a machine. However, this is far from being true. Selecting which task to allocate next is the key decision that gives rise to the scheduling problem itself. If, for example, we consider a problem with 50 tasks, each with 50 operations that must be performed on 10 machines, and assuming that it is not possible to make allocations in the future, 500 different allocations can be made. Thus, the set of actions should contain all the possible allocations that can be made at a given time, and the agent has to make the key decision of choosing the action to perform. The state set \(S\) contains all possible states of the _Job Slop_ problem. For a scheduling problem of this category to be converted into a Markov decision process, it is necessary to establish that a state change is only possible when a new assignment is made. Considering that all states are not subject to the previous states (i.e., in Equation (1), \(s^{\prime}\) is only conditioned by \(s\) and \(a\)), it is possible to state that \(S\) is in accordance with the requirements to formalize a Markov decision process [48]. This work proposes, then, that \(S\) is the collection of all possible permutations of a scheduling plan. As such, there must be a state for each possible assignment of operations to a machine. However, it is important to note that this does not mean that the implementation of the environment should do these calculations in advance (or ever). Calculating such a large number of possibilities would make this environment very slow in any system that does not have a lot of computational power, which is somewhat impractical for reinforcement learning algorithms, since millions of iterations have to be done for it to learn. What this definition represents is that the \(S\) state set formally contains all possible permutations. In practice, the learning algorithm decides how to deal with this information.