To solve aircraft arrival sequencing and scheduling problems, and imp rove the typical predatory search algorithm(PSA), an innovative PSA is developed . The new PSA uses variable constraints of local search and global search to avo id falling into local optimal solutions and the degeneration of solutions. To te st t he performance of new PSA, a case study with ten arriving flights and two runway s is performed. Test results show that the new PSA performs much better than typ ical PSA and genetic algorithm(GA) in the aspects of the rate of gaining optimal solutions and the computational time.