With the emergence of cloud computing, many applications are migrated onto clouds. Video-on-demand (VoD) can be implemented on the cloud platform with geo-distributed cloud servers to serve worldwide users. New videos are distributed to these geo-distributed cloud servers. This distribution should be properly scheduled based on the videos' sizes, videos' popularities and the available network bandwidth, so that the mean completion time is minimized. We formulate this problemas a preemptive scheduling problem, prove that it is NP-hard, and design a heuristic scheduling algorithm to solve it. This algorithm iteratively determines: 1) themost preferred file to be received by the most preferred destination server by pairwise analysis and PageRank, and 2) the most preferred source servers which can transmit this file to the most preferred destination server with appropriate data rates. The simulation results demonstrate that the proposed scheduling algorithm gives much smaller mean completion time than four scheduling algorithms.