  The way heuristic optimizers are designed has evolved over the decades, as
computing power has increased. Initially, trajectory metaheuristics used to
shape the state of the art in many problems, whereas today, population-based
mechanisms tend to be more effective.Such has been the case for the Linear
Ordering Problem (LOP), a field in which strategies such as Iterated Local
Search and Variable Neighborhood Search led the way during the 1990s, but which
have now been surpassed by evolutionary and memetic schemes. This paper focuses
on understanding how the design of LOP optimizers will change in the future, as
computing power continues to increase, yielding two main contributions. On the
one hand, a metaheuristic was designed that is capable of effectively
exploiting a large amount of computational resources, specifically, computing
power equivalent to what a recent core can output during runs lasting over four
months. Our analysis of this aspect relied on parallelization, and allowed us
to conclude that as the power of the computational resources increases, it will
be necessary to boost the capacities of the intensification methods applied in
the memetic algorithms to keep the population from stagnating. And on the
other, the best-known results for today's most challenging set of instances
(xLOLIB2) were significantly outperformed. Instances with sizes ranging from
300 to 1000 were analyzed, and new bounds were established that provide a frame
of reference for future research.
