Data Science

Pesquisa Operacional na prática

Por: Everton Gago, maio 31, 2021

O termo Pesquisa Operacional (PO) surgiu durante a II Guerra Mundial como uma ferramenta para solucionar problemas de logística militar, mas com os avanços tecnológicos não demorou até que a PO fosse reconhecida como uma ciência multidisciplinar com aplicações em outras áreas. A PO combina técnicas de modelagem matemática e algoritmos computacionais, auxiliando na resolução de problemas complexos e servindo como apoio à tomada de decisão.

 

Do ponto de vista acadêmico, a PO é uma ciência multidisciplinar que envolve programação matemática, simulação, teoria dos jogos, teoria das filas, análise de malhas, teoria de decisão, aprendizado de máquina e ciência dos dados; já do ponto prático, a PO demanda um esforço de equipe, exigindo uma estreita cooperação entre tomadores de decisão, analistas e pessoas que serão afetadas pelas decisões.

 

Este artigo traz uma aplicação prática da PO, solucionando um problema de designação de pessoas. O problema de designação de pessoas consiste em designar pessoas para realizar tarefas. Neste exemplo vamos designar pessoas para atender necessidades em projetos de desenvolvimento de software, onde características específicas são importantes, tais como: senioridade, conhecimento em tecnologias e fluência em idiomas.

 

O objetivo da designação é maximizar o fator de combinação da semelhança entre as pessoas e as necessidades, com a urgência de cada necessidade. Essa urgência pode ser medida pelo número de pessoas no squad, número de pessoas necessárias e a data de abertura da necessidade.

 

FUNÇÕES DE REGIMENTO

 

Vamos começar descrevendo o índice de variáveis do problema:

 

pi: i-ésima pessoa disponível para designação

nj: j-ésima necessidade em projeto de software

Sij: Similaridade entre a i-ésima pessoa e a j-ésima necessidade

uj: Urgência da necessidade j-ésima necessidade

Wij: Fator de combinação Sij+uj da i-ésima pessoa e j-ésima necessidade

Aij: Matriz de ativação entre a i-ésima pessoa e a j-ésima necessidade, tal que pi e nj {0,1}

Xij: Variável de maximização, tal que Xij {0,1}

 

Ao decorrer do artigo vamos nos referir estritamente às variáveis mencionadas acima, então sempre que necessário volte ao índice das variáveis para entender seu significado.

Partindo do pressuposto de que temos duas listas, uma de pessoas e outra de necessidades, ambas com suas características (senioridade, conhecimento em tecnologias e idiomas), podemos calcular a similaridade entre a i-ésima pessoa e a j-ésima necessidade.

 

Existem diversas formas de fazer esse cálculo, aqui vamos adotar um princípio trazido pela ortogonalidade entre dois vetores. A similaridade entre dois vetores aumenta, à medida que o ângulo formado entre eles diminui. Sendo assim, a similaridade entre dois vetores pode ser obtida através da relação dada pelo produto desses dois vetores, também conhecido como produto escalar.

 

Veja:

formula

Além da similaridade entre a pessoa e a necessidade, nossa modelagem depende da urgência. Vamos estabelecer algumas restrições para modelar a função de urgência:

 

  • Uma necessidade deve, a depender da taxa de contratação, ser atendida em 30 dias
  • A urgência uj0 à medida que dj-hjtj0

 

Onde djcorresponde ao número de dias desde a abertura da necessidade e hjcorresponde ao número de pessoas alocadas atualmente no squad do projeto. Chamaremos tjo número total de pessoas previstas no squad.

 

Assim, podemos definir nossa função de urgência como a diferença entre duas ponderações:

formula

De forma que a urgência aumenta com o passar do tempo, mas diminui à medida que pessoas são alocadas no squad de projeto. Vale destacar que a função de regimento da urgência é uma função linear, simplificando a análise do comportamento da função.

 

A seguir, a implementação da função de urgência:

Figura 1 - Função de urgência implementada em Python

Uma vez modeladas as similaridades Sij e as urgências uj, podemos facilmente calcular o fator de combinação Wij. Esse fator fará parte da função de maximização, através da qual vamos designar as pessoas para os projetos, respeitando as similaridades e priorizando as urgências.

Veja a seguir como fica o cálculo do fator de combinação wij:

Formula

Outro elemento que fará parte da função de maximização, é a matriz de ativação Aij. Através dessa matriz podemos assegurar que as pessoas designadas terão o mesmo papel requisitado pela necessidade.

Formula

Onde ci é o papel desempenhado pela pessoa e kj é o papel requisitado pela necessidade. Dessa forma, vamos anular as relações entre pessoas e necessidades com papéis diferentes. Essa é uma condição fundamental para solucionar o problema, impedindo que um Cientista de Dados seja designado à uma necessidade de Scrum Master, por exemplo.

 

A seguir, a implementação da matriz de ativação:

Figura 2 - Matriz de ativação implementada em Python


OTIMIZAÇÃO

 

Agora que modelamos as funções de regimento, podemos definir a função de otimização e as restrições do problema. As funções de restrição são muito importantes, pois é através delas que vamos garantir uma otimização consistente. Podemos criar quantas restrições forem necessárias, desde que elas não sejam excludentes.

 

A seguir, a função de otimização:

Vale lembrar que Wij é o fator de combinação entre pessoa, necessidade e urgência. Quanto maior esse fator, mais compatível a pessoa é com a necessidade e maior é a urgência atendida com a designação.

Em relação às restrições, temos que:

Uma pessoa deve ser designada à uma única necessidade de projeto

Formula

Uma necessidade de projeto deve ser designada à uma única pessoa

Formula

A seguir, a implementação da função de otimização e das restrições:

Figura 3 - Implementação da função de otimização e das restrições em Python


Depois de executar a otimização é possível recuperar a melhor combinação entre pessoa e necessidade. Controlamos pelo índice
i as pessoas e pelo índice j as necessidades.

 

A seguir, a implementação e print dos matches pessoas e necessidades:

Figura 4 - Implementação da função de otimização e das restrições em Python


Vale destacar que a PO deve ser utilizada como um ferramenta de suporte e apoio à tomada de decisão, tratando a designação automática como uma sugestão a ser avaliada pela gestão. Em casos muito específicos essa decisão poderia ser tomada automaticamente. A implementação completa deste artigo pode ser encontrada
aqui.

Posts relacionados

  • Receba nosso conteúdo em primeira mão.