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).
Conflict-Aware Scheduling Algorithm
(reference NPO-41320) is currently available for download from the TSP library.
Don't have an account?
Overview
The document outlines NASA's Conflict-Aware Scheduling Algorithm, developed at the Jet Propulsion Laboratory (JPL), aimed at improving the scheduling processes within the Deep Space Network (DSN). The current scheduling methods are described as labor-intensive, leading to human errors and inefficiencies. The new algorithm seeks to automate these processes, thereby enhancing performance and reducing the potential for mistakes.
The Conflict-Aware Scheduling Algorithm differs from traditional scheduling methods by generating schedules that prioritize all requests while minimizing conflicts, rather than simply marking unscheduled items. This approach allows for a more dynamic allocation of resources, accommodating varying request lengths based on resource availability. It is particularly beneficial for scenarios requiring continuous coverage and can handle complex cases where multiple resources are needed for a single request.
The document emphasizes the algorithm's capability to utilize historical scheduling data, which helps maintain consistency across different timeframes and reduces disruptions in scheduling. This feature is crucial for ensuring that the scheduling process remains efficient and effective over time.
The development of this technology is positioned as a significant step toward automating NASA's scheduling systems, which is essential for both current operations and future advancements in aeronautical and space activities. The algorithm is still in the early prototype stage, with ongoing refinements and feature additions planned, such as enhanced integration of historical data.
The document also notes that the technology has not yet been used outside of JPL, but there are plans for public disclosure in the future. Potential applications for the Conflict-Aware Scheduling Algorithm extend beyond NASA, with implications for various industries that rely on scheduling techniques, including manufacturing and traffic control.
In summary, the Conflict-Aware Scheduling Algorithm represents a novel approach to scheduling that prioritizes efficiency and conflict management, addressing the challenges faced by current systems. Its development is a crucial advancement for NASA and has the potential for broader applications in other sectors. The document serves as a technical support package, providing insights into the algorithm's functionality, development status, and future prospects.
