Sequencing for Concrete Placement Using RAG—CAD Data Structure

Abstract

A 2-1/2–dimensional (2-1/2D) boundary representation CAD data structure called rectangle adjacency graph (RAG) is presented. A review of nondeterministic polynomial (NP) completeness and proof of NP completeness of partition sequencing for a concrete placement process are provided. The proof is obtained by a polynomial transformation of the traveling salesman problem (TSP) which is known to be NP complete. An approximate algorithm that provides the best known ratio bound to TSP has been modified in order to develop a partition-sequencing algorithm that: (1) obtains appropriate cost functions between nonadjacent slabs; and (2) satisfies specific constraints related to concrete placement. The proposed partition-sequencing algorithm includes: (1) generating an appropriate cost function by obtaining the shortest path between each pair of odd-degree vertices in a minimum cost-spanning tree of RAG; (2) transforming the minimum cost-spanning tree of RAG into an Eulerian graph by duplicating edges that correspond to a minimum-cost perfect matching; and (3) conducting an Eulerian tour with an additional constraint of bypassing a vertex when its degree is greater than zero. An example application of the proposed algorithm is provided. The proposed algorithm has been implemented using computer-graphic functional interface standard, PHIGS, with C-program binding.