Skip to main content
Internet Archive's 25th Anniversary Logo

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

See other formats


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