| Revista: | Pesquisa operacional |
| Base de datos: | PERIÓDICA |
| Número de sistema: | 000313032 |
| ISSN: | 0101-7438 |
| Autores: | Marques, Fabiano do Prado1 Arenales, Marcos Nereu1 |
| Instituciones: | 1Universidade de Sao Paulo, Departamento de Ciencias de Computacao e Estatistica, Sao Carlos, Sao Paulo. Brasil |
| Año: | 2002 |
| Periodo: | Jul-Dic |
| Volumen: | 22 |
| Número: | 3 |
| Paginación: | 285-304 |
| País: | Brasil |
| Idioma: | Portugués |
| Tipo de documento: | Artículo |
| Enfoque: | Aplicado, descriptivo |
| Resumen en inglés | The Compartmentalized Knapsack Problem is a variation of the classical knapsack problem and can be stated considering the following hypothetical situation: an alpinist must load his knapsack with items. Two numbers, a weight and an utility value are associated with each item (so far, the problem coincides with the classical integer Knapsack Problem). However, the items are of different classes (food, medicine, utensil, etc.) and they have to be packed into separate compartments inside the knapsack. The compartments are flexible and have limited capacities. Each compartment has a fixed cost that depends on the class of the items and, in addition, each new compartment introduces a loss on the capacity of the knapsack. The Compartmentalized Knapsack Problem consists in determining suitable capacities for each compartment as well as their packing. The objective is to maximize the total utility value paid off the cost of the compartments. In this work, we model the problem as an integer non-linear optimization problem and we design some heuristic methods for its solution. A practical application of this problem arises in steel rolls cutting subject to lamination, which is discussed in detail in the appendix |
| Resumen en portugués | O Problema da Mochila Compartimentada é uma variação do clássico problema da mochila e pode ser enunciado considerando-se a seguinte situação hipotética: um alpinista deve carregar sua mochila com possíveis itens de seu interesse. A cada item atribui-se o seu peso e um valor de utilidade (até aqui, o problema coincide com o clássico Problema da Mochila). Entretanto, os itens são de agrupamentos distintos (alimentos, medicamentos, utensílios, etc.) e devem estar em compartimentos separados na mochila. Os compartimentos da mochila são flexíveis e têm capacidades limitadas. A inclusão de um compartimento tem um custo fixo que depende do agrupamento com que foi preenchido, além de introduzir uma perda da capacidade da mochila. O problema consiste em determinar as capacidades adequadas de cada compartimento e como esses devem ser carregados, maximizando o valor de utilidade total, descontado o custo de incluir compartimentos. Neste trabalho propomos um modelo de otimização não linear inteiro para o problema e algumas heurísticas para sua resolução. Uma aplicação prática de relevância deste problema aparece no corte de bobinas de aço, sujeito à laminação, detalhado em apêndice |
| Disciplinas: | Matemáticas, Ingeniería |
| Palabras clave: | Matemáticas aplicadas, Ingeniería industrial, Problema de la mochila, Problemas de corte, Empaquetamiento, Optimización combinatoria, Optimización entera, Optimización no lineal |
| Keyword: | Mathematics, Engineering, Applied mathematics, Industrial engineering, Knapsack problem, Cutting problems, Packing, Combinatorial optimization, Integer optimization, Nonlinear optimization |
| Texto completo: | Texto completo (Ver HTML) |
