Registration Number
0412U002676, Candidate dissertation
Status
к.ф.-м.н.
Date
18-05-2012
popup.evolution
.
Title
Development of methods and algorithms for solving anomalous and generalized parallel scheduling tasks
Author
Fedorenko Nataliya Konstantinovna,
popup.head Turchyna Valentyna Andreevna
popup.opponent Козін Ігор Вікторович
popup.opponent Ус Світлана Альбертівна
popup.rada
Dniepropetrovsk national university
Description
Об'єкт - оптимізаційні задачі на графах та методи їх розв'язання. Мета - розробка методів та алгоритмів розв'язання аномальних та узагальнених задач паралельного упорядкування. Методи - методи дискретної оптимізації, комбінаторного аналізу, статистичного аналізу. У роботі сформульовано та доведено необхідні умови виникнення чотирьох основних типів аномалій для задачі побудови паралельного упорядкування заданої ширини та мінімальної довжини для орграфів із неодиничними вагами вершин за умови заданого списку пріоритетів і для двоїстої до неї задачі. Виділено класи орграфів, для яких наявність транзитивних дуг не впливає на оптимальність алгоритму, заснованого на розстановці лексикографічних поміток, а також класи орграфів, для яких наявність транзитивних дуг завжди впливатиме на оптимальність. Визначено необхідні умови, за яких в оптимальному розв'язку задачі паралельного упорядкування спостерігатиметься порушення рівневого принципу. Запропоновано оцінки ширини упорядкування при розв'язанні задачі побудови паралельного упорядкування заданої довжини і мінімальної ширини. Розроблено алгоритми розв'язання класичних та узагальнених задач паралельного упорядкування, а саме, алгоритми побудови оптимального паралельного упорядкування мінімальної ширини при заданій довжині, алгоритм побудови всіх паралельних упорядкувань заданої довжини, алгоритми побудови паралельних упорядкувань заданої ширини, а також паралельних упорядкувань із шириною, що задана обмежуючою послідовністю, і алгоритми побудови паралельних упорядкувань для орграфів із двома типами вершин. Сфера - розпаралелення обчислень, управління ресурсами, навчальний процес.
Registration Date
2012-05-31
popup.nrat_date
2020-04-04 / 2026-06-30
