A conflict-aware scheduling algorithm is being developed to help automate the allocation of NASA's Deep Space Network (DSN) antennas and equipment that are used to communicate with interplanetary scientific spacecraft. The current approach for scheduling DSN ground resources seeks to provide an equitable distribution of tracking services among the multiple scientific missions and is very labor intensive. Due to the large (and increasing) number of mission requests for DSN services, combined with technical and geometric constraints, the DSN is highly oversubscribed. To help automate the process, and reduce the DSN and spaceflight project labor effort required for initiating, maintaining, and negotiating schedules, a new scheduling algorithm is being developed.

The scheduling algorithm generates a "conflict-aware" schedule, where all requests are scheduled based on a dynamic priority scheme. The conflict-aware scheduling algorithm allocates requests for DSN tracking services while identifying and maintaining the conflicts to facilitate collaboration and negotiation between spaceflight missions. These contrast with traditional "conflict-free" scheduling algorithms that assign tracks that are not in conflict and mark the remainder as unscheduled. In the case where full schedule automation is desired (based on mission/event priorities, fairness, allocation rules, geometric constraints, and ground system capabilities/constraints), a conflict-free schedule can easily be created from the conflict-aware schedule by removing lower priority items that are in conflict.

Unlike most existing scheduling engines that require fixed length schedule items in the request, the conflict-aware schedule provides a dynamic scheduling engine to determine allocation length during the scheduling process. This is made necessary by the variety of mission-tracking request types faced by the DSN. In addition to fixed track requests, missions may also need continuous coverage or may need to segment a track related to multiple ground assets to support a given request for service. In these cases, the schedule allocation length (time) will depend on the availability of each resource.

The conflict-aware scheduling algorithm combines scheduling heuristics, optimization, a search algorithm, and computational intelligence. At the beginning of the procedure, all requests pass through a scoring system (chosen from a simple mathematical equation or fuzzy logic) that determines the priority of each request on the basis of measures of fairness of the allocation, importance of the request, the type of request, and the allocation length. Starting with the highest priority request, technical and geometric constraints are combined to determine the available "timeline/antenna groups" for scheduling. scoring system that considers items already in the schedule and the request characteristics then identifies the best timeline/ antenna group and start times for each request. This then continues for each successive priority request (priority is recomputed dynamically) until all requests are scheduled.

The conflict-aware algorithm is not limited to DSN application. It can also be applicable to solution of scheduling problems in areas such as manufacturing and traffic control.

This work was done by Yeou-Fang Wang and Chester Borden for NASA's Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.techbriefs.com/tsp under the Information Sciences category. NPO-41320



This Brief includes a Technical Support Package (TSP).
Document cover
Conflict-Aware Scheduling Algorithm

(reference NPO-41320) is currently available for download from the TSP library.

Don't have an account? Sign up here.