МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ДНІПРОПЕТРОВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

ФІРСОВ ОЛЕКСАНДР ДМИТРОВИЧ

УДК 519.8

МОДЕЛІ І МЕТОДИ ПАРАЛЕЛЬНОГО УПОРЯДКУВАННЯ

01.05.02 – математичне моделювання та обчислювальні методи

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

кандидата фізико – математичних наук

Дніпропетровськ 2002

Дисертацією є рукопис.

Робота виконана на кафедрі обчислювальної математики та математичної кібернетики Дніпропетровського національного університету Міністерства освіти і науки України

Науковий керівник: | кандидат фізико-математичних наук, доцент

Турчина Валентина Андріївна, Дніпропетровський національний університет Міністерства освіти і науки України, доцент кафедри обчислювальної математики та математичної кібернетики.

Офіційні опоненти: | доктор фізико-математичних наук, професор

Перепелиця Віталій Опанасович, Запорізький державний університет Міністерства освіти і науки України, професор кафедри економічної кібернетики (м. Запоріжжя);

кандидат фізико-математичних наук, доцент

Козіна Галина Леонідівна, Запорізький національний технічний університет Міністерства освіти і науки України, доцент кафедри радіотехніки (м. Запоріжжя).

Провідна установа: | Інститут кібернетики ім. В.М. Глушкова НАН України,

відділ методів розв’язування складних задач оптимізації.

Захист відбудеться “12”грудня 2002 р. о 14:00 годині на засіданні спеціалізованої вченої ради К 08.051.09 при Дніпропетровському національному університеті за адресою: пр. Карла Маркса, 35, корп. 3, ауд. 25, м. Дніпропетровськ, 49044.

З дисертацією можна ознайомитись у науковій бібліотеці Дніпропетровського національного університету за адресою: вул. Казакова, 8, м. Дніпропетровськ, 49050.

Автореферат розісланий “11”листопада 2002 р.

Вчений секретар

спеціалізованої вченої ради К 08.051.09 В.А.Турчина

Загальна характеристика роботи

Актуальність теми. Оптимальні розв’язки спеціальних дискретних задач на графах, яким присвячена дисертаційна робота, дозволяють економити ресурси у системах, моделі яких являють собою завдання, на послідовність виконання яких накладено умови часткового порядку. Такими системами можуть виступати як лінії складання, послідовності робіт, так і послідовності операцій, які виконуються ЕОМ. Причому у зв’язку з розповсюдженням багатопроцесорних систем останнє використання стає найактуальнішим.

Практичним застосуванням графових моделей до багатопроцесорних ЕОМ займається ряд наукових шкіл. В обчислювальному центрі МДУ під керівництвом чл.-кор. РАН Воєводіна В.В. проводяться дослідження по узгодженню архітектури ЕОМ та алгоритмів, по розробці відповідного програмного забезпечення. В лабо-раторії ОС МДУ (керівник д. ф.-м. н. Смелянський Р.Л.) проводяться дослідження формальних моделей мультипроцесорних систем. Вчені НДІ багатопроцесорних об-числювальних систем Таганрогського державного радіотехнічного університету дос-ліджують концепцію багатопроцесорних систем з архітектурою, що програмується, та відповідним програмним забезпеченням.

Проблемам сіткового календарного планування, частковими випадками яких є досліджувані у роботі задачі, присвячено роботи вчених Інституту кібернетики ім. В. М. Глушкова: Михалевича В. C., Кукси А.І., Шора Н.З., вчених Новосибірського та Омського університетів: Гімаді Э.Х., Севастьянова С. В., Серваха В.В. та ін.

Напрямки досліджень та підходи до розв’язання проблем, що розглядаються вченими цих наукових шкіл, поєднує те, що вони використовують графові моделі. Причому, так чи інакше, будується упорядкування вершин графу, яке відповідає послідовності виконання завдань будь то на багатопроцесорній системі чи в плані виконання проекту. Тобто розв’язується задача побудови оптимального паралельного упорядкування вершин ациклічного орграфа. Роботи з цього напрямку проводяться як в Україні, так і в країнах “ближнього” та “дальнього” зарубіжжя. У цій сфері працювали: Ху Т., Фуджі М., Гері М., Джонсон Д., Ленстра Д., а також Танаєв В.С., Шкурба В.В., Кукса А.І., Бурдюк В.Я.

Відомо, що загальна задача паралельного упорядкування відноситься до класу NP-повних, тому дослідження поліноміально-розв’язних випадків, якому присвячена дисертаційна робота, є актуальним як з теоретичної, так і з практичної точок зору.

Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана на кафедрі обчислювальної математики та математичної кібернетики Дніпропетровського національного університету згідно з індивідуальним планом підготовки аспіранта та держбюджетною темою 07-174-00 (номер держреєстрації 0100V005244), співвиконавцем якої є дисертант, в рамках наукових програм та планів університету.

Мета і задачі дослідження. Метою дослідження є розробка методів та алгоритмів розв’язування спеціальних оптимізаційних дискретних задач паралельного упорядкування вершин ациклічного орграфу.

Для досягнення цієї мети було визначено такі напрямки досліджень:

1)

2)

3)

4)

5)

Об’єкт дослідження – ациклічні орграфи, що є моделями послідовностей операцій, на які накладено умови часткового порядку.

Предмет дослідження – підкласи графів, для яких здійснюється пошук точних та наближених алгоритмів.

Методи дослідження. При отриманні основних результатів дисертаційної роботи використовувались точні методи розв’язання задач дискретної оптимізації, методи комбінаторного аналізу, методи побудови графічних моделей.

Наукова новизна одержаних результатів. Вперше одержано рішення наукової задачі застосування та обгрунтування єдиного підходу для розробки ефективних алгоритмів розв’язання задач паралельного упорядкування вершин ациклічних орграфів, виділення підкласів графів, для яких існують поліноміальні алгоритми розв’язку задачі паралельного упорядкування у класичній постановці та задачі з додатковими обмеженнями, а також отримання оцінок параметрів паралельних упорядкувань.

Для задачі паралельного упорядкування

-

-

-

-

-

Для задачі паралельного упорядкування з додатковими обмеженнями

-

-

-

-

Практичне значення одержаних результатів. Теоретичні результати, що отримані в дисертації, перш за все можна рекомендувати до використання при аналізі та розробці моделей програм, що реалізуються на багатопроцесорних ЕОМ, а також при узгодженні алгоритмів та архітектури ЕОМ. Крім того, вони можуть використовуватися при складанні розкладів виконання робіт, на порядок яких накладається відношення часткового порядку.

Результати роботи впроваджені в навчальний процес Дніпропетровського національного університету при викладанні дисциплін “Паралельні обчислення”, ”Задачі паралельних упорядкувань” та при виконанні курсових і дипломних робіт.

Особистий внесок здобувача. Всі результати, які становлять суть дисерта-ційної роботи, отримані автором самостійно. В роботах, що написані у співавторстві, дисертанту належать: в [1] доведення теорем та розробка алгоритмів розв’я-зування задач, в [2] ідея аналізу графа, доведення теорем та розробка алгоритмів, в [3] доведення умови існування щільного упорядкування, в [4] отримання умов існування паралельних упорядкувань, що задовольняють директивним термінам, в [6] формулювання та доведення теореми, а також розробка алгоритму, в [5] та [7] розробка алгоритму розв’язування задачі.

Апробація результатів дисертації. Матеріали дисертації доповідались та обговорювались на першій міжнародній конференції “Наука і освіта 98” (Дніпропетровськ 23-30 квітня 1998 року); на XII міжнародній конференції “Проблемы теоретической кибернетики” (Нижній Новгород, 17-22 травня 1999 року); на VII міжнародній конференції “Математика. Компьютер. Образование.” (Дубна, 23-30 січня 2000 року); на міжнародному колоквіумі математиків “IKM’2000” (Веймар, Німеччина, 22-24 червня 2000 року); на IV Всеросійському симпозиумі “Математическое модели-рование и компьютерные технологии” (Кисловодськ, 11-15 липня 2000 року); на міжнародній конференції “МКММ'2000” (п.Лазурне Херсонської обл. 9-14 вересня 2000 року); на міжнародній конференції “Интеллектуальные и многопроцессорные системы - 2001” (Дивноморськ, 1-6 жовтня 2001 року); на міжнародній міждисциплінарній науково-практичній конференції “Сучасні проблеми науки та освіти” (Керч, 27 червня – 4 липня 2001 року); щорічних наукових конференціях за підсумками НДР у Дніпропетровському національному університеті (1998-2002 р.).

Дисертаційна робота в цілому обговорювалась на науковому семінарі кафедри обчислювальної математики та математичної кібернетики Дніпропетровського національного університету.

Публікації. Результати дисертації опубліковано у 7-ми наукових статтях, з них 4 статті у наукових фахових виданнях з переліку, затвердженого ВАК України, 6-ох матеріалах та тезах доповідей конференцій.

Структура та обсяг роботи. Дисертаційна робота складається з вступу, чотирьох розділів, висновків та списку літератури. Робота викладена на 124 сторінках тексту, список використаних літературних джерел містить 116 найменувань.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтовано актуальність теми дисертаційної роботи; зазначено її зв’язок з науковими програмами, планами, темами; сформульовано мету і задачі дослідження; подано характеристику наукової новизни, теоретичного та практичного значення одержаних результатів; відзначено особистий внесок здобувача в публікаціях, виконаних у співавторстві, а також ступінь апробації результатів.

У першому розділі зроблено огляд стану досліджуваної проблеми і вибір напрямків досліджень.

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

Багато практичних задач можуть бути сформульовані в такий спосіб: маємо кінцеве число робіт, на порядок виконання яких накладаються несуперечливі технологічні обмеження. Припустимо, що тривалості робіт однакові. Потрібно організувати таке виконання робіт, при якому:

1)

2)

3)

або:

1)

2)

3)

Для побудови математичної моделі цих задач застосуємо відому формалізацію. Нехай V={1,2,...,n} множина, що відповідає номерам робіт, а UVV, причому (і,j)U тоді і тільки тоді, коли робота і безпосередньо передує роботі j. Тоді граф G=(V,U) буде відповідати технологічним обмеженням на порядок виконання робіт.

Лінійним упорядкуванням S множини V, що складається з n елементів, називається розміщення елементів множини V по n місцях, розташованих у лінію так, що кожен елемент знаходиться тільки на одному місці.

Довжиною l упорядкування S називається число не порожніх місць в ньому.

Шириною h упорядкування S називається величина h(S)=maxS[і], де і=1,...,n, S[і] множина елементів, що знаходяться в упорядкуванні S на місці і.

Паралельним упорядкуванням вершин орграфа G=(V,U) називається таке лінійне упорядкування S його вершин, що якщо (і,j)U (іS[p], jS[q]), то p<q.

Розглянемо наступні оптимізаційні задачі.

Задача 1. По заданому графу G і заданому значенню h треба побудувати паралельне упорядкування мінімальної довжини. Таке упорядкування назвемо оптимальним. Задачу позначимо через S(G,h,l).

Задача 2. По заданому графу G і заданому значенню l, треба побудувати пара-лельне упорядкування мінімальної ширини. Цю задачу позначимо через S(G,l,h).

Упорядкування, на кожному місці якого стоїть h вершин, за виключенням, можливо, останнього, назвемо щільним.

Початок досліджуваних у дисертаційній роботі задач покладено Т.С. Ху. Він розглядає задачу, пов'язану з оптимальною організацією робіт, що відповідають лінії складання. Для цього випадку ним запропонований і теоретично обґрунтований точний, поліноміальний алгоритм, що дозволяє завершити досліджуваний технологічний процес за мінімальний час при умові, що число виконавців фіксоване.

У роботах Бекішева Г.А. продовжені дослідження з даної теми. Він запропонував зведення досліджуваних задач до задач цілочисельного лінійного програмування.

Фуджі М. запропонував точний алгоритм розв’язку задачі в окремому випадку, коли число виконавців дорівнює двом. В основу алгоритму покладена побудова максимального паросполучення в графі.

Фахівці ленінградської школи дослідників Шахбазян К.В., Тушкіна Т.А. засто-сували до даних задач відомий точний підхід, заснований на методі спрямованого перебору (метод “гілок та меж”), і провели обчислювальний експеримент.

Гері М. та Джонсон Д. запропонували ще один підхід до розв’язку задачі у випадку двох виконавців.

Зведенню даних задач до оптимізаційних задач на мережах спеціального виду присвячено роботи Бурдюка В.Я. та Турчиної В.А.

Проведений аналіз відомих результатів виявив, що:

1)

2)

3)

4)

5)

У другому розділі розглянуто метод аналізу довільного графа за допомогою дводольних підграфів та спеціальних множин, які отримали назву множин переходу.

При побудові оптимальних упорядкувань тільки деяка визначена частина вершин графа і відповідні їм зв'язки впливають на оптимальність упорядкування. Інакше кажучи, тільки відносно частини вершин графу існує невизначеність при побудові упорядкування. Тоді можна припустити, що пошук саме цих вершин і буде визначальним при побудові шуканого упорядкування.

Нехай граф має наступну структуру – ациклічний і без транзитивних дуг.

Будь-який граф у такому випадку можна представити як об'єднання двочасткових підграфів, виділених за визначеним правилом. Наприклад, двочасткові підграфи, які одержані з вершин і зв'язків сусідніх множин S[j], S[j+1] абоS[j],S[j+1], де S[j] - відповідає крайньому лівому, аS[j] - крайньому правому положенню вершин в упорядкуванні, побудованому для необмеженого числа виконавців. Усі способи вибору множин для побудови двочасткових підграфів можна описати за допомогою спеціально визначених S-множин вершин графа. Один із варіантів вибору таких множин дозволить аналізувати нові структури графів, а, крім того, ці множини зручно використовувати при генерації довільного графу, відповідаючого заданим умовам, для його застосування при обчислювальному експерименті.

S-множиною назвемо множину Vt, яка побудована з довільного числа вершин підграфа Gt, що не мають вхідних дуг, де підграф Gt одержано в результаті видалення з графа Gt-1 на (t1)-ому кроці вершин множини Vt-1 (V1 – побудована з довільного числа вершин початкового графа G1, які не мають вхідних дуг).

Теорема 1. Якщо для двочасткового орграфа G={V1,V2,U1} виконується умова

di](V2– (h–k))/k[, (1)

де di=deg i, iV1,

k=mod(V1,h), k0 (k дорівнює залишку від ділення V1 на h),

то для цього графа існує щільне упорядкування (у випадку k=0 щільне упорядкування існує завжди).

Складність перевірки співвідношення (1) для графа G={V1,V2,U1} прямо про-порційна числу вершин в ньому.

Застосовуючи умову (1), одержуємо оцінки параметрів упорядкування:

l2max(l,]n/h[)-k, (2)

де k - число підграфів, для яких виконується умова (1),

hmin{(max{S[c], ]S[l-w]/2[}),(max{[c], ][l-w]/2[})}, (3)

де c=l-m; w=1,…,m; m=l-l.

Використовуючи такий підхід, можна одержати ряд верхніх оцінок параметрів упорядкування для різних класів графів. Крім того, можна будувати оцінки для конкретних графів з урахуванням їх індивідуальної структури і можливостей обчислювальної техніки.

Узагальнимо умову (1) на випадок довільного графа.

Введемо підмножину вершин Ktj множини Vt, таку, що Ktj=kt=mod(Vt,h), t=1,…,l, j=1,…,. Позначимо через i множину безпосередніх послідовників вершини iV1, а через tj= множину безпосередніх послідовників вершин множини Ktj.

Тоді у разі існування щільного упорядкування буде існувати визначена підмножина вершин Ktj множини Vt та підмножина вершин з h-Ktj вершин множини Vt+1, що не належать відповідній множині tj. Причому вони будуть стояти на одному місці в упорядкуванні і утворювати множину, яка є визначальною при побудові щільного чи оптимального упорядкування, у разі якщо щільне не існує.

Назвемо множину S[j] в упорядкуванні S множиною переходу між S-множинами Vt і Vt+1 , якщо вона складається з вершин тільки цих множин (з кожної множини Vt та Vt+1 множині S[j] належить хоча б одна вершина). Число усіх варіантів вибору таких множин з множини V не більше . У конкретному упорядкуванні така множина може бути тільки одна.

Теорема 2. Якщо для кожного двочасткового підграфу Dt={Vt,Vt+1,Ut}, t=1,…,l–1, графа G, виконується умова dti](Vt+1–(h–kt))/kt[, де dti=deg i, iVt; kt+1=mod(Vt+1–(h–kt), h); то для нього існує щільне упорядкування фіксованої ширини h.

Дослідимо умову теореми 2 з метою одержання числових характеристик підкласу графів, що вона описує.

Граф G можна однозначно задати, знаючи число вершин на кожній S-множині і зв'язки між вершинами. Умова теореми 2 дозволяє оцінити число вершин на кожнім рівні, при заданих di і h.

При фіксованому h величина Vt+1dtjktj+(h–ktj)–ktj ; ktj може набувати значення від нуля до h–1. Максимальне значення вираз, що стоїть праворуч, набуде у випадку максимального ktj. Тоді одержимо Vt+1>dtj(h–1)–h+2.

Якщо dtj=2, що відповідає підкласу графів, які описують обчислення нерозгалуджених арифметичних операцій (графи мають зворотну орієнтацію), то Vt+1>h. Тобто для таких графів виконується рівневий принцип вибору вершин.

Якщо dtj=1, що відповідає підкласу графів, кожен з яких є кореневим деревом або лісом з таких дерев, то Vt+1>1, з чого випливає, що для дерева виконується рівневий принцип вибору вершин. Таким чином, застосування запропонованого підходу дозволяє в окремому випадку одержати класичний результат.

Далі методика аналізу множин переходу між S-множинами була застосована для розв’язування задачі S(G,2,l).

Щільне упорядкування існує, якщо існує такий набір множин tj та Ktm, що виконується умова:

tjKtm=, (4)

де t=1,…,l,

tj=, 1j= (множина вершин - безпосередніх послідовників Ktm).

А оскільки у цьому випадку k=1, то tj=t. Іншими словами, в графі визначені множини переходу для кожного рівня. Складність перевірки цієї умови визначається числом множин Ktj та tj на кожнім рівні, що у випадку h=2 і повному переборі варіантів приводить до складності розв’язування задачі O().

Виберемо S-множину як S[j] для графа G, отриманого в результаті доповнення вихідного графа G підграфами, що складаються з ланцюжків вершин так, що усі вершини лежать на критичних шляхах. Причому після побудови упорядкування S[j] для графа G вершини, що не належать графу G, із множин S[j] видаляються.

Проаналізуємо двочасткові підграфи, утворені цими S-множинами. Врахуємо, що у цьому випадку k може набувати значення 0 чи 1 (у разі k=0 вибір вершин довільний).

У випадку, якщо граф G такий, що l>2, для існування щільного упорядкування повинна виконуватися умова (4). Порушення цієї умови можливо, якщо множина переходу між рівнями відсутня або перетинання множин переходу для сусідніх рівнів не порожнє. Визначимо далі умову існування щільного впорядкування для довільного графа у досліджуваному випадку.

Теорема 3. Якщо між кожною S-множиною графа G визначено більше однієї множини переходу (на кожній S-множині вираз 1 виконується більш ніж для однієї вершини), то для даного графа існує щільне упорядкування ширини h=2.

Теорема доведена конструктивно, її доведення покладено в основу алгоритму розв’язку задачі S(G,2,l).

Тобто, за допомогою метода аналізу S-множин та множин переходу було одержано алгоритм, що не перевищує по складності алгоритм, запропонований Джонсом Д. та Гері М. Даний алгоритм не пропонується як альтернатива вже існуючому, що пов'язано з очевидною перевагою відомого алгоритму у простоті реалізації. Але, таким чином, ще раз підтверджується життєздатність запропонованого метода аналізу графів. Наступним кроком у застосуванні метода стало дослідження випадку, коли h=3.

Скористаємося введеними вище множинами переходу S[j] і підмножинами Ktr та tr. Якщо h=3, то kt може приймати значення 0,1,2. Множину переходу S[j], у якій kt=1 позначимо S1[j]. Використовуючи введене позначення, сформулюємо теорему.

Теорема 4. Якщо для множин Vt, Vt+1 (t=1,…,l-1) графа G існує більш одного варіанту вибору множин переходу S1 і виконуються умови:

1) M2M2=, де М2 – деяка множина з двох вершин, що належать одному з варіантів вибору множини S1\Ktr, а М2- деяка множина з двох вершин, що належать іншому варіанту вибору множини S1\Ktr;

2) для множин М2 і М2 існує хоча б одна вершина, що належить Vt і не є безпосереднім попередником вершин з цих множин;

то для графа G існує щільне упорядкування його вершин ширини h=3.

На основі конструктивного доведення цієї теореми запропоновано алгоритм побудови щільного упорядкування у випадку, коли виконуються вимоги теореми.

Покажемо складність розв’язку задачі S(G,3,l) для випадків коли l дорівнює 2, 3 та 6.

Твердження 1. Складність алгоритму розв’язку задачі S(G,3,l) у випадку, коли граф G=(V1,V2,U) – двочастковий, не перевершує О(n).

Виходячи з доведення твердження, запропоновано алгоритм розв’язку задачі S(G,3,l) для двочасткового графа.

Визначення. Тричастковим графом G=(V1,V2,V3,U) назвемо граф у якого l=3.

Твердження 2. Складність алгоритму розв’язку задачі S(G,3,l) у випадку, коли граф G=(V1,V2,V3,U) – тричастковий, не перевершує О(n2).

Алгоритм розв’язку задачі S(G,3,l) для тричасткового графу випливає з доведення твердження та попереднього алгоритму.

Визначення. Шестичастковим графом G=(V1,V2,V3,V4,V5,V6,U) назвемо граф у якого l=6.

Твердження 3. Складність алгоритму розв’язку задачі S(G,3,l) у випадку, коли граф G=(V1,…,V6,U) – шестичастковий, не перевершує О(n4).

Узагальнюючи отримані результати, для довільного графа одержано оцінку складності зверху наступного виду О(n]l/3+1[). При такому підході зберігається експоненційна складність розв’язку задачі S(G,3,l), але, очевидно, що вона значно нижча складності розв’язку даної задачі за допомогою узагальненого варіанту методу гілок та меж, чи розв’язку відповідної задачі ЦЛП.

Найкращим результатом, що дозволяє одержати наближений розв’язок задачі S(G,3,l), є алгоритм точного розв’язку задачі S(G,2,l) за допомогою лексикографічної нумерації вершин. Оцінка точності зверху для нього 2–2/h. У випадку h=3 одержуємо, що довжина упорядкування побудованого за допомогою лексикографічного підходу, не більш ніж у 1,33 рази перевершує оптимальну.

Використовуючи результати тверджень 1-3, пропонується наступний підхід і алгоритм наближеного розв’язку задачі S(G,3,l) з гарантованою похибкою.

Виділимо в довільному графі кінцеве число підграфів, що складаються з однакового числа S-множин. Розв’яжемо задачу S(G,3,l) для кожного з цих підграфів. Розв’язок загальної задачі одержимо у вигляді щільної послідовності упорядкувань для підграфів. При такому підході, у гіршому випадку, довжина упорядкування виросте, у порівнянні з оптимальним, на k1 місце, де k - число S-множин у підграфі.

Розіб'ємо граф G (l>5) на шестичасткові підграфи. Тоді відповідно до твердження 3, складність алгоритму розв’язку задачі S(G,3,l) для кожного підграфу не перевершує О(n5).

Доведено, що співвідношення довжини наближеного упорядкування до оптимального при такому підході наближається до значення 9/8.

Використовуючи розбивку графа на підграфи, можна отримати цілий ряд наближених алгоритмів для інших значень h та окремих підкласів графів.

Для відповіді на питання: які властивості повинен мати довільний граф, упорядкування вершин якого, побудоване згідно з рівневим принципом, буде оптимальним, досить у якості множин Vt, використаних у теоремі, взяти множиниS[j], відповідні визначенню рівня, та застосувати умови доведених теорем.

Отримано умови, при яких рівневий принцип вибору вершин при побудові оптимального упорядкування може бути порушений.

Твердження 4. Рівневий принцип вибору вершин порушується, якщо всі множини переходу між рівнями 1 і 2 належатьS[2]S[1].

Твердження 5. Рівневий принцип вибору вершин у межах одного рівня порушується, якщо рівню 1 належать вершини, які не входять ні в один з варіантів вибору множин переходу між рівнями 1 і 2.

Виділимо підклас графів, для яких лексикографічна нумерація вершин дозволить побудувати оптимальне упорядкування вершин довільної ширини.

Розглянемо граф G, для якого не існує множин переходу, таких, що вершини, які його утворюють, не належать сусіднім рівням. І нехай h довільне.

Розглянемо S-множини, які відповідають рівням, позначимо їх через Vt (t=1,…,l), та підмножини вершин Ktr множин Vt і tr, які введені раніше.

Нехай вершини графа пронумеровані згідно лексикографічного принципу. Тоді підмножини Ktr і відповідно tr будуть однозначно визначені відносно номерів вершин, що входять у ці підмножини. Для побудови щільного упорядкування вершини підмножини Ktr не повинні бути зв’язані з (hkr) вершинами наступного рівня, що мають максимальні номери в межах цього рівня.

Твердження 6. Щільне упорядкування вершин графа G може бути отримане в результаті лексикографічної нумерації його вершин, якщо вершини підмножини Ktr не зв’язані з (hkt) вершинами наступного рівня, що мають максимальні номери в межах цього рівня.

У класі задач теорії розкладів велика увага приділяється задачам, у яких одним із заданих параметрів є директивний термін. Розглянемо одну з таких задач, що виникає при побудові паралельного впорядкування, і застосуємо для неї аналіз двочасткових підграфів.

Нехай завдання із множини V={1,...,n} обслуговуються h паралельними ідентичними приладами. Не втрачаючи загальності, вважатимемо тривалість обслуговування всіх завдань однаковими. Для кожного завдання задано директивний термін (до якого необхідно завершити його обслуговування).

Заборонено переривання в обслуговуванні завдань. На множині задане відношення часткового порядку, що визначає можливу послідовність обслуговування завдань.

Поставимо у відповідність завданню вершину v орграфа. Граф редукції цього відношення позначимо через G={V,U}.

Вершину графа G={V,U} представимо у вигляді одноелементної множини і позначимо {v}kj, де (=1,...,d) - директивний термін; k - індекс, що відповідає вершині з директивним терміном у множині S[j] (якщо кількість вершин, що мають директивний термін , дорівнює p, то k=1,...,p), j – номер множини S[j].

Проаналізуємо множини S[j]. Використовуючи наведені позначення, представимо множину V у вигляді:

( {v}1k1 ) ( {v}2k1 ) ...( {v}dk1 )

( {v}1k2 ) ( {v}2k2 ) ...( {v}dk2 ) (8)

( {v}1kl ) ( {v}2kl ) ...( {v}dkl )=V

Представлення (8) однозначно описує положення вершини з директивним терміном у графі відносно множин S[j] (строка j співвідношення (8) відповідає S[j]). Існування вершини з директивним терміном , що стоїть на позиції j, і виконання умови <j для цієї вершини роблять неможливим побудову розкладу, що задовольняє заданим директивним термінам. Таким чином, приходимо до необхідної умови існування шуканого упорядкування, а саме виконання рівності:

S[j]{v}kj = , =1,...,j-1, j=2,...,l. (9)

З урахуванням (8) та (9) одержуємо необхідну умову існування упорядкування, що не порушує задані директивні терміни:

] {v}kj /[h. (10)

Третій розділ присвячено дослідженню узагальненої задачі паралельного упорядкування.

Введемо додаткові обмеження, які приводять до узагальнення. Тоді задачу можна сформулювати наступним чином. Дано орієнтований граф G={V,U}, V=n (n - число вершин) і параметри hj (j=1,…,l) - обмеження на потужність множин S[j]. Потрібно побудувати таке упорядкування S, що на кожнім із j місць стоїть не більш hj вершин, причому l(S) - мінімальне. Позначимо цю задачу S(G,hj,l).

Для дерева існує розроблений Т. Ху точний алгоритм побудови оптимального упорядкування для випадку, коли hj=const (j=1,…,l). У випадку ж, коли hj-довільні, рівневий принцип може порушуватися. Доведено умову порушення рівневого принципу.

Позначимо S[1]j (j=2,…,l) – як множину S[1], одержувану для кожного підграфа Gj в результаті видалення з нього, у процесі побудови упорядкування, hj-1 вершин, S[1]1 – відповідає множині S[1] побудованої для вихідного графа. Тоді сформулюємо наступне твердження.

Теорема 8. Порушення рівневого принципу вибору вершин можливо тільки у випадку, коли існує j, таке, що виконується нерівність:

hj<S[1]j< hj+1+ hj, (10)

де j=1,…,l.

Наслідок 1. У випадку виконання умови теореми 8 порушення рівневого принципу вибору вершин можливе тільки у випадку, коли hjhj+1.

Наслідок 2. Якщо не існує j такого, що hj<S[1]j<hj+1+hj, де j=1,…,l, то HLF – стратегія вибору вершин оптимально розв’язує задачу S(G,hj,l).

Для побудови оптимального упорядкування вершин ордерева у разі обмежень, які задані для кожного місця в упорядкуванні, доведено оптимальність відомого алгоритму.

Як було показано, задача S(T,hj,l) не може бути розв’язана точно класичним алгоритмом, що базується на рівневому принципі.

Дослідимо цей принцип для випадку, коли hj дорівнює 1 чи 2.

Розглянемо відомий алгоритм розв’язку задачі S(G,2,l), що базується на лексикографічному порядку нумерації вершин. Покажемо, що він буде оптимальним для довільного орграфу без транзитивних дуг та випадку, коли hj дорівнює 1 чи 2.

Нехай вершини графа G занумеровано згідно з лексикографічним порядком, та l 2.

Лема 1. В кожному підграфі G графа G, що отриманий внаслідок вилучення з початкового графа k вершин з максимальними номерами, зберігається початкова лексикографічна нумерація.

Теорема 9. Алгоритм розв’язку задачі S(G,2,l), що базується на лексикографічному порядку нумерації вершин, точно розв’язує задачу S(G,hj,l) у випадку, коли hj може набувати значення 1 або 2.

Крім розглянутих часткових випадків для узагальненої задачі досліджуються відомі точні алгоритми.

Для точного розв’язку задачі S(G,h,l) можна застосовувати метод “гілок та меж”, причому метод можна застосовувати безпосередньо в термінах розв'язуваної задачі, на відміну від інших методів, що вимагають зведення цієї задачі до інших оптимізаційних задач, таких як ЦЛП, чи максимальний умовний потік.

Застосуємо метод “гілок та меж” для розв’язку задачі S(G,l,hj) у тому випадку, якщо існує таке щільне упорядкування S, для якого S[j]=hj, j=1,...,l.

Для використання методу необхідно задати правило розбивки припустимої множини на підмножини і спосіб обчислення оцінки цільової функції на припусти-мих підмножинах. У якості оцінки візьмемо умову щільності упорядкування.

Далі наведено реалізовану схему побудови упорядкування.

Для кожної вершини v визначаємо інтервал припустимих місць Idmv. Номера позицій, на яких дана вершина стоїть в упорядкуваннях S іS+ (деS+ - упорядкування, в якому множиниS+[k] (k=1,...,l), визначають крайнє праве розташування вершин в упорядкуванні довжини l при необмеженому h), дають границі інтервалу і його місце розташування на цілочисельної множині L={1,...,l}.

Об'єднаємо інтервали припустимих місць Idmv (v=1,…,n) однакової довжини, з однаковим номерами позицій, на яких дана вершина стоїть в упорядкуванні S, у групи інтервалів припустимих місць GIdmzr, де - z номер групи, r - число інтервалів, що входять у цю групу.

Поставимо вершину v1 з інтервала Idmv1 в упорядкування S на місце k1. Тоді перевіримо умову щільності упорядкування для вершин із груп інтервалів припустимих місць GIdmze (для яких номери позицій вершин, що їх утворюють, стоять в упорядкуванніS, лівіше номера позиції, на якому утворююча інтервал Idmv1 вершина стоїть в упорядкуванні S).

Перевіримо умову щільності, якщо буде потрібно, для всіх можливих розміщень вершин в упорядкуванні S. Якщо вона виконується для всіх вершин графа, то побудоване в такий спосіб упорядкування буде шуканим.

Використання сіткового підходу дає змогу точно розв’язувати задачі S(G,hj,l) та S(G,l,hj). Вперше алгоритм розв’язування задачі про максимальний умовний потік для задач S(G,h,l) та S(G,l,h) був застосований Турчиною В.А. Розглянемо задачу S(G,hj,l) у наступній постановці.

Нехай заданий набір обмежень, такий, що n, де r – номер останнього обмеження, n - кількість вершин у графі. Необхідно побудувати упорядкування, яке відповідало б набору обмежень, та мало мінімальну довжину.

Побудуємо (s,t) - мережу спеціального виду. Основу її буде складати двочастковий граф G1={V1V2,U1}, V1=V.

Визначаємо множину V2 та набір обмежень Hk, за допомогою розробленого алгоритму. При цьому будуть отримані й обмеження на місця p+1,p+2,…,l.

Вводимо джерело s і стік t, а також дуги (s,r) для будь-якого jV1, дуги (r,t) для любого rV2. Зв'язки між множинами V1 і V2 визначаємо так: якщо r[j,j], те вводимо дугу (j,r) (тут j,j - місце вершини і відповідно в упорядкуваннях S, S.

Пропускні спроможності дуг (s,j) для будь-якого jV1 і дуг (j,r) для будь-якого rV2 вва-жаємо рівними одиниці, а пропускні спроможності дуг (j,r) вважаємо рівними значенням еле-ментів послідовності Hk. Для розв’язування поставленої за-дачі використовуємо алгоритм пошуку максимального умовного потоку. За скінченну кількість кроків буде побудований потік величини n, а, отже, розв’язана вихідна задача.

Упорядкування при цьому будується в такий спосіб: якщо потік по дузі (j,r) (jV1; rV2) дорівнює одиниці, то в упорядкуванні вершина j ставиться на місце r.

Оскільки пропускна спроможність дуги (r,t) ( rV2) дорівнює hr, то потік по цій дузі не більше hr, а, отже, на r-ому місці в упорядкуванні буде стояти не більш hr вершин, тобто умова задачі виконується. Оптимальність гарантується оптимальністю алгоритму пошуку максимального умовного потоку.

При вирішенні практичних задач, тобто побудові упорядкувань для довільних графів, виникає питання поведінки алгоритмів в середньому. Тому у четвертому розділі було проведено обчислювальний експеримент з метою порівняння поведінки алгоритмів, що базуються на рівневій стратегії, лексикографічній нумерації та ме-тоді “гілок та меж” для спеціально виділених підкласів графів.

Генерація графу була реалізована за наступною схемою.

1.

2.

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

Таким чином, у середовищі Delphi 6.0 було реалізовано генерацію графів з урахуванням задання числа вершин на рівні (фіксованого чи випадкового із заданого діапазону) та імовірності появи зв’язку між двома вершинами (вибору підкласу графів).

Обчислення були організовані наступним чином: для підкласів графів з ймовірностями виникнення зв’язку від 5 до 95 з шагом 5 генерувалися по 100 графів з заданими параметрами вибору обмежень на кількість вершин на рівні, для кожного з них будувались упорядкування за допомогою методу “гілок та меж”, рівневого принципу та лексикографічної нумерації (у випадку коли h дорівнює трьом за допомогою запропонованого у розділі 2 наближеного алгоритму), обчислювались середні значення довжини упорядкування для кожної з ймовірностей, співвідношення між середніми значеннями довжин та заносились до таблиць по даним з яких будувалися гістограми.

Отримані дані дозволяють зробити висновок, що застосування алгоритмів, що використовують рівневу стратегію та лексикографічну нумерацію для довільних графів може давати задовільні для практичного застосування результати, причому точність роботи досліджених алгоритмів залежить від кількості зв’язків між вершинами та числа вершин на кожному рівні.

ВИСНОВКИ

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

Основні наукові результати роботи полягають у наступному.

Для задачі паралельного упорядкування вершин ациклічного орграфу розроблено новий метод аналізу орграфів, який узагальнює відомі підходи до її розв’язання.

За допомогою розробленого методу виділені підкласи графів, для яких доведено можливість побудови точних поліноміальних алгоритмів розв’язання задач паралельного упорядкування.

Для виділених підкласів графів розроблено точні поліноміальні алгоритми побудови паралельних оптимальних упорядкувань.

Розроблено поліноміальний алгоритм побудови наближеного упорядкування для випадку трьох виконавців.

Отримано умови, при яких відомі алгоритми, що базуються на рівневому принципі та лексикографічній нумерації, не дозволяють побудувати оптимальні упорядкування вершин графу.

Отримано нові оцінки довжини та ширини паралельних упорядкувань.

Для задачі паралельного упорядкування з додатковими обмеженнями у вигляді директивних термінів вперше отримано умови існування паралельних упорядкувань.

Для узагальненої задачі паралельного упорядкування вперше застосовано точні методи розв’язку.

Обгрунтовано відомі алгоритми пошуку розв’язку узагальненої задачі для випадку, коли граф є деревом, та для випадку, коли обмеження на ширину упорядкування не перевищує двох.

Для цієї задачі вперше отримано умови, при яких застосування відомого алгоритму, що базується на рівневому принципі, не є оптимальним.

Проведено обчислювальний експеримент, у якому протестовано поведінку в середньому відомих алгоритмів та показано, що алгоритм, який використовує лексикографічну нумерацію, не є оптимальним для підкласу графів, що є моделлю послідовностей нерозгалуджених арифметичних операцій.

Вірогідність усіх отриманих в роботі результатів підтверджується коректністю формулювання поставлених задач та строгістю математичних викладок.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.