Robust fixed interval satellite range scheduling

The Satellite Range Scheduling problem has been solved in previous work by the authors. However, real scenarios may involve contingencies on the satellites, the ground stations or the communication link, which in practice can be translated as communication requests eventually being dropped from the schedule with a certain probability. Compared to existing sub-optimal approaches which add back-up passes to a nominal schedule, robust scheduling finds the schedule with maximal expected performance. Robust schedules are not necessarily free of conflicts, conversely to optimal schedules, and thus finding the robust schedule poses increased complexity. The authors investigate the tractability bounds for the case where these requests have fixed start and end times, different priorities, and different failure probabilities, and provide a linear time algorithm for obtaining the robust schedule in scenarios with a single scheduling entity, laying the foundations for studying more complex cases.