An appropriate and efficient gate assignment is of great importance in airports since it plays a major role in the revenue obtained from the airport operations. In this study, we have focused mainly on maximum gate employment, or in other words minimize the total duration of un-gated flights. Here, we propose a method that combines the benefits of heuristic approaches with some stochastic approach instead of using a purely probabilistic approach to top-down solution of the problem. The heuristic approaches are usually used in order to provide a fast solution of the problem and later stochastic searches are used in order to ameliorate the previous results of the heuristic approach whenever possible. The proposed method generates an assignment order for the whole planes that corresponds to assignment priority. The ordering process is followed by the allocation step. Since, in practice, each airport has its own physical architecture, there have been arisen many constraints mainly concerning airplane types and parking lots in this step. Sequentially handling the plane ordering and allocation phases provides us great modularity in handling the constraints. The effectiveness of the proposed methodology has been tried to be illustrated firstly on fictively generated flight schedule data and secondly on the real world data obtained from a real world application developed for Istanbul Ataturk Airport. (C) 2011 Elsevier Ltd. All rights reserved.