|
|
 |
|
|
|
|
|
Scheduling
Software for Complex Scenarios
Computer Technology
Originating Technology/NASA Contribution
|
Often
considered the most complex machine ever built,
the space shuttle requires intricate planning
and scheduling to prepare for launch. Pictured
here is the Space Shuttle Columbia on April 12,
1981, preparing for the very first shuttle launch. |
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.
|
On
June 16, 2005, the Space Shuttle Discovery rested
on a mobile launcher platform that sat atop a
crawler-transporter, on its way to Launch Pad
39B, while the canister that delivered the mission
STS-114 payloads to the launch pad departed. |
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.
|
|
|
|
