# Intelligent Scheduling with Reinforcement Learning
## 5 Computational Study
### Quality of Solutions Analysis  
Based on the presented literature review (Section 2), it can be argued that the most used metric to measure the quality of a plan is its makespan, which represents the time of completion of the last operation of a plan. Thus, this section analyzes and compares the makespan of the solutions obtained by the proposed system with those obtained with _SPT_ and _LPT_, for instances TAI1-TAI80.  
The known optimal values [49] for each problem are included in this analysis (or best known upper bound when there is no optimal value. However, it is important to note that these makespan values for each instance have, in the great majority, different authors. As a result that there is not a common unsurpassed technique for JSPs, customized approaches have been developed for the needs of each instance. These strategies achieve the goal of obtaining the best-known result for a given instance but, unfortunately, cannot be replicated on other instances. For example, [PERSON] et al. [65] present the optimal solution value for the instances TAI27 and TAI28 (among others), but the optimal solution value for the TAI29 problem was proposed by [PERSON] et al. [66].  
Figure 6 shows a graph containing the optimal (or best known upper bound) makespan (_OPT_) and the makespan obtained by each method. The _OPT_ line (in blue) represents the known optimal value [49] (or best known upper bound) and, as such, no other method can go below it. By analyzing Figure 6, it can be verified that the _SPT_ method is the one that needs more time to complete all problems, while _CUN_ obtained the better solution values.  
Figure 6: Makespan for _LPT_, _SPT_, _CUN_ and the optimal value for each instance.  
Frequently, the normalized makespan is used as a measure (instead using the raw makespan value) to compare the quality of the solutions [2]. The formula is described in Equation (3), where _met_ represents a given method and _opt_ represents the optimum value. Thus, the normalized makespan is the ratio between the difference of the makespan of a given method with the optimal makespan and the optimal makespan.  
\[norm_{x}=\frac{met_{x}-opt_{x}}{opt_{x}} \tag{3}\]  
Figure 7 contains the boxplots of the normalized makespan of the three methods. The same conclusion can be reached in both measures. In fact, we can observe that for _CUN_ the median of normalized makespan is very near to 0.25, for _LPT_ the median is close to 0.5 and _SPT_ has a median near of 0.6. We can conclude about evidences of the advantage in the _CUN_ system performance when compared with _LPT_ and _SPT_.  
In order to validate the results obtained, a statistical inference analysis was performed. Similarly to the efficiency analysis (Section 5.1) we conducted a _Friedman_ test [63] to detect if these differences are statistic significant.  
A \(p\)-value \(<2.2\times 10^{-16}\) was obtained from the _Friedman_ test, which allows us to conclude that there are significant differences, in the medians, of the normalized makespan of the three methods. In order to decide which heuristics are significantly different from each other we perform, like in Section 5.1, a _Nemenyi_ test [64] and we got the pairwise \(p\)-values shown in Table 2.  
We can conclude that the differences between all pairs are significant and that the _CUN_ results (i.e., the agent proposed in this work) represent significantly better solutions than the _LPT_ and _SPT_ heuristics.