In contrast to the existing airport gate assignment studies where flight have fixed schedules, we consider the more realistic situation where flight arrival and departure times can change. Our objectives are achieved through gate assignments where time slots alloted to aircraft at gates deviate from scheduled slots minimally. The solution approach uses insert and interval exchange moves together with a time shift algorithm. We then use these neighborhood moves in Tabu Search and Memetic Algorithms. Computational results are provided and verify that our heuristics work well in small cases and much better in large cases when compared with CPLEX solver.