# Manufacturing Scheduling Using Colored Petri Nets and Reinforcement Learning
## 5 Simulation and State Space Results  
### Validation of the Scheduling Method  
Verification of the proposed scheduling method has been done by comparing simulation results for makespan obtained in this study with published literature results. Validation of the method has been supported by the state space results of modeled system properties. The method was tested by applying it to known job shop benchmark examples, i.e., ft6 (six resources and six jobs) [65], as well as the example introduced by [PERSON] and [PERSON] [26] with lot sizes (1,1,1,1), (5,5,2,2), and (10,10,6,6). The scheduling goal was to obtain the minimal makespan. A total of 10 states were included. Two dummy states represented the initial state and the terminal state. The terminal state was reached when the obtained makespan was not larger than 5% of the known optimal makespan. The scheduling agent could choose between two possible actions in each state. The first policy action corresponded to a restricted CTPN scheduling model of the benchmark example under investigation, such as the one of the SPT rule, whereas the second policy action was an unrestricted CTPN scheduling model. Each simulation experiment was run for 1000 replications. Replication results were averaged for each simulation experiment. Simulation results are shown in Table 4. When the Q-learning was implemented with \(\varepsilon=0\) the agent always favored the second policy action, i.e., the unrestricted CTPN scheduling model, except for the first scheduling cycle where the initial condition was guiding it to choose the first policy action. When the agent followed an \(\varepsilon\)-greedy policy, i.e., a policy with \(\varepsilon=0.2\), it was choosing both policy actions, e.g., in one simulation run of the ft6 benchmark example with \(\varepsilon=0.2\), the best obtained solution was 57, whereas the agent chose the first policy action 97 times and the second policy action 903 times. The first policy action, i.e., the implementation of the SPT rule led to a makespan of 93, whereas the second policy action led to a makespan of 57. The Q-learning algorithm always converged to the optimal solution for the examples introduced in [24]. The best solution obtained for the ft6 benchmark example was 57. State space was extracted for the CTPN scheduling system model of the job shop example introduced in [26] with lot size (1,1,1,1). One scheduling cycle was taken in the system model. State space analysis results for home, liveness, deadlock exploration, and fairness properties, as well as  
Figure 6: The CTPN model of the Q-Learning substitution transition. occurrence graph (OG) (reachability graph) and strongly connected graph (SCC) statistics are shown in Figure 6. Full state space has been calculated. 18 dead markings were identified. Using the OG graph marking information, it was found that all dead markings correspond to the final system state reached when the scheduling was completed. They differ in the combinations of individual job completion times and makespan. Dead transition instances (TIs) are shown in Figure 7. However they correspond to the transitions of the second policy action submodel, i.e., Policy Action 2 submodel in Figure 4. Since the implemented state space system model allowed one scheduling cycle and the initial condition guided the agent to choose the first policy action, the Policy Action 2 subnet was not enabled. When more than one scheduling cycle was included in the model, there were no dead Tis; however the number of dead markings as well as the number of nodes increased. The absence of dead TIs indicates that there are no deadlocks in the system, since a deadlock would appear if a transition could not be enabled, blocking the occurrence of a possible system state. There are no live TIs as well, since there are dead markings. Additionally, there are no infinite occurrence sequences, thus the system always terminates, a result that is further supported by the identical number of nodes and arcs for the state space and SCC graphs.