(untitled) (Research, Society and Development, 2022)
This work studies the classic problem of job shop scheduling for makespan minimizing. Due to the combinatorial nature and computational complexity of this problem, the use of metaheuristic techniques combined with local search methods is quite widespread as it allows satisfactory results in a viable computational time. In general, local search methods are based on empirical permutations of the operations that make up the critical path of a solution, the so-called critical operations, which demand the calculation of the critical path for each of the solutions generated in the search process. In addition to increasing the computational cost of local search, this approach promotes permutations of operations that do not result in any improvement in the solution. This work investigates the distribution of critical operations on the machines and the correlation between this distribution and problem characteristics. The objective is to estimate machines that concentrate critical operations and identify characteristics that contribute to the definition of local search methods that do not depend on the calculation of the critical path for each solution. Computational experiments with usual instances from literature show that there is a concentration of critical operations in some machines and, in some cases, a positive correlation between this concentration and the average processing times of the operations, which can provide subsidies for creating more efficient local search methods.