Metaheurísticas híbridas baseadas em programação por restrições para um problema de corte bidimensional guilhotinado com defeitos e restrições de precedência

Abstract

Problemas de corte bidimensional (2BP, do inglês \textit{Two-Dimensional bin packing problem}) são problemas clássicos de otimização combinatória pertencentes à classe NP-Difícil e tem aplicações em diversos setores como a indústria têxtil, metalúrgica e de vidro. Estes problemas consistem em alocar um conjunto de itens retangulares em placas retangulares maiores com tamanho padronizado, a fim de minimizar o desperdício de matéria-prima. Nesta dissertação é estudado um problema restrito de corte bidimensional guilhotinado associado à produção de vidro considerado no \textit{\citeA{challenge2018}}, no qual existe a possibilidade de rotacionar itens em 90° e possuem ordem de precedência para serem produzidos, e as placas retangulares de matéria-prima podem possuir defeitos como rachaduras e trincos. São propostas como técnicas para este problema duas heurísticas gulosas randomizadas e um método de aprimoramento de soluções baseado em uma modelagem de programação lógica por restrições combinada com uma heurística gulosa randomizada. As técnicas foram combinadas em metaheurísticas \textit{Multistart} e \textit{GRASP} (do inglês, \textit{Greedy Randomized Adaptive Search Procedure}) a fim de se obterem melhores soluções. Os experimentos realizados mostram que o uso do método de aprimoramento de soluções é vantajoso, e que algumas combinações de técnicas se mostram mais eficazes para determinados tipos de instâncias. Uma versão preliminar deste trabalho foi qualificada para a etapa final do \textit{\citeA{challenge2018}}.

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: Cutting Optimization Problem” (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 “ROADEF/EURO Challenge: Cutting Optimization Problem” (2018).