Fast and accurate forecasting of schedulable capacity of electric vehicles (EVs) plays an important role in enabling the integration of EVs into future smart grids as distributed energy storage systems. Traditional methods are insufficient to deal with large-scale actual schedulable capacity data. This paper proposes forecasting models for schedulable capacity of EVs through the parallel gradient boosting decision tree algorithm and big data analysis for multi-time scales. The time scale of these data analysis comprises the real time of one minute, ultra-short-term of one hour and one-day-ahead scale of 24 hours. The predicted results for different time scales can be used for various ancillary services. The proposed algorithm is validated using operation data of 521 EVs in the field. The results show that compared with other machine learning methods such as the parallel random forest algorithm and parallel k-nearest neighbor algorithm, the proposed algorithm requires less training time with better forecasting accuracy and analytical processing ability in big data environment.