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.

O problema de corte de estoque em indústrias de móveis de pequeno e médio portes

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Problemas de corte e empacotamento na indústria de móveis: um estudo de caso

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

青藏高原东缘川西云杉林皆伐后灌木生长、繁殖与更新的研究

植物群落及其环境在干扰后的演替格局和过程的研究，是群落和生态系统动态研究的一个热点。选取青藏高原东缘山原区川西云杉林皆伐后，从草地过渡到灌丛的关键阶段的4 个皆伐迹地（恢复时间为8 a、10 a、16 a 和21 a），研究皆伐及自然恢复过程对林下典型灌木银露梅（Potentilla glabra）和唐古特忍冬（Lonicera tangutica）的生长与繁殖能力的影响以及灌木植物在迹地上的更新情况，分析灌木在不同生境中的适应对策和适应能力的差异,为揭示青藏高原东缘山原区迹地植被从草甸到灌丛演替的过程和特点及促进迹地演替与植被恢复进程提供理论依据和技术支撑。研究主要结论如下：1）皆伐后银露梅生长和繁殖能力显著提高，但对唐古特忍冬的影响不明显。皆伐后银露梅丛基径、高度和各部分生物量都显著增加（P < 0.05），但唐古特忍冬只有叶生物量和地下生物量增加，总生物量和其余构件生物量无显著变化。皆伐后，银露梅的结实数量、结实株数、不结实株数和结实株/不结实株比例显著增加（P < 0.05）。自然恢复过程中，银露梅和唐古特忍冬生长能力以及银露梅的结实量都表现出降低的趋势。随着迹地自然恢复时间的增加，银露梅和唐古特忍冬的基径、高度、丛叶片数和各部分生物量有减少的趋势。银露梅的结实株数增加, 但结实数量减少。2）皆伐对银露梅和唐古特忍冬生物量分配模式影响不一致。原始林和迹地中（除CT85）银露梅的生物量大小关系皆为：地下>茎>侧枝>叶。唐古特忍冬在原始林中的生物量大小关系为：茎＞地下部分＞侧枝＞叶,而皆伐后生物量的分配情况改变，生物量大小关系变为：地下部分＞茎＞侧枝＞叶。随着自然恢复时间的增加，银露梅减少了地下生物量的分配，而唐古特忍冬增加了地下生物量的分配。3）皆伐和恢复时间的增加改变了迹地物种组成，促使阳性乔、灌木在迹地上定居。4 个迹地上共出现了灌木15 种，乔木3 种，没有出现天然云杉和冷杉幼苗。随着恢复时间的增加，迹地上的灌木物种由原始林下的耐阴物种逐步发展为以针刺悬钩子（Rubus pungens）为主的阳性灌木。4）影响灌木幼苗密度和幼树密度的因子不一致。灌木幼苗密度与灌木层盖度显著负相关，与苔藓层盖度显著正相关。幼树密度与草本层盖度正相关，与苔藓层盖度、灌木层盖度和高度负相关。5）研究发现在青藏高原东缘山原区皆伐15～20 a 后，迹地仍以草本植物为主，推测皆伐后至少20 a 以上迹地才可能向灌丛阶段过渡，比高山峡谷地区的演替进程至少推迟了20 a。银露梅和唐古特忍冬在皆伐后自然恢复过程中表现出不同的生长与繁殖策略是由两个物种的生物学特性的差异引起的。银露梅比唐古特忍冬更适应迹地退化环境。促进青藏高原东缘山原林区迹地森林恢复一方面是尽量减少人为活动的破坏，另一方面，可以通过在迹地中播种适当的乡土乔、灌木种子（如白桦、银露梅）等人工措施，以加快演替进程。The succession pattern and process of plant community and their environments is a hot spotin community and ecosystem dynamic study. Four clearcuts were chosen in Rangtang(recovery time of 8 a、10 a、16 a and 21 a), which represented the key stage of thecommunity evolved from grass stage to shrub stage in the eastern margin of theQinghai-Tibetan Plateau. The growth and reproduction of the Potentilla glabra andLonicera tangutica and the natural regeneration of shrub plants in the primary Piceabalfouriana forest and 4 clearcuts were studied to explore how clear cutting andnatural recovery process affected the understory shrub species during the 21 years inthe eastern margin of the Qinghai-Tibetan Plateau. The main results were below.1) The growth and reproduction of P. glabra significantly increased after forestclear cutting.. But it was not so significant as to the L. tangutica. The organismbiomass and total biomass of P. glabra were increased obviously after clear cutting（P< 0.05）. But only leaves and underground biomass of L. tangutica increasedsignificantly after clear cutting（P < 0.05）. The number of fruit and growth of P. glabraincreased significantly after clear cutting too（P < 0.05）. The ramet height, basaldiameter , organism biomass and friut number of P. glabra and L. tangutica reducedas the increase of recovery time.2) The biomass allocation patterns varied between P. glabra and L. tangutica inthe primary forest and clearcuts. The biomass allocation of P. glabra both in primary forest and clearcuts was followed as: underground part > stem > branch > leaves.However, the biomass allocation of L. tangutica had changed after the clear cutting.The biomass allocation of L. tangutica in the primary forest was followed as: stem >underground part > branch > leaves and it was underground part > stem > branch >leave in clearcuts. The biomass allocation of P. glabra and L. tangutica varied amongclearcuts. Aboveground biomass was increased while underground biomass decreasedfor P. glabra with the increase of recovery period. However, the L. tangutica showedthe reverse changing pattern.3) Clear cutting and recovery time had changed the species composition of theclearcuts. There were 15.shruby species and 3 tree species in the four clearcuts. Nospruce and fir seedlings were found. In the early stage after clear cutting, there wereonly understory shrub species from the primary Picea balfouriana forest. The sunnyspecies, especieally Rubus pungens invaded intensly as the increase of recovery time.4) There was a significant negative relationship between density of seedlingswith shrub layer coverage and positive correlation with moss coverage. The saplingshad significantly positive correlation with herb layer coverage and negativecorrelation with moss coverage, shrub layer coverage and height.5）Comparing to studies in Miyalou, a nearby high mountain and canyon area,the secondary sucession in this subalpine plateau areas lagged at least 20 years.P. glabra and L. tangutica showed different growth and reproduction strategies toclear cutting and natural recovery , which may associated with the difference of theirbiological characters. P. glabra was more adaptive to the clear cutting than the L.tangutica. Two suggestions were probably recommended to promote the recoveryprogress in the subalpine plateau areas based on the results of this study. Limitanthropogenic disturbance, and meanwhile sow native tree and shrub seeds inclearcuts.

Effect of handpiece tip design on the cutting efficiency of an air abrasion system

Purpose : the aim of this study was to evaluate the effect of nozzle angle and tip diameter on the cutting efficiency of an air abrasion system. Materials and Methods: Thirty-six extracted human third molars were air-abraded with the PrepStar microabrasion machine using a handpiece with either 80degrees or 45degrees nozzle angles with 0.38 or 0.48 nun tip orifice diameters. The following parameters were held constant: abrasive particle size (27 mum), air pressure (80 psi), distance (2 mm.) and duration (15 seconds). The cutting efficiency was compared using enamel, dentin and cementum substrates. Width and depth of the cutting patterns were analyzed and measured using scanning electron micrographs. Results: Statistical analysis using three-way ANOVA and Duncan's Multiple Range test revealed that the width of the cuts was significantly greater when the cavities were prepared using the 45degrees nozzle angle. Significantly deeper cavities were produced with the 80degrees nozzle angle. The tip orifice of the nozzle influenced the cutting efficiency in softer substrates, dentin and cementum. Precise removal of hard tissue is best accomplished using the 80degrees angle nozzle tips for all types of tooth surfaces, enamel, dentin and cementum.

The usable leftover one-dimensional cutting stock problem-a priority-in-use heuristic

We consider a one-dimensional cutting stock problem in which the material not used in the cutting patterns, if large enough, is kept for use in the future. Moreover, it is assumed that leftovers should not remain in stock for a long time, hence, such leftovers have priority-in-use compared to standard objects (objects bought by the industry) in stock. A heuristic procedure is proposed for this problem, and its performance is analyzed by solving randomly generated dynamic instances where successive problems are solved in a time horizon. For each period, new demands arise and a new problem is solved on the basis of the information about the stock of the previous periods (remaining standard objects in the stock) and usable leftovers generated during those previous periods. The computational experiments show that the solutions presented by the proposed heuristic are better than the solutions obtained by other heuristics from the literature. © 2012 The Authors. International Transactions in Operational Research © 2012 International Federation of Operational Research Societies.

Influence of air abrasion tips and operation modes on enamel-cutting characteristics

Objective: To assess the influence of air abrasion tips and system operation modes on enamel cutting. Methods: Forty bovine teeth were abraded with the air abrasion system Mach 4.1 for 10 and 15 seconds, employing conventional and sonic tips of 0.45-mm inner diameter and a 90° angle, and 27.5-μm aluminum oxide at 5.51 bar air pressure in continuous and pulsed modes. The width and depth of the resulting cuts were measured in SEM. Results: The multivariate analysis of variances revealed that, compared to the sonic tip, the conventional tip produced shallower cuts independent of the operation mode and the application period. Conclusions: The cutting patterns observed in this study suggest that the pulsed mode produced deeper cuts when both the conventional and sonic tips were used, and that the sonic tip cut more dental tissue than the conventional one.

A genetic algorithm for the one-dimensional cutting stock problem with setups

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Switching Patterns and Steady-State Analysis of Grid-Connected and Stand-Alone Single-Stage Boost-Inverters for PV Applications

Renewable or sustainable energy (SE) sources have attracted the attention of many countries because the power generated is environmentally friendly, and the sources are not subject to the instability of price and availability. This dissertation presents new trends in the DC-AC converters (inverters) used in renewable energy sources, particularly for photovoltaic (PV) energy systems. A review of the existing technologies is performed for both single-phase and three-phase systems, and the pros and cons of the best candidates are investigated. In many modern energy conversion systems, a DC voltage, which is provided from a SE source or energy storage device, must be boosted and converted to an AC voltage with a fixed amplitude and frequency. A novel switching pattern based on the concept of the conventional space-vector pulse-width-modulated (SVPWM) technique is developed for single-stage, boost-inverters using the topology of current source inverters (CSI). The six main switching states, and two zeros, with three switches conducting at any given instant in conventional SVPWM techniques are modified herein into three charging states and six discharging states with only two switches conducting at any given instant. The charging states are necessary in order to boost the DC input voltage. It is demonstrated that the CSI topology in conjunction with the developed switching pattern is capable of providing the required residential AC voltage from a low DC voltage of one PV panel at its rated power for both linear and nonlinear loads. In a micro-grid, the active and reactive power control and consequently voltage regulation is one of the main requirements. Therefore, the capability of the single-stage boost-inverter in controlling the active power and providing the reactive power is investigated. It is demonstrated that the injected active and reactive power can be independently controlled through two modulation indices introduced in the proposed switching algorithm. The system is capable of injecting a desirable level of reactive power, while the maximum power point tracking (MPPT) dictates the desirable active power. The developed switching pattern is experimentally verified through a laboratory scaled three-phase 200W boost-inverter for both grid-connected and stand-alone cases and the results are presented.

Performance evaluation of a two-stage silica gel plus water adsorption based cooling-cum-desalination system

The first objective of this paper is to show that a single-stage adsorption based cooling-cum-desalination system cannot be used if air cooled heat rejection is used under tropical conditions. This objective is achieved by operating a silica gel + water adsorption chiller first in a single-stage mode and then in a 2-stage mode with 2 beds/stage in each case. The second objective is to improve upon the simulation results obtained earlier by way of empirically describing the thermal wave phenomena during switching of operation of beds between adsorption and desorption and vice versa. Performance indicators, namely, cooling capacity, coefficient of performance and desalinated water output are extracted for various evaporator pressures and half cycle times. The improved simulation model is found to interpret experimental results more closely than the earlier one. Reasons for decline in performance indicators between theoretical and actual scenarios are appraised. (C) 2015 Elsevier Ltd and IIR. All rights reserved.

Guided growth of neurons and glia using microfabricated patterns of parylene-C on a SiO2 background.

This paper describes a simple technique for the patterning of glia and neurons. The integration of neuronal patterning to Multi-Electrode Arrays (MEAs), planar patch clamp and silicon based 'lab on a chip' technologies necessitates the development of a microfabrication-compatible method, which will be reliable and easy to implement. In this study a highly consistent, straightforward and cost effective cell patterning scheme has been developed. It is based on two common ingredients: the polymer parylene-C and horse serum. Parylene-C is deposited and photo-lithographically patterned on silicon oxide (SiO(2)) surfaces. Subsequently, the patterns are activated via immersion in horse serum. Compared to non-activated controls, cells on the treated samples exhibited a significantly higher conformity to underlying parylene stripes. The immersion time of the patterns was reduced from 24 to 3h without compromising the technique. X-ray photoelectron spectroscopy (XPS) analysis of parylene and SiO(2) surfaces before and after immersion in horse serum and gel based eluant analysis suggests that the quantity and conformation of proteins on the parylene and SiO(2) substrates might be responsible for inducing glial and neuronal patterning.

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