NASA Technical Reports Server (NTRS) 19950017327: A format for the interchange of scheduling models

N95- 23747

A Format for the Interchange of Scheduling Models

John P. Jaap & Elizabeth K. Davis

National Aeronautics and Space Administration (NASA)
Marshall Space Flight Center, AL 35812
Phone (205) 544-2226 Fax (205) 544-5873
John.Jaap@msfc.nasa.gov

KEY WORDS AND PHRASES

Activity modeling, activity scheduling,
model interchange, space station.

INTRODUCTION

In recent years a variety of space-activity
schedulers have been developed within the aero-
space community. Space-activity schedulers are
characterized by their need to handle large num-
bers of activities which are time-window con-
strained and make high demands on many
scarce resources, but are minimally constrained
by predecessor/successor requirements or criti-
cal paths.

Two needs to exchange data between these
schedulers have materialized. First, there is sig-
nificant interest in comparing and evaluating the
different scheduling engines to ensure that the
best technology is applied to each scheduling
endeavor. Second, there is a developing re-
quirement to divide a single scheduling task
among different sites, each using a different
scheduler. In fact, the scheduling task for Inter-
national Space Station Alpha (ISSA) will be dis-
tributed between NASA centers and among the
international partners. The format used to in-
terchange scheduling data for ISSA will likely
use a growth version of the format discussed in
this paper.

The model interchange format (or MIF,
pronounced as one syllable) discussed in this
paper is a robust solution to the need to inter-
change scheduling requirements for space ac-
tivities. It is highly extensible, human-readable,
and can be generated or edited with common
text editors. It also serves well the need to sup-
port a "benchmark" data case which can be de-
livered on any computer platform.

FILE FORMAT

The data which is interchanged via the
model interchange format is contained in a data
set or file. When the data is stored in a file on a
platform which supports a file extension as part
of the file name, the extension ".MIF" should
be used.

A MIF file is arranged in lines or records.
Each record contains a single keyword and may
contain data values. Keywords are surrounded
by vertical bars. They are case sensitive and
should not contain characters, such as spaces or
commas, which might be used as input delimit-
ers in common user interfaces.

The information is organized as a hierarchy
in parent, child, sibling relationships. No key-
word can be the same as an ancestor or the sib-
ling of an ancestor. Therefore, on any record, a
keyword which is a child, sibling, ancestor, or
sibling of an ancestor of the keyword of the
previous record may be listed without ambigu-
ity. But, while descending the hierarchy, ances-
tral keywords can not be skipped. To obtain the
full meaning of the data on a record, the key-
word on the record and all keywords (records)
in its ancestry must be considered. The order of
the records in a file is usually significant; arbi-
trary reordering of the information is not al-
lowed.

The file format limits the use of vertical
bars to keywords and disallows the use of the
backslash (\) character throughout. Identifiers
or names cannot contain a comma, parenthesis,
or space. The file format also specifies formats
for the following data types: single integer,
multiple integers including range-of-integers,
real numbers, time expressions, date expres-
sions, and character strings.

369

FILE CONTENTS

At the time of this writing, over 200 key-
words have been defined in three independent
hierarchy structures: a data set description hier-
archy, a mission model hierarchy, and an activ-
ity model hierarchy. Figure 1 shows the logical

File

1 — Data Set Description

| — Mission Model

ata Se

^ — Steps . . .

1 — Sub-steps .

Activitv Model AAA

Steps ...

1 — Sub-steps

Activitv Model UK

Steps . . .

1 — Sub-steps

Figure 1. MIF File Organization.

organization of the file, with hierarchies shown
for the data set description, mission model, and
several activity models.

Data Set Description

The data set description tells what is on the
file, its source, and related data.

Mission Model

The mission model describes the availabili-
ties of the resources for a particular scheduling
task. The following items are included in the
mission model:

• Identifiers and descriptive data.

• Resource availability profiles (including re-
source envelope definitions).

• Equipment reconfiguration data and crew re-
location times.

• Pre-scheduled crew timeline and duty cycle
data.

Activity Models

Activity models are used to describe the
payloads or experiments to be scheduled. Each
payload or experiment requires one or more ac-
tivity models; for complex payloads, an activity
model is usually included for each functional
objective.

An activity model is the collection of con-
straint definitions describing a payload or ex-
periment. Some of the constraints apply to the
model as a whole, while others only apply to the
model partitions, known as steps and sub-steps.

The smallest required, fully functioning,
clearly delineated partition of an activity model
is called a step. The steps of an activity model
describe most of the resource constraints of the
model. Each activity model in a MIF file must
have at least one step.

The optional partition of an activity model
which supports the execution of one or more
steps is called a sub-step. Two classes of sub-
steps are currently defined: crew monitoring
sub-steps and resource carry-through sub-steps.

An execution of an activity model is called a
performance. The performance of an activity
model is generally considered to consist of the
execution of the model’s steps and sub-steps. A
model may be performed multiple times to col-
lect data. Each performance may contain a dif-
ferent set of steps and sub-steps, or they may be
arranged differently when compared to other
performances of the same model. Step-based
schedulers usually require that each perform-
ance contain at least one step.

The model/step/sub-step structure for repre-
senting requirements was chosen because it was
judged to be more robust than other representa-
tions. This representation observes well the ax-
iom that models should exhibit high fidelity and
flexibility; high fidelity means that an observer
can correlate the model to the actual activity;
high flexibility means that the model can repre-
sent the scheduling flexibility of the actual ac-
tivity. The chosen representation also supports
interchanges with schedulers which use models
with requirement profiles attached directly to
the model; in the model interchange format, a
one- step model with requirement profiles on
that step is used.

370

AVAILABILITY

Currently the Mission Planning Division at
the Marshall Space Flight Center is the keeper
of this format. As stated earlier, a growth ver-
sion of this format is expected to be used for in-
terchanging scheduling data for International
Space Station Alpha (ISSA). The current defi-
nition may be superseded by the ISSA defini-
tion, and the ISSA configuration control func-
tion may become the keeper of this format.

Those wishing to have the format extended
should contact the authors of this paper.

Documentation

The complete model interchange format is
available in printed form, or electronically in
PostScript, Bookreader, and possibly World
View formats. Documentation can also be ac-
cessed on the World Wide Web via Mosaic.

Sample Data Cases

Sample files containing the subset of the de-
fined format currently used by Marshall Space
Flight Center are available for several Spacelab
missions and some ISSA data cases.

Software Requirements

Implemented of software which reads a
MIF file should allow for extensions of the for-
mat. Since at some future date new keywords
may be defined, the software should contain
code to ignore unrecognizable keywords. They
must also develop mapping code to convert data
in the MIF representation to their internal repre-
sentation.

Implemented of software which writes a
MIF file must develop mapping code to trans-
late their data to the MIF representation.

SAMPLE MIF DATA

Figure 2 shows part of a two-step activity
model with variable separations and durations.
This figure also shows a sub-step (its keyword is
| -step | ). The sub-step could also have been
positioned before step 1 or after step 2. Repre-
senting the requirements as two steps and a sub-

step is considered a high fidelity representation
because it closely matches the usual description
of the activity. The model has high flexibility
because it captures the variable step separation
and duration, and the choice of crewmembers
for step 2. As shown, the model does not re-

| Model | SEPAC-1

|Comment| Beam firing (low power)

|Partner| USA
jstepl 1

|description| Capacitor charge
jscience_value| 0
jduration| 0:15:00
jnondepletable| POWER
|profile| 2.750
|carry-through|

|sub-step| trickle
|— step[ trickle

|-description| capacitor trickle charge
|-nondepletable| POWER
|— profilel 0.128
|step| 2

|description| Beam Firing (level 1)

| separation |

|min| 0:00:00
|max| 0:30:00
|duration|

|min| 0:10:00
|max| 0:20:00
jpreferred| 0:20:00
|science_value| 4
jcrewlist|

|type| FULLTIME
|pick| 1

|crewmember| PS1
jcrewmemberj PS2
jat_location| MODULE
|crewlist|

|type| FULLTIME
jpick| 1

jcrewmember| Commander
|at_location| MID-DECK
|intersected_opp| SHADOW
|intersected_opp| K-band
|nondepletable| POWER
|profile| 0.500

Figure 2. A Model with Variable Durations.

quire that high power be available immediately
before shadow. The sub- step would not be
scheduled whenever the separation between

371

steps 1 and 2 is zero.

Figure 3 presents part of a one-step activity
model with a power profile (shown in inset).

Figure 3. A Model with a Power Profile.

This type of model would be used in schedulers
which use activity models with requirement pro-
files attached directly to the model. The current
format limits profiles to constant values, ramps,
and step functions.

SUMMARY

The four significant requirements that drove
the formulation of the model interchange format
were that it must be universal, extensible, port-
able, and human-readable. Since this format
was developed chiefly for the interchange of
data, rather than for the storage and manipula-

tion of data within schedulers, these require-
ments were deemed to be more important than
efficiency.

Universality

A format was needed which could be used
by all space-activity schedulers. This format
provides for all known constraints and require-
ments which affect the scheduling of space ac-
tivities. The section entitled "File Contents" in
this paper describes the current contents.

Extensibility

It was necessary that the format be one
which can evolve as new capabilities are added
to existing schedulers and as new schedulers are
developed. This format may be extended by
adding to existing hierarchies; i.e., by defining
new children or siblings at any level. Entirely
new hierarchies may also be defined; this is
equivalent to defining siblings of the highest
level in the current hierarchy.

Portability

Since currently available schedulers are on
different platforms, a format which could be
read or written on any platform was needed. To
this end, the information is stored in a MIF file
as ASCII characters only and is line- or record-
oriented. A benefit of this characteristic is that
the file can be edited with common text editors.

Human-readable

A person can easily read a MIF file or use a
text editor to create/edit one by virtue of the fol-
lowing attributes:

• The syntax is simple. There are a limited
number of rules and special characters.

• A cascading outline hierarchy is used. Each
entry in the hierarchy resides on a separate
line with no other keywords. Ancestry key-
words are not necessarily repeated; the com-
mon conventions for outline presentation are
followed.

• The format is free. Virtually nothing within
a line is positional. The user can indent as
desired to improve readability.

372