Пошук максимальних незалежних множин вершин графа для вдосконалення програмних проєктів
Зафіксовано потребу вдосконалення програмного проекту за рахунок непротирічної інтеграції технологічно-описового та нормативного підходів проектного менеджменту шляхом налаштування класичних задач дискретної оптимізації на графах для задач керування програмним проектом, кращі практики розв’язання як...
Saved in:
| Published in: | Проблеми програмування |
|---|---|
| Date: | 2022 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут програмних систем НАН України
2022
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/188631 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Пошук максимальних незалежних множин вершин графа для вдосконалення програмних проєктів/ О.О. Слабоспицька, П.І. Стецюк, О.М. Хом’як // Проблеми програмування. — 2022. — № 3-4. — С. 73-84. — Бібліогр.: 12 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-188631 |
|---|---|
| record_format |
dspace |
| spelling |
Слабоспицька, О.О. Стецюк, П.І. Хом’як, О.М. 2023-03-10T18:18:32Z 2023-03-10T18:18:32Z 2022 Пошук максимальних незалежних множин вершин графа для вдосконалення програмних проєктів/ О.О. Слабоспицька, П.І. Стецюк, О.М. Хом’як // Проблеми програмування. — 2022. — № 3-4. — С. 73-84. — Бібліогр.: 12 назв. — укр. 1727-4907 DOI: https://doi.org/10/15407/pp2022.03-04.073 https://nasplib.isofts.kiev.ua/handle/123456789/188631 519.8 Зафіксовано потребу вдосконалення програмного проекту за рахунок непротирічної інтеграції технологічно-описового та нормативного підходів проектного менеджменту шляхом налаштування класичних задач дискретної оптимізації на графах для задач керування програмним проектом, кращі практики розв’язання яких недостатньо регламентовані в руслі технологічного підходу. Запропоновано клас задач керування програмним проектом для демонстрації перспективності зазначеної інтеграції. Досліджено дві задачі булевого лінійного програмування для знаходження деякої незалежної множини максимального розміру (розділ 1) та алгоритм знаходження всіх можливих незалежних множин максимального розміру (розділ 2). У розділі 3 надано постановку задачі знаходження заданої кількості незалежних множин, які не перетинаються й мають найбільшу суму кількостей вершин у незалежних множинах. На її основі описано алгоритм Візинга-Плесневича для розфарбування вершин графа мінімальною кількістю кольорів. Для розв’язання булевих задач використано спеціалізовану мову математичного програмування AMPL і відповідну їй програму-солвер gurobi. Для основних розроблених алгоритмів наведено рамкові версії коду мовою AMPL та результати їх запускання. У розділі 4 розглянуто показові приклади вдосконалення програмного проекту за допомогою розроблених алгоритмів: формування з 25 фахівців, між якими в попередніх проектах мали місце конфлікти, згуртованих безконфліктних під-команд для портфеля програмних проектів; оптимізації розкладу автономного тестування компонентів повторного використання в складі критичної програмної системи; формування ядер незалежних команд у критичному програмному проекті. The need is fixed to software project enhancing with seamless integration of technological-descriptive and normative project management approaches by means of classical Graph Discrete Optimization Problems tailoring for software project management tasks, poorly equipped with best practices within technological approach. Class of software project management tasks is proposed to demonstrate the benefits of such integration. Two Boolean linear programming problems are investigated for searching some maximum size independent set (Section 1) and an algorithm for searching all possible maximum size independent sets (Section 2). Section 3 presents Problem Statement for searching a given number of non-intersecting independent sets with maximum sum of vertices’ numbers within independent sets. Based on it, Vizing-Plesnevich algorithm is described for coloring the graph vertices with the minimum number of colors. To solve Boolean problems, both specialized mathematical programming language AMPL and corresponding solver program named gurobi are used. For basic algorithms developed, reference AMPL code versions are given as well as their running results. Illustrative examples of software project enhancing with the algorithms elaborated are considered in Section 4, namely: 25 specialists being conflicted during their previous projects partitioning into coherent conflict-free sub-teams for software projects portfolio; schedule optimization for autonomous testing of reusable components within a critical software system; cores composing for independent teams in a critical software project. uk Інститут програмних систем НАН України Проблеми програмування Методи і засоби програмної інженерії Пошук максимальних незалежних множин вершин графа для вдосконалення програмних проєктів Maximum independent sets of graph vertices searching for software projects improvement Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Пошук максимальних незалежних множин вершин графа для вдосконалення програмних проєктів |
| spellingShingle |
Пошук максимальних незалежних множин вершин графа для вдосконалення програмних проєктів Слабоспицька, О.О. Стецюк, П.І. Хом’як, О.М. Методи і засоби програмної інженерії |
| title_short |
Пошук максимальних незалежних множин вершин графа для вдосконалення програмних проєктів |
| title_full |
Пошук максимальних незалежних множин вершин графа для вдосконалення програмних проєктів |
| title_fullStr |
Пошук максимальних незалежних множин вершин графа для вдосконалення програмних проєктів |
| title_full_unstemmed |
Пошук максимальних незалежних множин вершин графа для вдосконалення програмних проєктів |
| title_sort |
пошук максимальних незалежних множин вершин графа для вдосконалення програмних проєктів |
| author |
Слабоспицька, О.О. Стецюк, П.І. Хом’як, О.М. |
| author_facet |
Слабоспицька, О.О. Стецюк, П.І. Хом’як, О.М. |
| topic |
Методи і засоби програмної інженерії |
| topic_facet |
Методи і засоби програмної інженерії |
| publishDate |
2022 |
| language |
Ukrainian |
| container_title |
Проблеми програмування |
| publisher |
Інститут програмних систем НАН України |
| format |
Article |
| title_alt |
Maximum independent sets of graph vertices searching for software projects improvement |
| description |
Зафіксовано потребу вдосконалення програмного проекту за рахунок непротирічної інтеграції технологічно-описового та нормативного підходів проектного менеджменту шляхом налаштування класичних задач дискретної оптимізації на графах для задач керування програмним проектом, кращі практики розв’язання яких недостатньо регламентовані в руслі технологічного підходу. Запропоновано клас задач керування програмним проектом для демонстрації перспективності зазначеної інтеграції. Досліджено дві задачі булевого лінійного програмування для знаходження деякої незалежної множини максимального розміру (розділ 1) та алгоритм знаходження всіх можливих незалежних множин максимального розміру (розділ 2). У розділі 3 надано постановку задачі знаходження заданої кількості незалежних множин, які не перетинаються й мають найбільшу суму кількостей вершин у незалежних множинах. На її основі описано алгоритм Візинга-Плесневича для розфарбування вершин графа мінімальною кількістю кольорів. Для розв’язання булевих задач використано спеціалізовану мову математичного програмування AMPL і відповідну їй програму-солвер gurobi. Для основних розроблених алгоритмів наведено рамкові версії коду мовою AMPL та результати їх запускання. У розділі 4 розглянуто показові приклади вдосконалення програмного проекту за допомогою розроблених алгоритмів: формування з 25 фахівців, між якими в попередніх проектах мали місце конфлікти, згуртованих безконфліктних під-команд для портфеля програмних проектів; оптимізації розкладу автономного тестування компонентів повторного використання в складі критичної програмної системи; формування ядер незалежних команд у критичному програмному проекті.
The need is fixed to software project enhancing with seamless integration of technological-descriptive and normative project management approaches by means of classical Graph Discrete Optimization Problems tailoring for software project management tasks, poorly equipped with best practices within technological approach. Class of software project management tasks is proposed to demonstrate the benefits of such integration. Two Boolean linear programming problems are investigated for searching some maximum size independent set (Section 1) and an algorithm for searching all possible maximum size independent sets (Section 2). Section 3 presents Problem Statement for searching a given number of non-intersecting independent sets with maximum sum of vertices’ numbers within independent sets. Based on it, Vizing-Plesnevich algorithm is described for coloring the graph vertices with the minimum number of colors. To solve Boolean problems, both specialized mathematical programming language AMPL and corresponding solver program named gurobi are used. For basic algorithms developed, reference AMPL code versions are given as well as their running results. Illustrative examples of software project enhancing with the algorithms elaborated are considered in Section 4, namely: 25 specialists being conflicted during their previous projects partitioning into coherent conflict-free sub-teams for software projects portfolio; schedule optimization for autonomous testing of reusable components within a critical software system; cores composing for independent teams in a critical software project.
|
| issn |
1727-4907 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/188631 |
| citation_txt |
Пошук максимальних незалежних множин вершин графа для вдосконалення програмних проєктів/ О.О. Слабоспицька, П.І. Стецюк, О.М. Хом’як // Проблеми програмування. — 2022. — № 3-4. — С. 73-84. — Бібліогр.: 12 назв. — укр. |
| work_keys_str_mv |
AT slabospicʹkaoo pošukmaksimalʹnihnezaležnihmnožinveršingrafadlâvdoskonalennâprogramnihproêktív AT stecûkpí pošukmaksimalʹnihnezaležnihmnožinveršingrafadlâvdoskonalennâprogramnihproêktív AT homâkom pošukmaksimalʹnihnezaležnihmnožinveršingrafadlâvdoskonalennâprogramnihproêktív AT slabospicʹkaoo maximumindependentsetsofgraphverticessearchingforsoftwareprojectsimprovement AT stecûkpí maximumindependentsetsofgraphverticessearchingforsoftwareprojectsimprovement AT homâkom maximumindependentsetsofgraphverticessearchingforsoftwareprojectsimprovement |
| first_indexed |
2025-12-07T20:24:19Z |
| last_indexed |
2025-12-07T20:24:19Z |
| _version_ |
1850882454831759360 |