In order to solve the scheduling problem of service vehicles for aircraft turnaround, a partheno-genetic algorithm with hierarchical encoding structure was proposed targeting uncertain task duration.The service activity number and vehicle number were employed to encode the control and parametric genes chromosome, respectively, which characterized the temporal and vehicle scheduling rules in turnaround service, ensuring the applicability of algorithm. The schedulable capacity concept for service vehicle was introduced in chromosome decoding process to optimize search ability. The roulette strategy according to fitness function values was adopted to control the evaluation direction of generation. An instance indicated the proposed algorithm could promote the efficiency of service vehicles while decrease the cost.