In this paper, the authors discuss how to solve a set of typical constraint satisfaction problems, Job-Shop scheduling problems. Based upon the depth-first search, formal strategies of enforcing consistency, selecting operation and selecting start time are given, heuristic strategies of enforcing consistency and incomplete back jumping are introduced to further enhance the efficiency in solving Job-Shop scheduling problems.