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

作　　者：Peng Lin Linling Kuang Xiang Chen Jian Yan Jianhua Lu Xiaojuan Wang 

机构地区：[1]Department of Electronic Engineering, Tsinghua University [2]China Electronic Equipment of System Engineering Institute [3]Tsinghua Space Center, Tsinghua University

出　　处：《Journal of Systems Engineering and Electronics》2014年第5期800-810,共11页系统工程与电子技术（英文版）

基　　金：supported by the National Natural Science Foundation of China(61132002;91338101;91338108);the National S&T Major Project(2011ZX03004-001-01);the Research Fund of Tsinghua University(2011Z05117);the Co-innovation Laboratory of Aerospace Broadband Network Technology

摘　　要：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.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.

关 键 词：nonhomogeneous parallel machines scheduling problem with time window （NPM-TW） adaptive subsequence adjustment （ASA） asymmetric path-relinking （APR） evolutionary asymmetric path-relinking （EvAPR）. 

分 类 号：TN927.2[电子电信—通信与信息系统]