Joseph J Destefano

US Patent:

58484035, Dec 8, 1998

Filed:

Apr 11, 1997

Appl. No.:

8/838914

Inventors:

Daniel C. Gabriner - Lexington MA
Stephen D. Milligan - Stow MA
Joseph J. Destefano - Northboro MA
David J. Montana - Arlington MA

Assignee:

BBN Corporation - Cambridge MA

International Classification:

G06F 1518

US Classification:

706 13

Abstract:

An improved Genetic Algorithm scheduling system includes system for encoding and testing hard constraint information. Each resource and task includes an associated capability and constraint indicating component. A comparison of the capability and constraint components provides an indication of the associated resource is capable of perform the proposed task. The system also includes a method of creating genomes using cost factors and weight settings to produce initial genomes which encode at least partly optimized schedules. The weight settings can be manipulated to emphasize different cost factors during genomes creation. This method also allows changes to be added into a running GA scheduling system, in that new or changed tasks and new or changed resources are encoded into the genome population. The system further includes a method of efficiently detecting and deleting duplicate genomes by converting genomes into a schedule representation, then re-encoding the genomes, and performing a sequential comparison of the genomes.