Route-reduction-based dynamic programming for large-scale satellite range scheduling problem. Issue 11 (2nd November 2019)

• Record Type: Journal Article
• Authors: Liu, Zhenbao; Feng, Zuren; Ren, Zhigang
• Is Part Of: Engineering optimization. Volume 51:Issue 11(2019)
• Page Start: 1944
• Page End: 1964
• Publication Date: 2019-11-02
• Subjects: Range scheduling -- dynamic programming -- critical resource -- route reduction -- combinatorial optimization; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2018.1558445
• Languages: English
• ISSNs: 0305-215X

Abstract

ABSTRACT: Satellites offer many services through communication with stations, such as tracking, navigation, telecommand uplink, earth observation, etc. How to coordinate these services is referred to as the satellite range scheduling problem (SRSP). In the research, it is found that only the resources (referring to time slots of stations) requested by more than one satellite simultaneously influence scheduling results. These resources are called critical resources and selected as scheduling elements, which makes some jobs optimally served in advance and the problem be decomposable into a multi-stage decision process, so dynamic programming is suitable to be employed. For large-scale SRSPs, a route-reduction-based dynamic programming (RR-DP) is presented, wherein a multi-level route reduction strategy is adopted to alleviate 'the curse of dimensionality'. Experimental results reveal that RR-DP can find optimal solutions for small-to-medium sized problems and outperforms state-of-the-art methods for large-scale problems.