Banca de DEFESA: JUNOT FREIRE DOS SANTOS NETO

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE : JUNOT FREIRE DOS SANTOS NETO
DATA : 27/11/2020
HORA: 08:00
LOCAL: IME - UFBA (https://conferenciaweb.rnp.br/events/junot-freire-dos-santos-neto)
TÍTULO:

Heuristics and metaheuristics for a constrained two-dimensional guillotine cutting problem

PALAVRAS-CHAVES:

2-Dimensional bin packing problem, Metaheuristics, Constraint Programming

PÁGINAS: 46
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação
SUBÁREA: Teoria da Computação
ESPECIALIDADE: Análise de Algoritmos e Complexidade de Computação
RESUMO:

Two-Dimensional bin packing problems (2BP) are classic combinatorial optimization problems belonging to the NP-Hard class and have applications in several sectors such as the textile, metallurgical and glass industries. 2BP consists in allocating a set of rectangular items in larger rectangular plates with a standardized size in order to minimize the waste of raw material. In this dissertation, we approach a restricted version of the 2BP with guillotine cuts presented in the ROADEF/EURO Challenge 2018, in which there is a possibility to rotate items in 90° and soma itens have a order of precedence to be produced, and the rectangular plates may present defects in certain points. We propose two randomized greedy heuristics and a method for improving solutions based on a constraint programming model combined with a random greedy heuristic. The techniques are combined in Multistart and Greedy Randomized Adaptative Search Procedure (GRASP) metaheuristics in order to obtain better solutions. Computational experiments show that the use of the solution improvement method is advantageous, and that some combinations of the proposed techniques are more effective for certain types of instances. A preliminary version of this work was qualified for the final phase of the ROADEF/EURO Challenge 2018.

MEMBROS DA BANCA:
Interno - 2115562 - RAFAEL AUGUSTO DE MELO
Interno - 2250653 - TIAGO DE OLIVEIRA JANUARIO
Externo à Instituição - BRUNO DE ATHAYDE PRATA - UFC