Scheduling Software for Complex Scenarios

Originating Technology/NASA Contribution

Preparing a vehicle and its payload for a single launch is a complex process that involves thousands of operations. Because the equipment and facilities required to carry out these operations are extremely expensive and limited in number, optimal assignment and efficient use are critically important. Overlapping missions that compete for the same resources, ground rules, safety requirements, and the unique needs of processing vehicles and payloads destined for space impose numerous constraints that, when combined, require advanced scheduling.

Traditional scheduling systems use simple algorithms and criteria when selecting activities and assigning resources and times to each activity. Schedules generated by these simple decision rules are, however, frequently far from optimal. To resolve mission-critical scheduling issues and predict possible problem areas, NASA historically relied upon expert human schedulers who used their judgment and experience to determine where things should happen, whether they will happen on time, and whether the requested resources are truly necessary.

Partnership

NASA selected Stottler Henke Associates, Inc., a software design firm with a long history of solving NASA’s unique dilemmas, to capture and encode the knowledge embodied by these human experts. Located in San Mateo, California, the company is a leader in innovative artificial intelligence software applications. For this project, the company was contracted through a Small Business Innovation Research (SBIR) award facilitated by Kennedy Space Center.

As a result of the partnership, Stottler Henke developed Aurora, an intelligent planning and scheduling system that enables NASA to solve complex scheduling problems quickly, by encoding and applying sophisticated, domain-specific decision-making rules.

The proof-of-concept prototype was completed in the summer of 2001, and the Aurora scheduling system entered operational use at Kennedy in late 2003. It is being used to schedule the use of floor space and other resources at the Space Station Processing Facility, where International Space Station components are prepared for space flight. Aurora is also at the core of a system that generates short- and long-term schedules of the ground-based activities that prepare space shuttles before each mission and refurbish them after each mission. This system replaced the Automated Manifest Planner, also developed by Stottler Henke and used by NASA since 1994.

The software Stottler Henke designed for NASA applies a combination of artificial intelligence techniques to produce a system capable of rapidly completing a near-optimal schedule. It combines sophisticated scheduling mechanisms with domain knowledge and a bevy of expert conflict-resolution techniques to solve scheduling problems. It also takes into account a number of problems unique to Kennedy, such as the need to schedule floor space and maintain certain spatial relationships among the tasks and components. Aurora then graphically displays resource use, floor space use, and the spatial relationships among different activities. Scheduling experts can interactively modify and update the schedule, and can request detailed information about specific scheduling decisions. This allows them to supply additional information or verify the system’s decisions and override them, if necessary, to resolve any conflicts.

The company has modified the software and released it as a commercial scheduling tool that is usable in non-NASA situations, allowing the general public to solve a plethora of industry scheduling problems.

Product Outcome

Although there are a number of commercially available scheduling systems, none, according to Stottler Henke, offers all of the features and advantages of Aurora. Furthermore, the degree of domain knowledge required for decisions and the unusual sets of unnatural constraints set by the traditional scheduling software makes them of limited use for truly complex scenarios. The level of complexity the Aurora software was designed to handle, however, is quite useful in a variety of industries. It is practical for solving planning problems for which human expertise can be encoded and applied to generate near-optimal scheduling solutions automatically. It reduces, then, reliance on domain experts, and it changes the scheduling process from a painstaking exercise that takes days and weeks to one that can be accomplished in hours.

It is currently being incorporated into two major systems. One is for the United Space Alliance, LLC, to provide space crews with onboard scheduling capability for the Crew Exploration Vehicle. The second is for a major aircraft manufacturer to help schedule assembly operations of its next-generation airliner.

With Aurora, users can define attributes for individual tasks, groups of tasks, resources, resource sets, and constraints. These attributes can be considered by user-supplied or built-in scheduling decision rules that are invoked at key scheduling decision points within single- or multipass algorithms, such as determining which task to schedule next, selecting the overall best time window and resources, or handling the situation where not all of the required resources are available at the required time. Additional attributes of each resource can be considered when making intelligent resource selection decisions in order to generate schedules that are as close to optimal as possible.

Aurora’s graphical user interface enables users to enter domain-specific knowledge and specify their scheduling requirements quickly and easily. Interactive displays enable users to visualize and edit the schedule’s resource allocations and the temporal relationships among activities. Scheduling problems, such as unresolved conflicts, are highlighted to attract the user’s attention.

Aurora allows users to export reports about resource use, which can then be opened in a standard spreadsheet program. It can also export any of its schedule displays as an image the size of the schedule display itself, allowing the user to include the schedule in presentations or otherwise distribute it. The software can also print any of its schedule displays.

One of the biggest advantages of the Aurora software, though, is that it is cost-efficient. It used to be that, in order for a company to develop a customized scheduling system, the company would have to pay hundreds of thousands or even millions of dollars. Aurora can be customized for far less. It eliminates the need for costly, time-consuming experts and can produce accurate, dependable results.

Aurora™ is a trademark of Stottler Henke Associates, Inc.