In order to obtain an optimal runway-scheduling scheme to improve the efficiency of runway operation，a constrained multi-objective model for arrivals and departures on multi-runways is constructed，and an improved genetic simulated annealing algorithm is proposed by analyzing the characteristics of both the genetic algorithm and the simulated annealing one． In the proposed algorithm，the objective functions for runway scheduling are processed by means of the Pareto dominance and the ideal point method，and the constraint conditions are handled by using the penalty objective functions and the dominated feasible solution． Furthermore，the mechanisms of updating new particles and selecting the best scheme are determined． For the purpose of improving the performance of the optimal solution，the convergence speed of the proposed algorithm is controlled by changing the temperature adaptively． Finally，the effectiveness of the proposed algorithm is verified by the actual runway scheduling of a domestic huge airport． The results show that the proposed algorithm based on the Pareto dominance can obtain a set of better feasible solutions of runway scheduling and is of a better timeliness．