Optimal tool partitioning rules for numerically controlled punch press operations. (English) Zbl 0830.90064

Gaboune, B.; Laporte, G.; Soumis, F.

RAIRO, Rech. Opér. 28, No. 3, 209-220 (1994).

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.

MSC:

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

Keywords:

flexible manufacturing; numerical control machine; shortest path; acyclic graph