Aircraft arrival sequencing and scheduling (ASS) at airports, which is an NP-hard problem, is a major issue in daily air traffic control (ATC) operations. Much effort has been made to tackle this problem using genetic algorithms (GAs) whose chromosomes are the permutation of the order of each aircraft in the arriving queues. This paper attempts to design an efficient GA whose chromosomes are constructed as the permutation of the categories of the arriving aircraft. The advantage of the resulting GA is the reduced encoding space so that the searching efficiency is promoted, which is very important for its real time application. The extensive comparative simulation study shows that this novel aircraft category based GA outperforms the aircraft order based GAs.