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

dc.contributorUniversidade Estadual Paulista (UNESP)
dc.creatorSenne, Edson Luiz França
dc.creatorLorena, Luiz Antonio Nogueira
dc.creatorSalomão, Silvely Nogueira de Almeida
dc.date2014-05-20T15:14:23Z
dc.date2016-10-25T17:48:17Z
dc.date2014-05-20T15:14:23Z
dc.date2016-10-25T17:48:17Z
dc.date2007-04-01
dc.date.accessioned2017-04-05T23:04:08Z
dc.date.available2017-04-05T23:04:08Z
dc.identifierProdução. Associação Brasileira de Engenharia de Produção, v. 17, n. 1, p. 71-83, 2007.
dc.identifier0103-6513
dc.identifierhttp://hdl.handle.net/11449/29166
dc.identifierhttp://acervodigital.unesp.br/handle/11449/29166
dc.identifier10.1590/S0103-65132007000100005
dc.identifierS0103-65132007000100005
dc.identifierS0103-65132007000100005.pdf
dc.identifier0000-0002-6544-2964
dc.identifierhttp://dx.doi.org/10.1590/S0103-65132007000100005
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/873847
dc.descriptionEste 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.
dc.descriptionThis 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.
dc.languagepor
dc.publisherAssociação Brasileira de Engenharia de Produção
dc.relationProdução
dc.rightsinfo:eu-repo/semantics/openAccess
dc.subjectOtimização combinatória
dc.subjectproblemas de atribuição
dc.subjectrelaxação lagrangeana
dc.subjectgeração de colunas
dc.subjectCombinatorial optimization
dc.subjectassignment problems
dc.subjectlagrangean
dc.subjectcolumn generation
dc.titleMétodos de geração de colunas para problemas de atribuição
dc.typeOtro


Este ítem pertenece a la siguiente institución