Full text
| |
| Author(s): |
Vinícius Loti de Lima
Total Authors: 1
|
| Document type: | Doctoral Thesis |
| Press: | Campinas, SP. |
| Institution: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Defense date: | 2021-12-14 |
| Examining board members: |
Flávio Keidi Miyazawa;
Eduardo Uchoa Barboza;
Luciana Salete Buriol;
Marco Lübbecke;
Stefan Irnich
|
| Advisor: | Flávio Keidi Miyazawa; Thiago Alves de Queiroz |
| Abstract | |
This thesis focuses on combinatorial optimization, one of the major optimization fields. This field consists of decision problems, in which we are given a potentially huge discrete set of possible solutions, and we must find a single solution that optimizes an objective function. Such problems have an extensive number of real world applications, mainly in industrial logistics and supply chain. First, we study network flow formulations that can be applied to general combinatorial optimization problems. We present a survey discussing theoretical foundations and main successful applications of the so-called pseudo-polynomial arc flow models. Then, we propose novel exact solution methods to solve such models, involving column generation, specialized branching rules, and variable fixing strategies. We apply the proposed solution methods to well-studied cutting, packing, and scheduling problems from the literature, including, for instance, the classical bin packing and cutting stock problems. Our computational experiments show the effectiveness of the proposed methods by solving to proven optimality an extensive number of open benchmark instances of several problems. The second part of this thesis give special attention to the area of two-dimensional cutting and packing problems, which is among the most studied areas in combinatorial optimization. We survey the most relevant references that appeared in the last two decades and propose an online library to systematically arrange the most relevant materials regarding such problems. These contributions can facilitate future research in the active area of two-dimensional cutting and packing. Our last contribution concerns a real world problem arising from an Italian meat-producing company. The problem consists of a large set of complex decisions, involving the daily workforce allocation and scheduling of orders in the company. To solve this problem, we propose a three-phase constructive heuristic, which is embedded in a multi-start framework. Our algorithm outperforms in average the decisions made by the former strategy of the company (AU) | |
| FAPESP's process: | 17/11831-1 - Algorithms and models for cutting and packing problems |
| Grantee: | Vinícius Loti de Lima |
| Support Opportunities: | Scholarships in Brazil - Doctorate (Direct) |