# Job Shop Scheduling Problem Optimization by Means of Graph-Based Algorithm
## 5 Conclusions  
In this article, we proposed a graph-based algorithm that can be used for scheduling-related optimization problems. It was based on the Generalized Framework for Lifelong Planning A*. This algorithm was then tested against the classic genetic algorithm on forty benchmarking instances for the job shop scheduling problem.  
The experimental results on the JSSP showed that our proposed algorithm reached the best known makespan in thirteen instances while the genetic algorithm did so only in twelve. The graph-based algorithm found a better solution than the genetic algorithm on twenty-two tested benchmarking instances, found a solution with at least the same makespan as the GA on another twelve instances, and ended in optimality in eleven of these instances. The best-known makespan's average deviation from the best makespan acquired by the graph-based algorithm was 4.7% for \(\alpha\), 5.05% for \(\beta\) and 5.08% for \(\gamma\); the genetic algorithm had an average deviation of 5.19%, and on all but fourteen instances, the proposed algorithm managed to find the solution faster (on average, about 200-300% faster) than the genetic algorithm. Additionally, on all remaining instances, the graph-based algorithm managed to find a solution in the same time frame as the GA.  
The average makespan's average deviation from the best-known makespan was 9.63% for the genetic algorithm, while the graph-based algorithm's variations had an average deviation of 9.22% for \(\alpha\), 10.39% for \(\beta\) and 10.48% for \(\gamma\). Additionally, on all but six benchmarking instances, the proposed algorithm managed to find a solution faster (on average, about 100%-200% faster) than the genetic algorithm; on five of these instances, the graph-based algorithm managed to find a solution in the same time frame as the GA.  
Therefore, we can state that our proposed algorithm generally gives the same or better results--in comparison with the genetic algorithm's basic implementation--on the job shop scheduling problem. The practical consequences of the identified improvements (in makespan and calculation speed) are economic; these improvements will bring a price reduction.  
The manner of priority calculation has a nonnegligible impact on solutions. An appropriately chosen priority calculation can improve results, and an inappropriately chosen priority calculation can worsen them. Therefore, the proposed algorithm's performance can be further improved by proposing new methods of priority calculation.  
Conceptualization, J.S. and V.S.; Methodology, J.S.; Software Z.B. and R.K.; Validation, V.S.; Formal Analysis, [PERSON] and V.S.; Investigation, [PERSON]; Resources, V.S.; Data Curation, [PERSON]; Writing--Original Draft Preparation, [PERSON]; Writing--Review & Editing, V.S.; Visualization, [PERSON]; Supervision, V.S.; Project Administration, J.S.; Funding Acquisition, V.S. All authors have read and agreed to the published version of the manuscript.  
The research described in this paper was financed by a grant from the Ministry of the Interior of the Czech Republic, Program of Security Research, VI20192022135 \"Deep hardware detection of network traffic of next generation passive optical network in critical infrastructures\".  
Not applicable.  
Data Availability Statement: Data are contained within the article.  
This article is based upon grant of the Ministry of the Interior of the Czech Republic, Program of Security Research, VI20192022135, \"Deep hardware detection of network traffic of next generation passive optical network in critical infrastructures\".  
The authors declare no conflict of interest. The funders had no role in the design of the study; in the collection, analyses, or interpretation of data; in the writing of the manuscript, or in the decision to publish the results.  
The following abbreviations are used in this manuscript.  
GA Genetic Algorithm  
GLPA\({}^{\star}\) Generalized Lifelong Planning A\({}^{\star}\)  
JSSP Job Shop Scheduling Problem  
LPA\({}^{\star}\) Lifelong Planning A\({}^{\star}\)