Одноетапні задачі теорії розкладів у багаторівневій системі планування (стр. 1 )

Міністерство освіти і науки України

Національний університет “Львівська політехніка”

МЕЛЬНИК ОЛЕНА ОЛЕКСІЇВНА

УДК 004.9 : 519.854.2

ОДНОЕТАПНІ ЗАДАЧІ ТЕОРІЇ РОЗКЛАДІВ

У БАГАТОРІВНЕВІЙ СИСТЕМІ ПЛАНУВАННЯ

05.13.06 – інформаційні технології

Автореферат

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

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

Львів-2013

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

Робота виконана в Закарпатському державному університеті Міністерства освіти і науки України

Науковий керівник	доктор технічних наук, професор, Ващук Федір Григорійович, Закарпатський державний університет, завідувач кафедри "Програмне забезпечення систем"
Офіційні опоненти:	доктор технічних наук, професор, Медиковський Микола Олександрович, Національний університет "Львівська політехніка", завідувач кафедри "Автоматизовані системи управління" доктор технічних наук, професор, , Національний технічний університет України "Київський політехнічний інститут", професор кафедри "Автоматизовані системи обробки інформації та управління"

Захист відбудеться "___" травня 2013 р. о _____ год. на засіданні спеціалізованої вченої ради Д 35.052.14 у Національному університеті "Львівська політехніка" (79013, м. Львів, ва, ауд. 108, V навчальний корпус).

З дисертацією можна ознайомитись у бібліотеці Національного університету "Львівська політехніка" (79013, м. Львів, в).

Автореферат розісланий "____" квітня 2013 р.

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

спеціалізованої вченої ради,

к. т.н., доцент А. Є. Батюк

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

Актуальність теми. Планування – процес прийняття рішень, що має важливе значення як у виробничих системах, так і у сфері різноманітних послуг. Постановкам задач планування в складних системах та методам їх розв’язання присвячені наукові праці провідних вітчизняних і зарубіжних вчених:
, Скуріхіна В. І., , Танаєва В. С., , Подчасової Т. П., , Бітрана Г. Р., Пінедо М.,
, , Лікмена Р. С., та ін. Найпоширенішими є виробничі системи з мережевим представленням технологічних процесів та обмеженими ресурсами. Їх частка становить до 80% всіх типів виробничих систем. Це, зокрема, дрібносерійні виробництва, виробничі цехи, виробництва на замовлення, виробництва з виготовлення партій продукції, будівельні виробництва, системи планування та управління проектами тощо.

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

Аналіз наукових публікацій показує, що оптимальним для вирішення задачі планування в ієрархічній системі є підхід, в основі якого є об’єднання об’ємного і календарного планування по низці найбільш поширених критеріїв з урахуванням технологічних вимог, наявності ресурсів, завантаження устаткування та інших особливостей виробництва. Зазначений підхід реалізовано та в рамках єдиної багаторівневої системи планування з мережевим представленням технологічних процесів й обмеженими ресурсами. Ця система представлена комплексом взаємозв’язаних моделей дискретної оптимізації і високоефективних методів розв’язання задач планування. На основі зазначеного підходу за допомогою точних алгоритмів з поліноміальною та експоненційною складовими (ПДС-алгоритмів) для одного приладу успішно розв'язано такі задачі: мінімізації сумарного зваженого моменту виконання взаємозв’язаних завдань (що є ключовою при побудові пріоритетно-упорядкованої послідовності, яка визначає порядок призначення завдань на виконання), мінімізації сумарного запізнення при виконанні завдань; мінімізації сумарного запізнення відносно директивних строків виконання завдань паралельними приладами. Модульна структура програмного забезпечення системи дає змогу розширяти її функції, включати додаткові критерії оптимальності. Однак, в системі не розглядаються задачі складання розкладів за критерієм мінімізації сумарного випередження і запізнення з урахуванням налагоджень обладнання як при виконанні завдань групами, так і окремих завдань.

Більшість відомих напрацювань, присвячених проблемі розв'язання задач планування, пов’язаних з налагодженням приладів, передбачають одержання оптимального розв'язку на основі методів: гілок та границь, динамічного планування або частково цілочисельного програмування, як правило, для задач невеликої розмірності (до 20 завдань). Проте, недостатньо досліджені питання розв’язання задач оптимізації одним приладом з налагодженнями евристичними методами та для великої кількості завдань.

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

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

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

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

Для досягнення поставленої мети необхідно вирішити такі задачі:

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

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

· розробити нові методи мінімізації сумарного випередження і запізнення на одному приладі з налагодженнями, залежними від послідовності завдань;

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

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

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

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

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

Наукова новизна одержаних результатів полягає у наступному:

вперше розроблено:

· метод розв’язання задачі сумарного випередження і запізнення груп завдань на одному приладі з налагодженнями (дозволені простої приладу);

· метод розв’язання задачі сумарного випередження і запізнення груп завдань на одному приладі з налагодженнями (простої обладнання заборонені);

· два методи розв’язання задачі сумарного випередження і запізнення завдань на одному приладі з налагодженнями, залежними від послідовності;

удосконалено:

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

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

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

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

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

Особистий внесок здобувача. Усі наукові результати дисертаційної роботи отримані автором самостійно. У друкованих працях, опублікованих у співавторстві, автору належать: [1] – система моделювання; [1, 7] – інформаційні технології та реалізація у вигляді алгоритмів розроблених методів розв’язання досліджуваних задач у багаторівневій системі планування та управління з мережевим представленням технологічних процесів та обмеженими ресурсами; [2, 3, 9, 11] – розробка та статистичне обґрунтування двох нових ефективних методів розв’язання задачі мінімізації сумарного випередження і запізнення завдань на одному приладі із налагодженнями, що залежать від послідовності; [4] – два нові ефективні методи розв’язання задачі мінімізації сумарного випередження і запізнення груп завдань на одному приладі із налагодженнями у разі, коли простої обладнання дозволені, та для випадку їх заборони; [4, 5, 6, 8] – статистичне обґрунтування методів розв'язання задач мінімізації сумарного випередження і запізнення груп завдань на одному приладі із налагодженнями (простої обладнання дозволені або заборонені); [10] – алгоритм побудови графа групи G.

Апробація результатів дисертації. Основні наукові теоретичні положення та практичні результати дисертаційної роботи доповідалися і обговорювалися на: міжнародній алгебраїчній конференції (Ужгород, 27-29 серпня 2001 р.);
ХХ Міжнародній науково-практичній конференції "Міжнародне співробітництво у впровадженні інноваційних технологій навчання у вищій школі" (Ужгород – Кошице (Словацька Республіка) – Мішкольц (Угорська Республіка), 11 – 14 травня 2010 р.); ІІІ Всеукраїнській науково-практичній конференції "Інформатика та системні науки" (Полтава, 1-3 березня 2012 р.); Міжнародній науково-практичній конференції "Інформаційні технології в науці, освіті і техніці" [ІТОНТ-2012] (Черкаси, 25-27 квітня 2012 р.); І Міжнародній науково-практичній конференції "Сучасні інформаційні системи та технології" [AIST-2012] (Суми, 15-18 травня 2012 р.), а також на наукових семінарах кафедр загальної інформатики та математичного моделювання і програмного забезпечення систем Закарпатського державного університету ( рр.).

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

Структура та обсяг дисертації. Дисертаційна робота складається зі вступу, чотирьох розділів, висновків, трьох додатків. Робота містить 186 сторінок, включаючи 151 сторінку основного тексту, 22 рисунки, 87 таблиць. Список використаних джерел містить 147 найменувань і викладений на 18 сторінках.

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

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

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

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

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

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

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

У другому розділі представлені нові ефективні методи розв’язання наступних задач мінімізації сумарного випередження та запізнення при виконанні завдань одним приладом з налагодженнями (1-МВЗН): у разі, коли простої обладнання дозволені; для випадку, коли простої обладнання заборонені; у разі, коли налагодження залежать від послідовності завдань.

Постановка задачі 1. Задача складання розкладів груп на одному приладі з часами налагодження сімейств може бути сформульована таким чином: задано число сімейств, позначене , і кількість завдань у кожному сімействі, представлена числом для сімейства , які необхідно виконати без переривання на одному приладі. Тривалість виконання і директивний строк -го завдання з сімейства визначені як і відповідно. Крім того, якщо завдання слідує за попереднім завданням з того ж сімейства, то між ними немає часу налагодження, інакше потрібен час налагодження сімейства перед наступним процесом виконання, причому не залежить від позиції, займаної сімейством. До того ж передбачається, що є налагодження до виконання першої роботи в будь-якій послідовності. Всі завдання доступні в момент часу нуль, простої приладу допускаються, а переривання завдань заборонено. Прилад виконує не більш ніж одне завдання одночасно, і не може виконувати жодного завдання, поки виконується його налагодження. Всі завдання в кожному сімействі мають бути призначені разом. Отже, у будь-якій допустимій послідовності повинно бути тільки налагоджень. Загальна кількість завдань . Ціль полягає в тому, щоб знайти розклад, який мінімізує сумарне випередження і запізнення всіх завдань: . Для розв’язання цієї задачі запропоновано нові методи, які реалізовані у вигляді алгоритмів А1, А2.

Постановка задачі 2. Множина з n незалежних завдань повинна бути призначена на виконання без переривань на одному приладі, який може працювати не більш ніж з одним завданням одночасно. Прилад та завдання передбачаються безупинно доступними з моменту часу нуль, а простої приладу не допускаються. Завдання j, де , вимагає часу виконання і в ідеалі повинно бути закінчене у свій директивний термін . Для окремих завдань задано час налагодження . Це означає, що в розкладі, в якому завдання j виконується відразу після завдання i, повинен бути час налагодження одиниць часу між моментами завершення завдання i, позначеним через , та часом початку завдання , що дорівнює . Упродовж періоду налагодження жодне інше завдання не може виконуватися приладом. Тривалості налагодження залежні від послідовності, тому що вони залежать як від , так і від . Ціль полягає в тому, щоб знайти розклад, який мінімізує сумарне випередження і запізнення всіх завдань: . Для розв’язання цієї задачі запропоновані нові методи, які реалізовані у вигляді алгоритмів А3, А4.

Вперше показано взаємозв’язок між методами розв’язання задач мінімізації сумарного запізнення завдань одним приладом (МСЗ), мінімізації сумарного випередження та запізнення завдань (МВЗ) одним приладом, розроблених у науковій школі , та 1-МВЗН. В основу розроблених методів покладено метод розв'язання задачі МВЗ, який в свою чергу заснований на ПДС-алгоритмі розв’язання задачі МСЗ. В алгоритмах А1 і А2 використано можливість врахування налагоджень безпосередньо в структурі алгоритму МВЗ, що дало змогу розробити ефективні, близькі до оптимальних, методи розв’язання задачі 1-МВЗН. У алгоритмах А3, А4 методом розв’язання задачі МВЗ побудовано початкову послідовність. Це дало можливість статистично значимо при локальному пошуку кращого розв’язку в околі поточного розв’язку потрапити в область глобального оптимуму та отримати ефективні, близькі до оптимальних алгоритми розв’язання задачі 1-МВЗН.

Задача 1-МВЗН груп завдань для випадку, коли дозволені простої обладнання складається з двох підзадач :

1) знайти оптимальну послідовність завдань у межах кожного сімейства, в якій досягається оптимальне значення заданого критерію ефективності;

2) побудувати послідовність сімейств, в якій досягається оптимальне значення критерію МВЗ.

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

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

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

Використовуються такі умовні позначення:

– поточний момент початку виконання сімейств, ;

– найефективніший момент початку виконання сімейств ;

– момент закінчення виконання сімейства ;

– сумарна тривалість виконання завдань сімейства із налагодженнями;

– поточний розклад виконання сімейств;

– поточне значення функціоналу;

– фактичний момент початку виконання сімейства ;

– фактичний момент закінчення виконання сімейства ;

– фактичний розклад виконання сімейств;

U – множина всіх сімейств , ;

V – множина всіх сімейств, призначених на виконання.

Алгоритм А1.

Для кожного сімейства , виконується:

Блок 1. Розв’язання задачі МСЗ на множині завдань кожного сімейства з урахуванням налагодження. Отримуємо для кожного сімейства , оптимальну послідовність завдань , за критерієм МСЗ.

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