Métodos de geração de colunas para problemas de atribuição

Página do item simplificado
dc.contributor.authorSenne, Edson Luiz França [UNESP]
dc.contributor.authorLorena, Luiz Antonio Nogueira
dc.contributor.authorSalomão, Silvely Nogueira de Almeida [UNESP]
dc.contributor.institutionUniversidade Estadual Paulista (Unesp)
dc.contributor.institutionInstituto Nacional de Pesquisas Espaciais (INPE)
dc.date.accessioned2014-05-20T15:14:23Z
dc.date.available2014-05-20T15:14:23Z
dc.date.issued2007-04-01
dc.description.abstractEste trabalho apresenta métodos de geração de colunas para dois importantes problemas de atribuição: o Problema Generalizado de Atribuição (PGA) e o Problema de Atribuição de Antenas a Comutadores (PAAC). O PGA é um dos mais representativos problemas de Otimização Combinatória e consiste em otimizar a atribuição de n tarefas a m agentes, de forma que cada tarefa seja atribuída a exatamente um agente e a capacidade de cada agente seja respeitada. O PAAC consiste em atribuir n antenas a m comutadores em uma rede de telefonia celular, de forma a minimizar os custos de cabeamento entre antenas e comutadores e os custos de transferência de chamadas entre comutadores. A abordagem tradicional de geração de colunas é comparada com as propostas neste trabalho, que utilizam a relaxação lagrangeana/surrogate. São apresentados testes computacionais que demonstram a efetividade dos algoritmos propostos.pt
dc.description.abstractThis work presents column generation methods for two important assignment problems: the Generalized Assignment Problem (GAP) and the problem of assigning cells to switches in cellular mobile networks (PACS). GAP is one of the most representative combinatorial optimisation problems and can be stated as the problem of optimising the assignment of n jobs to m agents, such that each job is assigned to exactly one agent and the resource capacity of each agent is not violated. PACS consists of determining a cell assignment pattern which minimizes cabling costs between a cell and a switch and transfer costs between cells assigned to different switches, while respecting certain constraints, especially those related to limited switch's capacity. The traditional column generation process is compared with the proposed algorithms that combine the column generation and lagrangean/surrogate relaxation. Computational experiments are presented in order to confirm the effectiveness of the proposed algorithms.en
dc.description.affiliationUNESP
dc.description.affiliationINPE
dc.description.affiliationUnespUNESP
dc.format.extent71-83
dc.identifierhttp://dx.doi.org/10.1590/S0103-65132007000100005
dc.identifier.citationProdução. Associação Brasileira de Engenharia de Produção, v. 17, n. 1, p. 71-83, 2007.
dc.identifier.doi10.1590/S0103-65132007000100005
dc.identifier.fileS0103-65132007000100005.pdf
dc.identifier.issn0103-6513
dc.identifier.lattes1338008237590056
dc.identifier.orcid0000-0002-6544-2964
dc.identifier.scieloS0103-65132007000100005
dc.identifier.urihttp://hdl.handle.net/11449/29166
dc.language.isopor
dc.publisherAssociação Brasileira de Engenharia de Produção
dc.relation.ispartofProdução
dc.relation.ispartofsjr0,200
dc.rights.accessRightsAcesso aberto
dc.sourceSciELO
dc.subjectOtimização combinatóriapt
dc.subjectproblemas de atribuiçãopt
dc.subjectrelaxação lagrangeanapt
dc.subjectgeração de colunaspt
dc.subjectCombinatorial optimizationen
dc.subjectassignment problemsen
dc.subjectlagrangeanen
dc.subjectcolumn generationen
dc.titleMétodos de geração de colunas para problemas de atribuiçãopt
dc.title.alternativeColumn generation methods for assignment problemsen
dc.typeArtigo
unesp.author.lattes1338008237590056[1]
unesp.author.orcid0000-0002-6544-2964[1]
unesp.campusUniversidade Estadual Paulista (Unesp), Faculdade de Engenharia, Guaratinguetápt

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
S0103-65132007000100005.pdf
Tamanho:
1.2 MB
Formato:
Adobe Portable Document Format
Baixar
Licença do Pacote
Agora exibindo 1 - 2 de 2
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.71 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.71 KB
Formato:
Item-specific license agreed upon to submission
Descrição:

Coleções

Artigos - Matemática - FEG