Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/58283
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorCampêlo Neto, Manoel Bezerra-
dc.contributor.authorFigueiredo, Tatiane Fernandes-
dc.date.accessioned2021-05-10T16:48:50Z-
dc.date.available2021-05-10T16:48:50Z-
dc.date.issued2021-
dc.identifier.citationFIGUEIREDO, Tatiane Fernandes. Team formation problems: an integer linear optimization approach. 2021. 130 f. Tese (Doutorado em Ciência da Computação) - Universidade Federal do Ceará, Fortaleza, 2021.pt_BR
dc.identifier.urihttp://www.repositorio.ufc.br/handle/riufc/58283-
dc.description.abstractGiven a group of individuals, each one with a single skill, and a social network capturing the mutual affinity among them, the Team Formation Problem (TFP) aims to find a single team that meets the skills needed to perform a task while seeking to optimize the communication costs between the involved individuals. In the first part of this work, we study a generalized version of the TFP denominated as Multiple Team Formation Problem (MTFP), which allows distinct demands of workers per ability as well as multiple work teams and fractions of dedication time per team for each individual. In this case, the total communication cost is given by the sum of weighted pairwise relations between members within a same team. In the second part, we introduce a new variant of the TFP to be called Competitive Teams Formation Problem (CTFP). Using the theory of social balance, in this problem, we represent the social network that connects the involved individuals as a signed graph and consider both intra-team and inter-teams communication costs by asking to have only positive relationships between individuals of a same team and only negative relationships between individuals of different teams. For the MTFP, we propose an Integer Linear Programming (ILP) formulation and sets of valid inequalities. Computational experiments attest that the ILP model strengthened by valid inequalities consistently outperforms the existing quadratic formulation for MTFP. We also consider a generalized version of the MTFP where individuals may have multiple skills. To handle this version, we adapt the initial ILP model into two new models and present other valid inequalities. For the CTFP, we also propose an ILP formulation and valid inequalities derived from the structural balance theory that enhance the computational performance of the model. Finally, we close this work with general conclusions and directions for future works.pt_BR
dc.language.isoenpt_BR
dc.subjectTeam formation problempt_BR
dc.subjectSocial balancept_BR
dc.subjectBranch & cutpt_BR
dc.subjectValid inequalitypt_BR
dc.subjectReformulation linearization techniquept_BR
dc.titleTeam formation problems: an integer linear optimization approachpt_BR
dc.typeTesept_BR
dc.description.abstract-ptbrDado um conjunto de indivíduos, cada um com uma habilidade única, e uma rede social captando a afinidade mútua entre eles, o Problema de Formação de Equipe (TFP -Team Formation Problem) visa encontrar uma única equipe que reúna as habilidades necessárias para realizar uma tarefa, enquanto busca otimizar os custos de comunicação entre os indivíduos envolvidos. Na primeira parte deste trabalho, estudamos uma generalização do TFP denominada como Problema de Formação de Múltiplas Equipes (MTFP - Multiple Team Formation Problem), que permite demandas distintas de trabalhadores para cada tipo de habilidade, assim como requisições de múltiplas equipes de trabalho e possibilidade de fracionamento do tempo de dedicação de cada indivíduo entre os times. Nesse caso, o custo total de comunicação é dado pela soma dos pesos das relações dos pares de indivíduos de um mesmo time. Na segunda parte, introduzimos uma nova variante do TFP, a ser chamada Problema de Formação de Equipes Competitivas (CTFP - Competitive Teams Formation Problem). Utilizando a teoria do equilíbrio social, neste problema, representamos a rede social que conecta os indivíduos envolvidos por meio de um grafo de sinal e consideramos simultaneamente custos de comunicação intra-equipe e inter-equipes, requisitando que haja apenas relações positivas entre indivíduos de uma mesma equipe e apenas relações negativas entre indivíduos de equipes diferentes. Para o MTFP, propomos uma formulação de Programação Linear Inteira (ILP) e famílias de desigualdades válidas. Experimentos computacionais atestam que o modelo ILP fortalecido por desigualdades válidas supera consistentemente a formulação quadrática apresentada na literatura para resolução do MTFP. Também consideramos uma versão generalizada do MTFP em que os indivíduos podem ter múltiplas habilidades. Para lidar com esta versão, adaptamos o modelo ILP inicial, gerando dois novos modelos, e apresentamos um outro conjunto de desigualdades válidas que fortalecem os dois modelos. Para o CTFP, também propomos uma formulação ILP, além de desigualdades válidas derivadas da teoria do equilíbrio estrutural que melhoram o desempenho computacional do modelo. Por fim, encerramos este trabalho com conclusões gerais e direções para trabalhos futuros.pt_BR
dc.title.enTeam formation problems: an integer linear optimization approachpt_BR
Appears in Collections:DCOMP - Teses defendidas na UFC

Files in This Item:
File Description SizeFormat 
2021_tese_tffigueiredo.pdf1,49 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.