Харківський національний університет радіоелектроніки

Скакаліна Олена Вікторівна

УДК 519.12.176

МОДЕЛІ І МЕТОДИ ОПТИМАЛЬНОГО ПОСЛІДОВНО-

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

З НЕІДЕНТИЧНИМИ ОБ’ЄКТАМИ

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

Автореферат

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

кандидата технічних наук

Харків 2002

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

Робота виконана в Житомирському інженерно-технологічному інституті Міністерства освіти і науки України.

Науковий керівник доктор технічних наук, професор Панішев Анатолій Васильович, Житомирський інженерно-технологічний інститут, завідувач кафедри інформатики та комп’ютерного моделювання

Офіційні опоненти:

доктор фізико-математичних наук, професор Яковлєв Сергій Всеволодович, Харківський національний університет внутрішніх справ, начальник факультету управління та інформатики, завідувач кафедри прикладної математики;

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

Провідна установа

Інститут проблем машинобудування ім. А.М. Підгорного НАН України, відділ математичних методів і оптимального проектування.

Захист відбудеться “ 5 ” листопада 2002 р. о 14 годині на засіданні спеціалізованої вченої ради Д 64.052.02 у Харківському національному університеті радіоелектроніки, за адресою 61166, м. Харків, просп. Леніна, 14; т. 433-053.

З дисертацією можна ознайомитись у бібліотеці Харківського національного університету радіоелектроніки, просп. Леніна, 14.

Автореферат розісланий 3.10.02 р.

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

спеціалізованої вченої ради Безкоровайний В.В.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

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

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

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

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

Зв’язок роботи з науковими програмами, планами, темами. Дослідження виконувалися у відповідності з координаційним планом Міністерства освіти і науки України за науковим напрямком “Технічна кібернетика” і у відповідності з планами науково-дослідних робіт Харківського національного автомобільно-дорожнього університету в рамках держбюджетних тем: № 0197V015183 “Розвиток математичних методів і алгоритмів скорочення перебору рішень в задачах створення інтелектуальних систем обробки інформації”, №0199V002692 “Моделювання послідовно-паралельних процесів функціонування технічних і виробничих систем на основі методів комбінаторної оптимізації і перспективних інформаційних технологій” на період з 1995 по 2000 роки.

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

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

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

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

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

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

5. Програмна реалізація розробленого методу і його модифікацій.

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

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

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

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

Наукова новизна одержаних результатів.

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

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

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

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

5. Надано теоретичне обгрунтування розробленим алгоритмам, наведено докази їх коректності з гарантованою оцінкою часу розв’язання кожної задачі.

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

Нова версія пакету 1PlusMmashine впроваджена на ОЦ “Полтаванафтогаз”.

Особистий внесок здобувача. В усіх перелічених публікаціях автор приймав участь у розробці математичних моделей, методів і алгоритмів розв’язання задач та їх реалізації на ПЕОМ. Зокрема, в роботі [1] автором удосконалено класифікацію оптимізаційних задач послідовно-паралельного упорядкування та призначення робіт в системах з неідентичними машинами; в роботах [1, 7] запропоновано модифікацію алгоритму пошуку множини розв’язків задачі про призначення з використанням теорії паросполучень; у роботі [2] автор запропонував ідею методу побудови локальних оптимальних рішень в підматрицях для розв’язання задач дискретної оптимізації; а в роботах [3, 4, 6, 8, 9] автору належить розробка моделей і алгоритмів розв’язання узагальнень задачі про призначення з використанням методу послідовної побудови локальних оптимальних рішень.

Апробація результатів дисертації. Результати досліджень доповідались і обговорювались на наукових конференціях:

- першій всеукраїнській науково-практичній конференції „Україна наукова 2001” (Дніпропетровськ, 2001 р.);

- другій міжнародній конференції „Математичні моделі та інформаційні технології у соціально-економічних та екологічних системах” (Луганськ, 2001);

- п’ятій міжнародній науково-практичній конференції "Наука і освіта – 2002" (Дніпропетровськ-Донецьк, 2002).

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

Структура і обсяг роботи. Дисертація складається із вступу, чотирьох розділів, висновків, списку використаних джерел і додатків. Повний обсяг дисертації становить 147 сторінок. Робота містить 17 рисунків на 6 сторінках, 3 таблиці на 2 сторінках, список використаних джерел, що містить 101 найменування, на 10 сторінках та два додатки на 7 сторінках.

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

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

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

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

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

1) Ресурси складаються з 1+т машин, де т неідентичних машин забезпечують паралельне виконання робіт. Таку систему машин будемо називати дворівневою у тому розумінні, що її входом є єдина машина, а виходом – т паралельних неідентичних машин.

2) Модель завдань описується множиною G з п двохетапних (двостадійних) незалежних робіт , які одночасно надходять на вхід системи. Перший етап роботи виконується машиною першого рівня за час , а другий етап – на машині і другого рівня за час . Припускається що , коли робота j не може бути виконана на машині і. Виключене одночасне виконання роботи більш, ніж на одній машині, і на будь-яку машину в кожний момент часу призначається не більш, ніж одна робота. Недопустиме переривання ні першого, а ні другого етапу кожної роботи . Всі п робіт готові до виконання у момент часу, умовно рівний 0.

3) Найбільш важливим з практичної точки зору показником ефективності є довжина розкладу або час функціонування системи.

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

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

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

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

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

Якщо на множині всіх перестановок , породжуваних матрицею , визначено функціонал |

, | (1)

то діагональ матриці , що доставляє мінімум (1), є рішенням звісної задачі про призначення.

Нехай з перестановкою і відповідній їй діагоналлю пов’язаний функціонал |

. | (2)

Тоді в результаті побудови перестановки, що мінімізує (2) на множині всіх перестановок , одержимо рішення мінімаксної задачі про призначення.

Сформульована у першому розділі задача побудови оптимального за швидкодією розкладу з п двохетапних робіт в системі з 1+т машин є узагальненням задачі (2) й при n>m належить до класу NP - складних проблем навіть тоді, коли всі машини другого рівня ідентичні.

У випадку n=m початкові дані задачі представлені таблицею , елементами якої є пари . Визначаючи двохетапну роботу парою , одержимо допустимий розклад робіт як перестановку т рядків таблиці . Розклад має довжину, що дорівнює

,

де

Необхідно знайти розклад мінімальної довжини |

. | (3)

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

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

Задача оптимального призначення n двоетапних робіт у системі з 1+m неідентичних машин для випадку n<m випливає з задачі (3) і міститься у знаходженні розкладу мінімальної довжини з прямокутної матриці .

Необхідно мінімізувати сумарний час виконання т автобусами m маятникових маршрутів між двома пунктами 1 і 2. Перевезення між цими пунктами повинні забезпечувати т1 автобусів автопідприємства, розташованого у пункті 1, і т2 автобусів автопідприємства, розташованого в пункті 2, т1+ т2=т. З розкладу руху по автостанціях відомо час відправлення для кожного рейсу з пункту 1 у пункт 2 і у зворотному напрямку. Будь-який автобус автопідприємства, розташованого у пункті k, , починає і завершує маршрут відповідно до розкладу в цьому пункті.

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

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

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

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

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

Кожна задача дослідження представлена схемою рішення у вигляді послідовності етапів перетворення вхідних даних і результатів роботи процедури послідовної побудови локальних оптимальних рішень (ППЛОР). Процедура ППЛОР будує локальні послідовності і обчислює значення цільового функціоналу кожної задачі при зверненні до наступних підпрограм:

1. Підпрограма обчислення суми (SUM);

2. Підпрограма знаходження максимального елемента масиву (MAX);

3. Підпрограма знаходження перестановки, що мінімізує функцію (SORT0());

4. Підпрограма знаходження перестановки, що мінімізує функцію (SORT());

5. Підпрограма знаходження мінімального значення в задачі про редактора.

ВИСНОВКИ

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

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

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

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

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

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

5. Наведено докази коректності розроблених алгоритмів і оцінено часову складність розв’язання кожної задачі.

6. Удосконалено програмний пакет 1plusMmashine, впроваджений у програмне середовище Mathematica, який орієнтований на розв’язання задач з області теорії розкладів.

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

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

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

1. Панишев А.В., Костикова М.В. Скакалина Е.В. Об одном обобщении задачи о назначениях // Радиоэлектроника и информатика. – 1999. – №2(07). - С. 96-101.

2. Панишев А.В., Подоляка О.А., Скакалина Е.В. Эффективный алгоритм распараллеливания работ на неидентичных машинах // Авиационно-космическая техника и технология. - 1999. - Вып. 13. – С. 136-146.

3. Панишев А.В., Скрипина И.В., Скакалина Е.В. Эффективное построение оптимальных решений в задаче о назначении транспортного типа // Автомобильный транспорт: Сб. науч. тр. – Харьков: ХГАДТУ. - 2000. – Вып. 4.– С. 63-65.

4. Скакаліна О.В., Скрипіна І.В. Мінімізація сумарного простою в задачах складання автобусних розкладів // Вісник ЖІТІ. – 2000. - Вип. 15. – С. 40-47.

5. Скакалина Е.В. Эффективное построение множества расписаний с минимальным суммарным временем завершения работ // Радиоэлектроника и информатика. – 2001. - №3(16). – С. 44-46.

6. Подоляка О.О., Подоляка О.М., Скакаліна О.В. Ефективна схема побудови оптимальних за швидкодією розкладів в задачах про призначення двохетапних робіт на неідентичні машини // Авіаційно-космічна техніка і технологія. – 2002. – Вип. 27. – С. 225-231.

7. Панишев А.В., Скакалина Е.В., Скрипина И.В. Эффективное построение множества оптимальных решений в обобщениях задачи о назначениях // Матеріали ІІ Міжнар. конф. "Математичні моделі та інформаційні технології в соціально-економічних та екологічних системах". – Луганськ.:СНУ. – 2001. – С. 171-172.

8. Панишев А.В., Скакалина Е.В., Скрипина И.В. Об одном обобщении задачи о назначениях // Матеріали І всеукраїнської науково-практичної конф. "Україна наукова ’2001" (Дніпропетровськ-Харків-Одеса.). – Дніпропетровськ: Наука і освіта – 2001. – Том 13. – С. 3-5.

9. Панишев А.В., Плечистый Д.Д., Скакалина Е.В. Схема построения локальных оптимальных последовательностей в решении обобщений задачи о назначениях // Матеріали V Міжнар. науково-практичної конф. "Наука і освіта – 2002" (Дніпропетровськ-Донецьк). – Дніпропетровськ: Наука і освіта . - 2002. – С. 54-55.

АННОТАЦИЯ

Скакалина Е.В. Модели и методы оптимального последовательно-параллельного упорядочения работ в системах с неидентичными объектами. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 – математическое моделирование и вычислительные методы. – Харьковский национальный университет радиоэлектроники, Харьков, 2002.

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

Эти задачи сведены в класс задач последовательно-параллельного упорядочения и назначения работ в двухуровневой системе из 1+т машин.

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

Ресурсы системы составляют 1+т машин. Входом системы является единственная машина первого уровня, а выходом - т неидентичных машин, обеспечивающих параллельное выполнение работ.

Модель заданий описывается множеством G из п независимых двухэтапных работ , одновременно поступающих на вход системы. Первый этап работы выполняется на машине первого уровня за время , а второй – на машине второго уровня за время , причем , если работа j не может быть выполнена на машине і. Одновременное выполнение работ более, чем на одной машине исключено, и на одну любую машину в каждый момент времени назначается не более чем одна работа. Недопустимы прерывания выполнения работ.

В качестве показателя эффективности выступает длина расписания или время функционирования системы.

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

Метод решения задачи заключается в последовательном улучшении допустимого решения и построении всех оптимальных решений. Он состоит из двух последовательно выполняемых процедур.

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

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

Выделено три способа построения оптимальных решений.

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

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

Способ в) заключается в замене двух компонент решения для подматрицы соответствующими им компонентами в этой же подматрице не принадлежащими решению и применении к полученной последовательности действий способа б).

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

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

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

Алгоритмы оптимального упорядочения и назначения транспортных операций программно реализованы в среде Mathematica в программном пакете 1PlusMmashine, ориентированном на решение задач из области теории расписаний.

Экспериментальные исследования доказали целесообразность его использования для решения задач составления эффективных расписаний транспортных перевозок.

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

АНОТАЦІЯ

Скакаліна О.В. Моделі і методи оптимального послідовно-паралельного упорядкування робіт у системах з неідентичними об’єктами. – Рукопис.

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

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

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

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

ABSTRACT

Scacalina E.V. Models and methods of optimal series-parallel works ordering in systems with non-identical objects. - the Manuscript.

Dissertation for scientific degree of Technical Science Candidate on a speciality 01.05.02 - mathematical modelling and computing methods. - Kharkov national university of radioelectronics, Kharkov, 2002.

The dissertation develops results of series-parallel processes research, which base model is the model of optimum ordering and assignment of works in the two-level system submitted by one machine at the first level and several parallel non-identical machines on second. The Optimization problems formulated with attraction of this model form a new class of generalizations by a assignments problem and basic problems of the scheduling theory. Necessity of their decision is caused by the broad range questions of the transport process effective organization.

All tasks of a considered class are effectively solved by the general computing circuit of optimum local solutions construction for submatrixes of a assignments matrix. This circuit as against known algorithms finds all solutions, delivering an optimum of target problems functional by polynomial time.

Optimum ordering and assignment algorithms of transport operations are realized as the program in Mathematica package.

Key words: mathematical model, an assignments matrix, the polynomial algorithm, the optimumal solution.