<p>This paper considers the flexible job shop scheduling problem with nonlinear routes, a production environment with a wide range of relevant practical applications, especially in today’s on-demand printing industry. In order to approximate the problem of real-world applications, we consider the influence of a position-based learning effect on the processing time of the operations. The goal is to minimize makespan. In the present work, we are concerned with the development of effective and efficient methods for its solution. For this purpose, a local search method and four trajectory metaheuristics are considered. In the local search, we show that the classical strategy of reallocating only those operations that are part of the critical path can miss better-quality neighbors, as opposed to what happens in the case where there is no learning effect. Consequently, we introduce an alternative type of neighborhood reduction that eliminates only neighbors that are not better than the current solution. Additionally, we analyze the application of the classical strategy on top of the new reduction. Through experimentation, we verify that it significantly shrinks the size of the neighborhood, thereby increasing efficiency, with minimal loss of effectiveness. Extensive numerical experiments are performed. Statistical tests confirm that tabu search based on the reduced neighborhood, when applied to large-sized instances, outperforms the other three metaheuristics, namely iterated local search, greedy randomized adaptive search, and simulated annealing. Experiments on classical instances with linear routes only show that the introduced methods also stand out in relation to methods from the literature. All methods, instances, and solutions are freely available.</p>