# Manufacturing Scheduling Using Colored Petri Nets and Reinforcement Learning
## 3 Methodology  
The method is based on hierarchical CTPNs. Scheduling is done by a single agent. The agent interacts with its environment in order to do the scheduling. At each step, \(t\), the agent observes the state \(s_{t}\), \(s\in S\), of the environment, follows a policy \(\pi_{t}\), and selects an action \(a_{t}\in A(s)\). As a result of its action, it receives an immediate reward \(r_{t}\in R\), and the state of the environment changes to \(s_{t+1}\in S\)[6]. The policy, \(\pi_{t}\), is a mapping from states to action probabilities: \(\pi_{t}(s,a)\) = probability that \(a_{t}\) = \(a\) when \(s_{t}\) = \(s\). The agent's goal is to obtain an optimal policy, \(\pi^{*}\). The value of a state, \(V^{\pi}(s)\), under a policy \(\pi\), is the expected reward the agent receives, when it starts from that state, \(s\). The action-value (Q-value), Q(s,a), is the expected reward the agent receives under policy \(\pi\), when it chooses an action a at state \(s\), The agent follows \(\pi\) thereafter. The optimal action-values Q*(s,a) are obtained when the agent follows an optimal policy, \(\pi^{*}\). There is a unique solution for the value of a state under an optimal policy, \(V^{*}(s)\), \(V^{*}(s)\) = \(max_{a}Q^{*}(s,a)\). If \(a^{*}\) is an action that maximizes Q*(s,a), then \(\pi^{*}(s)\equiv a^{*}\) = \(arg(max_{a}Q^{*}(s,a))\)[7]. The top CTPN model page includes the submodels of the scheduling agent and the simulation environment. The simulation environment submodel consists of the set of jobs, job data and job characteristics and set of machines. The scheduling agent submodel consists of a heuristics rule base submodel and an intelligent part submodel. The heuristics rule base submodel may be used depending on the scheduling problem. The intelligent part submodel consists of a perception module, a Q-learning module and an action module. The perception module perceives the current state of the environment. The information about the current state is received by the Q-learning module. The Q-learning submodel selects a policy action, \(a\), for the current state, \(s\), from a set of available policy actions. As a result of the agent's action, the environment arrives at a new state, \(s^{\prime}\). The agent perceives the new state and receives an immediate reward, \(r\), by the perception submodel. In each scheduling cycle the Q-learning is implemented by the agent to guide it to the optimal scheduling decision. The implementation is based on the following steps [7]:  
1. The agent perceives the current state, \(s\) and selects an action \(a\). Based on its action it receives an immediate reward, \(r\) and arrives at the next state, \(s^{\prime}\). 2. Q(s,\(a\)) values are updated as \[Q(s,a):=Q(s,a)+\alpha(r+\gamma\max_{b}Q(s^{\prime},b)-Q(s,a)).\] (1)
3. Go to (1) until \(s\) is a terminal state,  
where \(\alpha\) is the learning rate and \(\gamma\), \(0\leq\gamma<1\), is the discount factor. Steps (1)-(3) are steps of one episode which ends when a terminal state is reached. A number of episodes take place. The Q(s,a) values represent the long term reward. The learning rate determines the influence of the old Q(s,a) values on the new ones. The discount factor determines whether the agent takes into account immediate rewards more strongly than rewards received previously. The agent has the option of following an \(\varepsilon\)-greedy method in the training period, i.e., to randomly select an action for a percentage of time defined by \(\varepsilon\). The agent tries to maximize its long-term reward, i.e., the Q(s,a) values for each state action pair, thus the immediate reward guides the agent as to what action to take next. The minimal makespan is the scheduling objective considered as the optimality criterion in this paper. Makespan, i.e., \(\mathrm{C_{max}}\triangleq\max_{j\in\mathrm{J}}\{\mathrm{C_{j}}\}\), where \(\mathrm{J}=\{1,\ldots,n\}\) is the set of n jobs, and \(\mathrm{C_{j}}\) is the completion time of job j, is a widely used manufacturing scheduling objective.