Network scheduling and fleet assignment are essential tasks for airline operation. In order to generate an optimal flight plan, the flight route and the flight schedule of each aircraft in the fleet requires deliberated consideration and planning. Compared with commercial airlines, which are in pursuit of maximal benefit during the operations, the humanitarian air services have different goals and therefore different strategies are designed. The humanitarian air service dedicates to fulfilling maximal passenger requests by reacting in a relatively short time frame, and the overall cost efficiency needs to be maximised. In this research, the United Nations Humanitarian Service’s (UNHAS) South Sudan mission is taken as the case to study and a metaheuristic method on top of the multi-integer linear programming (MILP) model is designed to solve the optimisation problem. The optimisation process consists of two stages: the tabu search process to assign the flight routes among the fleet, and a variation of a Fleet Size and Mix Vehicle Routing Problem (FSMVRP) model to finally determine the time schedule of each aircraft. The model is able to unlimitedly split the passenger requests and recaptures passenger spillage. It considers much fewer assumptions during the solving process and it provides large flexibility for the planner to manually modify the model based on their purpose. A dynamic balance of aircraft utilisation time regarding the Minimum Guaranteed Hours (MGH) within the fleet is also discussed. The result of this method is compared with the previous study of S.P. Niemansburg, which shows 1% to 11% of cost saved on a single day's operation regarding different levels of passenger spillage.