Abstract
Based on the sociometric analysis of social networks, we introduce the sociotechnical teams formation problem (STFP). Given a group of individuals with different skill-sets and a social network that captures the mutual affinity between them, the problem consists in finding a set of pairwise disjoint teams, as harmonious as possible, with a minimum specified number of individuals per team per skill. We prove that STFP is \(\mathcal {NP}\)-hard and propose an integer linear programming formulation. We show several classes of facet-inducing inequalities for the corresponding polytope. Computational experiments performed on a set of 120 test instances attest the efficiency of a solution method based on the formulation strengthened by valid inequalities and on a simulated annealing algorithm used to provide good initial feasible solutions.
Similar content being viewed by others
References
Agustín-Blas, L. E., Salcedo-Sanz, S., Ortiz-García, E. G., Portilla-Figueras, A., Pérez-Bellido, Á. M., & Jiménez-Fernández, S. (2011). Team formation based on group technology: A hybrid grouping genetic algorithm approach. Computers & Operations Research, 38(2), 484–495.
Anagnostopoulos, A., Becchetti, L., Castillo, C., Gionis, A., & Leonardi, S. (2012). Online team formation in social networks. In Proceedings of the 21st international conference on World Wide Web, ACM (pp. 839–848).
Babad, E. (2001). On the conception and measurement of popularity: More facts and some straight conclusions. Social Psychology of Education, 5(1), 3–29.
Ballesteros-Pérez, P., González-Cruz, M. C., & Fernández-Diego, M. (2012). Human resource allocation management in multiple projects using sociometric techniques. International Journal of Project Management, 30(8), 901–913.
Baykasoglu, A., Dereli, T., & Das, S. (2007). Project team selection using fuzzy optimization approach. Cybernetics and Systems: An International Journal, 38(2), 155–185.
Bomze, I. M., Budinich, M., Pardalos, P. M., & Pelillo, M. (1999). The maximum clique problem. In Handbook of combinatorial optimization (pp. 1–74). Berlin: Springer.
Campion, M. A., Medsker, G. J., & Higgs, A. C. (1993). Relations between work group characteristics and effectiveness: Implications for designing effective work groups. Personnel Psychology, 46(4), 823–847.
Chen, R. C. (2012). Grouping optimization based on social relationships. Mathematical Problems in Engineering, 2012, 1–19. https://doi.org/10.1155/2012/170563.
Chen, R. C., Li, J. Y., Ma, N. J., & Chang, Y. T. (2013). Application of sociometry and genetic algorithm to selection of class officers. International Information Institute (Tokyo) Information, 16(2), 1233.
Chen, S. J., & Lin, L. (2004). Modeling team member characteristics for the formation of a multifunctional team in concurrent engineering. IEEE Transactions on Engineering Management, 51(2), 111–124.
de Oliveira, H. C. B., Martinez, M. R., Salgado, R. M., da Silva, L. E., & Figueiredo, T. F. (2010). Clusterização em redes sociais através do simulated annealing não monotônico. In SBPO - Simpósio Brasileiro Pesquisa Operacional (pp. 1996–2005).
Dorn, C., & Dustdar, S. (2010). Composing near-optimal expert teams: A trade-off between skills and connectivity. In R. Meersman, T. Dillon & P. Herrero (Eds.), On the move to meaningful internet systems: OTM (pp. 472–489).
Eiben, A. E., & Ruttkay, Z. (1996). Self-adaptivity for constraint satisfaction: Learning penalty functions. In Proceedings of IEEE international conference on evolutionary computation (pp. 258–261).
Farhadi, F., Sorkhi, M., Hashemi, S., & Hamzeh, A. (2011). An effective expert team formation in social networks based on skill grading. In 2011 IEEE 11th international conference on data mining workshops (ICDMW) (pp. 366–372).
Fitzpatrick, E. L., & Askin, R. G. (2005). Forming effective worker teams with multi-functional skill requirements. Computers & Industrial Engineering, 48(3), 593–608.
Gajewar, A., & Das Sarma, A. (2012). Multi-skill collaborative teams based on densest subgraphs. In Proceedings of the 2012 SIAM International Conference on Data Mining, SIAM (pp. 165–176).
Gutiérrez, J. H., Astudillo, C. A., Ballesteros-Pérez, P., Mora-Melià, D., & Candia-Véjar, A. (2016). The multiple team formation problem using sociometry. Computers & Operations Research, 75, 150–162.
Hendriks, M., Voeten, B., & Kroep, L. (1999). Human resource allocation in a multi-project R&D environment: Resource capacity allocation and project portfolio planning in practice. International Journal of Project Management, 17(3), 181–188.
Kirkpatrick, S. (1984). Optimization by simulated annealing: Quantitative studies. Journal of Statistical Physics, 34(5–6), 975–986.
Lappas, T., Liu, K., & Terzi, E. (2009). Finding a team of experts in social networks. In Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining (pp. 467–476).
Li, C. T., & Shan, M. K. (2010). Team formation for generalized tasks in expertise social networks. In IEEE Second International Conference on Social Computing (SocialCom) (pp. 9–16).
Li, C. T., Shan, M. K., & Lin, S. D. (2015). On team formation with expertise query in collaborative social networks. Knowledge and Information Systems, 42(2), 441–463.
Maurer, I. (2010). How to build trust in inter-organizational projects: The impact of project staffing and project rewards on the formation of trust, knowledge acquisition and product innovation. International Journal of Project Management, 28(7), 629–637.
Moreno, J. L. (1941). Foundations of sociometry: An introduction. Sociometry, 4(1), 15–35.
Shi, Z., & Hao, F. (2013). A strategy of multi-criteria decision-making task ranking in social-networks. The Journal of Supercomputing, 66(1), 556–571.
Sorkhi, M., Alvari, H., Hashemi, S., & Hamzeh, A. (2012). A game-theoretic framework to identify top-k teams in social networks. In KDIR (pp. 252–257).
Teixeira, L. O., & Huzita, E. H. M. (2014). Disen-alocahr: A multi-agent mechanism for human resources allocation in a distributed software development environment. In S. Omatu, H. Bersini, J. M. Corchado, S. Rodríguez, P. Pawlewski & E. Bucciarelli (Eds.), 11th international conference on distributed computing and artificial intelligence (Vol. 290, pp. 227–234).
Trist, E. (1981). The evolution of socio-technical systems. Occasional Paper No. 2.
Wi, H., Oh, S., Mun, J., & Jung, M. (2012). A team formation model based on knowledge and collaboration. IEEE Engineering Management Review, 1(40), 44–57.
Wolsey, L. A., & Nemhauser, G. L. (1999). Integer and combinatorial optimization. New York: Wiley.
Zakarian, A., & Kusiak, A. (1999). Forming teams: An analytical approach. IIE Transactions, 31(1), 85–97.
Author information
Authors and Affiliations
Corresponding author
Additional information
Partially supported by Conselho Nacional de Desenvolvimento Cientfico e Tecnolgico - CNPq, Brasil (443747/2014-8, 305264/2016-8), and CAPES/STIC-AmSud.
Rights and permissions
About this article
Cite this article
Campêlo, M., Figueiredo, T. & Silva, A. The sociotechnical teams formation problem: a mathematical optimization approach. Ann Oper Res 286, 201–216 (2020). https://doi.org/10.1007/s10479-018-2759-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-018-2759-5