Heuristic Scheduling of the DRS Communication System

M. Adinolfi and A. Cesta

In Engineering Applications of Artificial Intelligence, 8(2):147-156, 1995

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 enables by current technology. This paper describes a system named DRS-Sched, a knowledge-based scheduler aimed at solving a conspicuous 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 built 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.