A method of computing globally optimal schedules and plans in the face of possibly temporally varying constraints involves the use of an improved genetic algorithm. The method and computer program are directed toward the eventual use to schedule tasks to be performed on spacecraft.

The main problem in scheduling is to select the order and the starting and ending times of tasks so that they do not violate constraints; among other things, this means that the instantaneous aggregate demands of the tasks must not exceed the available resources (e.g., finite power-generating capacities) and that the tasks must be completed within the allowable time. One can treat a scheduling problem as a global-optimization problem if one embeds resource limits and other constraints into a cost or fitness function. One can then use a genetic algorithm to search the space of potential solutions.

This Heuristic Routine generates feasible solutions for the improved genetic algorithm. This routine has been found to be particularly effective for scheduling tasks subject to resource and time constraints.
The present genetic algorithm incorporates several improvements over a prior algorithm that result in better performance, including higher speed and improved schedules. One improvement is a heuristic routine (see figure) that takes the order of tasks as input and generates the starting times of the tasks as output.

Another improvement is a capability for systematic incorporation of time and task ordering constraints. Specific tasks can now be forced to be performed before, after, or during other tasks, and/or specified absolute times. Time-out and nonoverlap constraints can also be applied. These new time and task ordering constraints are added to the resource constraints that were included in the prior algorithm.

Still another improvement is a capability for adaptive resequencing. In this mode, the genetic algorithm functions in an environment where resource constraints, time constraints, and task priorities can change at any time. Examples have shown that the algorithm works well, even when such changes are made during computation.

This work was done by David Bayard, Hamid Kohen, George Papavassilopoulos, and Il-Jun Jeong of Caltech for NASA's Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.nasatech.com/tsp  under the Information Sciences category.

NPO-20884


This Brief includes a Technical Support Package (TSP).
An Improved Genetic Algorithm for Optimal Spacecraft Scheduling

(reference NPO-20884) is currently available for download from the TSP library.

Don't have an account? Sign up here.



NASA Tech Briefs Magazine

This article first appeared in the October, 2001 issue of NASA Tech Briefs Magazine.

Read more articles from the archives here.