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(n2) or in O(n3) time and that a closed form solution can sometimes be obtained in constant time. Numero: G-91-48 Prix: 2,26 Auteurs: Hansen, P., Jaumard, B., Xiong, J. Titre: The Cord-Slope Form of Taylor's Expansion in Univariate Global Optimization Date: novembre 1991 Pages: 21 Journal: Journal of Optimization Theory and Applications, 80(3):441-464, 1994. Abstract: Interval arithmetic and Taylor's formula can be used to bound the slope of the cord of a univariate function at a given point. Such bounds for the function, it's first derivative and second derivative allow to determine intervals in which this function cannot have a global minimum. Exploiting this information together with a simple branching rule yields an efficient algorithm for global minimization of univariate functions. Computational experience is reported on.
Published November 1991 , 15 pages
This cahier was revised in November 1993