System and method for genetic algorithm scheduling systems

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.

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.

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.

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.

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.

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.