Data processing: artificial intelligence – Machine learning – Genetic algorithm and genetic programming system
Reexamination Certificate
1999-12-15
2003-12-09
Starks, Jr., Wilbert L. (Department: 2121)
Data processing: artificial intelligence
Machine learning
Genetic algorithm and genetic programming system
C706S012000, C706S912000
Reexamination Certificate
active
06662167
ABSTRACT:
FIELD OF THE INVENTION
The field of the invention is evolutionary processes; more particularly, the present invention relates to a method utilizing evolutionary processes for solving partial constraint satisfaction problems in order to produce a near-optimal or optimal sequence of products for manufacture.
SUMMARY OF THE INVENTION
The present invention relates to a method for solving partial constraint satisfaction problems, more particularly to a method of sequencing products for manufacture such that the sequence produced is a near-optimal or optimal sequence, meaning that direct cost associated with various labor, processes, and parts inventory are minimized and equipment and floor space utilization are maximized. One application of the method of the present invention is the sequencing of automobiles during manufacturing, in which vehicles are sequenced to go through a series of operations such as body forming, painting, component assembly (such as installing radios, seats, etc.) and final assembly (adding trim and chassis).
BACKGROUND OF THE INVENTION
The sequencing of manufacturing stages or tasks represents a combinatorial, or partial, constraint satisfaction and optimization problem.
As is understood by those skilled in the art, partial constraint satisfaction problems (PCSP's), such as scheduling or sequencing, do not lend themselves easily to automated solving. A solution to a PCSP typically must satisfy a set of hard constraints to be valid or feasible, and must minimize the costs associated with violating one or more conflicting soft constraints (i.e., the solution must present the best trade-off among the conflicting soft constraints). The soft constraints cannot be all completely or simultaneously satisfied in a solution. Thus, each soft constraint is allowed to be violated at a cost (i.e., partially satisfied) and the best solution is a valid solution (i.e., satisfying all hard constraints) which minimizes the costs incurred with violating the soft constraints and the degree of violation thereof.
PCSP's, such as the scheduling (or sequencing) of products for manufacture present a particularly difficult type of problem—a computationally complex problem, referred to as an NP-complete problem (see Garey, M. and Johnson, D. ,
Computers and intractability: a guide to the theory of NP-completeness
, Freeman, 1979.), for which search techniques that deterministically and exhaustively search the space of possibilities fail to generate a viable solution in a realistic time period. For the generic problem of assigning N tasks to M resources with a particular ordering of tasks at each resource, the number of possible solutions is
(
N
+
M
-
1
M
-
1
)
N
!
which implies super-exponential growth as a function of the number of tasks and resources. In addition to sheer size, this search space has a more complex topology than a Euclidean space or, when M >1, a space of permutations.
Exhaustive search (for the best sequence) is impractical for most of the real-world sequencing problems which often have a sequence length ranging from the 100's to the 1000's and are subject to many conflicting constraints. Traditional algorithmic techniques, such as dynamic programming (see Bellman, R. E., and Dreyfus, S. E.,
Applied dynamic programming
, Princeton University Press, 1962), and branch-and-bounds (see Lawler, E. L., and Wood, D. E., “Branch and bounds methods: A survey,”
Operations Research
, 14, 699-719, 1966) fail due to their lack of scalability. The heuristic methods developed to date are complicated by the details of a particular task, and the algorithmic consideration of the specific constraints is embodied in what amounts to a domain specific expert system. Such heuristic techniques are often highly specific to particular application domains and thus are not useful as general techniques for solving PCSP problems.
Real-world scheduling/sequencing problems present special difficulties not found in the less than real-world problems addressed in the art to date. These difficulties include: (1) the size and complexity of the real-world search space, which is far more formidable than the search typically defined in less than real-world problems; (2) the dynamic process inherent in real-world scheduling/sequencing problems (schedules remain valid only for a limited amount of time; after a certain duration, the world generally has changed enough that the scheduling algorithm has to find a different schedule; additionally, there are time constraints on how long it can take to schedule and reschedule that place limits on the amount of computation that can be performed by a scheduling algorithm; and (3) the different domains and applications present in real-world scheduling problems, which require solutions of different variations of the scheduling problem (these variations arise from a number of different sources, including: differences in the types of hard constraints, such as relative and absolute temporal restrictions, and resource capabilities constraints; the need for additional information beyond an ordered assignment of tasks to resources, such as absolute times, routes traveled, and manufacturing plans; and different sets of evaluation criteria, such as cumulative response time, throughput, time span, and cumulative employee satisfaction.) Real-world scheduling/sequencing algorithms thus must be flexible enough to accommodate different conditions and able to adapt to changes.
Evolutionary computation (abbreviated as “EC”), a general, stochastic framework inspired by the intrinsically robust search and optimization paradigms of biological evolution, presents the most promising direction in solving real-world PCSP's. EC algorithms have been applied to many hard optimization problems where classical methods (e.g., gradient search, linear programming, etc.) have failed to provide good solutions. See, e.g.. Back, T., Fogel, D. B., and Michalewicz, Z, eds.,
Handbook of Evolutionary Computation
. New York: Oxford Univ. Press and Institute of Physics, 1997.
All EC algorithms share the same basic high-level philosophy and structure. In any EC algorithm, a “population” of individuals, called “chromosomes,” is maintained. Each chromosome represents a potential solution to the problem to be solved. An “initialization process” is incorporated to create the initial population (i.e., the first generation of chromosomes). A “fitness measure” representing certain optimization criteria is employed to evaluate how fit or optimized each chromosome is, and a “selection process” is used to select chromosomes for “reproduction” based on their fitness values. The reproduction process applies “genetic operators” to the selected chromosomes to create probabilistically perturbed variants, called “offspring,” among which are likely fitter chromosomes. A unary genetic operator alters a (parent) chromosome in some fashion probabilistically, and is called a “mutation.” A binary genetic operator combines probabilistically determined portions of two parent chromosomes to produce two offspring, and is called a “crossover.” The offspring chromosomes are then evaluated by the fitness measure and, based on their values of fitness, are used to replace certain worse chromosomes in the population to form a new generation.
The general EC procedure can be outlined as follows, where t denotes generation index and P(t) denotes the population of chromosomes at t:
Begin
t=0;
Initialization (to create P(t) typically randomly);
Repeat
Fitness evaluation of P(t);
Selection of chromosomes in P(t);
Reproduction to produce a P(t+1);
t=t+1;
Until certain termination condition is satisfied (when t=T)
End.
By repeating the above evaluation-selection-reproduction loop, the population can be “evolved” to fitter populations (Darwinian survival of the fittest). Note that in the process, P(t) remains of the same size, i.e., has the same number of chromosomes. After a certain number of generations (which is either predetermined, or decided based on specified “
Hirl Joseph P.
Kilpatrick & Stockton LLP
Starks, Jr. Wilbert L.
LandOfFree
Method for generating near-optimal sequencing of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for generating near-optimal sequencing of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for generating near-optimal sequencing of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3154967