A Lagrangian relaxation approach to a coupled lot-sizing and cutting stock problem

Industrial production processes involving both lot-sizing and cutting stock problems are common in many industrial settings. However, they are usually treated in a separate way, which could lead to costly production plans. In this paper, a coupled mathematical model is formulated and a heuristic method based on Lagrangian relaxation is proposed. Computational results prove its effectiveness. (C) 2009 Elsevier B.V. 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.

Reservoir Management For Flood And Drought Protection Using Infinite Horizon Model Predictive Control

Model Predictive Control (MPC) is a control method that solves in real time an optimal control problem over a finite horizon. The finiteness of the horizon is both the reason of MPC's success and its main limitation. In operational water resources management, MPC has been in fact successfully employed for controlling systems with a relatively short memory, such as canals, where the horizon length is not an issue. For reservoirs, which have generally a longer memory, MPC applications are presently limited to short term management only. Short term reservoir management can be effectively used to deal with fast process, such as floods, but it is not capable of looking sufficiently ahead to handle long term issues, such as drought. To overcome this limitation, we propose an Infinite Horizon MPC (IH-MPC) solution that is particularly suitable for reservoir management. We propose to structure the input signal by use of orthogonal basis functions, therefore reducing the optimization argument to a finite number of variables, and making the control problem solvable in a reasonable time. We applied this solution for the management of the Manantali Reservoir. Manantali is a yearly reservoir located in Mali, on the Senegal river, affecting water systems of Mali, Senegal, and Mauritania. The long term horizon offered by IH-MPC is necessary to deal with the strongly seasonal climate of the region.

Forecasting multivariate time series under present-value-model short- and long-run co-movement restrictions

It is well known that cointegration between the level of two variables (e.g. prices and dividends) is a necessary condition to assess the empirical validity of a present-value model (PVM) linking them. The work on cointegration,namelyon long-run co-movements, has been so prevalent that it is often over-looked that another necessary condition for the PVM to hold is that the forecast error entailed by the model is orthogonal to the past. This amounts to investigate whether short-run co-movememts steming from common cyclical feature restrictions are also present in such a system. In this paper we test for the presence of such co-movement on long- and short-term interest rates and on price and dividend for the U.S. economy. We focuss on the potential improvement in forecasting accuracies when imposing those two types of restrictions coming from economic theory.

Effects of tributyltin exposure in hermit crabs: Clibanarius vittatus as a model

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

Parametric correlation functions to model the structure of permanent environmental (co)variances in milk yield random regression models

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

Bayesian analysis of random regression models using B-splines to model test-day milk yield of Holstein cattle in Brazil

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Random regression analyses using B-splines functions to model growth from birth to adult age in Canchim cattle

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Random regression analyses using B-spline functions to model growth of Nellore cattle

The objective of this study was to estimate (co)variance components using random regression on B-spline functions to weight records obtained from birth to adulthood. A total of 82 064 weight records of 8145 females obtained from the data bank of the Nellore Breeding Program (PMGRN/Nellore Brazil) which started in 1987, were used. The models included direct additive and maternal genetic effects and animal and maternal permanent environmental effects as random. Contemporary group and dam age at calving (linear and quadratic effect) were included as fixed effects, and orthogonal Legendre polynomials of age (cubic regression) were considered as random covariate. The random effects were modeled using B-spline functions considering linear, quadratic and cubic polynomials for each individual segment. Residual variances were grouped in five age classes. Direct additive genetic and animal permanent environmental effects were modeled using up to seven knots (six segments). A single segment with two knots at the end points of the curve was used for the estimation of maternal genetic and maternal permanent environmental effects. A total of 15 models were studied, with the number of parameters ranging from 17 to 81. The models that used B-splines were compared with multi-trait analyses with nine weight traits and to a random regression model that used orthogonal Legendre polynomials. A model fitting quadratic B-splines, with four knots or three segments for direct additive genetic effect and animal permanent environmental effect and two knots for maternal additive genetic effect and maternal permanent environmental effect, was the most appropriate and parsimonious model to describe the covariance structure of the data. Selection for higher weight, such as at young ages, should be performed taking into account an increase in mature cow weight. Particularly, this is important in most of Nellore beef cattle production systems, where the cow herd is maintained on range conditions. There is limited modification of the growth curve of Nellore cattle with respect to the aim of selecting them for rapid growth at young ages while maintaining constant adult weight.

Random regression models using different functions to model test-day milk yield of Brazilian Holstein cows

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

Effect of amniotic membrane transplantation on corneal healing and proteoglycan expression in an experimental model of limbal deficiency in rabbits

PURPOSE. Amniotic membrane transplantation (AMT) has been used as a graft or as a dressing in ocular surface reconstruction, facilitating epithelization, maintaining normal epithelial phenotype, and reducing inflammation, vascularization, and scarring. The corneal transparency is due, at least in part, to the arrangement in orthogonal lamellae of collagen fibrils, surrounded by proteoglycans (PGs). These PGs regulate fibrilogenesis, the matrix assembly, and ultimately the corneal transparency. The purpose of the present study was to investigate the effects of AMT upon the corneal PGs after severe limbal injury.METHODS. Experiments were performed on the right corneas of 22 New Zealand female albino rabbits, and their left corneas were used as matched controls. These animals were divided into 3 groups: G1 (n = 10): total peritomy and keratolimbectomy, followed by application of 0.5 M NaOH; G2 (n = 10): submitted to the same trauma as G1, and treated by AMT; G3: no trauma, only AMT (n = 2). The right corneas of G2 and G3 were covered by DMSO 4 cryopreserved human amniotic membrane, fixed by interrupted 9-0 mononylon sutures, with its stromal face toward the ocular surface. After 7 or 30 days, the corneas were removed and PGs were extracted.RESULTS. Normal corneas contained approximately 9 mg of PGs per gram of dry tissue. AMT on intact cornea (G3) did not cause any changes in the concentration of PGs. In contrast, injured corneas contained much less PGs, both on the seventh and on the 30th day posttrauma. The PG concentration was even lower in injured corneas treated by AMT. This decrease was due almost exclusively to dermatan sulfate PGs, and the structure of dermatan sulfate was also modified, indicating changes in the biosynthesis patterns.CONCLUSIONS. Although beneficial effects have been observed on clinical observation and concentration of soluble proteins after AMT, the normal PG composition of cornea was not attained, even 30 days postinjury, indicating that the normal ocular surface reconstruction, if possible, is a long-term process. (Eur J Ophthalmol 2010; 20: 290-9)

Attractiveness of copperleaf-based bait to leaf-cutting ants

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

The application of preprocessing and cutting plane techniques for a class of production planning problems

This paper investigates properties of integer programming models for a class of production planning problems. The models are developed within a decision support system to advise a sales team of the products on which to focus their efforts in gaining new orders in the short term. The products generally require processing on several manufacturing cells and involve precedence relationships. The cells are already (partially) committed with products for stock and to satisfy existing orders and therefore only the residual capacities of each cell in each time period of the planning horizon are considered. The determination of production recommendations to the sales team that make use of residual capacities is a nontrivial optimization problem. Solving such models is computationally demanding and techniques for speeding up solution times are highly desirable. An integer programming model is developed and various preprocessing techniques are investigated and evaluated. In addition, a number of cutting plane approaches have been applied. The performance of these approaches which are both general and application specific is examined.

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.

A Lagrangian relaxation approach to a coupled lot-sizing and cutting stock problem

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)