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