# Manufacturing Scheduling Using Colored Petri Nets and Reinforcement Learning
## 2 Literature Review
### Reinforcement Learning  
Intelligent agents are composed of a perception mechanism, a cognition system, and an action module. They receive messages from the environment using the perception mechanism, evaluate the messages using the cognition module, and produce actions by the action module [5, 51, 52]. Learning and evolving are key mechanisms in intelligent agents. RL is a widely used method for this purpose. RL is the procedure by which an agent learns from interaction with its environment to achieve a goal, in general to obtain its own optimal control policy. A complete specification of an environment defines a task. At each time step, the agent receives some representation of the environment's state, from the set of possible states, and on that basis selects an action from the set of available actions. One time step later, in part as a consequence of its action, the agent receives a numerical reward, and finds itself in a new state. At each time step, the agent implements a mapping, called a policy, from states to probabilities of selecting each possible action. RL methods specify how the agent changes its policy as a result of its experience. The agent's goal is to maximize the total reward it receives over the long run [6]. RL problems can be solved using dynamic programming (DP) algorithms, although the time required for large problems may make their solution infeasible. Q-learning is a model-free RL algorithm that approximates DP [7]. The Q-learning algorithm estimates the value functions, Q(s,a), of state-action pairs. Q(s,a) is a discounted sum of future rewards. Once these values have been learned, the optimal policy, \(\pi^{\bullet}\)(s), from any state is the one with the highest Q-value. This algorithm converges to the optimal value functions, Q*(s,a), representing the optimal policy, for RL tasks that satisfy the Markov property, called Markov Decision Processes (MDPs). For Markovian environments the current state summarizes the history of past states, thus all the information an agent needs to take an action and make a transition from its current state to a next state is stored in its current state. If an agent learns the Q-values, then it can make optimal decisions at each state. RL has been applied to manufacturing scheduling [51, 53, 54, 55, 56, 57, 58, 59]. A single machine agent used Q-learning to determine if it could learn commonly accepted dispatching rules for three example cases in which the best dispatching rules had been previously defined in [PERSON] and Usher [53]. Agents were trained to an RL algorithm, called Q-III, used for dynamic job shop scheduling to select the most appropriate priority rule according to the shop conditions in real time in Aydin and Oztemel [51]. The temporal difference algorithm TD(\(\lambda\)), an RL algorithm, has been applied to job shop scheduling involving the scheduling of the various tasks that had to be performed to install and test the payloads placed in the cargo bay of the NASA space shuttle for each mission [54]. The objective was to schedule a set of tasks without violating any resource constraints while minimizing the total duration. An RL algorithm, called SMART, was developed and applied to the case of optimal preventative maintenance in a production inventory system [55, 56]. SMART was applied to the problem of optimizing a three- and four-machine transfer line, respectively, producing a single product type [57, 58]. The system goal was to maximize the throughput of the transfer line while minimizing work-in-process and failures. Dynamic control policies were obtained for a stochastic lot production scheduling problem using an RL-based approach implemented by a multi-agent control architecture [59]. A Neural Network-based approach was used to approximate the reinforcement value function. In [PERSON] and Riedmiller [60] a production scheduling method was presented where the scheduling problems were modeled as multi-agent RL problems. Resource agents made independent job dispatching decisions and improved their decisions by employing RL.