Exact and greedy algorithms of allocating experts to maximum set of programmer teams
https://doi.org/10.21122/2309-4923-2022-1-40-46
Abstract
The allocation of experts to programmer teams, which meet constraints on professional competences related to programming technologies, languages and tools an IT project specifies is a hard combinatorial problem. This paper solves the problem of forming the maximum number of teams whose experts meet all the constraints within each team. It develops and compares two algorithms: a heuristic greedy and exact optimal. The greedy algorithm iteratively solves the set cover problem on a matrix of expert competences until can create the next workable team of remaining experts. The paper proves that the allocation greedy algorithm is not accurate even if the set cover algorithm is exact. We call the allocation algorithm as double greedy if the set cover algorithm is greedy. The exact algorithm we propose finds optimal solution in three steps: generating a set of all non-redundant teams, producing a graph of team’s independency, and searching for a maximum clique in the graph. The algorithm of generating the non-redundant teams traverses a search tree constructed in such a way as to guarantee the creation of all non-redundant teams and absorbing all redundant teams. The edges of the non-redundant team independency graph connect teams that have no common expert. The maximum clique search algorithm we propose accounts for the problem and graph features. Experimental results show that the exact algorithm is a reference one, and the double-greedy algorithm is very fast and can yield suboptimal solutions for large-size allocation problems.
About the Author
A. A. Prihozhy
Belarusian national technical university
Belarus
Anatoly Prihozhy is a full professor at the Computer and system software department, doctor of science and professor
Belarus
Anatoly Prihozhy is a full professor at the Computer and system software department, doctor of science and professor
References
1. Joshi, S. Agile Development Working with Agile in a Distributed Team Environment / S. Joshi // MSDN Magazine, 2012, Vol.27, No.1, pp.1-6.
2. Collier, K.W., Agile Analytics: A Value-Driven Approach to Business Intelligence and Data Warehousing. – Pearson Education, 2012. – 74 p.
3. Muller, J.P., Rao, A.S., Singh, M.P. ATeams: An Agent Architecture for Optimization and Decision-Support, Proceedings 5th International Workshop, ATAL’98 Paris, France, July 4–7, 1998, pp. 261-276.
4. Masood Z., Hoda R., Blincoe K. (2017) Exploring Workflow Mechanisms and Task Allocation Strategies in Agile Software Teams. In: Baumeister H., Lichter H., Riebisch M. (eds) Agile Processes in Software Engineering and Extreme Programming. XP 2017. Lecture Notes in Business Information Processing, vol 283. Springer, Cham. https://doi.org/10.1007/978-3-319-57633-6_19.
5. R. Britto, P. S. Neto, R. Rabelo, W. Ayala and T. Soares, “A hybrid approach to solve the agile team allocation problem,” 2012 IEEE Congress on Evolutionary Computation, 2012, pp. 1-8, doi: 10.1109/CEC.2012.6252999.
6. Wrike [Электронный ресурс] – Режим доступа: https://www.wrike.com/, – Загл. с экрана – Яз. англ. Дата доступа – 28.10.2021.
7. Flow [Электронный ресурс] – Режим доступа: https://www.getflow.com/, – Загл. с экрана – Яз. англ. Дата доступа – 28.10.201
8. Gutirrez, J. H., Astudillo, C. A., Ballesteros-Pérez, P., Mora-Melià, D. and Candia-Véja, A. (2016) The multiple team formation problem using sociometry. Computers and Operations Research, 75. pp. 150-162. ISSN 0305-0548 https://doi.org/10.1016/j.cor.2016.05.012
9. Barricelli, N.A. Symbio genetic evolution processes realized by artificial methods / N.A. Barricelli // Methodos, 1957, pp. 143–182/
10. Prihozhy A.A., Zhdanouski A.M. Method of qualification estimation and optimization of professional teams of programmers. «System analysis and applied information science». – 2018, No. 2, pages 4-11. https://doi.org/10.21122/2309-4923-2018-24-11
11. Prihozhy, A. Genetic algorithm of optimizing the size, staff and number of professional teams of programmers / A. Prihozhy, A. Zhdanouski // Open Semantic Technologies for Intelligent Systems. – Minsk, BSUIR, 2019. – P. 305–310.
12. Prihozhy A.A., Zhdanouski A.M. Genetic algorithm of optimizing the qualification of programmer teams. System analysis and applied information science. – 2020, No. 4, pages 31-38. https://doi.org/10.21122/2309-4923-2020-4-31-38
13. Sijin, J. Perspectives on Software, Technology and Business: Programmer Competency Matrix / J. Sijin // [Electronic resource]. –Mode of access: https://sijinjoseph.com/programmer-competency-matrix/. – Date of access: 28.10.2021.
14. Karp R.M. (1972) Reducibility among Combinatorial Problems. In: Miller R.E., Thatcher J.W., Bohlinger J.D. (eds) Complexity of Computer Computations. The IBM Research Symposia Series. Springer, Boston, MA. https://doi.org/10.1007/978-14684-2001-2_9
15. Prihozhy, A.A. Asynchronous scheduling and allocation / A.A. Prihozhy / Proceedings Design, Automation and Test in Europe. Paris, France. – IEEE, 1998, pp. 963-964.
16. A. Prihozhy, S. Casale-Brunet, E. Bezati and M. Mattavelli. “Efficien Dynamic Optimization Heuristics for Dataflow Pipelines,” IEEE International Workshop on Signal Processing Systems, IEEE, pp. 337342, October 2018.
17. Prihozhy, A., Casale-Brunet, S., Bezati, E., M. Mattavelli. Pipeline Synthesis and Optimization from Branched Feedback Dataflow Programs. Journal of Signal Processing Systems, Springer Nature, 2020, Vol. 92, pages 1091–1099 https://doi.org/10.1007/s11265-020-01568-5.
Review
For citations:
Prihozhy A.A. Exact and greedy algorithms of allocating experts to maximum set of programmer teams. «System analysis and applied information science». 2022;(1):40-46. https://doi.org/10.21122/2309-4923-2022-1-40-46
Views:
438
Email this article 