# Job Shop Scheduling Problem Optimization by Means of Graph-Based Algorithm
## 4 Computational Result  
The algorithms were implemented in C# language on a personal computer with Intel Core P7550. For these experiments, a variation of operation-based representation was chosen, wherein all operations for a job are named by the same symbol in the sequence and interpreted according to the order of occurrence in the given sequence. Therefore, each job appears in the sequence exactly m times and each repetition refers to a unique operation, which is dependent on the context and does not indicate a predetermined operation of the job. This way, any permutation of elements in a sequence always yields a feasible schedule [33]. Although the values of newly acquired states may no longer depend on their predecessors, the position of symbols in the sequence of the newly acquired states does. As for this problem, we changed the symbols position in the sequence only if it was not changed in one of their predecessors. Experiments performed by means of the graph-based algorithm used three different methods of calculation of priority K(u). The results of experiments marked \(\alpha\) were obtained by using the basic calculation of priority K(u): K1(u) = rhs(u) and K2(u) = g(u). For \(\beta\), priority K(u) consisted of K1(u) = h(u) and K2(u) = rhs(u). Results for experiments marked \(\gamma\) used K1(u) = h(u) and K2(u) = \(-\)rhs(u), where rhs(u) represents the makespan and h(u) is the sum of completion times of all machines, calculated by the function StateEvaluation() as a byproduct. Experiments solved by the genetic algorithm were performed using roulette wheel selection, one-point crossover with the corresponding repair process and reciprocal exchange mutation. All tests used the same crossover rate (0.8) and population size (100). The mutation used was relatively low (1/n), where n represents the number of genomes in a chromosome. These parameters were chosen because they showed the best results for this problem type. Instances of problems for the job shop scheduling problem were commonly used as benchmarking instances [34] and were taken from the database of scheduling problems, OR-Library [35]. One hundred tests on each instance were performed for each algorithm. For a better variation of results, starting states of the graph algorithm were randomly generated. These experiments were compared by several factors: the time taken to find the best solution, makespan, the average value of makespans found and the average time taken to find these makespans. The results of these tests are summarized in Table 1, which also lists number of jobs, number of machines, instances [36], the best-known solution and the overall time of optimization for the given problem. We did not test the problem of limiting the proposed algorithm with respect to the number of jobs or machines. Limiting the algorithm by comparison through the most well-known makespans was sufficient enough for the given application area. An example of Gantt graphs for the instance la09 can be found in Figures 1 and 2. The purpose of the performed experiments was not necessarily to reach the best-known makespan, but rather to show what makespan could be found by our proposed algorithm in an allocated time; to how fast it performed and compare it to results reached under the same conditions by an unmodified GA. For this reason, we let each of the tested algorithms run for a certain amount of time--unless the best-known makespan was found. The results of comparative experiments showed that our proposed graph-based algorithm was able to find the same or better solutions compared to the genetic algorithm--and managed to find them faster. The graph-based algorithm also managed to find the same average makespan as the GA on eight benchmarking instances, and a better average makespan on eighteen instances. However, detailed examination of the experimental  
Figure 1: Gantt graph of makespan for la09 as found by graph-based algorithm. Figure 2: Gantt graph of makespan for la09 as found by genetic algorithm (GA).