Satellites underpin all economic, military, and scientific activity in space. Ground-based telescope observations provide much of the tracking information that enables collision avoidance and space traffic management, but recent growth in the size and dynamism of the satellite population divides the available observing capacity between multiple competing observation objectives. The task of selecting an optimal assignment of telescope observing capacity to observation objectives is NP-hard and involves domain-specific considerations such as sequence-dependent transition times, observability constraints, occlusion avoidance, and astrodynamic limitations. These features conspire to prevent direct and efficient application of traditional scheduling approaches over long time horizons.This work maps the task of scheduling ground-based sensor observations to an unrelated parallel machine scheduling problem with sequence-dependent transition times, restricted time windows, and a fixed time horizon. We contribute an integer programming model of the task, complete with inequality formulations of domain-specific constraints, and a decomposition algorithm that discovers reward-optimal schedules. Using the open-source CBC solver, the integer programming model can reliably be solved for problem instances with up to 6 sensors and 40 targets for a 4 minute time horizon within an equal runtime limit. To address more challenging problem instances, we propose a decomposition algorithm that supports early termination and returns suboptimal schedules along with an associated optimality gap for instances with up to 6 sensors and 200 targets over a 15 minute time horizon.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    An Integer Programming Approach to Observation Scheduling for Space Domain Awareness


    Contributors:


    Publication date :

    2024-03-02


    Size :

    1370374 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English




    Scheduling Personal Finances via Integer Programming

    Braun, O. / Sotskov, Y.N. | British Library Online Contents | 2013



    Towards Automated Scheduling of NASA's Deep Space Network: A Mixed Integer Linear Programming Approach

    Sabol, Jonathan A. / Alimo, Ryan / Hoffmann, Mark et al. | AIAA | 2021