Generalized multiple time windows model based parallel machine scheduling for TDRSS  

作　　者：LIN Peng KUANG Lin-ling CHEN Xiang YAN Jian LU Jian-hua WANG Xiao-juan 林鹏;匡麟玲;陈翔;晏坚;陆建华;王小娟(Department of Electronic Engineering, Tsinghua University, Beijing 100084, China Tsinghua Space Center, Tsinghua University, Beijing 100084, China China Electronic Equipment of System Engineering Institute, Beijing 100141, China)

机构地区：[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

出　　处：《Journal of Beijing Institute of Technology》2016年第3期382-391,共10页北京理工大学学报（英文版）

基　　金：Supported by the National Natural Science Foundation of China(91338101,91338108,61132002,6132106);Research Fund of Tsinghua University(2011Z05117);Co-innovation Laboratory of Aerospace Broadband Network Technology

摘　　要：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,ageneralized 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 jobcompletion probability can be obtained.Meanwhile,the computing time of the time-to-target can be shorten to 1/9 of the GRASP.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,ageneralized 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 jobcompletion probability can be obtained.Meanwhile,the computing time of the time-to-target can be shorten to 1/9 of the GRASP.

关 键 词：parallel machine scheduling problem with generalized multiple time windows （PMGMTW） positive/negative adaptive subsequence adjustment （p/n-ASA） evolutionary asymmetric key-path-relinking （EvAKPR） 

分 类 号：V556.8[航空宇航科学与技术—人机与环境工程]