System and method for genetic algorithm scheduling systems

• US 5,848,403 A
• Filed: 04/11/1997
• Issued: 12/08/1998
• Est. Priority Date: 10/04/1996
• Status: Expired due to Term

• Current Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.), Raytheon BBN Technlogies Corp. (Rtx Corporation)
• Original Assignee: BBN Corporation (Verizon Communications Inc.)
• Inventors: Milligan, Stephen D., Destefano, Joseph J., Gabriner, Daniel C., Montana, David J.
• Primary Examiner(s): Downs, Robert W.
• Application Number:
  US08/838,914
• Time in Patent Office: 606 Days
• Field of Search: 35/13, 705/8, 706/13
• US Class Current: 706/13
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]

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.

Claims

1. A system for encoding constraint information in a scheduling system running on a computer, said scheduling system for determining a schedule for a plurality of resources to perform a plurality of tasks, said system comprising:

a resource capability indicating component, associated with a resource, said resource capability indicating component indicating at least one capability of said resource;

a task constraint indicating component, associated with a task, said task constraint indicating component indicating at least one constraint requirement of said task;

wherein a comparison of said resource capability indicating component and said task constraint indicating component provides an indication to said scheduling system as to whether said resource associated with said resource capability indicating component has said at least one capability necessary for said at least one constraint requirement of said task associated with said task constraint indicating component.

2. The system of claim 1 wherein said resource capability indicating component includes a bit array.

3. The system of claim 2 wherein said task constraint indicating component includes a bit array.

4. The system of claim 3 wherein said comparison of said resource capability indicating component and said task constraint indicating component includes performing a binary AND operation on said resource bit array and said task bit array.

5. The system of claim 4 wherein said comparison of said resource capability indicating component and said task constraint indicating component includes comparing results of said performance of a binary AND operation with said task bit array.

6. The system of claim 3 wherein a predetermined index in said resource bit array encodes a capability indicator of said resource associated with said resource bit array.

7. The system of claim 6 wherein a predetermined index in said task bit array encodes a constraint indicator of said task associated with said task bit array.

8. The system of claim 7 wherein if said predetermined index in said task bit array and said predetermined index in said resource bit array are equal, said capability indicator matches said constraint indicator.

9. The system of claim 1 wherein said scheduling system running on a computer includes a Genetic Algorithm (GA) scheduling system.

10. A system for encoding constraint information in a genetic algorithm system running on a computer, said genetic algorithm system for determining a schedule for a plurality of resources to perform a plurality of tasks, said system comprising:

a resource bit array, associated with at least one resource, wherein at least one predetermined index into said resource bit array indicates a capability of said at least one resource;

a task bit array, associated with at least one task, wherein at least one predetermined index into said task bit array indicates a constraint of said at least one task; and

wherein a comparison of said resource bit array and said task bit array provides an indication to said genetic algorithm system that said at least one resource associated with said resource bit array can perform said at least one task associated with said task bit array.

11. The system of claim 10 wherein said comparison of said resource bit array and said task bit array includes performing a binary AND operation on said resource bit array and said task bit array.

12. The system of claim 11 wherein said comparison of said resource bit array and said task bit array includes:

comparing results of said binary AND operation on said resource bit array and said task bit array, with said task bit array.

13. The system of claim 10 wherein said task bit array includes a plurality of predetermined indexes, each indicating a constraint.

14. The system of claim 10 wherein said genetic algorithm system assigns a resource associated with said resource bit array to perform a task associated with said task bit array, based on said indication that said resource can perform said task.

15. The system of claim 14 wherein said genetic algorithm system assigns said resource to perform said task by encoding a genome with an indication that said resource will perform said task.

16. In a scheduling system running on a computer, said scheduling system for determining a schedule for a plurality of resources to perform a plurality of tasks, each of said plurality of resources including a plurality of associated cost factors, each associated cost factor including an associated predetermined weight setting, said predetermined weight setting providing an indication of a predetermined importance of said associated cost factor, a method for selecting a resource to perform a task comprising:

selecting one of said associated cost factors;

selecting an unscheduled task from said plurality of tasks;

for each resource in said plurality of resources, producing a cost factor bid for performing said selected task, based on said selected associated cost factor;

selecting a resource for performing said task based on said cost factor bid; and

providing an indication that said selected resource is scheduled to perform said selected task.

17. The method of claim 16 wherein said method for selecting a resource to perform a task is performed for each task of said plurality of tasks, using the said selected associated cost factor.

18. The method of claim 17 wherein said steps are performed a plurality of times to produce a plurality of schedules, wherein each produced schedule is produced with a different selected associated cost factor.

19. The method of claim 16 wherein said step of providing an indication that said selected resource is scheduled to perform said selected task includes encoding said indication that said selected resource is scheduled to perform said selected task into a genome for a Genetic Algorithm (GA) scheduling system.

20. The method of claim 16 wherein said step of selecting one of said associated cost factors includes selecting a plurality of said associated cost factors.

21. The method of claim 16 wherein said step of for each resource in said plurality of resources, producing a cost factor bid for performing said selected task includes the step of:

if a resource in said plurality of resources is unable to perform said selected task, not producing a cost factor bid for performing said selected task.

22. The method of claim 16 wherein said predetermined weight settings for all associated cost factors except for said selected one of said associated cost factors is set to a value of 0.

23. A method for generating a genome for a genetic algorithm system running on a computer, said genetic algorithm system for determining a schedule for a plurality of resources to perform a plurality of tasks, said method comprising:

providing a plurality of predetermined cost factors associated with each resource;

providing a plurality of weight settings corresponding to each of said plurality of predetermined cost factors, said weight settings indicating an importance of said associated cost factor;

selecting an unscheduled task from said plurality of tasks;

for each resource in said plurality of resources, producing a cost factor bid for performing said selected task, based on said selected predetermined cost factors and weight settings;

selecting a resource for performing said task based on said cost factor bid; and

initializing said genome with an indication that said selected resource is scheduled to perform said selected task.

24. The method of claim 23 wherein said method is performed for each task of said plurality of tasks, using said selected associated cost factor.

25. The method of claim 24 further including:

before the step of selecting an unscheduled task from said plurality of tasks, selecting a predetermined cost factor, and setting said associated weight settings to a value of 0 for all weight settings other than the weight setting associated with said selected cost factor.

26. The method of claim 25 wherein said steps for generating a genome are performed a plurality of times to generate a plurality of genomes, wherein a different one of said plurality of associated cost factors is selected for each performance of said steps for generating a genome.

27. The method of claim 24 wherein said method of generating a genome includes inserting said new genome into a genome population for a Generic Algorithm (GA) system which has already evolved said genome population.

28. The method of claim 27 wherein said new genome is generated in response to a change in at least one of said plurality of resources.

29. The method of claim 28 wherein a change in at least one of said plurality of resources includes adding and removing a resource.

30. The method of claim 27 wherein said new genome is generated in response to a change in at least one of said plurality of tasks.

31. The method of claim 30 wherein a change in at least one of said plurality of task includes adding and removing a task.

32. The method of claim 23 wherein said step of for each resource in said plurality of resources, producing a cost factor bid for performing said selected task includes the step of:

if a resource in said plurality of resources is unable to perform said selected task, not producing a cost factor bid for performing said selected task.

33. The method of claim 23 wherein each of said associated weight settings is a number value in the range of 0 and 1.

34. A method for generating a genome for a genetic algorithm system running on a computer, said genetic algorithm system for determining a schedule for a plurality of resources to perform a plurality of tasks, each of said plurality of resources including a plurality of associated cost factors, each cost factor including an associated weight setting, said method comprising:

selecting one of said associated cost factors;

assigning a value of 0 to each weight value associated with each associated cost factor other than said selected cost factor;

selecting an unscheduled task from said plurality of tasks;

for each resource in said plurality of resources, producing a cost factor bid for performing said selected task, based on said associated cost factors and associated weight values;

selecting a resource for performing said task based on said cost factor bid; and

initializing said genome with an indication that said selected resource is scheduled to perform said selected task.

35. A system for producing a population of genomes for a genetic algorithm system running on a computer, said genetic algorithm system for determining a schedule for a plurality of resources to perform a plurality of tasks, each of said plurality of resources including at least one associated cost factor, said system comprising:

a weight setting associated with each of said at least one associated cost factor, said weight setting providing an indication of an importance of said associated cost factor;

a means for calculating resource costs for a selected resource to perform a selected task with based on said associated cost factors and associated weight settings.

36. The system of claim 35 wherein said weight settings are dynamically changed to alter said indication of an importance of said associated cost factor.

37. The system of claim 35 wherein at least one of said plurality of resources or said plurality of tasks changes, and genomes are produced which include said changes.

38. In a Genetic Algorithm scheduling system running on a computer, said Genetic Algorithm scheduling system including a plurality of genomes for determining a schedule for a plurality of resources to perform a plurality of tasks, a method of adding a new task to said plurality of tasks while said genetic algorithm scheduling system is already running, comprising the steps of:

providing a plurality of predetermined cost factors associated with each resource;

providing a plurality of weight settings corresponding to each of said plurality of predetermined cost factors, said weight settings indicating an importance of said associated cost factor;

halting said running genetic algorithm scheduling system;

selecting a genome from said plurality of genomes;

for each resource in said plurality of resources, producing a cost factor bid for performing said new task, based on said selected predetermined cost factors and weight settings;

selecting a resource for performing said task based on said cost factor bid;

encoding said selected genome with an indication that said selected resource is scheduled to perform said new task; and

resume running said Genetic Algorithm scheduling system.

39. The method of claim 38 further including:

encoding all genomes in said plurality of genomes with said indication that said selected resource is scheduled to perform said new task.

40. The method of claim 38 wherein said genome is selected from said plurality of genomes based on a genome fitness evaluation.

41. The method of claim 38 wherein a resource in said plurality of resources becomes unavailable, and all tasks as presently scheduled to be performed by said now unavailable resource are added as new tasks.

42. A method of detecting duplicate genomes in a genetic algorithm system, said method comprising:

decoding first information encoded in a first genome;

converting said first decoded information into a first re-encoded genome;

decoding second information encoded in a second genome;

converting said second decoded information back into a re-encoded second genome; and

comparing said first re-encoded genome and said second re-encoded genome.

43. The method of claim 42 wherein said step of comparing said first re-encoded genome and said second re-encoded genome includes performing a sequential comparison of each element of said first and second re-encoded genomes.

44. The method of claim 42 further including after the step of comparing said first re-encoded genome and said second re-encoded genome, the step of:

if said first re-encoded genome and said second re-encoded genome are equal, eliminating one of said first and second re-encoded genome.