Our work focuses on permutation scheduling and permutation searching methods for the scheduling problem of satellites' randomized data transmission. A time window preempted permutation scheduling algorithm is put forward, which can ensure searching for optimal scheduling. A genetic stochastic search method is designed to carry out the search procedure for optimal permutations, using a stochastic neighborhood search algorithm with memory. Computational results show that our method can enhance the local search ability for genetic search, and makes an average improvement of about 2.72%.