DocumentCode
2529888
Title
On the number of linear extensions in a precedence graph
Author
Miller, Joseph M. ; Stockman, George C.
Author_Institution
Dept. of Comput. Sci., Michigan State Univ., East Lansing, MI, USA
fYear
1990
fDate
13-18 May 1990
Firstpage
2136
Abstract
An algorithm that acts as an oracle by estimating the number of sequential orders possible for a set of tasks and precedence constraints is presented. The basic oracle algorithm always completes in low order polynomial time even when there are an exponential number of orders, and it produces an exact answer for graphs with simple folds. The algorithm is applicable to many practical problems in CAPP and should be of value in searching for efficient sequences of operations
Keywords
graph theory; operations research; production control; scheduling; CAPP; linear extensions; precedence constraints; precedence graph; production planning; sequential orders; Artificial intelligence; Assembly; Computer science; Cost function; Data structures; Manufacturing; Polynomials; State estimation; Upper bound;
fLanguage
English
Publisher
ieee
Conference_Titel
Robotics and Automation, 1990. Proceedings., 1990 IEEE International Conference on
Conference_Location
Cincinnati, OH
Print_ISBN
0-8186-9061-5
Type
conf
DOI
10.1109/ROBOT.1990.126320
Filename
126320
Link To Document