Optimizing naval aircraft deck sortie scheduling is important for improving the sortie efficiency of naval aircraft groups. It is also an important link in realizing the automated scheduling of aircraft carriers. Firstly, a single-aircraft surface transit path library was constructed. This paper used the improved A* algorithm and the optimal control deck path planning algorithm to construct the transit path library between the deck parking position and take-off position, or between warmable and non-warmable parking positions. Secondly, a mathematical optimization model was constructed for the sortie scheduling of a mixed fleet of fixed-wing carrier aircraft and carrier helicopters. The model took the maximum sortie time of the fleet and taxiing time of the fleet of fixed-wing aircraft as the optimization objectives, and considered the process flow, spatial, and resource constraints. Thirdly, a discretized improved whale optimization algorithm (IWOA) was designed to solve the problem. To improve the optimization-seeking capability of the algorithm, we discretized the algorithm, optimized its coding method, and introduced pre-constraints, learning factors, parameter improvements, and population restart. Finally, we set up various cases and proposed a new strategy for simulation experiments: these simulations verified the validity of the model, the excellent optimization performance of the IWOA, and the superiority of the sortie strategy. The research in this study will help to implement automated aircraft carrier scheduling.