Data processing: artificial intelligence – Machine learning – Genetic algorithm and genetic programming system
Patent
1997-04-11
1998-12-08
Downs, Robert W.
Data processing: artificial intelligence
Machine learning
Genetic algorithm and genetic programming system
705 8, G06F 1518
Patent
active
058484035
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.
REFERENCES:
patent: 5319781 (1994-06-01), Syswerda
S. Bagchi, et al., "Exploring Problem-Specific Recombination Operators for Job Shop Scheduling", Proceedings of the 4.sup.th Int. Conf. of Genetic Algorithms, 1991.
J. Paredis, "Exploiting Constraints as Background Knowledge for Genetic Algorithms: a Case-study for Scheduling", Parallel Problem Solving from Nature, 2, R. Manner and B. Manderick (Editors), 1992.
H.-L. Fang, et al., "A Promising Genetic Algorithm Approach to Job-Shop Sceduling, Rescheduling, and Open-Shop Scheduling Problems", Proceedings of the Fifth International Conference on Genetic Algorithms, University of Illinois at Urbana-Champaign, Jul. 17-21, 1993.
M.D. Kidwell, et al. "Genetic Algorithm for Dynamic Task Scheduling", Proceedings of the IEEE 13.sup.th Annual International Pheonix Conference on Computers and Communications, Apr. 12-15, 1994.
C.Y. Lee, et al., "A Genetic Algorithm for Job Sequencing Problems with Distinct Due Dates and General Early-Tardy Penalty Weights", Computers Ops. Res. vol. 22, No. 8, pp. 857-869 (1995).
E. Falkenauer and S. Bouffouix, "A Genetic Algorithm for Job Shop," Proc. 1991 IEEE Int'l. Conf. on Robotics and Automation, pp. 824-829, Apr. 1991.
H. Mitra and P. Ramanathan, "Genetic Approach for Scheduling Non-preemptive Tasks with Precedence and Deadline Constraints," Proc. 26th Hawaii Int'l. Conf. on System Sciences, vol. 2, pp. 556-564, Jan. 1993.
G.H. Kim and C.S.G. Lee, "An Evolutionary Approach to the Job-shop Scheduling Problem," 1994 IEEE Int'l. Conf. on Robotics and Automation, pp. 501-506, May 1994.
I. Ahmad, et al., "Task Assignment in Distributed Computing Systems," Proc. Int'l. Phoenix Conf. on Computers and Communications, pp. 49-53, Mar. 1995.
L.-J. Park and C.H. Park, "Genetic algorithm for job shop scheduling problems based on two representational schemes," Electronics Letters, vol. 31, No. 23, pp. 2051-2053, Nov. 1995.
S. Ronald, et al., "Representational Redundancy in Evolutionary Algorithms," IEEE Int'l. Conf. on Evolutionary Computation, vol. 2, pp. 631-636.
I. Ono, et al., "A Genetic Algorithm for Job-shop Scheduling Problems Using Job-based Order Crossover," Proc. 1996 IEEE Int'l. Conf. on Evolutionary Computation, pp. 547-552.
Destefano Joseph J.
Gabriner Daniel C.
Milligan Stephen D.
Montana David J.
BBN Corporation
Downs Robert W.
Suchyta Leonard C.
LandOfFree
System and method for genetic algorithm scheduling systems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for genetic algorithm scheduling systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for genetic algorithm scheduling systems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-190396