Method for generating near-optimal sequencing of manufacturing tasks subject to user-given hard and soft constraints
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06N-003/00
G06N-003/12
G06F-015/18
출원번호
US-0461962
(1999-12-15)
발명자
/ 주소
Xiao, Jing
대리인 / 주소
Kilpatrick Stockton LLP
인용정보
피인용 횟수 :
29인용 특허 :
8
초록▼
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 "
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.
대표청구항▼
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 "
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. 9890400, Humble, 235/383; US-4924363, 19900500, Kornelson, 362/125; US-5172314, 19921200, Poland et al., 364/401; US-5198644, 19930300, Pfeiffer et al., 235/383; US-5382779, 19950100, Gupta, 235/383; US-5448226, 19950900, Failing, Jr. et al., 340/825.35; US-5461561, 19951000, Ackerman et al., 364/401; US-5465085, 19951100, Caldwell et al., 340/825.35; US-5493107, 19960200, Gupta et al., 235/383; US-5572653, 19961100, DeTemple et al., 395/501; US-5583487, 19961200, Ackerman et al., 340/825.35; US-5771005, 19980600, Goodwin, III, 340/825.35; US-5793029, 19980800, Goodwin, III, 235/483; US-5794211, 19980800, Goodwin, 705/023; US-5870714, 19990200, Shetty et al., 705/020; US-5907143, 19990500, Goodwin, III, 235/383; US-5914670, 19990600, Goodwin, III et al., 340/825.52; US-5933813, 19990800, Teicher et al., 705/026; US-5943654, 19990800, Goodwin, III et al., 705/014; US-6012040, 20000100, Goodwin, III, 705/020; US-6047263, 20000400, Goodwin, III, 705/020; US-6073843, 20000600, Goodwin, III et al., 235/383
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (8)
Collins John E. ; Sisley Elizabeth M., Computer implemented system for integrating active and simulated decisionmaking processes.
Chin Goodwin R. ; Dietrich ; Jr. Walter C. ; Ervolina Thomas Robert ; Fasano John Peter ; Poole Elizabeth Jodi ; Tang Jung-Mu, Framework for manufacturing logistics decision support.
McCormack Michael D. (Plano TX) Feldman D. Scott (Anchorage AK) Bowling Chester M. (Evergreen CO), Genetic method of scheduling the delivery of non-uniform inventory.
Santos, Cipriano A.; Sahai, Akhil; Singhal, Sharad; Beyer, Dirk; Zhu, Xiaoyun, Assigning resources to an application component by taking into account an objective function with hard and soft constraints.
McArdle,James Michael, Computer controlled method using genetic algorithms to provide non-deterministic solutions to problems involving physical restraints.
Funes, Pablo; Popovici, Elena; Gaudiano, Paolo; Buchsbaum, Daphna; Garagic, Denis; Ecemis, M. Ihsan; Bingham, Chris; Bonabeau, Eric, Method and system for fast, generic, online and offline, multi-source text analysis and visualization.
Xu, Xiaodong; Tao, Xiaofeng; Wang, Da; Cui, Qimei; Zhang, Ping; Chen, Xin; Wu, Dezhuang, Method for joint optimization of schedule and resource allocation based on the genetic algorithm.
Bonabeau, Eric; Anderson, Carl; Scott, John M.; Budynek, Julien; Malinchik, Sergey, Methods and systems for applying genetic operators to determine system conditions.
Bonabeau, Eric; Anderson, Carl; Scott, John M.; Budynek, Julien; Malinchik, Sergey, Methods and systems for applying genetic operators to determine system conditions.
Bonabeau, Eric; Anderson, Carl; Scott, John M.; Budynek, Julien; Malinchik, Sergey, Methods and systems for applying genetic operators to determine systems conditions.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.