Generalized multiple time windows model based parallel machine scheduling for TDRSS

The scheduling efficiency of the tracking and data relay satellite system (TDRSS) is strictly limited by the scheduling degrees of freedom (DoF), including time DoF defined by jobs' flexible time windows and spatial DoF brought by multiple servable tracking and data relay satellites (TDRSs). In this paper, a generalized multiple time windows (GMTW) model is proposed to fully exploit the time and spatial DoF. Then, the improvements of service capability and job-completion probability based on the GMTW are theoretically proved. Further, an asymmetric path-relinking (APR) based heuristic job scheduling framework is presented to maximize the usage of DoF provided by the GMTW. Simulation results show that by using our proposal 11% improvement of average job-completion probability can be obtained. Meanwhile, the computing time of the time-to-target can be shorten to 1/9 of the GRASP.