The socio-technical teams formation problem: Complexity, Mathematical Formulations and Computational Results

Using concepts of the socio-technical systems theory, this dissertation defines mathematically the problems of cooperative teams formation considering social and technical constraints separately, and then presents their computational complexity. Mainly, it is defined and studied the central problem in this work, which jointly considers social and technical requirements for creating teams of cooperative work, to be called FEST (Socio-Technical Teams Formation Problem). Two mathematical formulations and a meta-heuristic are proposed for FEST. One formulation uses a cubic number of variables and constraints, whereas the second one has a quadratic number of variables but an exponential number of constraints. The proposed heuristic is based on the Non-monotonic Simulated Annealing meta-heuristic with local search using swap-like operators. The correctness of both formulations is proved. A polynomial algorithm to separate the constraints of the second formulation is presented. It is proved that the two formulations provide the same linear programming bound, and valid inequalities to strengthen it are proposed. For the compact formulation, some classes of valid inequalities are shown to be facet-inducing under suitable hypotheses. Finally, it is statistically analyzed the performance of the presented formulations and meta-heuristic. Real and random generated instances are used in the computational experiments.Utilizando conceitos da Teoria dos Sistemas Sociotécnicos, este trabalho define matematicamente os problemas de formação de equipes cooperativas considerando separadamente restrições sociais e técnicas e apresenta a complexidade computacional dos mesmos. Sobretudo, é definido e estudado o problema central deste trabalho, que considera conjuntamente requisitos sociais e técnicos para criação de equipes de trabalho cooperativo, denominado FEST (Problema de Formação de Equipes Sociotécnicas). Duas formulações matemáticas e uma meta-heurística para o FEST são propostas. Uma formulação utiliza um número cúbico de variáveis e restrições, enquanto a segunda formulação possui um número quadrático de variáveis, mas um número exponencial de restrições. A meta-heurística proposta é baseada no Simulated Annealing Não-Monotônico com busca local que usa operadores tipo swap. A corretude de ambas as formulações é provada. Um algoritmo polinomial para separar as restrições da segunda formulação é apresentado. Mostra-se que as duas formulações fornecem o mesmo limite de programação linear, e desigualdades válidas para fortalecê-lo são propostas. Para a formulação compacta, algumas classes de desigualdades válidas são demonstradas indutoras de facetas sob hipóteses apropriadas. Por fim, foi analisado estatisticamente o desempenho das formulações e da meta-heurística apresentadas. Instâncias reais e geradas aleatoriamente são usadas nos experimentos computacionais