New and improved results for packing identical unitary radius circles within triangles, rectangles and strips

The focus of study in this paper is the class of packing problems. More specifically, it deals with the placement of a set of N circular items of unitary radius inside an object with the aim of minimizing its dimensions. Differently shaped containers are considered, namely circles, squares, rectangles, strips and triangles. By means of the resolution of non-linear equations systems through the Newton-Raphson method, the herein presented algorithm succeeds in improving the accuracy of previous results attained by continuous optimization approaches up to numerical machine precision. The computer implementation and the data sets are available at http://www.ime.usp.br/similar to egbirgin/packing/. (C) 2009 Elsevier Ltd, All rights reserved.

Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

We investigate several two-dimensional guillotine cutting stock problems and their variants in which orthogonal rotations are allowed. We first present two dynamic programming based algorithms for the Rectangular Knapsack (RK) problem and its variants in which the patterns must be staged. The first algorithm solves the recurrence formula proposed by Beasley; the second algorithm - for staged patterns - also uses a recurrence formula. We show that if the items are not so small compared to the dimensions of the bin, then these algorithms require polynomial time. Using these algorithms we solved all instances of the RK problem found at the OR-LIBRARY, including one for which no optimal solution was known. We also consider the Two-dimensional Cutting Stock problem. We present a column generation based algorithm for this problem that uses the first algorithm above mentioned to generate the columns. We propose two strategies to tackle the residual instances. We also investigate a variant of this problem where the bins have different sizes. At last, we study the Two-dimensional Strip Packing problem. We also present a column generation based algorithm for this problem that uses the second algorithm above mentioned where staged patterns are imposed. In this case we solve instances for two-, three- and four-staged patterns. We report on some computational experiments with the various algorithms we propose in this paper. The results indicate that these algorithms seem to be suitable for solving real-world instances. We give a detailed description (a pseudo-code) of all the algorithms presented here, so that the reader may easily implement these algorithms. (c) 2007 Elsevier B.V. All rights reserved.

Microstructural, Mechanical and Tribological Characterisation of CVD and PVD Coatings for Metal Cutting Applications

The present thesis focuses on characterisation of microstructure and the resulting mechanical and tribological properties of CVD and PVD coatings used in metal cutting applications. These thin and hard coatings are designed to improve the tribological performance of cutting tools which in metal cutting operations may result in improved cutting performance, lower energy consumption, lower production costs and lower impact on the environment.  In order to increase the understanding of the tribological behaviour of the coating systems a number of friction and wear tests have been performed and evaluated by post-test microscopy and surface analysis. Much of the work has focused on coating cohesive and adhesive strength, surface fatigue resistance, abrasive wear resistance and friction and wear behaviour under sliding contact and metal cutting conditions. The results show that the CVD deposition of accurate crystallographic phases, e.g. α-Al2O3 rather than κ-Al2O3, textures and multilayer structures can increase the wear resistance of Al2O3. However, the characteristics of the interfaces, e.g. topography as well as interfacial porosity, have a strong impact on coating adhesion and consequently on the resulting properties.  Through the deposition of well designed bonding and template layer structures the above problems may be eliminated. Also, the presence of macro-particles in PVD coatings may have a significant impact on the interfacial adhesive strength, increasing the tendency to coating spalling and lowering the surface fatigue resistance, as well as increasing the friction in sliding contacts. Finally, the CVD-Al2O3 coating topography influences the contact conditions in sliding as well as in metal cutting. In summary, the work illuminates the importance of understanding the relationships between deposition process parameters, composition and microstructure, resulting properties and tribological performance of CVD and PVD coatings and how this knowledge can be used to develop the coating materials of tomorrow.