In the past, research regarding the airline fleet scheduling problem in Taiwan consistently focused on a single fleet, a situation quite different from current operating conditions. Among this research, few have taken into account the necessary maintenance schedules for airline fleets. In addition, most of the decision objectives focus on profit maximization or operating cost minimization, which are considered only from the airline company’s viewpoint. This research proposes a multi-objective mathematical model, in which four decision objectives are considered at the same time. These objectives cover concerns from both owners and customers. The proposed model also allows the flexibility of adding maintenance constraint. Actual operational data collected from a Taiwan-based airline company is used to verify the model and the results are reported.