ESP: Automatic Scheduler

Once all the data was collected into the Model Editor and the Opportunity Editor, mission planners were ready to use the scheduling software to automatically generate a timeline.

ESP built timelines incrementally by adding one performance (occurrence) of an activity at a time.  ESP took the select-and-load approach by first selecting the activity to schedule and the adding it to the timeline (see figure below).
 

One might assume that this approach is "forward-marching" (beginning at the start time and moving to the end time). However it is not; the scheduler intentionally "scatters" the activities on the timeline.  It does the in order to meet requirements placed on the activities, such as delays between performances, requirements for specified time constraints and others.

The algorithm for determining where an activity fits was quite robust. However, it did not have the ability to remove an already-scheduled performance from the timeline nor did it anticipate what will be selected next for scheduling.

The selection order determined the resulting timeline, and changing the order was the only way to vary a timeline (without changing the activity requirements). The user had extensive control of the selection order. The activities to be scheduled could be divided into groups, the groups could be reordered, one of 5 available selection methods could be assigned to each group, and a scheduling window assigned for each group. One option allowed the user to specify a random selection and to request that multiple timelines be produced. The scheduler provided a basic grading scheme to compare or evaluate the results.

Grading Scheme

The grade of schedule in ESP was computed by using a weighted equation. The user controlled the weights (W's ranging from 0 to 100) in the equation. Then, the equation was normalized; i.e., the top grade is nominally 100%. The grade could exceed 100% because the requested usage was based on the minimum step durations and the schedule times were the actual times -- these may have differed when a model allowed a variable step duration.

The equation for grade was:

GRADE = 100 (W_pP + W_mM + W_cC + W_tT + W_aA)  / (W_p + W_m + W_c + W_t + W_a)

P = Number of performances scheduled / number requested
M = Number of models scheduled / number requested
C = Crew time (excluding desired monitoring) / minimum requested
T = Experiment operation time / minimum requested

A = (a₁ + a₂ + a₃ + ... a_i) / n

a_i = number of performances scheduled / number requested
n = number of models requested

Timeline Import and Merge

Import was used to load previously generated schedule into ESP. When using import the user specified the window, the activity models to exclude, the starting point for the import, and (if desired) crew reassignments.

Since the import takes the usage of resources (consumables, nondepletables and equipment) from the model file, the latest information would be incorporated into the timeline.

Import was used two ways.

• Schedules from previous runs of ESP could be reloaded for additional development.
• Multiple timelines could be merged. This was done by choosing a starting point which already had a schedule in it. When merging, the program checked for double booking of a crew member and allowed the user to fix it. It prevented overlapping performances of the same model, but no other validation checks were made; the timeline validation was used for other checks.

Checkpoint Manager

During an ESP session a mission planner would usually checkpoint and restart several times. A checkpoint was an internally-saved timeline; restarting meant starting from a previous checkpoint. Of course, the same thing could be done by saving the timeline to a file and then importing the file into an empty starting point. Check-pointing and restarting was much faster than saving and importing.

Overview of Scheduling Process

The constraint checking process of ESP was based on calculating windows which were nested in a hierarchy such that each lower window was totally contained within the window above it. At each level of hierarchy, a window could contain many windows at the next lower level, and each of these could contain many windows. Checking of constraints began at the topmost window and proceeded downward and across. When an acceptable window was found, checking proceeded immediately to the next lower level. If, at any level, an acceptable window could not be found, the window above it is "failed", and the next window at the level of the failed window was defined. This technique is called "depth-first searching." Checking was successfully completed whenever an acceptable window was found at the bottom level. Checking failed whenever another window at the top level could not be defined. Models with mandatory concurrence were processed simultaneously.

ESP dynamically changed its interpretation of the requirements: whenever maximizing fails, minimizing was attempted; whenever the crew group chosen for a lock-in sequence was not available for a later step in the sequence, a different crew group was chosen.

The windows for each model were independently nested; i.e., the performance sub-window for the selected model was nested within the performance window for the selected model, but is not nested within any of the windows for the promoted model. The windows for each step were also independently nested; i.e., the crew sub-window for step 5 of a model was nested within the nondepletable/equipment sub-window for step 5, but was not nested within any of the windows for the other steps on that model. The performance level windows for the selected and promoted models had to overlap each other sufficiently in order to meet mandatory concurrence requirements. If a model or step did not have a requirement, the associated window was set equal to the next higher level window; for example, if there were no sequencing requirements, the sequencing sub-window were set equal to the performance sub-window. The definitions of the windows are given below.

• Macro-window - calculated by the selection method to efficiently place a performance. The current selection methods set this equal to the scheduling window. When using the generate command, the user specifies the macro-window.
• Performance Window - performance time window from model.
• Performance Sub-window - ensures that performance delays are met.
• Sequencing Sub-window - ensures that sequencing delays are met.
• Mandatory Concurrence Time Frame - ensures that steps with mandatory concurrence start together.
• Step Window - considers step delays and leaves time for steps not yet checked.
• Non-mandatory Concurrence Sub-window - ensures that steps with necessary or desired concurrence start together.
• Selected/avoided Opportunity Sub-window - ensures that selected or avoided orbit opportunity requirements are met.
• Intersected Opportunity Sub-window - ensures that intersected orbit opportunity requirements are met.
• Nondepletable Resource and Equipment Sub-window - ensures that nondepletable and equipment requirements (including tolerance, but not carry-through) are met.
• Crew Sub-window - ensures that full-time crew is available.