# Job Shop Scheduling Problem Optimization by Means of Graph-Based Algorithm
## 1 Introduction  
Nowadays, graph-based algorithms are a popular tool for solving various optimization problems. However, most optimization methods are only used for solving one type of task. On the other hand, methods for optimization of several problems, in most cases, lack sufficient computing power. There are a wide variety of different algorithms available for the optimization of scheduling problems. One of the most well-known is the genetic algorithm (GA). In this article, we introduce the draft of a graph-based algorithm for scheduling optimization problems. The proposed algorithm aims to have the flexibility and scope of application of advanced optimization methods--such as genetic algorithms--and to retain most of the positive characteristics of advanced graph algorithms. We researched the literature carefully and paid great attention--though the references contained mainly general literature reviews. Our proposed algorithm appears unique; we could not find any other reference with comparable results for the given problem. There are many different methods, algorithms and modifications, some of which already contain some of the required properties. Their structure allows for further adaptation. Additionally, some algorithms are directly intended for further development into new algorithms. From various graph-based algorithms, the Forward Version of GeneralizedLifelong Planning A* (GLPA*) [1] --used for path planning in mobile robot navigation--was chosen. We then attempted to modify it for use in other types of optimization and tested it on various travelling salesman problems against the genetic algorithm (GA) [2,3]. The solution was based on a new algorithm, a hybrid between graph-based and genetic algorithms. An algorithm was designed and implemented that combines the advantages of graph-based and genetic algorithms. We chose the genetic algorithm for comparison because it was suited for this purpose and remains one of the most well-known algorithms for optimization in the planning area. The key parameters for the solution in the given area were makespan and calculation speed. Optimization according to other parameters would be possible; however, given the importance of the above two key parameters, it would not make sense. The task of developing new optimization procedures resulted from a general effort to optimize problem solving. Our proposed graph-based algorithm has been successfully tested on other problems (see references) and was more successful that the commonly-used genetic algorithm in solving the Job Scheduling. The motivation for the development of new algorithms was to obtain faster, more accurate results in the given area. In this paper, the term \"performance\" refers to the success of our algorithm according to the following parameters: makespan and calculation speed. Using those parameters, our new graph-based algorithm was compared with a genetic algorithm (for makespan differences, see conclusion; for calculation speed, see Table 1). These parameters were chosen because they are key, and because, according to references, measuring other parameters would have made little sense. For the industry, improvements in makespan and calculation speed are economically-driven (e.g., seeking a reduction in price). The graph-based algorithm had a better average deviation from best-known makespans than the GA. The average deviations of the best-known makespans from the best makespans were as follows: 5.19% for GA and 4.7% for \(\alpha\); 5.05% for \(\beta\) and 5.08% for \(\gamma\), for the developed (graph-based) algorithm. The average calculation speed of the proposed graph algorithm is two to three times higher than the GA. When researching the new graph-based algorithm, we proceeded through five steps: (1) analysis of graph-based algorithms, (2) analysis of genetic algorithms, (3) development and design of new algorithm, (4) verification of algorithm on job shop scheduling problem (JSSP), and (5) comparison with the genetic algorithm used in the given area.