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.

Reliability properties under a stopping time shift

Considering a series representation of a coherent system using a shift transform of the components lifetime T-i, at its critical level Y-i, we study two problems. First, under such a shift transform, we analyse the preservation properties of the non-parametric distribution classes and secondly the association preserving property of the components lifetime under such transformations. (c) 2007 Elsevier B.V. All rights reserved.

Optimization heuristic solutions, how good can they be? : With empirical applications in location problems

Combinatorial optimization problems, are one of the most important types of problems in operational research. Heuristic and metaheuristics algorithms are widely applied to find a good solution. However, a common problem is that these algorithms do not guarantee that the solution will coincide with the optimum and, hence, many solutions to real world OR-problems are afflicted with an uncertainty about the quality of the solution. The main aim of this thesis is to investigate the usability of statistical bounds to evaluate the quality of heuristic solutions applied to large combinatorial problems. The contributions of this thesis are both methodological and empirical. From a methodological point of view, the usefulness of statistical bounds on p-median problems is thoroughly investigated. The statistical bounds have good performance in providing informative quality assessment under appropriate parameter settings. Also, they outperform the commonly used Lagrangian bounds. It is demonstrated that the statistical bounds are shown to be comparable with the deterministic bounds in quadratic assignment problems. As to empirical research, environment pollution has become a worldwide problem, and transportation can cause a great amount of pollution. A new method for calculating and comparing the CO2-emissions of online and brick-and-mortar retailing is proposed. It leads to the conclusion that online retailing has significantly lesser CO2-emissions. Another problem is that the Swedish regional division is under revision and the border effect to public service accessibility is concerned of both residents and politicians. After analysis, it is shown that borders hinder the optimal location of public services and consequently the highest achievable economic and social utility may not be attained.

Essays on decision sciences: exploring cognition, information processing, and complexity

This thesis provides three original contributions to the field of Decision Sciences. The first contribution explores the field of heuristics and biases. New variations of the Cognitive Reflection Test (CRT--a test to measure "the ability or disposition to resist reporting the response that first comes to mind"), are provided. The original CRT (S. Frederick [2005] Journal of Economic Perspectives, v. 19:4, pp.24-42) has items in which the response is immediate--and erroneous. It is shown that by merely varying the numerical parameters of the problems, large deviations in response are found. Not only the final results are affected by the proposed variations, but so is processing fluency. It seems that numbers' magnitudes serve as a cue to activate system-2 type reasoning. The second contribution explores Managerial Algorithmics Theory (M. Moldoveanu [2009] Strategic Management Journal, v. 30, pp. 737-763); an ambitious research program that states that managers display cognitive choices with a "preference towards solving problems of low computational complexity". An empirical test of this hypothesis is conducted, with results showing that this premise is not supported. A number of problems are designed with the intent of testing the predictions from managerial algorithmics against the predictions of cognitive psychology. The results demonstrate (once again) that framing effects profoundly affect choice, and (an original insight) that managers are unable to distinguish computational complexity problem classes. The third contribution explores a new approach to a computationally complex problem in marketing: the shelf space allocation problem (M-H Yang [2001] European Journal of Operational Research, v. 131, pp.107--118). A new representation for a genetic algorithm is developed, and computational experiments demonstrate its feasibility as a practical solution method. These studies lie at the interface of psychology and economics (with bounded rationality and the heuristics and biases programme), psychology, strategy, and computational complexity, and heuristics for computationally hard problems in management science.

A case study approach to classroom experiential learning of problem structuring methods

The proposed research aims at consolidating two years of practical experience in developing a classroom experiential learning pedagogic approach for the problem structuring methods (PSMs) of operational research. The results will be prepared as papers to be submitted, respectively, to the Brazilian ISSS-sponsored system theory conference in São Paulo, and to JORS. These two papers follow the submission (in 2004) of one related paper to JORS which is about to be resubmitted following certain revisions. This first paper draws from the PSM and experiential learning literatures in order to introduce a basic foundation upon which a pedagogic framework for experiential learning of PSMs may be built. It forms, in other words, an integral part of my research in this area. By September, the area of pedagogic approaches to PSM learning will have received its first official attention - at the UK OR Society conference. My research and paper production during July-December, therefore, coincide with an important time in this area, enabling me to form part of the small cohort of published researchers creating the foundations upon which future pedagogic research will build. On the institutional level, such pioneering work also raises the national and international profile of FGVEAESP, making it a reference for future researchers in this area.

Modelo de decisão multicritério para seleções interciclo das universidades novas: estudo na Universidade Federal do Rio Grande do Norte

The discussions wherein develop proposals for university reform in Brazil include, among other things, the conception of the university titled "New University", whose structural origin comes from the bill of higher education reform and unification of the foundations of education European upper (Bologna process). At its core, the Bologna process has imposed a series of transformations, among which, the promotion of mobility, as a stimulus to interinstitutional cooperation to enable an better and bigger qualification of the students. Nevertheless, what we see is that this point is one of the main points made flawed by Brazilian institutions that have adopted this model of higher education. An example is the Bachelor of Science and Technology - BC&T, Federal University of Rio Grande do Norte - UFRN, where there are problems of the internal order, represented by the problem of the reusing of the disciplines, such also of external order, in cases of transfers interinstitutional. Because of this, and knowing that this is a typical problem in which multiple criteria are involved, the aim of this study is to propose a multicriteria model for selection of interciclo of the BC&T of the UFRN which addresses the issue of mobility. For this, this study was of exploratory and study case nature, use as tools of data collection, the bibliographic and documentary research, as well as semi-structured interviews. For the elaboration of the model, were used the five phases most commonly used in the modeling of problems in operational research in a sample of 91 students of BC&T. As a result, we obtained a model that addresses the issue of internal and external mobility of the school and that, moreover, was also more robust and fair than the current model of BC&T and also what is used in other courses of the UFRN, taking into consideration the expected results by the decision makers

Contribuições da pesquisa operacional para gestão da produção e operações : uma análise exploratória da literatura

This research aims to investigate the evolution presented during three decades (1980, 1990 and 2000) of using the tools of Operations Research (OR) as a suport to decision making in Production Operation Management (POM). Hypothesis tests were made to verify the proportional growth of a given area over the decades to the detriment of the areas of facility layout, capacity planning, production scheduling and inventory management. Six journals were selected and from them more than 800 articles were used for classification and analysis in the grounds of review. It also discussed possible ways for future research and comparisons are made with other papers of literature review. As a result, it was found that areas of heuristics and simulation showed a greater quantity of contributions in all POM areas of this study

Distribuição da carga hidráulica em linhas de derivação otimizadas por programação linear

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

A modified Primal-Dual Logarithmic-Barrier Method for solving the Optimal Power Flow problem with discrete and continuous control variables

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

The minimization of open stacks problem: A review of some properties and their use in pre-processing operations

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

Multiobjective 0-1 integer programming for the use of sugarcane residual biomass in energy cogeneration

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

The non-central chi-square chart with two-stage samplings

In this paper, we consider the non-central chi-square chart with two stage samplings. During the first stage, one item of the sample is inspected and, depending on the result, the sampling is either interrupted, or it goes on to the second stage, where the remaining sample items are inspected and the non-central chi-square statistic is computed. The proposed chart is not only more sensitive than the joint (X) over bar and R charts, but operationally simpler too, particularly when appropriate devices, such as go-no-go gauges, can be used to decide if the sampling should go on to the second stage or not. (c) 2004 Elsevier B.V. All rights reserved.

An adaptation of the dual-affine interior point method for the surface flatness problem

This paper presents an adaptation of the dual-affine interior point method for the surface flatness problem. In order to determine how flat a surface is, one should find two parallel planes so that the surface is between them and they are as close together as possible. This problem is equivalent to the problem of solving inconsistent linear systems in terms of Tchebyshev's norm. An algorithm is proposed and results are presented and compared with others published in the literature. (C) 2006 Elsevier B.V. All rights reserved.

An evolutionary algorithm for the one-dimensional cutting stock problem

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

Solution approaches for the soft drink integrated production lot sizing and scheduling problem

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