2020
Autores
Oliveira, LT; Silva, EF; Oliveira, JF; Bragion Toledo, FMB;
Publicação
COMPUTERS & INDUSTRIAL ENGINEERING
Abstract
The irregular strip packing problem arises in a wide variety of industrial sectors, from garment and footwear to the metal industry, and has a substantial impact in raw-material waste minimization. The goal of this problem is to find a layout for a large object to be cut into smaller pieces. What differentiates this problem from all the other cutting and packing problems, and is its primary source of complexity, is the irregular (non-rectangular) shape of the small pieces. However, in practical applications, after a layout has been determined, a second problem arises: finding the path that the cutting tool has to follow to actually cut the pieces, as previously planned. This second problem is known as the cutting path determination problem. Although the solution of the first problem strongly influences the resolution of the second one, only a few studies are dealing with cutting/packing and cutting path determination together, and, to the best of the authors' knowledge, none of them considers the irregular strip packing problem. In this paper, we propose the first mathematical programming model that integrates the irregular strip packing and the cutting path determination problems. Computational experiments were run to show the correctness of the proposed model and the advantage of tackling the two problems together. Two variants of the cutting path determination problem were considered, the fixed vertex and the free cut models. The strengths and drawbacks of these two variants are also established through computational experiments. Overall, the computational results show that the integration of these problems is advantageous, even if only small instances could be solved to optimality, given that solving to optimality the integrated is at least as difficult as solving each one of the other problems individually. As future research, it should be highlighted that the proposed integrated model is a solid basis for the development of matheuristics aiming at tackling real-world size problems.
2020
Autores
Pedroso, JP;
Publicação
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Abstract
Physical properties of materials are seldom studied in the context of packing problems. In this work we study the behavior of semifluids: materials with particular characteristics that share properties both with solids and with fluids. We describe the importance of some specific semifluids in an industrial context, and propose methods for tackling the problem of packing them, taking into account several practical requirements and physical constraints. The problem dealt with here can be reduced to a variant of two-dimensional knapsack problem with guillotine cuts, where items are splittable in one of the dimensions and the number of cuts is not limited. Although the focus of this paper is on the computation of practical solutions, it also uncovers interesting mathematical properties of this problem, which differentiate it from other packing problems. A thorough computational experiment is used to assess the quality of the approaches proposed, which is analyzed and compared to relevant methods from the literature.
2020
Autores
Neto, T; Constantino, M; Martins, I; Pedroso, JP;
Publicação
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Abstract
While the objectives of forest management vary widely and include the protection of resources in protected forests and nature reserves, the primary objective has often been the production of wood products. However, even in this case, forests play a key role in the conservation of living resources. Constraining the areas of clearcuts contributes to this conservation, but if it is too restrictive, a dispersion of small clearcuts across the forest might occur, and forest fragmentation might be a serious ecological problem. Forest fragmentation leads to habitat loss, not only because the forest area is reduced, but also because the core area of the habitats and the connectivity between them decreases. This study presents a Monte Carlo tree search method to solve a bi-objective harvest scheduling problem with constraints on the clearcut area, total habitat area and total core area inside habitats. The two objectives are the maximization of both the net present value and the probability of connectivity index. The method is presented as an approach to assist the decision maker in estimating efficient alternative solutions and the corresponding trade-offs. This approach was tested with instances for forests ranging from some dozens to over a thousand stands and temporal horizons from three to eight periods. In general, multi-objective Monte Carlo tree search was able to find several efficient alternative solutions in a reasonable time, even for medium and large instances.
2020
Autores
Gleixner, A; Maher, SJ; Mueller, B; Pedroso, JP;
Publicação
ANNALS OF OPERATIONS RESEARCH
Abstract
Packing rings into a minimum number of rectangles is an optimization problem which appears naturally in the logistics operations of the tube industry. It encompasses two major difficulties, namely the positioning of rings in rectangles and the recursive packing of rings into other rings. This problem is known as the Recursive Circle Packing Problem (RCPP). We present the first dedicated method for solving RCPP that provides strong dual bounds based on an exact Dantzig-Wolfe reformulation of a nonconvex mixed-integer nonlinear programming formulation. The key idea of this reformulation is to break symmetry on each recursion level by enumerating one-level packings, i.e., packings of circles into other circles, and by dynamically generating packings of circles into rectangles. We use column generation techniques to design a "price-and-verify" algorithm that solves this reformulation to global optimality. Extensive computational experiments on a large test set show that our method not only computes tight dual bounds, but often produces primal solutions better than those computed by heuristics from the literature.
2020
Autores
Biró, P; Gyetvai, M; Klimentova, X; Pedroso, JP; Pettersson, W; Viana, A;
Publicação
Proceedings of the 34th International ECMS Conference on Modelling and Simulation, ECMS 2020, Wildau, Germany, June 9-12, 2020 [the conference was canceled because of the coronavirus pandemic, the reviewed papers are published in this volume].
Abstract
Following up the proposal of (Klimentova, Viana, Pedroso and Santos 2019), we consider the usage of a compensation scheme for multi-country kidney exchange programmes to balance out the benefits of cooperation. The novelty of our study is to base the target solution on the Shapley value of the corresponding TU-game, rather than on marginal contributions. We compare the long term performances of the above two fairness concepts by conducting simulations on realistically generated kidney exchange pools. © ECMS Mike Steglich, Christian Mueller, Gaby Neumann, Mathias Walther (Editors).
2020
Autores
Biro, P; Gyetvai, M; Klimentova, X; Pedroso, JP; Pettersson, W; Viana, A;
Publicação
ECMS 2020 Proceedings edited by Mike Steglich, Christian Mueller, Gaby Neumann, Mathias Walther
Abstract
The access to the final selection minute is only available to applicants.
Please check the confirmation e-mail of your application to obtain the access code.