METHOD FOR SOLVING PARTIAL CONSTRAINT SATISFACTION PROBLEMS FOR SEQUENCING TASKS

摘要

The present invention provides 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. More specifically, a computer implemented method for generating an optimized sequence of 'N' number of products for manufacture is provided, where said products are of 'M' number of distinct types with a fixed number ('Nt') of each type being desired and each product type comprising an array ('Q') of distinct features, wherein said manufacture is optionally constrained by one or more of the following constraints: the production requirement for each product type, feature-based position equations, and feature-based position inequalities, wherein each of said constraints is individually designated as either a hard constraint which cannot be violated, or as a soft constraint which can be violated at a predetermined cost; said method comprising: generating an initial population of chromosomes, wherein each chromosome represents a feasible sequence of products of various types for manufacture, feasibility depending on satisfaction of all of said hard constraints; associating a fitness value with each chromosome, said fitness value being a function of the predetermined cost associated with the degree of violation of each of said soft constraints; sorting said chromosomes based on the fitness value associated with each chromosome; and applying iteratively to the population of chromosomes a reproductive process, comprising (1) selection of a genetic operator, (2) selection of one or two chromosomes, the number of chromosomes to be selected correlating with the selected genetic operator, (3) application of the selected genetic operator to the selected one or two chromosomes to cause generation of one or two offspring, (4) insertion of one offspring chromosome into the sorted population, and (5) discard of one of the least desirable chromosomes in the population; said iterative process being continuously run until the fitness value for the best chromosome satisfies a known criterion or until a pre-determined time has elapsed.