Search academic texts

Information × Registration Number 0412U002676, Candidate dissertation Status к.ф.-м.н. Date 18-05-2012 popup.evolution o 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 Ус Світлана Альбертівна Description Об'єкт - оптимізаційні задачі на графах та методи їх розв'язання. Мета - розробка методів та алгоритмів розв'язання аномальних та узагальнених задач паралельного упорядкування. Методи - методи дискретної оптимізації, комбінаторного аналізу, статистичного аналізу. У роботі сформульовано та доведено необхідні умови виникнення чотирьох основних типів аномалій для задачі побудови паралельного упорядкування заданої ширини та мінімальної довжини для орграфів із неодиничними вагами вершин за умови заданого списку пріоритетів і для двоїстої до неї задачі. Виділено класи орграфів, для яких наявність транзитивних дуг не впливає на оптимальність алгоритму, заснованого на розстановці лексикографічних поміток, а також класи орграфів, для яких наявність транзитивних дуг завжди впливатиме на оптимальність. Визначено необхідні умови, за яких в оптимальному розв'язку задачі паралельного упорядкування спостерігатиметься порушення рівневого принципу. Запропоновано оцінки ширини упорядкування при розв'язанні задачі побудови паралельного упорядкування заданої довжини і мінімальної ширини. Розроблено алгоритми розв'язання класичних та узагальнених задач паралельного упорядкування, а саме, алгоритми побудови оптимального паралельного упорядкування мінімальної ширини при заданій довжині, алгоритм побудови всіх паралельних упорядкувань заданої довжини, алгоритми побудови паралельних упорядкувань заданої ширини, а також паралельних упорядкувань із шириною, що задана обмежуючою послідовністю, і алгоритми побудови паралельних упорядкувань для орграфів із двома типами вершин. Сфера - розпаралелення обчислень, управління ресурсами, навчальний процес. Registration Date 2012-05-18 popup.nrat_date 2020-04-04 Close