Methods and system are provided for scheduling and negotiating air traffic within an airspace surrounding an airport and scheduled to land at the airport. An air traffic control (ATC) system is used to monitor the altitudes, speeds and lateral routes of aircraft. The ATC system generates a scheduled time-of-arrival (STA) at one or more meter fix points associated with the airport, the STA is stored, and data is received or inferred with the ATC system for at least a first of the aircraft, including a minimum fuel-cost speed and predicted trajectory parameters of the first aircraft based on current values of its existing trajectory parameters. Auxiliary data, including earliest and latest estimated time-of-arrival (ETAmin) and (ETAmax) at the meter fix point, STA being within/ outside ETAmin, ETAmax are generated, instructions are transmitted to the first aircraft, and the STA is updated for each aircraft stored in a queue.