United States Patent 5,319,781

United States Patent	5,319,781
Syswerda	Jun. 7, 1994

Generation of schedules using a genetic procedure

**********************************
This abstract copy is from the USPTO web site. The "hot links" are not "hot" here. To pursue them, go to their web site. A link to their web site is provided in the Patent segment of our "Other Useful Links" section. A full coy of the patent is available for a fee at the Micro Patent web site.
*********************************

Inventors:	Syswerda; Gilbert P. (Winchester, MA).
Assignee:	Bolt Beranek and Newman Inc. (Cambridge, MA).
Appl. No.:	695,311
Filed:	May 3, 1991

Intl. Cl.:	G06F 15/00; G06F 9/00
U.S. Cl.:	395/650; 364/DIG.1; 364/281.8; 364/281.3
Field of Search:	395/650; 364/DIG. 1, 281.3, 281.8

References Cited [Referenced By:]

U.S. Patent Documents

5,148,513

Sept., 1992

Koza et al.

395/ 13

Other References

"A Genetic Algorithm for job shop", Falkenauer, E., and Bouffouix, S., Proc. of 1991 IEEE Int. Conf. on Robotics & Aut. Sacramento, Calif. Apr. 1991, pp. 824-829.

"Efficient Multiprocessor Scheduling Based on Genetic Algorithms", Hou, E. S., Hong, R. and Ansari, N. pp. 1239-1243.

Primary Examiner: Shaw; Gareth D.
Assistant Examiner: Katbab; A.
Attorney, Agent or Firm: Pahl, Jr.; Henry D.

Abstract

In the scheduling method disclosed herein, a genetic algorithm is employed to improve a population of possible schedules represented by respective chromosomes, where the chromosomes upon which the genetic algorithm operates are not a direct encoding of a possible schedules. Rather, the details of the scheduling problem and the real life constraints typically associated with such problems are hidden from the genetic algorithm by the use of a deterministic schedule builder which operates on lists of the desired tasks and which generates legal schedules, i.e. schedules which do not violate hard constraints. The legal schedules so generated are evaluated or scored and the scores are provided to the genetic algorithm as feedback for influencing subsequent operation of the genetic algorithm.

14 Claims, 9 Drawing Figures

Return to Recreational Boat Building Industry Home Page