Approaches to real world two-dimensional cutting problems
| Autor: | Paolo Toth, Enrico Malaguti, Rosa Medina Durán |
|---|---|
| Přispěvatelé: | Enrico Malaguti, Rosa Medina Durán, Paolo Toth |
| Rok vydání: | 2014 |
| Předmět: |
Mathematical optimization
Commercial software Information Systems and Management Computer science Strategy and Management Maximization Management Science and Operations Research Trim Cutting stock problem 2-Dimensional cutting stock Column generation Heuristics Branch and price algorithm Column generation Heuristics Integer programming |
| Zdroj: | Omega. 47:99-115 |
| ISSN: | 0305-0483 |
| DOI: | 10.1016/j.omega.2013.08.007 |
| Popis: | We consider a real world generalization of the 2-Dimensional Guillotine Cutting Stock Problem arising in the wooden board cutting industry. A set of rectangular items has to be cut from rectangular stock boards, available in multiple formats. In addition to the classical objective of trim loss minimization, the problem also asks for the maximization of the cutting equipment productivity, which can be obtained by cutting identical boards in parallel. We present several heuristic algorithms for the problem, explicitly considering the optimization of both objectives. The proposed methods, including fast heuristic algorithms, Integer Linear Programming models and a truncated Branch and Price algorithm, have increasing complexity and require increasing computational effort. Extensive computational experiments on a set of realistic instances from the industry show that high productivity of the cutting equipment can be obtained with a minimal increase in the total area of used boards. The experiments also show that the proposed algorithms perform extremely well when compared with four commercial software tools available for the solution of the problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect