  The flexible job shop scheduling problem with sequencing flexibility and
position-based learning effect is considered in the present work. In [K. A. G.
Araujo, E. G. Birgin, and D. P. Ronconi, Technical Report MCDO02022024, 2024],
models, constructive heuristics, and benchmark instances for the same problem
were introduced. In the present work, we are concerned with the development of
effective and efficient methods for its resolution. For this purpose, a local
search method and four trajectory metaheuristics are considered. In the local
search, we show that the classical strategy of only reallocating 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 analyze an alternative type of neighborhood reduction that
eliminates only neighbors that are not better than the current solution. In
addition, we also suggest a neighborhood cut and experimentally verify that
this significantly reduces the neighborhood size, bringing efficiency, with
minimal loss in effectiveness. Extensive numerical experiments with the local
search and the metaheuristics are carried on. The experiments show that tabu
search, built on the reduced neighborhood, when applied to large-sized
instances, stands out in relation to other the other three metaheuristics,
namely, iterated local search, greedy randomized adaptive search procedure, and
simulating annealing. Experiments with classical instances without sequencing
flexibility show that the introduced methods also stand out in relation to
methods from the literature. All the methods introduced, as well as the
instances and solutions found, are freely available. As a whole, we build a
test suite that can be used in future work.
