Федоренко Н. К. Розробка методів і алгоритмів розв'язання аномальних та узагальнених задач паралельного упорядкування

Об'єкт - оптимізаційні задачі на графах та методи їх розв'язання. Мета - розробка методів та алгоритмів розв'язання аномальних та узагальнених задач паралельного упорядкування. Методи - методи дискретної оптимізації, комбінаторного аналізу, статистичного аналізу. У роботі сформульовано та доведено необхідні умови виникнення чотирьох основних типів аномалій для задачі побудови паралельного упорядкування заданої ширини та мінімальної довжини для орграфів із неодиничними вагами вершин за умови заданого списку пріоритетів і для двоїстої до неї задачі. Виділено класи орграфів, для яких наявність транзитивних дуг не впливає на оптимальність алгоритму, заснованого на розстановці лексикографічних поміток, а також класи орграфів, для яких наявність транзитивних дуг завжди впливатиме на оптимальність. Визначено необхідні умови, за яких в оптимальному розв'язку задачі паралельного упорядкування спостерігатиметься порушення рівневого принципу. Запропоновано оцінки ширини упорядкування при розв'язанні задачі побудови паралельного упорядкування заданої довжини і мінімальної ширини. Розроблено алгоритми розв'язання класичних та узагальнених задач паралельного упорядкування, а саме, алгоритми побудови оптимального паралельного упорядкування мінімальної ширини при заданій довжині, алгоритм побудови всіх паралельних упорядкувань заданої довжини, алгоритми побудови паралельних упорядкувань заданої ширини, а також паралельних упорядкувань із шириною, що задана обмежуючою послідовністю, і алгоритми побудови паралельних упорядкувань для орграфів із двома типами вершин. Сфера - розпаралелення обчислень, управління ресурсами, навчальний процес.