Web-Based Request-Oriented Scheduling Engine (ROSE)
Project Number: 02-16
Investigators: John Jaap, Elizabeth Davis, Lea Richardson

Purpose

The purpose of this research is to develop the enabling technologies that will allow new approaches to planning and scheduling space activities.  This technology will have three components: a modeling schema, a scheduling engine, and a system architecture.  The modeling schema must be able to represent all scheduling requirements so that an automatic scheduling engine can produce a satisfactory schedule.  The scheduling engine must be able to correctly schedule all the information in the models.  The architecture must all allow multiple remote users to simultaneously build a single timeline. 

A robust implementation of a ROSE-based system would support multiple simultaneous users, each formulating models (defining scheduling requirements), submitting these models via the internet to a single scheduling engine operating on a single timeline, and immediately viewing the resulting timeline.  ROSE is significantly different from the engines currently in use.  Current engines support essentially one person at a time with a pre-defined set of requirements from many tasks, working in either a "batch" scheduling mode or an interactive/manual scheduling mode.

Background

The Ground Systems Department of the Flight Project Directorate at the Marshall Space Flight Center (MSFC) has 30+ years experience in payload activity planning and scheduling – beginning with Skylab, sixteen Spacelab missions, and continuing with the International Space Station.  Planning for manned space missions has always been labor intensive; during Skylab it was done with charts hand-drawn on paper, now it is done manually with the aid of computer-based timeline editors.  Several “automatic” schedulers have been written, but none have been truly successful.  The objective of this research is to define a scheduling engine that enables the migration to planning and scheduling paradigms which have as their central tenant the use of an automatic scheduler.

The current state of the art in modeling methodologies and scheduling engines results in a linear paradigm with knowledge contributed by task experts, vehicle experts and scheduling engine experts.  This paradigm, depicted in Figure 1, requires significant effort and flow time.  With sufficient software innovations, a modeling methodology could be devised such that the vehicle experts could enter the system and hardware constraints independently of the task knowledge.  The task experts could then enter their requirements directly into the scheduling engine.  A scheduling engine could be built which understands the requirements as presented by the task experts and eliminates the need for scheduling experts.  This paradigm is depicted in Figure 2.

The anticipated results of the ROSE research are a modeling methodology and a scheduling engine that will allow the new paradigm to be implemented.

Approach

Poor modeling is the downfall of automatic scheduling.  If all the requirements are not included in the model, then the scheduler has little chance of producing a satisfactory schedule.  The modeling schema must have an available representation for all the constraints and be friendly enough to allow the user to enter them all without excessive labor.  The scheduling systems currently used in NASA’s manned space flight program cannot capture many of the constraints which describe the operation sequences required to operate the Shuttle or the Space Station, especially those required by the science payloads.  This failure of the modeling schema has begotten the “scheduling cadre,” who digest all the requirements, build the best models allowed by the current schema, make notes containing the remainder of the requirements, and then generate the timeline using a timeline editor.

Evaluate Past and Present Systems—

The team will evaluate past and present planning and scheduling systems.  The investigators of ROSE have first-hand knowledge, as both developers and users, of the scheduling system used for most Spacelab missions.  The investigators have been in direct contact with the designers and users of the system used for the International Space Station (ISS).  The team will evaluate the system to be used by the European Space Agency for their ISS module and the system used by the Jet Propulsion Libratory (JPL) for many of their space missions.

Design and Prototype a New System—

The first task of the ROSE research is to define and prototype a maximally expressive modeling schema which can easily capture all the requirements and constraints.

The second task of the ROSE research is to define and demonstrate a scheduling engine that can schedule the maximally expressive models automatically.

Accomplishments

Evaluations—

One team member visited Deutschen Zentrum für Luft- und Raumfahrt (DLR) in Germany.  A day was devoted to meetings where DLR explained and demonstrated their planning and scheduling tools (entitled Plato and Pinta) to be used for scheduling the activities of the Columbus module of the International Space Station.  The ROSE team obtained and installed Plato and Pinta at MSFC.  Two team members visited JPL’s planning and scheduling team for a one-day meeting to review their scheduling methodology and to solicit comments about the design of our new scheduling algorithm.  A copy, including source code, of their scheduling software, ASPEN, was obtained and reviewed.  The Consolidated Planning System (CPS), developed by the Johnson Space Center (JSC), is used by JSC to schedule shuttle tasks and by MSFC and JSC to schedule ISS tasks.  CPS is locally installed and was reviewed by the team.  Analyzing these tools has affected the ROSE modeling schema and the scheduling algorithm.  In particular, a conversation with Dr. Martin Wickler at DLR was instrumental in the design of our scheduling algorithm.

Web Environment—

The web server environment to support the ROSE research was purchased and set up in March and April of 2002.  The topology is shown in Figure 3.  Two server-class computers were purchased and installed.  Each consists of dual Pentium-III-S processors running at 1.26 gigahertz, two 18-gigabyte SCSI disk drives, and a DVD drive.  One has a CD writer and one has a tape drive.  Both machines are running Windows 2000 server.  One machine is running the Internet Information Services web server software and the other is running Microsoft’s Sequel Server 2000 software.  Development software was purchased for all three team members.

Modeling Schema—

A modeling schema for representing all the requirements of tasks to be scheduled was designed and implemented.  The schema is a synergy of technological advances and domain-specific innovations.  Some of the key features are given below:

• Decomposition of the problem into salient components — Operations are decomposed into activities that define resource requirements and sequences that define relationships between activities.  Sequences can also contain other sequences, repeated activities and sequences, and optional activities and sequences. 
• Graphical paradigms — Simple graphical paradigms such as outlines and networks are used to build and depict the models.  Modeling itself is done using techniques such as drag-and-drop. 
• Modeling equipment modes — Implicit resource requirements are defined by equipment mode models.  This is the mechanism that separates the task models from the hardware/system models.
• Intuitive and rich expression of the relationships between components — The schema employs common-sense representations of temporal relationships using everyday concepts like sequential, during, and overlap.  Innovative enhancements to represent the continuance of resource usage between tasks, the interruption of tasks, minimal percent coverage, and temporal relationships to outside tasks have been added to the modeling schema. 
• Public services — The schema also introduces the concept of public services, models that are scheduled at the request of another model. 

The term “maximally expressive” has been applied to this schema – see published papers in a later paragraph.

Scheduling Engine—

A scheduling algorithm was designed, partially implemented and demonstrated.  The new scheduling algorithm is named Scheduling Algorithm for Temporal Relation Networks (SATRN).  SATRN is an incremental scheduling engine that schedules a request (adding one or more tasks to the timeline) and then waits for the next request.  SATRN converts the temporal relations of a sequence to time bounds on the sequence entities (embedded sequences or activities).  As each entity is scheduled, the bounds on not-scheduled entities are shrunk.  Recursion is used to process embedded sequences.  An activity’s requirements are checked by a depth-first search.  Variable activity durations are utilized to stay within the time bounds.  When an entity cannot be “asserted” (scheduled but not committed to the timeline), already asserted entities are adjusted to free up resources or smart backtracking and reordering is used to unshrink the bounds on the hard-to-schedule entity.  Backtracking is also used to explore alternate requirements. 

End-to-End Demonstration—

An end-to-end demonstration of ROSE was presented to the Flight Projects Directorate management in October of 2003.  This demonstration included using the web-based access to build/edit a model (create a scheduling request), submit it to the remote scheduling engine and display the results.

Spin-off—

The ROSE modeling schema is an evolutionary extension of the modeling schema currently used to collect planning and scheduling requirements for Space Station payloads.  In February 2002, some of modeling enhancements developed for ROSE were implemented in the current Space Station software.

Planned Future Work

Work on the partially-implemented scheduling algorithm is continuing and a paper describing the algorithm will be written.  The ROSE prototype has been re-titled Nexus and features are being added to improve the demonstration.  Figure 4 shows a screen shot from the demonstration.

Demonstration Booth at SpaceOps 2004—

Nexus (ROSE) will be demonstrated in the Ground Systems Department’s booth at the Eighth International Conference on Space Operations in Montréal, Canada, on May 17-20, 2004.  This demonstration will be remotely connected to a host computer at Marshall.

Future Applications—

Nexus (ROSE) is well-suited for use at a lunar base.  The astronauts could use it to schedule their daily activities while controllers on earth could remotely access the base to schedule crew tasks that are essential and to schedule unattended tasks.  The salient features of Nexus that make it suitable for remote usage are:

• Support for virtually simultaneous building of a single timeline by multiple local/remote users.
• The user-friendly interface, maximally expressive modeling and the immediate feedback significantly reduce the time required to learn how to model and schedule.

• Separating tasks modeling from hardware and system modeling allows earth-based controllers and lunar-based astronauts each to contribute their unique knowledge.

These same features also make Nexus well-suited for use on a trans-Mars vehicle and on a Mars base.

Publications and Patent Applications

A paper, entitled “Modeling Complex Operations Sequences,” was presented to the ISOMA 2002, 8th International Symposium on manufacturing and Applications, June 9-13, 2002.  This paper was co-authored by Dr.  John M.  Usher, Mississippi State University and John Jaap.

Abstract— This paper presents a modeling tool that is a part of the Request Oriented Scheduling Engine system being designed at NASA for the scheduling of payload space activities on board the International Space Station.  The resident modeler provides a robust method for easily representing complex sequences of activities for use in planning and scheduling activities.  Although directed toward space activity scheduling, the paper addresses other application areas for this technology.

A paper, entitled “Maximally Expressive Modeling of Operations Tasks,” was presented to the 2003 IEEE Aerospace Conference, March 8-15, 2003.  This paper was co-authored by the members of the research team.

Abstract— Planning and scheduling systems organize "tasks" into a timeline or schedule.  The tasks are defined within the scheduling system in logical containers called models.  The dictionary might define a model of this type as "a system of things and relations satisfying a set of rules that, when applied to the things and relations, produce certainty about the tasks that are being modeled." One challenging domain for a planning and scheduling system is the operation of on-board experiment activities for the Space Station.  In these experiments, the equipment used is among the most complex hardware ever developed, the information sought is at the cutting edge of scientific endeavor, and the procedures are intricate and exacting.  Scheduling is made more difficult by a scarcity of Space Station resources.  The models to be fed into the scheduler must describe both the complexity of the experiments and procedures (to ensure a valid schedule) and the flexibilities of the procedures and the equipment (to effectively utilize available resources).  Clearly, scheduling Space Station experiment operations calls for a "maximally expressive" modeling schema.

A paper entitled “An Enabling Technology for New Planning and Scheduling Paradigms” will be presented to the Eighth International Conference on Space Operations, May 17-21, 2004.  This paper was co-authored by John Jaap, Elizabeth Davis and Patrick Meyer.

Abstract— The Flight Projects Directorate at NASA’s Marshall Space Flight Center is developing a new planning and scheduling environment and a new scheduling algorithm to enable a paradigm shift in planning and scheduling concepts.  The current paradigm starts by collecting the requirements, called “task models,” from the scientists and technologists for the tasks that are to be scheduled.  Next, a cadre with knowledge of vehicle and hardware systems modifies these models to encompass and be compatible with the hardware model.  Finally, the models are modified to be compatible with the scheduling engine.  A future paradigm would provide a scheduling engine that accepts separate science models and hardware models.  The modeling schema would have the capability to represent all the requirements without resorting to notes.  Furthermore, the scheduling engine would not require that the models be modified to account for the capabilities (limitations) of the scheduling engine. 

A paper entitled “Maximally Expressive Modeling” has been submitted to the Fourth International Workshop on Planning and Scheduling for Space, June 23-25, 2004.  This paper was co-authored by the members of the research team. 

A presentation describing a ROSE-based operations concept for Space Station Operations was presented to the Payloads Operations Concept Architecture Assessment Study team, chartered by Headquarters to evaluate the current operations processes for Space Stations Payloads.

ROSE was presented to the MSFC center staff in August, 2003.

The papers and selected presentations are online at http://nexus.msfc.nasa.gov/publications.

Funding Summary ($k)

Status of Investigation

The CDDF is complete.