US5848403A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for genetic algorithm scheduling systems
Assignee: Level 3 Communications LLC
•
Filing: 1997-04-11
•
Granted: 1998-12-08
•
Expires: 2017-04-11
Abstract
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.
Inventors
- 👤 Daniel C. Gabriner
- 👤 Stephen D. Milligan
- 👤 Joseph J. DeStefano
- 👤 David J. Montana
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 22:57
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/50
Claims Analysis
Total Claims: 52
Claim 1
Independent Claim
138 words
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.
Claim 2
Independent Claim
138 words
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.
Claim 3
Dependent Claim
15 words
The system of claim 1 wherein said resource capability indicating component includes a bit array.
Claim 4
Dependent Claim
15 words
The system of claim 2 wherein said task constraint indicating component includes a bit array.
Claim 5
Dependent Claim
36 words
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.
Claim 6
Dependent Claim
36 words
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.
Claim 7
Dependent Claim
27 words
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.
Claim 8
Dependent Claim
27 words
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.
Claim 9
Dependent Claim
33 words
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.
Claim 10
Dependent Claim
20 words
The system of claim 1 wherein said scheduling system running on a computer includes a Genetic Algorithm (GA) scheduling system.
Claim 11
Independent Claim
144 words
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.
Claim 12
Independent Claim
144 words
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.
Claim 13
Dependent Claim
34 words
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.
Claim 14
Dependent Claim
41 words
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.
Claim 15
Dependent Claim
20 words
The system of claim 10 wherein said task bit array includes a plurality of predetermined indexes, each indicating a constraint.
Claim 16
Dependent Claim
40 words
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.
Claim 17
Dependent Claim
31 words
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.
Claim 18
Dependent Claim
145 words
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.
Claim 19
Dependent Claim
145 words
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.
Claim 20
Dependent Claim
33 words
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.
Claim 21
Dependent Claim
33 words
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.
Claim 22
Dependent Claim
48 words
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.
Claim 23
Dependent Claim
25 words
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.
Claim 24
Dependent Claim
57 words
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.
Claim 25
Dependent Claim
32 words
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.
Claim 26
Independent Claim
143 words
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.
Claim 27
Independent Claim
143 words
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.
Claim 28
Dependent Claim
24 words
The method of claim 23 wherein said method is performed for each task of said plurality of tasks, using said selected associated cost factor.
Claim 29
Dependent Claim
51 words
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.
Claim 30
Dependent Claim
47 words
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.
Claim 31
Dependent Claim
34 words
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.
Claim 32
Dependent Claim
25 words
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.
Claim 33
Dependent Claim
23 words
The method of claim 28 wherein a change in at least one of said plurality of resources includes adding and removing a resource.
Claim 34
Dependent Claim
25 words
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.
Claim 35
Dependent Claim
23 words
The method of claim 30 wherein a change in at least one of said plurality of task includes adding and removing a task.
Claim 36
Dependent Claim
57 words
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.
Claim 37
Dependent Claim
23 words
The method of claim 23 wherein each of said associated weight settings is a number value in the range of 0 and 1.
Claim 38
Independent Claim
154 words
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.
Claim 39
Independent Claim
154 words
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.
Claim 40
Independent Claim
106 words
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.
Claim 41
Independent Claim
106 words
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.
Claim 42
Dependent Claim
24 words
The system of claim 35 wherein said weight settings are dynamically changed to alter said indication of an importance of said associated cost factor.
Claim 43
Dependent Claim
28 words
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.
Claim 44
Dependent Claim
180 words
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.
Claim 45
Dependent Claim
180 words
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.
Claim 46
Dependent Claim
29 words
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.
Claim 47
Dependent Claim
21 words
The method of claim 38 wherein said genome is selected from said plurality of genomes based on a genome fitness evaluation.
Claim 48
Dependent Claim
34 words
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.
Claim 49
Independent Claim
62 words
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.
Claim 50
Independent Claim
62 words
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.
Claim 51
Dependent Claim
34 words
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.
Claim 52
Dependent Claim
45 words
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.
References Cited (Backward Citations)
US5319781A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-12-07 | 2002-06-08 | 2002-12-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-12-07 | 2006-06-08 | 2006-12-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-12-07 | 2010-06-08 | 2010-12-08 | $7700.00 | Window Closed / Lapsed |