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
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;
Conference_Titel :
Robotics and Automation, 1990. Proceedings., 1990 IEEE International Conference on
Conference_Location :
Cincinnati, OH
Print_ISBN :
0-8186-9061-5
DOI :
10.1109/ROBOT.1990.126320
