Task scheduling plays an important role for improving the efficiency of cloud. However, due to the features and complex scenarios of the cloud, traditional scheduling approaches face with three challenges: robust model, local optima and slow convergence. Therefore, in this paper, we firstly established a robust cloud task scheduling model, which takes heterogeneity, deadline, overheads of transmission and the cost into account. Then, we proposed a particle swarm optimization scheduling algorithm with the self-learning strategy and the neighbor heuristic mechanism. The self-learning strategy is adopted to improve the diversity of population and the neighbor heuristic mechanism can accelerate the convergence speed. In addition, a greedy policy was designed and applied to quickly improve the quality of the initial solutions. In this way, the proposed algorithm has a fast speed of convergence and can avoid trapping into the local optimum. Lastly, we conducted simulations on CloudSim platform. Both on small-scale and large-scale scheduling problems, the proposed scheduling approach outperforms other well-known representative scheduling algorithms in terms of makespan, users’ expense and waiting time.