Journal of Systems Engineering and Electronics ›› 2014, Vol. 25 ›› Issue (5): 800-810.doi: 10.1109/JSEE.2014.00093

• SYSTEMS ENGINEERING • Previous Articles     Next Articles

Adaptive subsequence adjustment with evolutionary asymmetric path-relinking for TDRSS scheduling

Peng Lin1,3, Linling Kuang2, Xiang Chen2,*, Jian Yan2, Jianhua Lu1,2, and Xiaojuan Wang3   

  1. 1. Department of Electronic Engineering, Tsinghua University, Beijing 100084, China;
    2. Tsinghua Space Center, Tsinghua University, Beijing 100084, China;
    3. China Electronic Equipment of System Engineering Institute, Beijing 100141, China
  • Online:2014-10-23 Published:2010-01-03


Due to the limited transmission resources for data relay in the tracking and data relay satellite system (TDRSS), there are many job requirements in busy days which will be discarded in the conventional job scheduling model. Therefore, the improvement of scheduling efficiency in the TDRSS can not only help to increase the resource utilities, but also to reduce the scheduling failure ratio. A model of nonhomogeneous parallel machines scheduling problems with time window (NPM-TW) is firstly built up for the TDRSS, considering the distinct features of the variable preparation time and the nonhomogeneous transmission rates for different types of antennas on each tracking and data relay satellite (TDRS). Then, an adaptive subsequence adjustment (ASA) framework with evolutionary asymmetric path-relinking (EvAPR) is proposed to solve this problem, in which an asymmetric progressive crossover operation is involved to overcome the local optima by the conventional job inserting methods. The numerical results show that, compared with the classical greedy randomized adaptive search procedure (GRASP) algorithm, the scheduling failure ratio of jobs can be reduced over 11% on average by the proposed ASA with EvAPR.