Heuristic scheduling of the DRS communication system

The DRS (Data Relay Satellite) System is a European Space Agency communication system whose management is particularly complex. Nevertheless, the particular domain of application is an example of problems that are becoming quite common in the communication scenarios enabled by current technology. This paper describes a system named DRS-Sched, a knowledge-based scheduler aimed at solving an important aspect of the whole DRS scheduling problem. In particular, the problem model addressed is rather distinctive: the activities to be scheduled have a temporal flexibility over both their allocation and duration intervals, and temporal preference functions over the allocation interval. Problem-solving in DRS-Sched integrates domain-specific predictive scheduling heuristics, that build a solution using a least commitment approach, and reactive heuristics, that try to improve the current schedule by locally modifying previous choices when a particular class of conflicts arises. The paper describes the problems addressed, and the basic algorithm and heuristics used in the current release of the system. An experimental evaluation is also presented, showing how the system satisfies quality requirements connected to different relevant aspects of the project.