The multi-objective flight instructor scheduling problem is an optimization problem that schedules instructors to teach a set of pilot training events. The objectives of the problem are to minimize labor cost, maximize workload consistency and maximize flight instructor satisfaction of their assignments. The problem is further complicated by various hard and soft constraints. We study a multi-objective cost function and convert it to a scalar-weighted objective function using a priori weighting scheme. We then design an efficient dynamic neighborhood based tabu search meta-heuristic to solve the problem. The algorithm exploits the special properties of different types of neighborhood moves. We also address issues of solution domination, tabu short-term memory, dynamic tabu tenure and aspiration rule. The application of the algorithm in a major US airline carrier is reported and the results show that our algorithm achieves significant benefits in practice.