The aircraft arrival scheduling (AAS) problem is an important issue in airport management that requires well-designed scheduling approaches to help improve the operating efficiency of airports. However, most of the existing approaches are based on a single runway while the multi-runway situation is more common and more complex in reality. In order to solve the multi-runway AAS (MRAAS) problem, this paper proposes a receding horizon control (RHC) based two-level ant colony system (ACS) approach. The RHC divides the problem with receding time windows. Therefore, the number of aircraft considered in each RHC stage is reduced, so that the ACS algorithm can endure less computational burden and search for good scheduling sufficiently. Moreover, in each RHC stage to schedule the aircraft, a two-level scheduling strategy is proposed to assist the ACS to deal with the multi-runway difficulty. During the first level scheduling, the ACS algorithm schedules aircraft based on a single runway. Then in the second level scheduling, we assign the aircraft to real multi-runways based on both the obtained sequence of the first level scheduling and the real occupancy condition of each runway. We have conducted experiments based on case study and compared the results with first come first serve (FCFS) approach, showing the feasibility as well as the higher performance of the proposed RHC-ACS-MRAAS approach.