A STOCHASTIC OPTIMIZATION MODEL FOR THE IRREGULAR KNAPSACK PROBLEM WITH UNCERTAINTY IN THE PLATE DEFECTS

Autor(es)

Layane Rodrigues de Souza Queiroz ^[1] ; Marina Andretta ^[2]

Afiliação do(s) autor(es)

^[1] Universidade de São Paulo. Instituto de Ciências Matemáticas e de Computação - Brasil

^[2] Universidade de São Paulo. Instituto de Ciências Matemáticas e de Computação - Brasil

• Tipo de documento: Artigo Científico
• Fonte: Pesquisa Operacional; v. 42, 2022-08-26.

Resumo

ABSTRACT The present research deals with the two-dimensional knapsack problem by considering the cutting of irregular items from a rectangular plate with defects. While the defects are only known at the time of cutting (in the future), we need first to select which items to produce from cutting the plate. The final items cannot have any defects and the goal is to maximize the profit from cutting the plate and producing the items. We propose a two-stage stochastic optimization model that makes use of a discrete set of scenarios with the realization of the plate defects. The first-stage decisions involve selecting items for cutting and possible production. The second-stage decisions consider the positioning of items in the plate given the scenarios with defects, and then the cancellation and non-production of some selected items, if any. We also extend this model to include a measure of risk, aiming at robust solutions. We perform computational tests on instances adapted from the literature that consider three types of defects, eight scenarios, and four cases for determining each scenario’s probability. The tests evaluate the impact of uncertainties on the problem by calculating the expected value of perfect information and the value of the stochastic solution. The results indicate a percentage reduction in the profit of up to 27.7%, on average, when considering a fully risk-averse decision-maker. (AU)

• Processo FAPESP: 16/01860-1 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento, localização e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 18/07240-0 - Incerteza em problemas de cortes e empacotamentos: planeamento robusto e replaneamento otimizado na produção e nos transportes
• Beneficiário: Franklina Maria Bragion de Toledo
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 13/07375-0 - CeMEAI - Centro de Ciências Matemáticas Aplicadas à Indústria
• Beneficiário: Francisco Louzada Neto
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs