A metaheuristic is a refined solution method able to find a satisfying solution to a difficult problem in a reasonable amount of time. A local search metaheuristic works on a single solution and tries to improve it iteratively. Tabu search is one of the most famous local search, where at each iteration, a neighbor solution is generated from the current solution by performing a specific modification (called a move) on the latter. The goal of this chapter is to present tabu search approaches with enhanced exploration and exploitationmechanisms. For this purpose, the following ingredients are discussed: different neighborhood structures (i.e., different types of moves), guided restarts based on a distance function, and deconstruction/reconstruction techniques. The resulting all-terrain tabu search approaches are illustrated for various production problems: car sequencing, job scheduling, resource allocation, and inventory management.