The total time requirement applies to about 25
percent of the DSN user set, but over a wide range of
time scales, from a full week on down to a fraction of
a single day. An example for the GRAIL A/B mission
(two spacecraft in lunar orbit) is shown in figure 8a.
The tracking gaps time line requirement applies to
about a third of the DSN user set. In some cases, the
gaps of concern are only for certain activity types, as
illustrated in figure 8b where gaps are only significant
between adjacent ranging passes.
About 20 percent of users have DSN complex distribution requirements, but this varies depending on
the phase of the mission. These requirements are typically driven by navigation considerations, where it is
important to have ranging data from widely separated baselines in order to reduce ephemeris errors.
Examples are shown in figure 8a–c, where satisfaction or violation of the distribution requirement is
clearly visible.
While most missions have on-board recorders,
only a handful can potentially be modeled simply
enough to include in the early stages of DSN scheduling. For those missions with uniform data collections rates and well-defined downlink rules, the
recorder time line requirement can provide early visibility into recorder capacity and how it is affected by
specific scheduling choices. An example is shown in
figure 8c for the STEREO A/B spacecraft.
By providing a highly visual view of these time line
constraints and preferences, users who are working
on schedule changes to resolve conflicts can immediately see whether their proposed changes would
introduce any violations. Presently, many scheduling
users have custom scripts that they use to evaluate
proposals from other users, but by providing for common models and visibility, feedback can be provided
much more rapidly. This feedback has the potential
to reduce the overall negotiation process effort and
duration.
Overview of Scheduling Strategies
There are a few basic design principles around which
the DSE algorithms have been developed, derived
from the role of the DSE as the provider of intelligent
decision support to DSN schedulers. In support of
schedule repair and negotiation, it is critically impor-
tant that the DSE follow a no surprises paradigm, that
is, no unexpected schedule changes (all changes to
the schedule must be requested, explicitly or implic-
itly, and the same sequence of operations on the
same data must generate the same schedule) and
even for infeasible scheduling requests, attempt to
return something reasonable in response, possibly by
relaxing aspects of the request; along with a diagno-
sis of the sources of infeasibility, this provides a start-
ing point for users to handle the problem
In contrast to this mode of operation is an auto-
generation phase of the scheduling process where the
goal is to integrate scheduling requests from all users.
The result is an initial schedule with minimal conflicts and violations to serve as a starting point for
collaborative conflict resolution. In this mode, maintaining schedule stability is not an objective, and a
much broader range of changes to the scheduled
activities is allowable, provided that overall conflicts
are reduced. The DSE supports both modes of operation with a portfolio of algorithms that can be
invoked by the S3 system for autogeneration, or by
end users when working on specific conflicted portions of the schedule.
Expanding Requests to Tracks
The initial layout algorithm is the primary algorithm
users invoke to generate tracks to satisfy the specifications of the request. It is also used to remove any
existing tracks and regenerate them around whatever other activities already exist in the schedule. The
algorithm consists of a series of systematic search
stages over the legal track intervals, successively
relaxing request constraints at each stage if no solution is found. The systematic search algorithm is a
depth-first search algorithm over the space of available antenna/equipment start times and durations
for each scheduling request. The set of legal antenna/equipment for scheduling is defined in the
request service alias specification, while the search
space of legal start times and durations is defined by
the request quantization value (usually 5 minutes).
The successive relaxation of constraints allow for
tracks to be generated even though the scheduling
request may be infeasible (in isolation or within the
context of the current schedule), and provides the
user a starting point to make corrective changes.
These changes may range from modifying the
scheduling request to introduce more tracking flexibility, to contacting other mission schedulers to
negotiate different request time opportunities. One
of the limitations of the initial layout algorithm is
its ability to schedule collections of requests associated with track relationships. As it iterates over these
requests, tracks may be generated without regard to
the feasibility of generating tracks for the future
requests in the collection. As a result, it is prone to
creating violations for users whose requests are
highly interconnected.
Relaxation proceeds in two stages, based on schedule content, then on constraint parameters. In the
first phase, if no conflict-free allocation can be found,
the engine successively ignores lower priority activities, then those of equal priority, and finally all pre-existing activities. If there is still no satisfying allocation, then requirement parameters are relaxed in the
following order: ( 1) timing relationships, ( 2) gap and
overlap parameters for split tracks, and ( 3) constraining event windows. Ultimately, only antenna-to-spacecraft visibility intervals are considered and an
activity of the specified duration is created to overlap
one of these.
