Enabling Limited Resource-Bounded Disjunction in Scheduling

Abstract

This paper describes three approaches to enabling a severely computationally limited embedded scheduler to consider a small number of alternative activities based on resource availability. This paper considers the case where the scheduler is so computationally limited that it cannot backtrack search. The first two approaches precompile resource checks (called guards) that only enable selection of a preferred alternative activity if sufficient resources are estimated to be available to schedule the remaining activities. The third approach mimics backtracking by invoking the scheduler multiple times with the alternative activities. This paper presents an evaluation of these techniques on Mars mission scenarios (called sol types) from NASA’s M2020 Perseverance Rover where these techniques and analysis contributed to the design of the onboard scheduler.