Exact and greedy algorithms of allocating experts to maximum set of programmer teams
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...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Belarusian National Technical University
2022-06-01
|
| Series: | Системный анализ и прикладная информатика |
| Subjects: | |
| Online Access: | https://sapi.bntu.by/jour/article/view/552 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849242664626552832 |
|---|---|
| author | A. A. Prihozhy |
| author_facet | A. A. Prihozhy |
| author_sort | A. A. Prihozhy |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-6c8c1d14fafe41b79ef2cff6d23cd254 |
| institution | Kabale University |
| issn | 2309-4923 2414-0481 |
| language | English |
| publishDate | 2022-06-01 |
| publisher | Belarusian National Technical University |
| record_format | Article |
| series | Системный анализ и прикладная информатика |
| spelling | doaj-art-6c8c1d14fafe41b79ef2cff6d23cd2542025-08-20T03:59:45ZengBelarusian National Technical UniversityСистемный анализ и прикладная информатика2309-49232414-04812022-06-0101404610.21122/2309-4923-2022-1-40-46414Exact and greedy algorithms of allocating experts to maximum set of programmer teamsA. A. Prihozhy0Belarusian national technical universityThe 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.https://sapi.bntu.by/jour/article/view/552programmerteamcompetenceexpertallocation problemoptimization |
| spellingShingle | A. A. Prihozhy Exact and greedy algorithms of allocating experts to maximum set of programmer teams Системный анализ и прикладная информатика programmer team competence expert allocation problem optimization |
| title | Exact and greedy algorithms of allocating experts to maximum set of programmer teams |
| title_full | Exact and greedy algorithms of allocating experts to maximum set of programmer teams |
| title_fullStr | Exact and greedy algorithms of allocating experts to maximum set of programmer teams |
| title_full_unstemmed | Exact and greedy algorithms of allocating experts to maximum set of programmer teams |
| title_short | Exact and greedy algorithms of allocating experts to maximum set of programmer teams |
| title_sort | exact and greedy algorithms of allocating experts to maximum set of programmer teams |
| topic | programmer team competence expert allocation problem optimization |
| url | https://sapi.bntu.by/jour/article/view/552 |
| work_keys_str_mv | AT aaprihozhy exactandgreedyalgorithmsofallocatingexpertstomaximumsetofprogrammerteams |