Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

On the L-approach for generating unconstrained two-dimensional non-guillotine cutting patterns

Texto completo
Autor(es):
de Queiroz, Thiago Alves [1] ; Miyazawa, Flavio Keidi [2] ; Wakabayashi, Yoshiko [3]
Número total de Autores: 3
Afiliação do(s) autor(es):
[1] Univ Fed Goias, Dept Math, UFG RC, Catalao, Go - Brazil
[2] Univ Estadual Campinas, Inst Comp, IC UNICAMP, Campinas, SP - Brazil
[3] Univ Sao Paulo, Inst Math & Stat, IME USP, Sao Paulo, SP - Brazil
Número total de Afiliações: 3
Tipo de documento: Artigo Científico
Fonte: 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH; v. 13, n. 2, p. 199-219, JUN 2015.
Citações Web of Science: 1
Resumo

Many cutting problems on two- or three-dimensional objects require that the cuts be orthogonal and of guillotine type. However, there are applications in which the cuts must be orthogonal but need not be of guillotine type. In this paper we focus on the latter type of cuts on rectangular bins. We investigate the so-called -approach, introduced by Lins et al. (J Oper Res Soc 54:777-789, 2003), which has been used to tackle, among others, the pallet loading problem and the two-dimensional unconstrained knapsack problem. This approach concerns a method to generate two -shaped pieces from an -shaped piece. More recently, Birgin et al. (J Oper Res Soc 63(2):183-200, 2012), raised two questions concerning this approach. The first question is whether one may restrict only to cuts on raster points (rather than on all discretization points), without loss in the quality of the solution. We prove that the answer to this question is positive. The second question is whether the -approach is an optimal method to solve the unconstrained knapsack problem. We show an instance of the problem for which this approach fails to find an optimum solution. (AU)

Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
Beneficiário:Carlos Eduardo Ferreira
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 13/08278-8 - Algoritmos para o problema de localização e roteamento com restrições de empacotamento
Beneficiário:Thiago Alves de Queiroz
Linha de fomento: Bolsas no Brasil - Pós-Doutorado