Abstract local search is a general approach to solving hard combinatorial optimization problems over large sets of complex constraints. It differs from traditional local search in that the local moves are carried out in a space of abstract solutions, which are evaluated by using a solution builder that constructs concrete solutions. The concrete solutions are analyzed for flaws that drive local moves in the abstract space. In this paper we focus primarily on scheduling, and discuss in detail two instances of abstract local search. Both use priorities to represent abstract solutions, but differ in the nature of the priority information and in the algorithms used to modify the priorities. These methods have been implemented, and the simpler of the two has been used to solve real-world scheduling problems two orders of magnitude larger than those usually studied in the AI literature.