## 4 Rdis
Moreover, the preliminary evaluation renders many of these combinations unnecessary. Because of using two forward and backward matrixes, when the positions of two jobs are not far from one another in the permutation, the evaluation of their swap can be performed very fast. The solutions provided by the RJP undergo both small and large neighborhood searches. As is seen in the pseudocode presented in Figure 3, the large neighborhood search is called at line 11. The pseudocode presented in Figure 5 describes how this large neighborhood search operates. As is seen in this pseudocode, the main loop starts at line 3 and is aimed at improving the given solution, shown with permutation \(\pi\), through modifying different parts of this permutation. The substrings selected for modification are called chunk and all have the same size of _chunkSize_. For the purpose of modification, a subproblem of the given problem is solved to optimality through evaluating all possible ordering of jobs in a given chunk, keeping other jobs fixed in their current positions. In particular, it is line 9 of the pseudocode that calculates the makespan values of all _chunkSize_! permutations. For instance, if the value of _chunkSize_ is 6, line 9 has to evaluate 6! = 720, different permutations to find the optimal one. As is shown in line 5, the number of chunks to be optimized for a given solution is controlled through a parameter named _sweepRatio_, which is in the range between 0 and 1. For instance, setting _sweepRatio_ to 0.5 and _chunkSize_ to 6 causes the first chunk, which starts from position 1 and ends in position 6, to be optimized and then the starting position for the next chunk to be set to \((1+6*0.5)=4\). In other words, around 50% of jobs for the optimized chunk are fixed and the remaining jobs appear in the first half of the next chunk to be optimized. After re-arranging the chunk starting at position 4, through the employed optimization process, and ending at position 9, positions 4, 5, and 6 are fixed and the next chunk starting from position 7 and ending in position 12 is selected for being re-arranged. Fixing half of the re-arranged jobs in a chunk and carrying the other half with the next chunk continues until a chunk is selected whose ending point is the last position in the  
Figure 5: The c-type pseudocode of largeNeighbourhoodSearch. permutation, signaling the end of a cycle. As indicated in lines 3 and 15 of the pseudocode, a new cycle can again resume from position 1 if the current cycle has been able to improve the solution. The quality of the obtained solutions depends on the values of _chunkSize_ and _sweepRatio_. Whereas increasing the value of _sweepRatio_ leads to increasing the exploration power and reduces computation time, its decreasing can produce better solutions at the expense of higher computation time. Since optimizing a chunk is involved with evaluating _chunkSize!_ permutations, the execution time is highly dependent on the chunk size. This implies that a combination of selecting a proper value for this parameter and a mechanism for the recognition of unfruitful chunks can greatly improve the efficiency of the stochastic algorithm. Values between 6 and 9 for _chunkSize_ can lead to improving solution quality, without increasing execution time significantly. With respect to having a necessary mechanism for the recognition of unfruitful chunks, line 7 detects such chunks based on the critical path properties of the current solution. This is done based on the fact that if all of the critical operations in a chunk belong to the same machine, optimizing such a chunk cannot reduce the makespan, and therefore the chunk can be skipped. In other words, regardless of the order of jobs in such an unfruitful chunk, the previous critical path persists in the new solution and this makes any decrease in the makespan impossible.