Title :
A complete complexity study of one-processor assembly and manufacturing planning tasks
Author :
Ramos, Carlos ; Rocha, João ; Vale, Zita
Author_Institution :
Inst. Superior de Engenharia do Porto, Portugal
Abstract :
This paper deals with a method to compute the number of plans that exist for an assembly or processing task. Since planning is a NP-hard problem, the application of some search methods must be avoided. However, up to now, the computation of the exact number of alternative plans for complex tasks and considering precedence constraints has not been performed. It is shown that the complexity of the problem does not depend just on the number of involved operations, components or parts. The complexity of the problem depends on the topology of the precedence between operations
Keywords :
assembly planning; computational complexity; production control; topology; trees (mathematics); NP-hard problem; assembly planning; complex tasks; manufacturing; parse trees; production control; slot block theory; topology; Assembly; Computer aided manufacturing; Explosions; Manufacturing processes; Manufacturing systems; NP-hard problem; Process planning; Pulp manufacturing; Search methods; Topology;
Conference_Titel :
Assembly and Task Planning, 2001, Proceedings of the IEEE International Symposium on
Conference_Location :
Fukuoka
Print_ISBN :
0-7803-7004-X
DOI :
10.1109/ISATP.2001.929057
