<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.3 20210610//EN" "JATS-journalpublishing1-3.dtd">
<article article-type="research-article" dtd-version="1.3" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xml:lang="ru"><front><journal-meta><journal-id journal-id-type="publisher-id">sapi</journal-id><journal-title-group><journal-title xml:lang="ru">Системный анализ и прикладная информатика</journal-title><trans-title-group xml:lang="en"><trans-title>«System analysis and applied information science»</trans-title></trans-title-group></journal-title-group><issn pub-type="ppub">2309-4923</issn><issn pub-type="epub">2414-0481</issn><publisher><publisher-name>Belarusian National Technical University</publisher-name></publisher></journal-meta><article-meta><article-id pub-id-type="doi">10.21122/2309-4923-2022-1-40-46</article-id><article-id custom-type="elpub" pub-id-type="custom">sapi-552</article-id><article-categories><subj-group subj-group-type="heading"><subject>Research Article</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="ru"><subject>Обработка информации и принятие решений</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="en"><subject>Data processing and decision–making</subject></subj-group></article-categories><title-group><article-title>Точный и жадный алгоритмы распределения экспертов на максимальном множестве групп программистов</article-title><trans-title-group xml:lang="en"><trans-title>Exact and greedy algorithms of allocating experts to maximum set of programmer teams</trans-title></trans-title-group></title-group><contrib-group><contrib contrib-type="author" corresp="yes"><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Прихожий</surname><given-names>А. А.</given-names></name><name name-style="western" xml:lang="en"><surname>Prihozhy</surname><given-names>A. A.</given-names></name></name-alternatives><bio xml:lang="ru"><p>Прихожий Анатолий Алексеевич – профессор кафедры программного обеспечения вычислительной техники и автоматизированных систем, доктор технических наук, профессор</p></bio><bio xml:lang="en"><p>Anatoly Prihozhy is a full professor at the Computer and system software department, doctor of science  and professor</p></bio><xref ref-type="aff" rid="aff-1"/></contrib></contrib-group><aff-alternatives id="aff-1"><aff xml:lang="ru"><institution>Белорусский национальный технический университет</institution><country>Беларусь</country></aff><aff xml:lang="en"><institution>Belarusian national technical university</institution><country>Belarus</country></aff></aff-alternatives><pub-date pub-type="collection"><year>2022</year></pub-date><pub-date pub-type="epub"><day>08</day><month>06</month><year>2022</year></pub-date><volume>0</volume><issue>1</issue><fpage>40</fpage><lpage>46</lpage><permissions><copyright-statement>Copyright &amp;#x00A9; Прихожий А.А., 2022</copyright-statement><copyright-year>2022</copyright-year><copyright-holder xml:lang="ru">Прихожий А.А.</copyright-holder><copyright-holder xml:lang="en">Prihozhy A.A.</copyright-holder><license xml:lang="ru" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>Данная работа распространяется под лицензией Creative Commons Attribution 4.0.</license-p></license><license xml:lang="en" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>This work is licensed under a Creative Commons Attribution 4.0 License.</license-p></license></permissions><self-uri xlink:href="https://sapi.bntu.by/jour/article/view/552">https://sapi.bntu.by/jour/article/view/552</self-uri><abstract><p>Распределение экспертов по программистским группам, отвечающее требованиям профессиональной компетенции в сфере программирования, специфицированным в ИТ-проекте, является сложной комбинаторной проблемой. В данной работе решается задача формирования максимального числа групп с включением в них экспертов, обеспечивающих выполнение каждой группой требований к компетенциям. В статье разрабатываются и сравниваются два алгоритма решения задачи: эвристический жадный и точный оптимальный. Жадный алгоритм итеративно решает задачу о покрытии на матрице экспертных компетенций до тех пор, пока не сможет создать работоспособную группу из оставшихся экспертов. В статье доказано, что этот алгоритм не оптимален, даже если задача о покрытии решается оптимально. Алгоритм назначения экспертов является дважды жадным, если он использует жадный алгоритм покрытия множества. Предлагаемый точный алгоритм находит оптимальное решение на трех шагах: создание набора всех не избыточных групп, построение графа независимости групп и поиск максимальной клики графа. Алгоритм генерации групп обходит дерево поиска, построенное так, чтобы гарантировать нахождение всех не избыточных групп и поглощение всех избыточных групп. Ребра графа независимости групп соединяют вершины-группы, не имеющие общих экспертов. В статье предложен алгоритм поиска максимальной клики, учитывающий особенности графа и решаемой задачи. Экспериментальные результаты показывают, что точный алгоритм является оптимальным эталонным, а алгоритм двойной жадности является быстрым и может давать решение</p></abstract><trans-abstract xml:lang="en"><p>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.</p></trans-abstract><kwd-group xml:lang="en"><kwd>programmer</kwd><kwd>team</kwd><kwd>competence</kwd><kwd>expert</kwd><kwd>allocation problem</kwd><kwd>optimization</kwd></kwd-group></article-meta></front><back><ref-list><title>References</title><ref id="cit1"><label>1</label><citation-alternatives><mixed-citation xml:lang="ru">Joshi, S. Agile Development Working with Agile in a Distributed Team Environment / S. Joshi // MSDN Magazine, 2012, Vol.27, No.1, pp.1-6.</mixed-citation><mixed-citation xml:lang="en">Joshi, S. Agile Development Working with Agile in a Distributed Team Environment / S. Joshi // MSDN Magazine, 2012, Vol.27, No.1, pp.1-6.</mixed-citation></citation-alternatives></ref><ref id="cit2"><label>2</label><citation-alternatives><mixed-citation xml:lang="ru">Collier, K.W., Agile Analytics: A Value-Driven Approach to Business Intelligence and Data Warehousing. – Pearson Education, 2012. – 74 p.</mixed-citation><mixed-citation xml:lang="en">Collier, K.W., Agile Analytics: A Value-Driven Approach to Business Intelligence and Data Warehousing. – Pearson Education, 2012. – 74 p.</mixed-citation></citation-alternatives></ref><ref id="cit3"><label>3</label><citation-alternatives><mixed-citation xml:lang="ru">Muller, J.P., Rao, A.S., Singh, M.P. ATeams: An Agent Architecture for Optimization and Decision-Support, Pro-ceedings 5th International Workshop, ATAL’98 Paris, France, July 4–7, 1998, pp. 261-276.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit4"><label>4</label><citation-alternatives><mixed-citation xml:lang="ru">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</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit5"><label>5</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit6"><label>6</label><citation-alternatives><mixed-citation xml:lang="ru">Wrike [Электронный ресурс] – Режим доступа: https://www.wrike.com/, – Загл. с экрана – Яз. англ. Дата доступа: 28.10.2021.</mixed-citation><mixed-citation xml:lang="en">Wrike [Электронный ресурс] – Режим доступа: https://www.wrike.com/, – Загл. с экрана – Яз. англ. Дата доступа – 28.10.2021.</mixed-citation></citation-alternatives></ref><ref id="cit7"><label>7</label><citation-alternatives><mixed-citation xml:lang="ru">Flow [Электронный ресурс] – Режим доступа: https://www.getflow.com/, – Загл. с экрана – Яз. англ. Дата доступа: 28.10.2021</mixed-citation><mixed-citation xml:lang="en">Flow [Электронный ресурс] – Режим доступа: https://www.getflow.com/, – Загл. с экрана – Яз. англ. Дата доступа – 28.10.201</mixed-citation></citation-alternatives></ref><ref id="cit8"><label>8</label><citation-alternatives><mixed-citation xml:lang="ru">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</mixed-citation><mixed-citation xml:lang="en">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</mixed-citation></citation-alternatives></ref><ref id="cit9"><label>9</label><citation-alternatives><mixed-citation xml:lang="ru">Barricelli, N.A. Symbio genetic evolution processes realized by artificial methods / N.A. Barricelli // Methodos, 1957, pp. 143–182</mixed-citation><mixed-citation xml:lang="en">Barricelli, N.A. Symbio genetic evolution processes realized by artificial methods / N.A. Barricelli // Methodos, 1957, pp. 143–182/</mixed-citation></citation-alternatives></ref><ref id="cit10"><label>10</label><citation-alternatives><mixed-citation xml:lang="ru">Прихожий А.А., Ждановский А.М. Метод оценки квалификации и оптимизация состава профессиональных групп программистов. «Системный анализ и прикладная информатика». – 2018, № 2, с. 4-11. https://doi.org/10.21122/2309-49232018-2-4-11</mixed-citation><mixed-citation xml:lang="en">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</mixed-citation></citation-alternatives></ref><ref id="cit11"><label>11</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit12"><label>12</label><citation-alternatives><mixed-citation xml:lang="ru">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</mixed-citation><mixed-citation xml:lang="en">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</mixed-citation></citation-alternatives></ref><ref id="cit13"><label>13</label><citation-alternatives><mixed-citation xml:lang="ru">Sijin, J. Perspectives on Software, Technology and Business: Programmer Competency Matrix / J. Sijin. – Mode of access: https://sijinjoseph.com/programmer-competency-matrix/. – Date of access: 28.10.2021.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit14"><label>14</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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</mixed-citation></citation-alternatives></ref><ref id="cit15"><label>15</label><citation-alternatives><mixed-citation xml:lang="ru">Prihozhy, A.A. Asynchronous scheduling and allocation / A.A. Prihozhy / Proceedings Design, Automation and Test in Europe. Paris, France. – IEEE, 1998, pp. 963-964.</mixed-citation><mixed-citation xml:lang="en">Prihozhy, A.A. Asynchronous scheduling and allocation / A.A. Prihozhy / Proceedings Design, Automation and Test in Europe. Paris, France. – IEEE, 1998, pp. 963-964.</mixed-citation></citation-alternatives></ref><ref id="cit16"><label>16</label><citation-alternatives><mixed-citation xml:lang="ru">A. Prihozhy, S. Casale-Brunet, E. Bezati and M. Mattavelli. “Efficient Dynamic Optimization Heuristics for Dataflow Pipelines,” IEEE International Workshop on Signal Processing Systems, IEEE, pp. 337342, October 2018.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit17"><label>17</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref></ref-list><fn-group><fn fn-type="conflict"><p>The authors declare that there are no conflicts of interest present.</p></fn></fn-group></back></article>
