The stochastic dynamic fleet scheduling problem with variable period and storage function are generally discussed. The major difficulty of the problem lies in the fact that the demands are typically uncertain, the transportation task with storage properties, the different length of time period in planning horizon, and the different vehicle loading capacity. In view of the description of the problem, the mathematical model is established. The decision vector and the state vector are introduced into the model to establish the dissolution model. The generating mechanism on the distribution of transportation task is devised with the queuing theory, and the method is designed for parameter fitting and model decomposing. Then the bi-level programming model is established. The alternating algorithm of the bi-level programming model is designed. Finally, the simulation experiment and the numerical analysis verify the feasibility and effectiveness of the proposed algorithm.