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.

A linear optimization approach to the combined production planning model

Two fundamental processes usually arise in the production planning of many industries. The first one consists of deciding how many final products of each type have to be produced in each period of a planning horizon, the well-known lot sizing problem. The other process consists of cutting raw materials in stock in order to produce smaller parts used in the assembly of final products, the well-studied cutting stock problem. In this paper the decision variables of these two problems are dependent of each other in order to obtain a global optimum solution. Setups that are typically present in lot sizing problems are relaxed together with integer frequencies of cutting patterns in the cutting problem. Therefore, a large scale linear optimizations problem arises, which is exactly solved by a column generated technique. It is worth noting that this new combined problem still takes the trade-off between storage costs (for final products and the parts) and trim losses (in the cutting process). We present some sets of computational tests, analyzed over three different scenarios. These results show that, by combining the problems and using an exact method, it is possible to obtain significant gains when compared to the usual industrial practice, which solve them in sequence. (C) 2010 The Franklin Institute. Published by Elsevier Ltd. All rights reserved.

An effective recursive partitioning approach for the packing of identical rectangles in a rectangle

In this work, we deal with the problem of packing (orthogonally and without overlapping) identical rectangles in a rectangle. This problem appears in different logistics settings, such as the loading of boxes on pallets, the arrangements of pallets in trucks and the stowing of cargo in ships. We present a recursive partitioning approach combining improved versions of a recursive five-block heuristic and an L-approach for packing rectangles into larger rectangles and L-shaped pieces. The combined approach is able to rapidly find the optimal solutions of all instances of the pallet loading problem sets Cover I and II (more than 50 000 instances). It is also effective for solving the instances of problem set Cover III (almost 100 000 instances) and practical examples of a woodpulp stowage problem, if compared to other methods from the literature. Some theoretical results are also discussed and, based on them, efficient computer implementations are introduced. The computer implementation and the data sets are available for benchmarking purposes. Journal of the Operational Research Society (2010) 61, 306-320. doi: 10.1057/jors.2008.141 Published online 4 February 2009

Orthogonal packing of identical rectangles within isotropic convex regions

A mixed integer continuous nonlinear model and a solution method for the problem of orthogonally packing identical rectangles within an arbitrary convex region are introduced in the present work. The convex region is assumed to be made of an isotropic material in such a way that arbitrary rotations of the items, preserving the orthogonality constraint, are allowed. The solution method is based on a combination of branch and bound and active-set strategies for bound-constrained minimization of smooth functions. Numerical results show the reliability of the presented approach. (C) 2010 Elsevier Ltd. All rights reserved.

Rural property size drives patterns of upland and riparian forest retention in a tropical deforestation frontier

Deforestation in Brazilian Amazonia accounts for a disproportionate global scale fraction of both carbon emissions from biomass burning and biodiversity erosion through habitat loss. Here we use field- and remote-sensing data to examine the effects of private landholding size on the amount and type of forest cover retained within economically active rural properties in an aging southern Amazonian deforestation frontier. Data on both upland and riparian forest cover from a survey of 300 rural properties indicated that 49.4% (SD = 29.0%) of the total forest cover was maintained as of 2007. and that property size is a key regional-scale determinant of patterns of deforestation and land-use change. Small properties (<= 150 ha) retained a lower proportion of forest (20.7%, SD = 17.6) than did large properties (>150 ha; 55.6%, SD = 27.2). Generalized linear models showed that property size had a positive effect on remaining areas of both upland and total forest cover. Using a Landsat time-series, the age of first clear-cutting that could be mapped within the boundaries of each property had a negative effect on the proportion of upland, riparian, and total forest cover retained. Based on these data, we show contrasts in land-use strategies between smallholders and largeholders, as well as differences in compliance with legal requirements in relation to minimum forest cover set-asides within private landholdings. This suggests that property size structure must be explicitly considered in landscape-scale conservation planning initiatives guiding agro-pastoral frontier expansion into remaining areas of tropical forest. (C) 2010 Elsevier Ltd. All rights reserved.

Expression Patterns of Cell Adhesion Molecules in Mice`s Lung After Administration of Meso-2,3-Dimercaptosuccinic Acid-Coated Maghemite Nanoparticles

We studied the expression pattern of cell adhesion molecules associated to transendothelial migration of leukocytes in different lung`s vascular compartments after administration of a magnetic fluid sample containing maghemite nanoparticles surface-coated with meso-2,3-dimercaptosuccinic acid. The analyses were conducted in mice 4 and 12 h after endovenous administration of the magnetic fluid in control mice. Firstly, the migratory activity of leukocytes after magnetic fluid surface-coated with meso-2,3-dimercaptosuccinic acid administration was confirmed using broncho-alveolar lavage and light microscopy. Then, the expression of cell adhesion molecules in the lung`s vascular compartments was investigated by immunofluorescence microscopy of frozen sections, using antibodies against L-selectin, P-selectin, E-selectin, macrophage antigen-1, and leukocyte function associated antigen-1. L- and P-selectin showed similar pattern of expression in the pulmonary vasculature in animals treated with magnetic fluid and in the control group. In contrast, macrophage antigen-1 and leukocyte function associated antigen-1 were found in capillary only in animals treated with magnetic fluid surface-coated with meso-2,3-dimercaptosuccinic acid administration. In addition, after magnetic fluid administration E-selectin was found in post-capillary sites. Our findings demonstrated that magnetic fluid surface-coated with meso-2,3-dimercaptosuccinic acid administration exhibits modulation effects on expression patterns of E-selectin, macrophage antigen-1, and leukocyte function associated antigen-1 in the lung`s vascular compartments. These findings are very important in a strategy to reduce the potential toxicity of magnetic fluid surface-coated with meso-2,3-dimercaptosuccinic acid administration for medical applications.

Hydrogen peroxide and supercritical carbon dioxide: a new bleaching stage for Eucalyptus kraft-O(2) pulps

Kraft pulp is currently bleached largely by the elemental chlorine free (ECF) technology with oxygen, chlorine dioxide, and hydrogen as active agents. This technology brought about significant environmental improvements in relation to standard processes based on chlorine gas and hypochlorite, but there is still need for further improvements. This study presents a novel environmentally friendly bleaching stage - the so-called `hydrogen peroxide in supercritical carbon dioxide`, P((SC-CO2)) - that can be adapted to current ECF bleaching processes, with preference in cases where hydrogen peroxide is already used. In this study, the P((SC-CO2)) stage was evaluated as a replacement to the last peroxide stage of the D(EP)DP bleaching sequence and to the first peroxide stage of the D(EP)DP sequence, for an oxygen delignified eucalypt kraft-O(2) pulp. The P((SC-CO2)) stage was run with 0.5% hydrogen peroxide, at 15% consistency, 70 degrees C, and 73 bar. The reaction time was 30 min. The performances of regular P stages and the new P((SC-CO2)) stage were compared. Promising results were observed with the DEP((SC-CO2))DP sequence; the P((SC-CO2)) decreased kappa number from 2.7 to 2.1, and the hexenuronic acid groups from 17.0 to 12.4 mmol kg(-1). The P((SC-CO2)) stage showed poor performance when applied in the D(EP)DP((SC-CO2)) sequence. It is concluded that the process presents potential but requires further optimization to improve selectivity and efficiency.

An insight into the beginning stage of the aqueous ring opening metathesis polymerization of exo,exo-7-oxabicyclo[2.2.1]hept-5-ene-2,3-dicarboxylic acid with Ru(III) compounds: the consumption of Ru(III) species in the presence of carboxylic acids monitored by ESR spectroscopy

The presence of paramagnetic species in the aqueous ring opening metathesis polymerizations of the exo,exo-7-oxabicyclo[2.2.1]hept-5-ene-2,3-dicarboxylic acid monomer with RuCl(3) and K(2)[RuCl(5)H(2)O] compounds was studied using ESR techniques. It was observed that the intensities of the Ru(III) signals in the ESR spectra decrease on the time scale of the induction period so that the ROMP can take place. The intensity of the Ru(III) signal almost disappeared 50 min after reacting with K(2)[RuCl(5)H(2)O] and after 100 mm in the case of RuCl(3). Reactions of the cis-[Ru(NH(3))(4)(H(2)O)(2)](tfms)(3) and [Ru(NH(3))(5)H(2)O](tfms)(3) complexes with the monomer and different organic compounds representing the organic functions in the monomer (furan, norbornene, but-2-ene-1,4-diol and formic, acetic, oxalic and maleic acids) were also monitored by ESR and UV/vis spectra. It was deduced that the organic acids provide the disappearance of the Ru(III) signal. The proton NMR relaxation times of the residual water in D(2)O for reactions with oxalic acid suggested that the presence of paramagnetic ions in the solution decreases along with