A high-quality scheduling scheme can not only satisfy users′ demands but also provide a basis for scientific decision-making of tracking and data relay satellites system. Aiming at the increasingly diversified users′ demands, a novel application paradigm for tracking and data relay satellites system, in which users can submit multiple service time windows that can slide within a certain period, was adopted. To handle this application paradigm, by considering the flexibility of task scheduling and the conflicts among tasks, a mathematical programming model for relay satellite schedule was developed and a scheduling algorithm based on stochastic search strategy was designed. The proposed algorithm includes five operators, i.e., resource matching and neighborhood construction, actual service time windows generation, conflict evaluation, local search and conflict resolution, and solution update. The proposed algorithm was verified by comparing with the heuristic algorithm based on time freedom degree according to extensive simulation experiments.