Arrival sequencing and scheduling (ASS) is an important part of air traffic control. In the literature, various formulations of the ASS problems have been established by taking different scheduling requirements into account, and various methods have been developed to cope with these ASS problems. However, it is usually uneasy to generalize a method designed for one ASS formulation to another, while an approach that is able to handle different ASS problems is of great significance since air traffic controllers may need to switch among different scheduling requirements in practice. Motivated by this observation, an approach that is applicable to a number of different problem formulations of ASS is proposed in this paper. Specifically, the ASS problems that include different objective functions and constraints are firstly abstracted as a constrained permutation-based problem. After that, a Sequence Searching and Evaluation (SSE) approach is developed for the constrained permutation-based problem. The SSE solves different ASS problems by separating the sequence searching in one stage using an Estimation of Distribution Algorithm framework, and evaluating sequences in the second stage. Experiment results show that SSE is capable of obtaining competitive solutions for a variety of ASS problems.