Моделі і методи паралельного упорядкування

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

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

УДК 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] отримання умов існування паралельних упорядкувань, що задовольняють директивним термінам, в [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 найменувань.

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

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

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

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

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

у кожен фіксований момент часу виконується число робіт, обмежене однією і тією же константою;

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

усі роботи завершуються в мінімальний термін;

або:

усі роботи завершуються в заданий термін;

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

потрібно мінімальне число виконавців.

Для побудови математичної моделі цих задач застосуємо відому формалізацію. Нехай 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 вершин, за виключенням, можливо, останнього, назвемо щільним.

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

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

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

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

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

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

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

не досліджене питання існування щільного розв'язку задачі, коли в кожен фіксований момент часу задіяна одна і та ж кількість виконавців;

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

практично не досліджене питання існування ефективних методів розв'язку задач для випадку, коли число виконавців змінне;

потрібно виділення підкласів задач, для яких існують точні алгоритми, що мають поліноміальну складність;

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

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

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

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

Будь-який граф у такому випадку можна представити як об'єднання двочасткових підграфів, виділених за визначеним правилом. Наприклад, двочасткові підграфи, які одержані з вершин і зв'язків сусідніх множин 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 вершин, тобто умова задачі виконується. Оптимальність гарантується оптимальністю алгоритму пошуку максимального умовного потоку.

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

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

Генеруються S-множини із заданими параметрами (при цьому задамо кількість вершин у кожній множині).

Генеруються зв'язки між вершинами j-ої та (j+1)-ої S-множин.

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

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

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

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

ВИСНОВКИ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фірсов О.Д. Наближений розв'язок задачі побудови паралельного упорядкування ширини три // Вісник Запорізького державного університету. -Запоріжжя: ЗДУ. - 2001. - №2. - С.98-104.

Фірсов О.Д., Турчина В.А. Аналіз графів за допомогою S-множин // Динамические системы. - Симферополь: КФТ. - 2001. - С.191-196.

Фирсов А.Д., Турчина В.А. Исследование плотных упорядочений для некоторых специальных структур // Вопросы прикладной математики и математического моделирования. - Дніпропетровьск: ДДУ. -1998. -С.194-196.

Турчина В.А., Фирсов А.Д. Условия существования параллельных упорядочений, удовлетворяющих директивным срокам // Питання прикладної математики і математичного моделювання. - Дніпропетровьск: ДДУ. - 1999. -С.144-146.

Турчина В.А., Фирсов А.Д. Алгоритм направленного перебора для построения плотных упорядочений // Питання прикладної математики і математичного моделювання. -Дніпропетровьск: ДНУ. - 2000. - С.79-85.

Турчина В.А., Фирсов А.Д. Исследование специальных моделей, описывающих технологические процессы // Сборник научных трудов “Математика. Компьютер. Образование”. М.:МГУ. -1999. -С. 169-173.

Турчина В.А., Фирсов А.Д. Сетевой подход к решению обобщенной задачи параллельного упорядочения // Математическое моделирование в образовании, науке и промышленности. -Санкт-Петербург. 2000. -С.181-183.

Турчина В.А., Фирсов А.Д. Генетический алгоритм решения задачи составления расписания с частичным порядком выполнения работ // Матеріали міжнародної міждисциплінарної науково-практичної конференції. Частина I. Харків. -2001. -С.222-223.

Турчина В.А., Фирсов А.Д. Исследование обобщенной задачи многопроцессорного расписания // Тезисы докладов международной конференции “Интеллектуальные и многопроцессорные системы”. Таганрог: Изд-во ТРТУ. -2001. -С.188-189.

Турчина В.А., Фирсов А.Д. Исследование обобщенной задачи упорядочения вершин графов, моделирующих специальные технологические процессы // Математическое моделирование и вычислительный эксперимент в естественных и гуманитарных науках. Часть II. Т.2. Кисловодск. 2000. С.69-70.

Турчина В.А., Фирсов А.Д. Некоторые специальные вопросы распараллеливания вычислений // Матеріали першої межнародної Наука і освіта 98”. Том 10. Дніпропетровьск: Наука і освіта. 1998. С.419.

Турчина В.А., Фирсов А.Д. Специальные параллельные упорядочения // Проблемы теоретической кибернетики. Тезисы докладов XII Международной конференции. Часть II. М.: МГУ. 1999. С.228.

Phirsof Alexander. Research of special models describing technological processes // IKM'2000:Digital Proceedings. - Bauhaus-Universitдt Weimar. -2000. -6p.

АНОТАЦІЯ

Фірсов О.Д. Моделі і методи паралельного упорядкування. Рукопис.

Дисертаційна робота на здобуття наукового ступеня кандидата фізико-математичних наук по спеціальності 01.05.02 - математичне моделювання та обчислювальні методи. Дніпропетровський національний університет, Дніпропетровськ, 2002.

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

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

Ключові слова: паралельне упорядкування, орграф, ширина упорядкування, довжина упорядкування, оцінка, мінімізація.

ANNOTATION

Firsov O.D. Models and methods of parallel schedulings. - Manuscript.

The dissertation for candidate degree in Physics and Mathematics by speciality 01.05.02 - mathematical modeling and computational methods. - Dniepropetrovsk National University, Dniepropetrovsk, 2002.

The dissertation is devoted to development of the methods and algorithms for solving the special discrete optimization problems of a parallel scheduling.

The new method of a digraph analysis, which allows to get estimations of the parallel scheduling parameters, has been proposed and substantiated in the dissertation. The new algorithms of building the optimal parallel schedulings, based on the proposed method, have been developed. The solution of the problem of parallel scheduling under the fixed value of one of parameters has been improved. The conditions of existence of the parallel scheduling, which satisfies the directive terms, have been received for the first time. The research of the generalized problem parallel scheduling with new bounds has received the further development.

Key words: parallel scheduling, digraph, width of scheduling, length of scheduling, estimation, minimization.

АННОТАЦИЯ

Фирсов А.Д. Модели и методы параллельного упорядочения. Рукопись.

Диссертационная работа на соискание ученой степени кандидата физико-математических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы. Днепропетровский национальный университет, Днепропетровск, 2002.

Работа посвящена разработке методов и алгоритмов решения специальных оптимизационных дискретных задач параллельного упорядочения.

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

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

На основе разработанного метода получены новые оценки параметров упорядочений. Предложена схема получения верхних оценок параметров упорядочений.

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

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

Получены необходимые условия существования параллельных упорядочений, которые удовлетворяют директивным срокам.

Глубже исследована обобщенная задача параллельного упорядочения. Впервые получено достаточное условие нарушения уровневого принципа построения оптимального упорядочения в случае, если ширина является сменным параметром. Доказано, что известный алгоритм может быть применен для решения обобщенной задачи для случая, если граф - ориентированное от корня дерево.

Также доказано, что известный алгоритм решения задачи S(G,2,l) для случая, если параметр h может принимать значение один или два, позволяет построить оптимальное упорядочение.

Применен метод “ветвей и границ” для решения задачи S(G,l,h) в случае, если существует плотное упорядочение вершин графа. Для решения обобщенной задачи параллельного упорядочения с ограничениями разработан алгоритм построения оптимального упорядочения.

Проведен вычислительный эксперимент, в котором оценено поведение в среднем алгоритмов, которые базируются на уровневой стратегии, лексикографической нумерации и методе “ветвей и границ”. В результате получены данные, которые отображены в таблицах и гистограммах. Из полученных данных следует, что применение алгоритмов, которые используют уровневый принцип и лексикографическую нумерацию для произвольных графов, может давать приемлемые для практического применения результаты, причем точность работы исследованных алгоритмов зависит от количества связей между вершинами и числа вершин на каждом уровне.

В случае, если ширина упорядочения равняется трем, проверен разработанный приближенный алгоритм и на практике подтверждена оценка точности его работы.

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

Ключевые слова: параллельное упорядочение, орграф, ширина упорядочения, длина упорядочения, оценка, минимизация.

Размещено на Allbest.ru

...