Date of publication xxxx 00, 0000, date of current version xxxx 00, 0000.
10.1109/ACCESS.2017.DOI

This work was supported by the Jet Propulsion Laboratory, California Institute
of Technology, under a contract with the National Aeronautics and Space
Administration (NASA). Copyrights 2021. All rights reserved.

Corresponding author: Ryan Alimo (e-mail<EMAIL_ADDRESS>
#  $\Delta$-MILP: Deep Space Network Scheduling via Mixed-Integer Linear
Programming

THOMAS CLAUDET1  RYAN ALIMO1  EDWIN GOH1
MARK D. JOHNSTON1  RAMTIN MADANI2  BRIAN WILSON1  Jet Propulsion Laboratory,
California Institute of Technology, Pasadena, CA 91109, USA  The University of
Texas at Arlington, TX 76015 USA

###### Abstract

This paper introduces $\Delta$-MILP, a powerful variant of the mixed-integer
linear programming (MILP) optimization framework to solve NASA’s Deep Space
Network (DSN) scheduling problem. This work is an extension of our original
MILP framework (DOI:10.1109/ACCESS.2021.3064928), and inherits many of its
constructions and strengths, including the base MILP formulation for DSN
scheduling. To provide more feasible schedules with respect to the DSN
requirements, $\Delta$-MILP incorporates new sets of constraints including 1)
splitting larger tracks into shorter segments and 2) preventing overlapping
between tracks on different antennas. Additionally, $\Delta$-MILP leverages a
heuristic to balance mission satisfaction and allows to prioritize certain
missions in special scenarios including emergencies and landings. Numerical
validations demonstrate that $\Delta$-MILP now satisfies 100% of the requested
constraints and provides fair schedules amongst missions with respect to the
state-of-the-art for the most oversubscribed weeks of the years 2016 and 2018.

###### Index Terms:

Optimization, optimization methods, scheduling.

=-15pt

##  I Introduction

NASA’s Deep Space Network (DSN) is the primary source of communications for
interplanetary spacecraft missions for most active missions around the world.
This paper considers NASA’s Deep Space Network (DSN) scheduling problem, which
is the problem of assigning the DSN’s finite antenna resources to its users
within a given time frame. DSN schedules are typically generated a year into
the future with allocations to the minute, and are performed in a semi-
automated manner with manual and interactive cleanup, one week at a time [1,
2]. The DSN is considered as the largest and most sensitive telecommunications
system in the world [3, 4]. DSN consists of three complexes, each with one
70-meter antenna and three to four 34-meter ones [5], situated roughly 120°
apart around the Earth: in Goldstone, California, Madrid, Spain, and Canberra,
Australia. NASA has estimated that deep space communications capabilities need
to be expanded by a factor of 10 each decade to keep up with the rising demand
for deep space communications [3]. Despite the growing demand for
communications time on the DSN, its operational budget has dropped by
approximately 10 million dollars per year since 2014 [4]. As a result,
automation plays a significant role for the efficient usage of the DSN’s
finite resources. DSN is a highly utilized asset, and communications requests
in recent years have frequently reached or even exceeded its full capacity.
Increasing mission demands have led to frequent oversubscription — situations
in which only a subset of the requested tracking time can be feasibly
allocated. For example, the Perseverance Mars rover provides higher-fidelity
data compared to the previous rovers; Perseverance includes eight cameras as
well as sophisticated scientific instruments which increase the load on the
DSN.

Over the past 20 years, different solutions have been proposed to automate DSN
scheduling. In 2006, a genetic algorithm for DSN scheduling was proposed [6],
and in 2008 a generalized differential evolutionary algorithm was investigated
to find a Pareto optimal solution to satisfy multiple objective functions [7].
More recently, a deep reinforcement learning approach was proposed in which
agents were trained to learn efficient strategies to generate feasible
schedules based on DSN requests for a given week [8]. In addition, many novel
solutions and improvements have been made to increase the operational
efficiency of the DSN scheduling process [9, 10, 11, 12, 13].

In our previous work [14], the problem was formulated as a mixed-integer
linear program (MILP). MILP has many applications such as for task graphs [15,
16], energy hub plants [17], flow shop scheduling [18, 19], or job shop
scheduling [20]. It is also extensively used for scheduling meetings [21], to
satellite operations [22, 23, 24, 25, 26, 27], or telescopes [28]. In this
work, we incorporated many important features of the DSN scheduling process
such as spacecraft visibility/view periods, setup/teardown times before and
after transmission. Finding valid schedules that satisfy the important
constraints encountered in the real world leads to a large MILP problem with
tens of thousands of binary optimization variables and hundreds of millions of
elements to set the problem up.

This work in [14] presented a new, computationally efficient, and scalable
formulation and algorithm to solve the DSN scheduling problem on a set of
historical DSN requests. In this paper, that framework is extended by
incorporating new constraints to achieve higher quality schedules in terms of
feasibility and optimality. One of the primary problems with the previous
approach was that the solution had less than 20% of its tracks found to be
feasible. A significant amount of scheduled tracks overlapped with one
another, while others fell outside the spacecraft view periods, and other
important constraints were not implemented.

In practice, the optimal schedules not only need to maximize the overall
number of assigned activities but more importantly to find a balance of the
satisfaction between all the missions. An activity is an input of the
scheduler. It is composed of a mission name, specific setup and teardown
times, and a set of view periods from which the spacecraft in visible in the
sky and able to communicate with the DSN network. A track is an output of the
scheduler. A track is a moment in time where a certain antenna will be
communicating with a certain spacecraft. Tracks are then subsets of available
view periods. Thus, this framework is extended to maximize the overall
satisfaction across all missions while still maximizing the amount of overall
tracking time, but now ensuring the respect of the realistic operational and
physical constraints imposed by DSN operations.

The main contributions of this paper can be summarized as follows:

  * •

Introducing new sets of constraints to only schedule valid tracks (tracks that
satisfy all required constraints).

  * •

Increasing the overall user satisfaction across missions by incorporating a
dynamic objective function.

  * •

Implementing a prioritization feature to maximize one or multiple mission
satisfactions in case of emergencies or landings.

  * •

Evaluating the new performance of our MILP solution on the most oversubscribed
weeks in the DSN’s operational history in 2016 and 2018.

The structure of this paper is as follows: Section §II introduces DSN
scheduling terminology. Section §III derives the DSN scheduling problem
formulation. Section §IV presents the results obtained by the algorithm and
compares its performance with previous iterations from [14]. Section §V
finally draws conclusions on this work.

##  II Deep Space Network Scheduling Terminology

This section introduces the different terms to understand how DSN scheduling
works. Many missions today communicate with the DSN antennas. These missions
are also referred as users since they use the DSN, and antennas are also
called resources. DSN produces weekly schedules, so each mission, or user,
will make several communication demands to the DSN each week. These demands
include a minimum and maximum tracking time during which the DSN should
communicate with the spacecraft and the type of antenna that would be suited
for the task. From these pieces of information, DSN first attributes for each
required resource a time that will be sufficient for the antenna to prepare
the communication, also called a setup time, and a time necessary after the
communication also known as the teardown time. Second, knowing the position of
each spacecraft at any given time in the universe with respect to the DSN
antennas, DSN automatically computes the time windows during which each
spacecraft is visible from each antenna. For each antenna, the window starts
when the spacecraft rises from the horizon and ends when it sets. These
windows are called view periods. The DSN then concatenates each user demand,
the setup, teardown times, and the computed view periods to create what is
being called an activity. Since users make multiple requests per week, e.g.,
communicating with their spacecraft at least 2 hours per day, it creates as
many activities.

In order to fit more activities into the schedule, the DSN allows activities
to be split into smaller segments placed at different positions in the week.
The rule is that activities that request more than 8 hours may be split into
two 4-hour minimum chunks. The caveat to splitting activities in this fashion
is that each segment now requires setup and teardown time, which is, at the
end of the day, twice the amount of time that would be required if the whole
track was scheduled contiguously. This thus makes split activities more costly
to schedule, but can help creating space to place other tracks.

The missions operate independently of one another, and each mission would like
the DSN to schedule as many of their own activities as possible. As a result,
a perfect schedule from one mission’s perspective will not be ideal from the
point of view of all the other missions. On the other hand, the DSN wishes to
efficiently utilize its resources, and has concerns such as maximizing the
overall antenna usage. Thus, the goal of DSN scheduling is to satisfy the
highest number of activities, while ensuring the best satisfaction balance
between all the users.

###  II-A Mathematical notations

This section introduces the mathematical notations that are used to formulate
the DSN’s scheduling problem as a MILP problem. Let us denote
$\mathbb{R},\mathbb{N},\mathbb{N}^{*}$ as the sets of real numbers, natural
numbers, and nonnegative integers respectively 111Calligraphic uppercase
letters denote sets, mathbfface uppercase letters are used for matrices, and
mathbfface lowercase for vectors.. $|\mathcal{X}|$ denotes the cardinality of
a set $\mathcal{X}$. {0,1}|X|×|Y|, respectively {0,1}|X| denotes the set of
$|\mathcal{X}|\times|\mathcal{Y}|$ matrices, respectively $|\mathcal{X}|$
dimensional vectors with binary entries. $\boldsymbol{1}_{|\mathcal{X}|}$,
respectively $\boldsymbol{1}_{|\mathcal{X}|\times|\mathcal{Y}|}$ denotes a
$|\mathcal{X}|$ dimensional vector, respectively
$|\mathcal{X}|\times|\mathcal{Y}|$ dimensional matrix of ones.
$x\in\mathcal{X}$ means that element $x$ is in the set $\mathcal{X}$.
$M_{i,j}$ represents the element on row $i$ and column $j$ of matrix
$\mathbf{M}$. $\mathbf{M}\leq\mathbf{N}$ means that all the entries of
$\mathbf{M}$ are less or equal to the ones of $\mathbf{N}$.
$\textrm{diag}\\{\boldsymbol{X}\\}$ is a diagonal matrix formed by the
elements of vector $\boldsymbol{X}$. $(.)^{T}$ is the transpose operator.
$\mathbb{Z}/n\mathbb{Z}$ is the modular arithmetic set on the remainders of
integers in the division by $n$. {$a_{1},...,a_{n}$} is a list containing
elements $a_{1},...,a_{n}$. $\mathcal{X}\subseteq\mathcal{Y}$ signifies that
$\mathcal{X}$ is a subset of $\mathcal{Y}$. $\forall x\in\mathcal{X}$
signifies for all elements x in $\mathcal{X}$, $\exists$ for there exist, and
$\Leftrightarrow$ for equivalence.

###  II-B DSN mathematical objects definitions

Using the notations defined in §II-A, our goal is to assign resources to
spacecraft. To do so, let us define four key matrices related to DSN
scheduling.

First, $\boldsymbol{R}\in\\{0,1\\}^{|\mathcal{R}|\times|\mathcal{V}|}$ maps
resources to view periods. It has $|\mathcal{R}|$ rows as well as
$|\mathcal{V}|$ columns, and for each resource $r\in\mathcal{R}$, a 1 is
assigned to the corresponding column if this resource is the one corresponding
to view period $v\in\mathcal{V}$, and otherwise a 0.

Then, $\mathbf{A}\in\\{0,1\\}^{|\mathcal{A}|\times|\mathcal{V}|}$ maps
activities to view periods. $A_{a,v}=1$ if and only if view period
$v\in\mathcal{V}$ is found in activity $a\in\mathcal{A}$.

Matrix $\mathbf{M}\in\\{0,1\\}^{|\mathcal{M}|\times|\mathcal{A}|}$ maps
missions to activities. $M_{m,a}=1$ if and only if mission $m\in\mathcal{M}$
defines activity $a\in\mathcal{A}$.

A notion of time is finaly needed to know when these view periods can be
scheduled. To do that, let us finally define
$\mathbf{V}\in\\{0,1\\}^{|\mathcal{V}|\times|\mathcal{T}|}$ that maps view
periods to time frames. For example, if the time-granularity of the schedule
is 1 hour, and if view period $v_{i}$ can only be scheduled between Monday
0:00 am and 8 am UTC, the matrix will be filled with ones the first 8 columns
on the $i^{th}$ line of $\mathbf{V}$.

As stated in the previous section, a user requests a minimum and a maximum
(best-case) tracking time in hours. Let us call the concatenated vector of all
of them $\mathbf{d}_{min}$ and
$\mathbf{d}_{max}\in\mathbb{N^{*|\mathcal{A}|}}$.

Each antenna also has a setup and teardown time in minutes, and the
concatenations of all of them across activities are:
$\mathbf{\delta}_{\uparrow}$ and
$\mathbf{\delta}_{\downarrow}\in\mathbb{N}^{*|\mathcal{A}|}$. To be more
precise, $\mathbf{\delta_{\uparrow}}$ and
$\mathbf{\delta_{\downarrow}}\in(\mathbb{Z}/15\mathbb{Z})^{|\mathcal{A}|}$
which means that the greatest common divisor of all the setups and teardowns
will be equal to 15 minutes. This implies that the maximum time-granularity
must be equal to 15 minutes. For example, taking it larger as 1 hour would
make us lose 45 minutes at every teardown since they only last 15 minutes in
reality.

Finally, $\boldsymbol{\gamma}_{\uparrow}$ and
$\boldsymbol{\gamma}_{\downarrow}\in\mathbb{N}^{|\mathcal{V}|}$ are for the
minimum uninterrupted time that should be spent on each activity once it is
started, and the amount of time that the resource should remain idle after the
activity is interrupted.

Now, regarding the optimization variables,
$\mathbf{x}\in\\{0,1\\}^{|\mathcal{A}|}$ tells when entire activities are
completed or not throughout the planning horizon (at least the minimum
requested time has been scheduled).

Also, $\mathbf{X}\in\\{0,1\\}^{|\mathcal{V}|\times|\mathcal{T}|}$ defines if
view period $v\in\mathcal{V}$ is allocated or not at time $t\in\mathcal{T}$ in
the schedule.

Moreover,
$\mathbf{X^{\uparrow}}\in\\{0,1\\}^{|\mathcal{V}|\times|\mathcal{T}|}$,
respectively
$\mathbf{X^{\downarrow}}\in\\{0,1\\}^{|\mathcal{V}|\times|\mathcal{T}|}$ tells
at what time $t\in\mathcal{T}$ each view period $v\in\mathcal{V}$ starts,
respectively ends, and following [14]:

$X^{\uparrow}_{v,t}=1\;\Leftrightarrow\;X_{v,t-1}=0\;\wedge\;X_{v,t}=1,$ (1)
$X^{\downarrow}_{v,t}=1\;\Leftrightarrow\;X_{v,t-1}=1\;\wedge\;X_{v,t}=0.$ (2)

Finally,
$\mathbf{Y}^{\uparrow}\in\\{0,1\\}^{|\mathcal{V}|\times|\mathcal{T}|}$,
respectively
$\mathbf{Y}^{\downarrow}\in\\{0,1\\}^{|\mathcal{V}|\times|\mathcal{T}|}$,
tells during which interval $[t_{1}:t_{2}],\;t_{1},\;t_{2}\in\mathcal{T}$ the
track starts up, respectively tears down:

$Y^{\uparrow}_{v,t}=1\;\Leftrightarrow\;\exists\;t<\tau\leq
t+\delta^{\uparrow}_{v}:\quad X^{\uparrow}_{v,\tau}=1,$ (3)
$Y^{\downarrow}_{v,t}=1\;\Leftrightarrow\;\exists\;t-\delta^{\downarrow}_{v}<\tau\leq
t:\quad X^{\downarrow}_{v,\tau}=1.$ (4)

##  III Problem Statement

This section introduces new constraints in addition to the ones implemented in
[14]. But all of the them are being reviewed for the purpose of completeness.

###  III-A Constraints

The previous constraints implemented by [14] were the following:

  1. 1.

Each resource can only communicate with one spacecraft at any given time.

  2. 2.

If a track is scheduled, its tracking time must occur within a valid view
period (the spacecraft must be visible in the sky above the antenna).

  3. 3.

If a track is scheduled, it must be scheduled for at least its minimum
requested tracking time, and at most its maximum requested tracking time.

  4. 4.

A track must always start with the right setup time before tracking time can
occur, and end with the right teardown time.

  5. 5.

The possibility for missions to use 2 or more antennas at the same time must
be implemented (e.g. for Delta-Differential-One-Way-Ranging used for
navigation measurements, or for very far away spacecraft like Voyager that
need more power than what a single antenna could provide).

These constraints correspond to equations (6b)-(6i) in the problem
formulation.

In this work, new constraints are being proposed that the DSN leverages in
practice.

  1. 1.

For the same mission, tracks must not overlap on different antennas (e.g.,
having a part of a first track on a certain antenna happening at the same time
as another part of a second track on a different antenna):

$\boldsymbol{M}\boldsymbol{A}(\boldsymbol{Y}^{\downarrow}+\boldsymbol{X}+\boldsymbol{Y}^{\uparrow})\leq\boldsymbol{1}_{|\mathcal{M}|\times|\mathcal{T}|}.$
(5)

Each mission $m\in\mathcal{M}$, with
$\mathbf{M}\in\\{0,1\\}^{|\mathcal{M}|\times|\mathcal{A}|}$ has activites
$a\in\mathcal{A}$, with
$\mathbf{A}\in\\{0,1\\}^{|\mathcal{A}|\times|\mathcal{V}|}$, who themselves
have view periods $v\in\mathcal{V}$, with
$\mathbf{V}\in\\{0,1\\}^{|\mathcal{V}|\times|\mathcal{T}|}$ with resources
$r\in\mathcal{R}$ and available times $t\in\mathcal{T}$ as part of them. This
constraint states that, either for the setup, the tracking, or the teardown
time of a track, it is forbidden for any view periods of any activities of any
missions to appear more than once for a given time.

  2. 2.

Activities may be split into segments, i.e. not scheduled contiguously.

    1. (a)

If an activity is split, setup and teardown times are required for each
segment.

    2. (b)

An activity can only be split if its maximum duration is above 8 hours, and
each segment must be greater than the maximum between 4 hours and half of the
minimum duration.

    3. (c)

Parts must sum up between the minimum and maximum required durations.

To take into account splitting, the following algorithm based on the XOR gate
in electronics is being used:

for  _each activity $a_{i}$_ do

if  _$d_{\mathrm{max},i}\geq 8$ hours_ then

Duplicate $a_{i}$ to form $a_{i}^{\prime}$ & $a_{i}^{\prime\prime}$.

Append the three to the $\mathcal{A}_{i}^{*}$ set.

$(d_{max,i^{\prime}},d_{max,i^{\prime\prime}})\leftarrow d_{max,i}/2$

$(d_{min,i^{\prime}},d_{min,i^{\prime\prime}})\leftarrow\max(4\;\textrm{hours},d_{min,i}/2)$

end if

Add constraints to the solver:

$x_{a_{i}^{\prime}}\leq x_{a_{i}^{\prime\prime}}$

$x_{a_{i}^{\prime\prime}}\leq x_{a_{i}^{\prime}}$

$x_{a_{i}}\leq 1-x_{a_{i}^{\prime}}$

end for

Algorithm 1 XOR Splitting

Activities having a maximum duration greater or equal to 8 hours are
duplicated twice. For each of them, the maximum duration is divided by 2 and
the minimum duration is set to the maximum between 4 hours and half of the
minimum duration. Note that the max function is being used to make the model
more general in case $d_{min,i}\geq 8$ hours. Then, 3 constraints are being
added to ensure that the solver either schedules the full activity or the two
new duplicated activities, but nether both. One could see the electronics
analogy with the Exclusive-OR (XOR - $\oplus$) gate having the truth table
shown in Table I.

TABLE I: The Exclusive-OR (XOR - $\oplus$) table. P and Q are here binary variables usually used in logic. It is only desired to have the possibility to schedule either the full track $(P=1,Q=0)$, or the two duplicated tracks $(P=0,Q=1)$, but never both at the same time $(P=1,Q=1)$. Linear constraints for splitting are derived from the table and shown in Algorithm 1. Original track P | The two duplicated tracks Q | P$\oplus$ Q
---|---|---
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0

For example, if an activity requests between 8 and 10 hours, two new
activities will be created with the same view periods. They will both have a
minimum duration of 4 hours and a maximum duration of 5 hours. So that, if the
full track is scheduled, $x_{a_{i}^{\prime}}=x_{a_{i}^{\prime\prime}}=0$ and
$x_{a_{i}}=1$, which verifies the inequalities stated in the algorithm, and
the duration will be between the minimum and the maximum requested durations.
On the other hand, if a track is split,
$x_{a_{i}^{\prime}}=x_{a_{i}^{\prime\prime}}=1$ and $x_{a_{i}}=0$, each
duplicated track will have its minimum duration set to 4 hours and its maximum
duration to 5 hours, so that the sum will have a duration between 8 and 10
hours, which is what was required.

###  III-B Standard form

The goal is to maximize the number of tracks (or scheduled view periods) as
well as activities, and the objective function rewards these two quantities
with the coefficients $\boldsymbol{c}_{1}\in\mathbb{R}^{|\mathcal{A}|}$ and
$\boldsymbol{c}_{2}\in\mathbb{R}^{|\mathcal{V}|}$. The first coefficient
$\boldsymbol{c}_{1}$ gives priority to the activities, when
$\boldsymbol{c}_{2}$ rewards a better tracking time.This optimization is
subject to different constraints, with (6b) - (6i) from [14] and with the new
constraints (6j) - (6m). The complete problem formulation is thus the
following:

$\displaystyle\underset{\begin{subarray}{c}\boldsymbol{Z}\end{subarray}}{\text{maximize}}~{}~{}\boldsymbol{c}_{1}^{\top}\boldsymbol{x}\boldsymbol{1}_{|\mathcal{A}|}+\boldsymbol{c}_{2}^{\top}\boldsymbol{X}\boldsymbol{1}_{|\mathcal{T}|}$
(6a) $\displaystyle\mathrm{subject~{}to}$
$\displaystyle~{}\boldsymbol{X}\leq\boldsymbol{V}$ (6b)
$\displaystyle~{}X_{v,t}-X_{v,t-1}=X^{\uparrow}_{v,t}-X^{\downarrow}_{v,t}~{}~{}\forall
v\in\mathcal{V},\;\;\forall t\in\mathcal{T}$ (6c)
$\displaystyle~{}\sum^{t}_{\tau=t-\gamma^{\uparrow}_{v}+1}{X^{\uparrow}_{v,\tau}}\leq
X_{v,t}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\forall v\in\mathcal{V},\;\;\forall
t\in\mathcal{T}$ (6d)
$\displaystyle~{}\sum^{t}_{\tau=t-\gamma^{\downarrow}_{v}+1}{X^{\downarrow}_{v,\tau}}\leq
1-X_{v,t}~{}~{}~{}~{}~{}\forall v\in\mathcal{V},\;\;\forall t\in\mathcal{T}$
(6e)
$\displaystyle~{}Y^{\uparrow}_{v,t}=\sum^{t+\delta^{\uparrow}_{v}}_{\phantom{-}\tau=t+1\phantom{\delta^{\downarrow}_{v}}}{\\!\\!\\!\\!\\!\\!X^{\uparrow}_{v,\tau}}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\forall
v\in\mathcal{V},\;\;\forall t\in\mathcal{T}$ (6f)
$\displaystyle~{}Y^{\downarrow}_{v,t}=\sum^{t}_{\tau=t+1-\delta^{\downarrow}_{v}}{\\!\\!\\!\\!\\!\\!X^{\downarrow}_{v,\tau}}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\forall
v\in\mathcal{V},\;\;\forall t\in\mathcal{T}$ (6g)
$\displaystyle~{}\boldsymbol{R}(\boldsymbol{Y}^{\downarrow}+\boldsymbol{X}+\boldsymbol{Y}^{\uparrow})\leq\boldsymbol{1}_{|\mathcal{R}|\times|\mathcal{T}|}$
(6h)
$\displaystyle~{}\mathrm{diag}\\{\boldsymbol{d}_{\min}\\}\boldsymbol{x}\leq\boldsymbol{A}\boldsymbol{X}\boldsymbol{1}_{|\mathcal{T}|}\leq\mathrm{diag}\\{\boldsymbol{d}_{\max}\\}\boldsymbol{x}$
(6i)
$\displaystyle~{}\boldsymbol{M}\boldsymbol{A}(\boldsymbol{Y}^{\downarrow}+\boldsymbol{X}+\boldsymbol{Y}^{\uparrow})\leq\boldsymbol{1}_{|\mathcal{M}|\times|\mathcal{T}|}$
(6j) $\displaystyle~{}x_{a_{i}^{\prime}}\leq
x_{a_{i}^{\prime\prime}}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\forall(a_{i}^{\prime},a_{i}^{\prime\prime})\in\mathcal{A}_{i}^{*},~{}~{}\forall
i\in\\{1,...,|\mathcal{A}|\\}$ (6k)
$\displaystyle~{}x_{a_{i}^{\prime\prime}}\leq
x_{a_{i}^{\prime}}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\forall(a_{i}^{\prime},a_{i}^{\prime\prime})\in\mathcal{A}_{i}^{*},~{}~{}\forall
i\in\\{1,...,|\mathcal{A}|\\}$ (6l) $\displaystyle~{}x_{a_{i}}\leq
1-x_{a_{i}^{\prime}}~{}~{}~{}~{}~{}\forall(a_{i},a_{i}^{\prime})\in\mathcal{A}_{i}^{*},~{}~{}\forall
i\in\\{1,...,|\mathcal{A}|\\}$ (6m)

where the optimization variables are contained in $\boldsymbol{Z}$ such that:

$\displaystyle\boldsymbol{Z}:=(\boldsymbol{X},\,\boldsymbol{X}^{\uparrow},\,\boldsymbol{X}^{\downarrow},\,\boldsymbol{Y}^{\uparrow},\,\boldsymbol{Y}^{\downarrow},\,\boldsymbol{x}).$

  * •

(6a) is the objective function and represents the score obtained by the total
number of activities and view periods scheduled.

  * •

(6b) signifies that we can only schedule view periods that exist.

  * •

(6c) restates the definitions of (1) and (2).

  * •

(6d) and (6e) enforce the minimum up and down time constraints.

  * •

(6f) and (6g) define $\boldsymbol{Y}^{\downarrow}$ and
$\boldsymbol{Y}^{\uparrow}$, i.e., (3) and (4).

  * •

(6h), analogously to (6j), makes sure that it is impossible to assign multiple
activities to a single resource at each time (including setup, communication,
and teardown times).

  * •

(6i) restricts the duration of each scheduled activity to be bounded by the
minimum and maximum time requirements.

###  III-C User Satisfaction

One of the issues in [14] which was briefly discussed was the balance between
user satisfactions. It is observed that some missions were highly satisfied
whereas others only had a negligible percentage of their requested hours
satisfied.

Such schedules may result in mission emergencies as some missions did not get
enough scheduled hours. As a result, the DSN planners will need to modify the
schedules for the following week to get data from these underscheduled
missions. In order to satisfy a certain user, the most hours has to be given
to him. However, with an oversubscribed schedule, efficient trade-offs have to
be made to balance the satisfaction between all users in the objective to
maximize the overall one. To compare the performances of the MILP optimization
algorithms in finding an optimized solution within a specific time budget, the
user satisfaction was chosen to be measured using different metrics. First,
the root mean square (RMS) of the satisfaction $U_{RMS}$:

$U_{RMS}=\sqrt{\frac{1}{|\mathcal{M}|}\sum_{m\in\mathcal{M}}\left(\frac{T_{R_{m}}-T_{S_{m}}}{T_{R_{m}}}\right)^{2}},$
(7)

where $T_{S_{m}}$ and $T_{R_{m}}$ are the scheduled and requested tracking
times for mission $m\in\mathcal{M}$, and $|\mathcal{M}|$ is the number of
missions. $U_{RMS}$ measures the standard deviation of the residuals between
the scheduled and the requested durations. Since it is desired to schedule as
many time as requested, the residuals need to be minimized, thus the metric as
well.

Then, the maximum unsatisfied fraction is defined as:

$U_{MAX}=\max_{m\in\mathcal{M}}\left(\frac{T_{R_{m}}-T_{S_{m}}}{T_{R_{m}}}\right).$
(8)

This metric measures the worst satisfaction that could be ensured for all the
different missions and has to be minimized. 222Minimizing $U_{MAX}$ is
equivalent to maximizing the minimum satisfaction.

And finally, the goal is to maximize the overall satisfaction ratio among
missions:

$U_{AVG}=\frac{1}{|\mathcal{M}|}\sum_{m\in\mathcal{M}}\frac{T_{S_{m}}}{T_{R_{m}}}.$
(9)

Regarding the algorithm to improve the user satisfaction itself, the idea is
to start with an objective function that does not prioritize any missions at
first. A satisfaction threshold is set, which is the ratio between the
requested and scheduled time of a user, and the optimization runs. After
getting the results that are being saved, the satisfactions of the missions
are computed. For each mission that has a satisfaction smaller than the
threshold, its weights in the objective function are doubled. This is to give
the mission a bigger priority as the objective function has to be maximized,
and the algorithm iterates over multiples runs. If all the missions happen to
have a satisfaction above the threshold after a certain iteration, the
threshold is increased. If after a certain number of runs, the last threshold
is not beaten, the solver stops. The last step is then to decide which result
should be kept, and it will not always be the last one. It is chosen the
solution that minimizes the euclidean distance $d$ in the
($U_{RMS},U_{MAX},1/U_{AVG}$) space, which are the 3 chosen metrics. In case
where it is asked to prioritize one or multiple missions (denoted by the $p$
index) as will be discussed in §IV-D, the satisfaction metric $1/U_{PRIO}$ of
these users will be added:

$U_{PRIO}=\frac{1}{|\mathcal{M}_{p}|}\sum_{m_{p}\in\mathcal{M}_{p}}\frac{T_{S_{m_{p}}}}{T_{R_{m_{p}}}}.$
(10)

The general-case distance $d$ is thus the following:

$d=\sqrt{U_{RMS}^{2}+U_{MAX}^{2}+\frac{1}{U_{AVG}^{2}}+\frac{1}{U_{PRIO}^{2}}}.$
(11)

Note that the two first have to be minimized, when the two last have to be
maximized. This is why the inverse is taken for them. Algorithm 2 summarizes
this.

k $\leftarrow$ 0

threshold $\leftarrow$ $\eta_{0}$

while  _k ¡ k_max_ do

Solve problem $\eqref{2a}-\eqref{2m}$ during k_time

Save the solution.

for  _Each mission in the results_ do

Compute its satisfaction (ratio of scheduled hours by requested).

if  _satisfaction ¡ threshold_ then

Double its weights in the objective function.

end if

end for

while  _min(satisfactions) ¿= threshold_ do

threshold $\leftarrow$ threshold + incr_threshold

k $\leftarrow$ 0

end while

if  _Current solution == Previous solution_ then

k_time $\leftarrow$ 2.k_time

k $\leftarrow$ 0

end if

k $\leftarrow$ k + 1

end while

for  _Each solution_ do

Compute $U_{RMS},U_{MAX},1/U_{AVG},1/U_{PRIO}$.

Compute distance d and keep the solution that minimizes it.

end for

Algorithm 2 Dynamic objective function

##  IV Numerical Results

###  IV-A Input Datasets

A set of User Loading Profiles (ULPs) was used for Week 44 in 2016 (W44 2016)
as well as weeks 10, 20, 30, 40, and 50 of 2018, all of which being
oversubscribed. The algorithm thus has to make efficient choices to increase
the chosen metrics.

The input data is the set of all the activities for these given weeks. Table
II summarizes the dataset that is used in this work.

TABLE II: Summary of the input data used for DSN scheduling problems. #
Resources represents the number of available antennas, Requested $n_{a}$ is
the total number of requested activities during that week, $T_{R}$ is the
total tracking time in hours requested from all missions, and # Missions is
the number of missions asking for hours during that specific week.

Dataset | # Resources | Requested $n_{a}$ |  $T_{R}$ (hrs) | # Missions
---|---|---|---|---
W44 2016 | 14 | 284 | 1418 | 29
W10 2018 | 12 | 257 | 1192 | 30
W20 2018 | 12 | 294 | 1406 | 33
W30 2018 | 12 | 293 | 1464 | 32
W40 2018 | 12 | 333 | 1737 | 33
W50 2018 | 12 | 275 | 1292 | 29

This section evaluates the new framework on real-world datasets from NASA’s
Deep Space Network historical schedules. Numerical evaluations were performed
on these 6 oversubscribed weeks and results were compared with the state-of-
the-art.

###  IV-B Experimenting on week 44, 2016

Week 44 in 2016 (W44 2016) is an oversubscribed week where several algorithms
tried to find the optimal schedule for, including [8] with Deep Reinforcement
Learning (DeepRL) and [14] with Mixed-Integer Linear Programming (MILP). As
shown in Table II, W44 2016 consists of 14 resources, 284 activities, 1418
hours of requested tracking time, and 29 different missions. Also, Table III,
provides a summary of the parameters associated with the 284 activities in
this data set. Each week in our dataset is discretized into a set of 15-minute
time intervals.

TABLE III: Average parameter values organized by missions for the week 44 in
2016 DSN data set. $T_{R}$ is the total number of requested hours for each
user. $n_{a}$ is the number of activities for each user. $d_{min}$ and
$d_{max}$ are the average minimum and maximum durations requested by the user
in hours. $\delta^{\uparrow}$ and $\delta^{\downarrow}$ are the average setup
and teardown times of all the requests of the user in minutes.

Mission |  $T_{R}$ (hrs) | $n_{a}$ |  $\boldsymbol{d}_{\min}$(hrs) |  $\boldsymbol{d}_{\max}$(hrs) |  $\boldsymbol{\delta}_{\uparrow}$(mins) |  $\boldsymbol{\delta}_{\downarrow}$(mins)
---|---|---|---|---|---|---
ACE | 27.5 | 10 | 2.75 | 2.75 | 60 | 15
CAS | 72.0 | 8 | 7.2 | 9 | 60 | 15
CHDR | 21 | 21 | 1 | 1 | 60 | 15
DAWN | 168 | 21 | 6.4 | 8 | 60 | 15
DSCO | 1 | 1 | 1 | 1 | 60 | 15
GTL | 23.1 | 21 | 1.1 | 1.1 | 30 | 15
HYB2 | 6 | 2 | 3 | 3 | 60 | 15
JNO | 128 | 18 | 5.95 | 7.11 | 63.33 | 16.67
KEPL | 12 | 2 | 6 | 6 | 60 | 15
LRO | 13 | 13 | 1 | 1 | 60 | 15
M01O | 113 | 15 | 6.04 | 7.53 | 60 | 15
MER1 | 17.5 | 7 | 2.5 | 2.5 | 45 | 15
MEX | 56 | 7 | 6.4 | 8 | 60 | 15
MMS1 | 51.2 | 13 | 3.94 | 3.94 | 60 | 15
MOM | 25.5 | 8 | 3.19 | 3.19 | 46.88 | 15
MRO | 112 | 14 | 6.4 | 8 | 60 | 15
MSL | 42 | 7 | 6 | 6 | 60 | 15
MVN | 72 | 9 | 6.4 | 8 | 60 | 15
NHPC | 70 | 7 | 8 | 10 | 60 | 15
ORX | 45 | 10 | 4.5 | 4.5 | 60 | 15
SOHO | 84 | 21 | 4 | 4 | 60 | 15
STA | 28 | 7 | 4 | 4 | 60 | 15
STB | 15.5 | 3 | 5 | 5.17 | 45 | 15
STF | 20 | 5 | 4 | 4 | 60 | 15
THB | 14 | 4 | 3.5 | 3.5 | 60 | 15
THC | 14 | 4 | 3.5 | 3.5 | 60 | 15
VGR1 | 65 | 8 | 6.67 | 8.13 | 46.88 | 15
VGR2 | 84.5 | 11 | 6.41 | 7.68 | 35.45 | 15
WIND | 17.5 | 7 | 2.5 | 2.5 | 60 | 15

One of the challenges of the DSN’s scheduling problem is the nonuniform
requested time distribution between missions. Table III illustrates that for
week 44, 2016. For instance, DAWN333DAWN is a mission studying Vesta and
Ceres, two protoplanets in the asteroid belt. requested 168 hours of tracking
time while DSCO 444DSCO is the Deep Space Climate Observatory only asked for 1
hour. As a result, a single hour of tracking time for DSCO is a lot more
important than 1 hour for DAWN.

Figure 1: Number of view periods per antenna during W44 2016. Some antennas
for which there are zeros were not available during the week. This explains
why no tracks could be scheduled at that time on these resources, and why this
week is considered as one as the hardest of the year.

Using $\Delta$-MILP, for week 44 in 2016, Fig. 1 illustrates the availability
of different antennas for the different days of the week. For each cell, the
number of times the related antenna could be requested on a given day is
indicated. It is observed that there is a non-homogeneity between antennas.
Some of them were under maintenance or got completely shut down such as with
DSS-34 and DSS-45. Moreover, since DSN antennas do not have the same diameter
and are not placed at the same location, there are some disparities between
antennas of a same complex on a given day. This enforces the difficulty of
balancing mission satisfactions in this setup.

Figure 2: Satisfaction ratios for W44 2016, the most oversubscribed week of
the year, using $\Delta$-MILP. 100% valid tracks were scheduled. 901 hours
(63.5%) as well as 208 requests (73.2%) were satisfied. The average
satisfaction ratio $U_{AVG}$ is 69.9%, the $U_{RMS}$ is 0.35 and the minimum
satisfaction is 45.8% $(U_{MAX}=54.2\%)$ which strongly outperforms any other
implementations developed so far.

The following bar chart on Fig. 2 gives the satisfaction ratios for W44 2016.
All MILP formulations are solved using GUROBI 9.1.2 through MATLAB R2020b on a
laptop computer with Intel Core i7 4.1 GHz CPU, and 16 GB of RAM. Regarding
the initialization of Algorithm 2, the objective function was initialized by
giving an equal weight to every completed activity and assigned view period
($c_{1}\leftarrow\mathbf{1}_{|\mathcal{A}|}$,
$c_{2}\leftarrow\mathbf{1}_{|\mathcal{V}|}$ from (6a)). The maximum number of
iterations (k_max) was assigned to 10 to have enough runs to efficiently
balance the satisfaction. The time limit per iteration (k_time) was set to 30
minutes as the solver generally found and for some weeks converged to a
solution after that time. If it cannot, following Algorithm 2, the time limit
doubles. The initial threshold $\eta_{0}$ was set to 15% and its increment
(incr_threshold) to 5%.

Results for $\Delta$-MILP show that the satisfaction is well balanced between
every mission with a minimum of 45.8% provided by Algorithm 2. Only valid
tracks were scheduled and more than 63% of hours and 73% of requests were
satisfied. These numbers are significantly higher than the state-of-the-art as
shown in Table IV.

Figure 3: Final schedule using $\Delta$-MILP for W44 2016. Blank gaps mean
that no view periods were available to be scheduled. Black tracks represent
maintenance times. SC means Spacecraft.

On Fig. 3, the final schedule is shown. All missions have a different color,
and a technician hovering them with a mouse would see more precisions such as
the mission’s name, the exact moment of the setup, the communication, and the
tear-down time, but also the track-id and the antennas involved. There are
still some time frames during which no tracks were placed. This is either
because no view periods were available at that time to be scheduled, or since
it did not produce a better solution.

Then, on Fig. 4, a heatmap of the scheduled hours for each mission and on each
antenna is displayed. The cell for NHPC 555New Horizon is a mission to study
the dwarf planet Pluto. on DSS-43 is very bright since the mission only
required 70-m antennas, and DSS-43 was the only one that had view periods with
the spacecraft during that week.

Finally, on Fig. 5, the antennas communication, available and maintenance
times are shown. For DSS-45, no time was left available. The scheduled hours
are well distributed among the different antennas, which is one of the
concerns of the DSN.

Figure 4: Heatmap of the scheduled durations for all antennas and missions.
All of the hours of NHPC were scheduled on DSS-43 as it was the only 70-m
antenna that had view periods with the spacecraft during that week. Figure 5:
Antenna usage for W44 2016. Communication time in red, available time in light
red, and maintenance or shutdown time in grey. DSS-43 scheduled all of its
available hours. This bar chart shows a balance between all the hours of the
different antennas, which is one of the objectives from the DSN perspective.

###  IV-C More comparisons with weeks 10, 20, 30, 40, and 50 in 2018

In addition to week 44 in 2016, the real world DSN’s dataset was also studied
to propose new comparisons for weeks 10, 20, 30, 40, and 50 in 2018. Results
are shown in Table IV. 4 algorithms were compared. The first two were the ones
introduced in [14] using an unweighted objective function as well as
randomizing the weights at every iteration. In [14], they were uniformly drawn
from the interval $[1,5]$ and $[0,0.01]$, respectively. Then, there is
$\Delta$-MILP, and the results after its first iteration (30 minutes of run
time), $\Delta$-MILP(0).

For every week, it is observed that $\Delta$-MILP outperforms by more by 5
times the original MILP [14] in terms of hours satisfied, overall satisfied
time fraction, number of satisfied requests, as well as overall satisfied
request fraction, average satisfied ratios, RMS and maximum unsatisfied time
fraction. Algorithms provided by [14] did not respect all the constraints,
that is why the goal of this work also was to extend the constraints set. It
should be noted that no more constraints were added to be assessed between
[14] and $\Delta$-MILP.

It can also be seen that $\Delta$-MILP(0) sometimes places more hours or
satisfy more requests than $\Delta$-MILP. However, when looking at the
$U_{MAX}$ metric, the satisfaction of $\Delta$-MILP outperforms
$\Delta$-MILP(0), showing the usefulness of Algorithm 2 to increase the
minimum satisfaction using this dynamic objective function and iterative
threshold approach.

TABLE IV: Comparison of scheduling results using previously implemented algorithms and new ones. A valid track is a track that satisfies all the constraints defined in §III-B Metric | Alg. | W44 2016 | W10 2018 | W20 2018 | W30 2018 | W40 2018 | W50 2018
---|---|---|---|---|---|---|---
Valid tracks (%) | Unweighted [14] | 16.5 | 19.0 | 14.2 | 11.9 | 13.5 | 14.3
Randomized [14] | 22.1 | 20.2 | 22.0 | 40.0 | 32.9 | 25.1
$\Delta$-MILP(0) | 100 | 100 | 100 | 100 | 100 | 100
$\Delta$-MILP | 100 | 100 | 100 | 100 | 100 | 100
Hours satisfied | Unweighted [14] | 171 | 152 | 136 | 135 | 114 | 127
Randomized [14] | 207 | 159 | 156 | 127 | 70 | 134
$\Delta$-MILP(0) | 900 | 855 | 990 | 990 | 885 | 821
$\Delta$-MILP | 901 | 822 | 1059 | 983 | 949 | 816
Overall satisfied time fraction (%) | Unweighted [14] | 11.9 | 12.2 | 9.7 | 9.2 | 6.5 | 9.8
Randomized [14] | 14.6 | 13.3 | 11.1 | 8.7 | 4.1 | 10.4
$\Delta$-MILP(0) | 63.5 | 71.8 | 70.4 | 67.6 | 51.0 | 63.5
$\Delta$-MILP | 63.5 | 69.1 | 75.4 | 67.1 | 54.6 | 63.1
# of satisfied requests | Unweighted [14] | 51 | 47 | 38 | 34 | 43 | 41
Randomized [14] | 62 | 40 | 46 | 31 | 24 | 45
$\Delta$-MILP(0) | 216 | 212 | 239 | 232 | 223 | 212
$\Delta$-MILP | 208 | 203 | 249 | 231 | 223 | 197
Overall. satisfied request fraction (%) | Unweighted [14] | 17.8 | 17.5 | 12.9 | 11.5 | 12.6 | 14.7
Randomized [14] | 21.8 | 15.6 | 15.6 | 10.6 | 7.2 | 16.4
$\Delta$-MILP(0) | 76.1 | 82.5 | 81.3 | 79.2 | 67.0 | 77.1
$\Delta$-MILP | 73.2 | 79.0 | 84.7 | 78.8 | 67.0 | 71.6
Avg. satisfied ratios (%) | Unweighted [14] | 21.2 | 22.7 | 17.9 | 9.4 | 17.1 | 17.4
Randomized [14] | 22.9 | 20.1 | 18.0 | 8.9 | 5.5 | 14.5
$\Delta$-MILP(0) | 76.3 | 85.4 | 86.7 | 82.5 | 70.3 | 81.3
$\Delta$-MILP | 69.9 | 81.5 | 88.8 | 81.4 | 70.8 | 73.8
RMS of unsatisfied time fraction, $U_{RMS}$ | Unweighted [14] | 0.82 | 0.82 | 0.86 | 0.92 | 0.88 | 0.85
Randomized [14] | 0.80 | 0.84 | 0.85 | 0.92 | 0.95 | 0.87
$\Delta$-MILP(0) | 0.36 | 0.27 | 0.25 | 0.28 | 0.44 | 0.30
$\Delta$-MILP | 0.35 | 0.26 | 0.21 | 0.29 | 0.40 | 0.35
Max. unsatisfied time fraction (%), $U_{MAX}$ | Unweighted [14] | 100 | 100 | 100 | 100 | 100 | 100
Randomized [14] | 100 | 100 | 100 | 100 | 100 | 100
$\Delta$-MILP(0) | 86.4 | 91.7 | 72.7 | 79.2 | 100 | 72.8
$\Delta$-MILP | 54.2 | 47.9 | 64.1 | 64.3 | 100 | 60.0
Run time (hours) | Unweighted [14] | 15 | 15 | 15 | 15 | 15 | 15
Randomized [14] | 15 | 15 | 15 | 15 | 15 | 15
$\Delta$-MILP(0) | 0.5 | 0.5 | 0.5 | 0.5 | 0.5 | 0.5
$\Delta$-MILP | 7.5 | 18 | 10.5 | 13.5 | 22.5 | 7.5
Figure 6: Iterations of the solutions from Algorithm 2 for W40 2018 which is
the hardest of this year. The blue dots are the iterative solutions and the
red broken line indicates the minimum distance, and thus the chosen schedule
in this metric space.

Fig. 6 shows the 3 metrics $(U_{RMS},\;U_{MAX}$, and $1/U_{AVG})$ computed
from the iterations of $\Delta$-MILP. The schedules gradually improve with
respect to them.

###  IV-D Prioritizing a mission

A last feature was finally implemented to give the possibility to prioritize
one or multiple missions. Prioritization is a key factor during the DSN
operations. Examples of which would be the landing of a new spacecraft or an
emergency where there is a chance to lose the spacecraft (e.g., the Spirit
rover from its Martian sand trap [29]). In such cases, our algorithm for DSN
scheduling has to create a trade-off to be able to schedule as many hours as
possible for these specific missions while not decreasing the satisfaction of
the other ones too much.

When incorporating the priority requests for the DSN, the overall
implementation will remain as it was described in §III-B for Algorithm 2.
However, instead of starting with weights of ones within the objective
function as given in (6a), it is considered a nonuniform vector that embeds
the priority for each mission. The larger the multiplier is, the more
important the mission will become. Here, after discussing with the DSN
operators and considering their experience in this area, it was considered a
multiplier of 5 for the missions with a higher priority, i.e.
$c_{1}(i_{p})\leftarrow 5,\;\forall i_{p}\in\mathcal{A}_{p}$, the prioritized
activities set.

Fig. 7 shows the results for W44 2016 where NHPC is being prioritized with a
weight of 5. Comparing with Fig. 2, the satisfaction for NHPC went from 50% to
90%, and all the other mission satisfactions went from all above 45% to all
above 26%. From Fig. 4, since NHPC could only be scheduled on 70-m antennas
such as DSS-43 and DSS-63, prioritizing it would reduce the amount of
scheduled hours for the other missions that need to use the same antennas such
as JNO666Juno mission was developed to reveal the story of Jupiter’s formation
and evolution., MRO777Mars Reconnaissance Orbiter is a spacecraft that was
designed to study the geology and climate of Mars, provide reconnaissance of
future landing sites, and relay data from surface missions back to Earth., or
STF888Splitzer Space Telescope was designed to study the early universe in
infrared light..

Figure 7: Satisfactions for W44 2016 when prioritizing NHPC (New Horizon).
When comparing with Fig. 2, the satisfaction for NHPC went from 50% to 90%,
and all the other mission satisfactions went from all above 45% to all above
26%.

##  V Conclusions and Future Work

In this paper, the Deep Space Network scheduling terminology was first
introduced. The problem formulation was then derived with a new set of
constraints and this paper presented a new algorithm to improve the user
satisfaction. New results were showed and compared with the previous
iterations from [14], and $\Delta$-MILP outperformed them in terms of
satisfaction and feasibility of its schedules.

Parallel developments on DSN scheduling at the Jet Propulsion Laboratory use
Deep Reinforcement Learning [8]. Future work on this research could be to
hybridize both approaches. Because is becomes harder to improve the objective
function as the schedules get filled, an idea could be to train an agent to
make the hardest decisions in a short amount of time. Training this agent
could be done using scheduling examples that $\Delta$-MILP would provide by
performing longer and more intense searches for this purpose. This
hybridization could then help providing better schedules and at a faster pace.
Also, comparisons of the $\Delta$-MILP results with other methodologies such
as Deep Reinforcement Learning and Quantum Computing solutions will be studied
in future publications. $\Delta$-MILP will be extended to many other
applications in the future such as stabilization of balloons [30], multi-agent
motion planning [31], automated data accountability for Mars missions [32] and
derivative-free optimization [33].

## Acknowledgment

The authors gratefully acknowledge funding from Jet Propulsion Laboratory,
California Institute of Technology, under a contract with the National
Aeronautics and Space Administration (NASA) in support of this work. The
authors thank Alexandre Guillaume, Hamsa Shwetha Venkataram, Chris Mattmann,
Joe Lazio, Becky Castano, Thomas Bewley, Alex Sabol, Farhad Kamangar, Dave
Hanks, Fred Hadaegh for fruitful discussions and support.

## References

  * [1] B. J. Clement, M. D. Johnston (2005). “The deep space network scheduling problem”, AIAA, Pittsburgh, PA, USA, 2005.
  * [2] M. D. Johnston, D. Tran, B. Arroyo, S. Sorensen, P. Tay, B. Carruth, A. Coffman, and M. Wallace, 2014. Automated scheduling for NASA’s deep space network. AI Magazine, 35(4), pp.7-25.
  * [3] J. Taylor, Deep space communications, vol. 1. Hoboken, NJ, USA: Wiley, 2016\.
  * [4] “Nasa’s management of the deep space network,” Nat. Aeronaut. Space Admin., Office Inspector Gen., Washington, DC, USA, Tech. Rep. IG-15-013, 2015.
  * [5] W. A. Imbriale, Large antennas of the deep space network, vol. 1. Hoboken, NJ, USA: Wiley, 2005.
  * [6] A. Guillaume, S. Lee, Y.-F. Wang, H. Zheng, R. Hovden, S. Chau, Y.-W. Tung, and R. J. Terrile, “Deep space network scheduling using evolutionary computational methods,” in Proc. IEEE Aerosp. Conf., Mar. 2007, pp. 1-6.
  * [7] M. D. Johnston, “An evolutionary algorithm approach to multi-objective scheduling of space network,” Commun. Int. J. Intell. Automat. Soft Com- put., vol. 14, no. 3, pp. 367-376, 2008.
  * [8] E. Goh, H. S. Venkataram, M. Hoffmann, M. D. Johnston and B. Wilson, ”Scheduling the NASA Deep Space Network with Deep Reinforcement Learning,” 2021 IEEE Aerospace Conference (50100), 2021, pp. 1-10.
  * [9] C. E. Bell, “Scheduling deep-space network data transmissions: a lagrangian relaxation approach,” in Applications of Artificial Intelligence 1993: Knowledge-Based Systems in Aerospace and Industry, vol. 1963. Bellingham, WA, USA: SPIE, 1993, pp. 330-340.
  * [10] S. Chien, G. Rabideau, R. Knight, R. Sherwood, B. Engelhardt, D. Mutz, T. Estlin, B. Smith, F. Fisher, T. Barrett, G. Stebbins, and D. Tran, “Aspen - automated planning and scheduling for space mission operations,” in Proc. Space Ops, 2000, pp. 1-10.
  * [11] M. D. Johnston, D. Tran, and B. Arroyo, “Request-driven scheduling for NASA’s deep space network,” in Proc. Int.Workshop Planning Scheduling for Space (IWPSS), 2009, pp. 1-10.
  * [12] T. M. Hackett, M. Johnston, and S. G. Bilen, “Spacecraft block scheduling for NASA’s deep space network,” in Proc. Space Ops, 2018, p. 2578.
  * [13] J. A. Sabol, R. Alimo, M. Hoffmann, E. Goh, B. Wilson, and M. Johnston, “Towards automated scheduling of NASA’s deep space network: A mixed integer linear programming approach,” in Proc. AIAA Scitech Fo
  * [14] A. Sabol, R. Alimo, F. Kamangar and R. Madani, “Deep space network scheduling via mixed-integer linear programming,” in IEEE Access, vol. 9, pp. 39985-39994, 2021. rum, Jan. 2021, p. 667.
  * [15] S. K. Roy, R. Devaraj, and A. Sarkar, “Optimal scheduling of PTGs with multiple service levels on heterogeneous distributed systems,” in Proc. Amer. Control Conf. (ACC), Jul. 2019, pp. 157-162.
  * [16] S. K. Roy, R. Devaraj, A. Sarkar, K. Maji, and S. Sinha, “Contention-aware optimal scheduling of real-time precedence-constrained task graphs on heterogeneous distributed systems,” J. Syst. Archit., vol. 105, May 2020, Art. no. 101706.
  * [17] M. Jadidbonab, B. Mohammadi-Ivatloo, M. Marzband, and P. Siano, “Short-term self-scheduling of virtual energy hub plant within thermal energy market,” IEEE Trans. Ind. Electron., vol. 68, no. 4, pp. 3124-3136, Apr. 2021.
  * [18] L. Meng, C. Zhang, X. Shao, B. Zhang, Y. Ren, and W. Lin, “More MILP models for hybrid flow shop scheduling problem and its extended problems,” Int. J. Prod. Res., vol. 58, no. 13, pp. 3905-3930, Jul. 2020.
  * [19] Y. Xiao, S. Zhang, P. Yang, M. You, and J. Huang, “A two-stage flow-shop scheme for the multi-satellite observation and data-downlink scheduling problem considering weather uncertainties,” Rel. Eng. Syst. Saf., vol. 188, pp. 263-275, Aug. 2019.
  * [20] L. Meng, C. Zhang, X. Shao, and Y. Ren, “MILP models for energy-aware flexible job shop scheduling problem,” J. Cleaner Prod., vol. 210, pp. 710-723, Feb. 2019.
  * [21] T. Tsuruta and T. Shintani, “Scheduling meetings using distributed valued constraint satisfaction algorithm,” in Proc. ECAI, 2000, pp. 383-387.
  * [22] A. J. Vazquez and R. S. Erwin, “On the tractability of satellite range scheduling,” Optim. Lett., vol. 9, no. 2, pp. 311-327, Feb. 2015.
  * [23] S. Chien, G. Rabideau, J. Willis, and T. Mann, “Automating planning and scheduling of shuttle payload operations,” Artif. Intell., vol. 114, nos. 1-2, pp. 239-255, Oct. 1999.
  * [24] X. Chen, G. Reinelt, G. Dai, and A. Spitz, “A mixed integer linear programming model for multi-satellite scheduling,” Eur. J. Oper. Res., vol. 275, no. 2, pp. 694-707, Jun. 2019.
  * [25] D.-H. Cho and H.-L. Choi, “A traveling salesman problem-based approach to observation scheduling for satellite constellation,” Int. J. Aeronaut. Space Sci., vol. 20, no. 2, pp. 553-560, Jun. 2019.
  * [26] Y. She, S. Li, and Y. Zhao, “Onboard mission planning for agile satellite using modified mixed-integer linear programming,” Aerosp. Sci. Technol., vol. 72, pp. 204-216, Jan. 2018.
  * [27] Y. Du, T.Wang, B. Xin, L.Wang,Y. Chen, and L. Xing, “A data-driven parallel scheduling approach for multiple agile Earth observation satellites,” IEEE Trans. Evol. Comput., vol. 24, no. 4, pp. 679-693, Aug. 2020.
  * [28] M. D. Johnston, “Automated telescope scheduling,” Space Telescope Sci. Inst., Baltimore, MD, USA, Tech. Rep. 306, 1988.
  * [29] Kerr, R. A. (2009). Mars rover trapped in sand, but what can end a mission?.
  * [30] T. Claudet, T. Bewley, and S. R. Alimo, “Stabilization of a planetary-explorer balloon-payload system using tensegrity,”, in AIAA Scitech Forum, 2021, pp. 0741.
  * [31] Yun, Kyongsik, Changrak Choi, Ryan Alimo, Anthony Davis, Linda Forster, Amir Rahmani, Muhammad Adil, and Ramtin Madani. ”Multi-Agent Motion Planning using Deep Learning for Space Applications.” In ASCEND 2020, p. 4233. 2020.
  * [32] R. Alimo, Ryan, Dylan Sam, Dounia Lakhmiri, Brian Kahovec, and Dariush Divsalar. ”Automated Data Accountability for Missions in Mars Rover Data.” In 2021 IEEE Aerospace Conference (50100), pp. 1-8. IEEE, 2021.
  * [33] Alimo, Ryan, Pooriya Beyhaghi, and Thomas R. Bewley. ”Delaunay-based derivative-free optimization via global surrogates. Part III: nonconvex constraints.” Journal of Global Optimization (2020): 1-34.

|  Thomas Claudet is in his final year to obtain a double M.S. degree. First,
in Electrical and Computer Engineering at IMT Atlantique, France, specialized
in Robotics. Then, in Mechanical Engineering at the Georgia Institute of
Technology, Atlanta, USA. He is writing a Master’s Thesis for NASA Goddard
Space Flight Center on Safe Planetary Landing using Semantic Segmentation and
Reinforcement Learning. He has been working with the Jet Propulsion Laboratory
as a Visiting Student Researcher on the Stabilization of Planetary-Explorer
Balloons, Deep Space Network Scheduling, Spacecraft Swarm Trajectory
Optimization, and Autonomous Robotics with team CoSTAR (JPL, Caltech, MIT) for
the DARPA subterranean Challenge. He is the Founder, Project Manager, and Lead
Scientist of his CubeSat club.
---|---
|  Ryan Alimo is a data scientist working in machine learning at the Jet
Propulsion Laboratory, California Institute of Technology. Dr. Alimo is
advancing the field of human-AI and multiagent systems using integration of
the optimization algorithms with deep learning and deploying them to
spacecraft formation flying, deep-space communication, and data accountability
for the Mars data.
---|---
|  EDWIN GOH is a data scientist at the Jet Propulsion Laboratory, California
Institute of Technology. His research focuses on the application of machine
learning to enable data-driven design, optimization and operation of aerospace
systems. His work includes DSN scheduling using reinforcement learning,
automated machine learning systems, and radiation-tolerant neuromorphic
computing hardware for deep learning in space. He received his B.S., M.S., and
Ph.D. degrees in Aerospace Engineering from Georgia Tech in 2015, 2017 and
2020, respectively
---|---
|  MARK D. JOHNSTON is a principal engineer at the Jet Propulsion Laboratory,
California Institute of Technology. He currently manages the Deep Space
Network (DSN) Service Management and Operations office, responsible for
planning, scheduling and execution of DSN communications and tracking
services. He has worked on various planning and scheduling technologies for
space projects sponsored by NASA, as well as in commercial domains. His
research interests include reactive planning and scheduling, multi-objective
optimization, and evolutionary algorithms. He holds an A.B. degree summa cum
laude from Princeton University, and a Ph. D. from MIT, both in Physics. He is
the originator of the Spike scheduling system, developed for use on Hubble
Space Telescope, and used on both the Chandra and Spitzer great observatories
as well as various space- and ground-based observatories.
---|---
|  RAMTIN MADANI received the Ph.D. degree in electrical engineering from
Columbia University, New York, NY, USA, in 2015. In 2016, he was a
Postdoctoral Scholar with the Department of Industrial Engineering and
Operations Research, University of California, Berkeley. He is currently an
Assistant Professor with the Department of Electrical Engineering, The
University of Texas at Arlington, Arlington, TX, USA.
---|---
|  BRIAN WILSON is a principal data scientist at the Jet Propulsion
Laboratory, California Institute of Technology. He has had a long career in
GPS technology, ionospheric atmospheric remote sensing, data assimilation,
parallel scientific workflows, semantic eScience, big data map-reduce
computing, and most recently machine learning. Currently, he is the supervisor
of the AI and Analytics Group at JPL, an innovative team of 25 data scientists
who are impossibly young.
---|---