Anti-patterns are poor solutions to design problems that make software systems hard to understand and to extend. Components involved in anti-patterns are reported to be consistently related to high changes and faults rates. Developers are advised to perform refactoring to remove anti-patterns, and consequently improve software design quality and reliability. However, since the number of anti-patterns in a system can be very large, the process of manual refactoring can be overwhelming. To assist a software engineer who has to perform this task, we propose a novel approach RePOR (Refactoring approach based on Partial Order Reduction). We perform a case study with five open source systems to assess the performance of RePOR against two well-known metaheuristics (Genetic Algorithm, and Ant Colony Optimization), one conflict-aware refactoring approach and, a new approach based on sampling (Sway). Results show that RePOR can correct a median of 73% of anti-patterns (10% more than existing approaches) with a significant reduction in effort (measured by the number of refactorings applied) ranging from 69% to 85%, and a reduction of execution time ranging between 50% and 87%, in comparison to existing approaches.