zbMATH — the first resource for mathematics

Optimal tool partitioning rules for numerically controlled punch press operations. (English) Zbl 0830.90064
Summary: The purpose of this paper is to formulate and solve an optimization problem arising in the operations of a numerical control machine such as a punch press. Holes of \(n\) different types must be punched by a press on a linear object such as a metallic bar. Each type of hole requires a different tool and tools are mounted on a fixed rotating carousel. Holes are punched in several passes on the bar, using each time a contiguous subset of tools. The problem is to determine a partition of the tools into subsets that will minimize expected completion time. The problem is first formulated as a shortest path problem on an acyclic graph. It is shown how this problem can be solved in \(O(n^2)\) or in \(O(n^3)\) time and that a closed form solution can sometimes be obtained in constant time.

90B30 Production models
90C90 Applications of mathematical programming
90C35 Programming involving graphs or networks
90C60 Abstract computational complexity for mathematical programming problems
Full Text: DOI EuDML