Mathematical Models of Placement Optimisation: Two- and Three-Dimensional Problems and Applications
We study NP-hard placement optimisation problems, which cover a wide spectrum of industrial applications, including space engineering. This chapter considers tools of mathematical modelling and a solution strategy of placement problems illustrated with ex
- PDF / 888,373 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 48 Downloads / 177 Views
Mathematical Models of Placement Optimisation: Two- and Three-Dimensional Problems and Applications Yuri Stoyan and Tatiana Romanova
Abstract We study NP-hard placement optimisation problems, which cover a wide spectrum of industrial applications, including space engineering. This chapter considers tools of mathematical modelling and a solution strategy of placement problems illustrated with examples and pictures. A class of 2D and 3D geometric objects, called phi-objects, is introduced and considered as mathematical models of real objects. We review the main concept of our studies, i.e. phi-functions. One may also find a clear definition of phi-function as an analytical tool for describing placement constraints, including containment, non-overlapping, allowable distances, prohibited areas, object translations and rotations. A mathematical model of a basic placement problem is constructed as constrained optimisation problem. We propose a solution strategy for placement problems. The reader will get acquainted with an application problem of the basic placement problem encountered in space engineering and find a number of computational results for 2D and 3D applications. Keywords Mathematical modelling • Packing and cutting • Phi-functions • Optimisation
15.1
Introduction
The placement problems in question, being a part of operational research and computational geometry, have multiple 2D and 3D applications. They can extensively be used in garment industry, sheet metal cutting, furniture making, shoe manufacturing for 2D case. Other engineering applications involve 3D geometry:
Y. Stoyan (*) • T. Romanova Department of Mathematical Modeling, Institute for Mechanical Engineering Problems of the National Academy of Sciences of Ukraine, Kharkov, Ukraine e-mail: [email protected] G. Fasano and J.D. Pinte´r (eds.), Modeling and Optimization in Space Engineering, Springer Optimization and Its Applications 73, DOI 10.1007/978-1-4614-4469-5_15, # Springer Science+Business Media New York 2013
363
364
Y. Stoyan and T. Romanova
space engineering, mechanical engineering, car manufacturing, shipbuilding, 3D laser cutting, modelling granular media and liquids, radio-surgery treatment planning, medicine, materials science, nanotechnology, robotics, coding, pattern recognition systems, control systems, space apparatus control systems, etc. The common placement problem lies in arranging a given set of objects within a given region (a container) in order to minimise waste of industrial materials, to minimise the use of space or maximise the number of objects, to minimise deviation from the centre of gravity, etc. In spite of the variety of practical and scientific applications, the placement problems may be reduced to the following basic placement optimisation problem. Basic Problem Place a set of geometric objects (from now on simply: objects) Ti, i 2 f1; 2; :::; ng ¼ In into a container O, so that the given restrictions on the placement of the objects are fulfilled and the given objective function reaches its extreme value
Data Loading...
