Пошук максимальних незалежних множин вершин графа для вдосконалення програмних проєктів - Слабоспицька, О.О.; Стецюк, П.І.; Хом’як, О.М. (Проблеми програмування, 2022)
Зафіксовано потребу вдосконалення програмного проекту за рахунок непротирічної інтеграції технологічно-описового та нормативного підходів проектного менеджменту шляхом налаштування класичних задач дискретної оптимізації на графах для задач керування програмним проектом, кращі практики розв’язання яких недостатньо регламентовані в руслі технологічного підходу. Запропоновано клас задач керування програмним проектом для демонстрації перспективності зазначеної інтеграції. Досліджено дві задачі булевого лінійного програмування для знаходження деякої незалежної множини максимального розміру (розділ 1) та алгоритм знаходження всіх можливих незалежних множин максимального розміру (розділ 2). У розділі 3 надано постановку задачі знаходження заданої кількості незалежних множин, які не перетинаються й мають найбільшу суму кількостей вершин у незалежних множинах. На її основі описано алгоритм Візинга-Плесневича для розфарбування вершин графа мінімальною кількістю кольорів. Для розв’язання булевих задач використано спеціалізовану мову математичного програмування AMPL і відповідну їй програму-солвер gurobi. Для основних розроблених алгоритмів наведено рамкові версії коду мовою AMPL та результати їх запускання. У розділі 4 розглянуто показові приклади вдосконалення програмного проекту за допомогою розроблених алгоритмів: формування з 25 фахівців, між якими в попередніх проектах мали місце конфлікти, згуртованих безконфліктних під-команд для портфеля програмних проектів; оптимізації розкладу автономного тестування компонентів повторного використання в складі критичної програмної системи; формування ядер незалежних команд у критичному програмному проекті.