Compartmentalized knapsack problems: one-dimensional and two-dimensional cases
Arc flow-based formulations for extensions of the one-dimensional cutting stock pr...
Advanced search
Extensions for cutting stock problems: compartmentalized cutting patterns and integrated problems
Full text
| |
| Author(s): |
Aline Aparecida de Souza Leão
Total Authors: 1
|
| Document type: | Doctoral Thesis |
| Press: | São Carlos. |
| Institution: | Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) |
| Defense date: | 2013-02-08 |
| Examining board members: |
Marcos Nereu Arenales;
Flávio Keidi Miyazawa;
José Fernando da Costa Oliveira;
Maria do Socorro Nogueira Rangel;
Franklina Maria Bragion de Toledo
|
| Advisor: | Marcos Nereu Arenales |
| Abstract | |
In this thesis we present the constrained compartmentalized knapsack problem and the one dimensional cutting stock problem integrated with the capacitated lot sizing problem. For the constrained compartmentalized knapsack problem, the one dimensional version is presented and the two dimensional version is proposed, called one-dimensional compartmentalized knapsack problem and two-dimensional compartmentalized knapsack problem, respectively. For the cutting stock problem integrated with the capacitated lot sizing problem three variations are considered: one machine to produce one type of object; one machine to produce multiple types of objects; multiple machines to produce multiple types of objects. Some integer and mixed programming formulations, decompositions of the problems in master problem and subproblems and heuristics based on column generation method are proposed for the compartmentalized knapsack problem and the cutting stock problem integrated with the capacitated lot sizing problem. In particular, the period, the machine, and the period and machine Dantzig- Wolfe decompositions are applied for the integrated problem. Moreover, a heuristic based on the graph AND/OR is proposed for the two-dimensional compartmentalized knapsack problem. Computational results show that these mathematical formulations and methods provide good solutions (AU) | |
| FAPESP's process: | 08/09046-5 - Compartmentalized knapsack problems: one-dimensional and two-dimensional cases |
| Grantee: | Aline Aparecida de Souza Leão |
| Support Opportunities: | Scholarships in Brazil - Doctorate |