МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
Національний технічний університет України
“Київський політехнічний університет”
Войцев Андрій Валерійович
УДК 621.3
ПІДСИСТЕМА ОПЕРАТИВНОГО КАЛЕНДАРНОГО ПЛАНУВАННЯ
ГНУЧКОЇ ВИРОБНИЧОЇ СИСТЕМИ
Спеціальність: 05.13.20 – Гнучкі виробничі системи
Автореферат
дисертації на здобуття ученого ступеня
кандидата технічних наук
Київ – 2005
Дисертацією є рукопис.
Робота виконана у Східноукраїнському національному університеті імені Володимира Даля Міністерства освіти і науки України, на кафедрі "Автоматики і систем управління".
Науковий керівник: заслужений діяч науки і техніки України, доктор технічних наук, професор Войлов Юрій Григорович, Східноукраїнський національний університет імені Володимира Даля, завідувач кафедри "Автоматика і системи управління"
Офіційні опоненти: доктор технічних наук, професор Копп Вадим Якович, Севастопольський національний технічний університет, завідувач кафедри "Приладобудування";
кандидат технічних наук, доцент Лапковський Сергій Вікторович, Національний технічний університет України "Київський політехнічний інститут", доцент кафедри "Технології машинобудування".
Провідна організація: науково-виробнича корпорація "Київський інститут автоматики" Міністерства промислової політики України, м. Київ
Захист відбудеться 21 червня 2005 р. у 1500 годині на засіданні спеціалізованої вченої ради Д .002.04 при НТУУ "Київський політехнічний інститут" за адресою: 03056, м. Київ, проспект Перемоги, 37, корпус №18, кімната № 432.
З дисертацією можна ознайомитися в бібліотеці НТУУ "Київський політехнічний інститут" за адресою: 03056, м. Київ, проспект Перемоги, 37.
Автореферат розісланий 19 травня 2005 року.
Учений секретар
спеціалізованої вченої ради,
к.т.н., професор Л.С. Ямпольський
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. До числа виробництв, що є перспективними з позиції гнучкої автоматизації, можна з упевненістю віднести переробну промисловість, особливо її складову – виробництво упакування.
Виробництво полімерного упакування є складним науково-виробничим комплексом, що реалізує комплексно-автоматизоване багатономенклатурне виробництво, з подальшою можливістю оперативного перебудування його відповідно до визначеного асортименту продукції. На відміну від достатньо вивчених галузей гнучкої автоматизації, таких як машинобудування і приладобудування, перероблююча галузь має свої відмінні риси. Насамперед, це найширша номенклатура при масовому виробництві одиниці виробу і, як наслідок, величезна номенклатура виробничих операцій.
Продуктивність устаткування виробничого комплексу дає змогу за кілька годин роботи забезпечити замовника упакуванням для випуску піврічної програми виробу однієї номенклатури. Тому переналагоджувати устаткування можна в середньому на кожній групі устаткування кілька разів за зміну, причому необхідність такого переналагодження визначається виключно кон'юнктурою ринку. І ось тут самим вузьким місцем стає оперативне календарне планування, оскільки саме від часу відведеного на планування, і ступеня оптимальності календарного плану залежить рівень втрат від простоїв виробничої ділянці.
Досвід використання старих методів оперативного планування у виробництві полімерного упакування показав їхню неефективність і навіть неспроможність. Стає очевидним, що сучасному рівню виробництва (і не тільки розглянутому) і управління мають відповідати нові методи оперативного календарного планування (ОКП). Тому завдання формування оптимальних календарних планів-графіків роботи гнучкого виробництва має актуальне значення.
Зв'язок роботи з науковими програмами, планами, темами. Дисертація виконана протягом 2002-2004 років відповідно з планами держбюджетної науково-дослідної роботи БКТ__: “Розробка і удосконалення систем і елементів автоматизованого управління і контролю на базі обчислювальної і мікропроцесорної техніки для різних виробничих підрозділів і технологічних комплексів”, затвердженої наказом по Східноукраїнському національному університету ім. В.Даля від 8 листопада 2002 р. №438-04.
Мета і завдання дослідження. Метою дисертаційної роботи є підвищення ефективності функціонування гнучкої виробничої системи на прикладі реалізації ГВС виробництва полімерного харчового упакування завдяки використанню підсистеми оперативно-календарного планування із забезпеченням аналізу календарних планів підприємства, прогнозування й оптимізації роботи устаткування.
Для досягнення поставленої мети в роботі вирішуються такі основні завдання:
1. Дослідження виробничої системи і побудова математичних моделей її типових компонентів.
2. Побудова на основі моделей типових компонентів узагальненої моделі системи.
3. Обґрунтування методики оптимізації роботи ГВС і розробка оптимального алгоритму виготовлення полімерного упакування.
4. Обґрунтування і вибір основних критеріїв оцінки ефективності роботи системи.
5. Виконання експериментальних досліджень на моделі виробничої системи з визначенням величин параметрів настроювання алгоритму оптимізації для подальшого отримання субоптимальних розкладів роботи устаткування.
6. Розробка методики оцінки надійності субоптимальних розкладів, яка має забезпечити високу точність визначення термінів виконання календарних планів.
Об'єктом досліджень у дисертаційній роботі є підсистема оперативного календарного планування гнучкої виробничої дільниці для виготовлення харчового полімерного упакування з масово-швидкозмінним типом виробництва.
Предметом досліджень є методи, моделі й алгоритми синтезу підсистеми оптимального оперативного календарного планування виробництва харчового полімерного упакування.
Методи досліджень. Вирішення сформульованих у дисертаційній роботі завдань базується на використанні моделей математичної фізики, методів обчислювальної математики (теорія матриць, пірамідально-рекурсивне визначення простору, теорія графів) і обчислювальної техніки, теорії розкладів, імітаційного моделювання, теорії систем і системного аналізу, генетичних алгоритмів комбінаторної оптимізації і теорії надійності.
Наукова новизна отриманих результатів складається із наступних положень:
1.
Застосовано новий оригінальний підхід до оперативного планування, який засновано на динамічному синтезі розкладів, що дозволило удосконалити структуру системи управління оперативним календарним плануванням роботи гнучкої дільниці виробництва полімерного харчового упакування, мінімізувати склад устаткування і забезпечити високу ефективність його використання.
2.
Розроблено оригінальний метод подання інформації про послідовність виконання запланованих операцій для об'єктів досліджуваної ГВС, особливість якої полягає в багатоваріантності технологічних маршрутів виробництва виробів.
3.
Створено оригінальну методику символьного подання варіантів рішень у процесі пошуку квазиоптимальних розкладів за допомогою генетичних алгоритмів.
4.
Модифіковано метод побудови квазиоптимальних розкладів шляхом застосування генетичних алгоритмів, що дозволило забезпечити одержання квазиоптимальних графіків роботи устаткування за малі інтервали часу.
5.
Отримано теоретичні оцінки і сформульовано вимоги до надійності розкладів, що дозволяє враховувати стохастичність процесів, які відбуваються в системі, і визначати часові параметри початку і завершення з високою точністю усіх операцій.
Практична значимість отриманих результатів. Методи моделювання роботи гнучкої виробничої дільниці, розроблені і наведені в дисертаційній роботі, дозволили вирішити широке коло завдань, пов'язаних з різнобічним аналізом ГВС із масово-швидкозмінним типом виробництва, а саме:
1.
Використання генетичних алгоритмів і сучасних методів моделювання дало можливість системі ОКП формувати календарні плани-графіки в реальному масштабі часу, що, у свою чергу, дозволило оперативно реагувати на зміну плану виробництва і стан технологічного устаткування, тобто швидко й ефективно перебудовувати розклад роботи устаткування в будь-який момент часу.
2.
Розроблений для оптимізації процедури гнучкого планування модифікований генетичний алгоритм дозволив одержати квазиоптимальні розклади роботи устаткування за обраним критерієм оптимальності, що, врешті, підвищило ефективність функціонування дільниці виробництва полімерного упакування і отримання точних результатів. Оцінка ж надійності розкладів дала можливість максимально точно визначати час запуску і завершення випуску кожного планованого виробу, що забезпечило істотне скорочення матеріальних, складських і буферних запасів сировини і готової продукції.
3.
Результатом досліджень стало створення програмно-алгоритмічного комплексу, що реалізує гнучку виробничу систему оперативного планування виробництва полімерного упакування.
Упровадження результатів роботи засвідчено відповідним актом.
Особистий внесок здобувача. Автором запропоновано динамічний синтез розкладів для удосконалення структури системи управління оперативним календарним плануванням роботи гнучкої дільниці виробництва полімерного харчового упакування; розроблено оригінальний метод подання інформації про послідовність виконання запланованих операцій для об'єктів досліджуваної ГВС; створено оригінальну методику символьного подання варіантів рішень у процесі пошуку квазиоптимальних розкладів за допомогою генетичних алгоритмів; модифіковано метод побудови квазиоптимальних розкладів шляхом застосування генетичних алгоритмів, що дозволило забезпечити одержання квазиоптимальних графіків роботи устаткування за малі інтервали часу; отримано теоретичні оцінки і сформульовано вимоги до надійності розкладів, що дозволяє враховувати стохастичність процесів, які відбуваються в системі, і визначати часові параметри початку і завершення з високою точністю усіх операцій.
Апробація результатів дисертації. Основні положення і висновки дисертаційної роботи доповідалися й обговорювалися на VII Міжнародній науково-практичній конференції "Університет і регіон" (грудень, 2001), Луганськ, Україна; II Міжнародній науково-технічній конференції "Інформаційна техніка та електромеханіка" (квітень 2003), Луганськ, Україна; I Всеукраїнській науково-практичній конференції "Інформаційні технології і безпека в управлінні" (жовтень 2004), Луганськ, Україна; Науковій конференції професорсько-викладацького складу і наукових працівників СНУ ім. В.Даля "Наука - 2004"(квітень 2004), Луганськ, Україна; об'єднаних наукових семінарах Східноукраїнського національного університету імені Володимира Даля (Луганськ, 2002 - 2004 р/р.); наукових семінарах Науково-дослідного і проектно-конструкторського інституту системних технологій “Іскра” (Луганськ, 2000-2004 р/р.).
Публікації. Основні положення дисертаційної роботи опубліковано в 9 друкованих працях: з яких 5 статей в наукових фахових виданнях, 4 роботи опубліковано в працях наукових конференцій.
Структура й обсяг роботи. Дисертаційна робота складається зі змісту, вступу, чотирьох розділів і висновку, викладених на 163 сторінках машинописного тексту, містить 44 рисунки, 4 таблиці, список літературних джерел із 133 найменувань.
ЗМІСТ РОБОТИ
У вступі обґрунтовано актуальність теми, сформульовано мету і завдання досліджень, перераховані основні положення, що виносяться на захист.
У першому розділі проаналізовано сучасний стан досліджень у сфері оперативного календарного планування гнучкими виробничими процесами. Проведено аналіз методів побудови календарних планів-графіків і оцінки їхньої надійності, методів і засобів моделювання ГВС.
Проведений аналіз стану досліджень і розробок в області оперативного календарного планування дозволив зробити ряд узагальнень і сформулювати мету і завдання досліджень даної роботи.
Для оперативного управління (ОУ) ГВС полімерного упакування характерні [2] високі вимоги до деталізації і точності розрахунку виробничих завдань, забезпечення їхньої оптимальності, взаємозв'язку і погодженості для різних рівнів оперативного управління і планово-облікових періодів, збалансованості з ресурсами, оперативності розрахунків шляхом створення АСУ реального часу, досягнення єдності матеріальних і інформаційних потоків. Високі вимоги пред'являються і до складання календарних розкладів на короткі відрізки часу (декаду, тиждень). Усе це може бути забезпечене за наявності науково обґрунтованих (оптимальних) календарно-планових нормативів.
Досвід використання існуючих методів оперативного планування у виробництві полімерного упакування показав їхню неефективність і навіть неспроможність. Пошуку методів побудови оптимальних розкладів присвячена досить велика кількість наукових праць. Однак дане завдання у загальному випадку повністю не вирішене.
Методи повного перебору на практиці не застосовуються, тому що час пошуку оптимуму перевищує припустиме в умовах масово-швидкозмінного типу виробництва.
Використання методів математичного програмування при розв'язанні завдання складання розкладів не дає результатів через велику кількість теоретично можливих елементарних розкладів. Тому такий підхід оцінюється фахівцями як недостатньоперспективний через громіздкість системи обмежень і швидке зростання обсягу обчислень при збільшенні розмірності задачі. До того ж лінійне програмування використовується тільки для односпрямованих маршрутів, що унеможливлює його використання неможливим для гнучкого виробництва, що досліджується.
При вирішенні завдань послідовного обслуговування велику популярність має метод так званих гілок і рубежів. Істотним недоліком даного методу є проблематичність його використання з числом одиниць устаткування, що обслуговується, більш трьох. Метод гілок і рубежів неможливо використовувати для побудови ОКП масово-швидкозмінного виробництва, тому що даний тип виробництва, по-перше, відрізняється наявністю деякої кількості однотипного взаємозамінного устаткування, виконання операцій на якому може відбуватися паралельно, а по-друге, різними технологічними маршрутами для усіх виробів, що випускаються.
Використання для завдань з паралельно-послідовними технологічними маршрутами евристичного методу і методу випадкового пошуку з навчанням не дозволяє одержати оптимальне чи близьке до оптимального рішення. У даному випадку можна стверджувати, що якість розкладів буде залежати тільки від суб'єктивних факторів, тобто від кваліфікації експертів.
При формуванні розкладів роботи устаткування в ГВС у більшості випадків домінує номінальний характер, тобто розклади будуються без урахування впливу фактора надійності елементів ГВС, хоча одним з найбільш важливих факторів, що впливають на оцінку календарного плану, є досягнутий рівень надійності виробничого процесу як на самому об'єкті управління, так і на підприємстві в цілому. Незважаючи на необхідність досліджень впливу надійності устаткування на надійність виконання виробничого плану, аналіз літератури показав, що це найменш досліджена сфера у ГВС.
З огляду на вище наведені недоліки методів оперативного планування, можна зробити наступний висновок: проблема забезпечення високої ефективності підсистеми оперативного календарного планування в ГВС не одержала остаточного вирішення, що і викликає необхідність проведення даного дослідження.
В другому розділі наведено вирішення завдання моделювання ГВС, у процесі якого проведено структурний і параметричний синтез моделі ГВС, отримано узагальнену модель ГВД виробництва полімерного упакування, розроблено програмну реалізацію моделі.
Розробка моделі ГВС викликана необхідністю вирішення завдань оцінки якості алгоритмів управління ГВС [3, 6], а саме: формування вихідної черги запуску, оперативного календарного планування, а також диспетчирування замовлень на обслуговування засобами транспортування.
За змістовну частину моделювання роботи ГВС була прийнята імітація руху компонентів матеріальних потоків за обробними ресурсами, під якими розуміється як їхнє обслуговування (обробка і транспортування), так і збереження в перервах між обслуговуваннями.
При формалізації процесу функціонування ГВС використано агрегативні моделі, що виконують одночасно кілька функцій. Стандартна форма подання досліджуваного об'єкта у виді А-схеми агрегативних моделей дозволила уніфікувати не тільки алгоритми імітації, але і дала можливість застосовувати стандартні методи обробки й аналізу результатів моделювання.
Для опису функціонування і взаємодії агрегатів (модулів) технологічної системи ГВС у структурі модульної проблемно-орієнтованої системи імітаційного моделювання використаний клас мереж Петрі “Операція – ресурс”, що дозволило виконати моделювання з урахуванням циклів відновлення наслідків помилкових дій, а також розподілу ресурсів у реальному часі.
При створенні імітаційної моделі ГВС застосовувався підхід, заснований на описі ГВС як дискретної агрегативної системи, що дозволило досліджувати як детермінований, так і стохастичний режими функціонування ГВС і окремих її компонентів [7], забезпечивши тим самим можливість оцінки надійності розкладів.
Агрегативний опис складного об'єкта дозволив подати його у вигляді кінцевого числа підсистем із збереженими зв'язками, що забезпечують їхню взаємодію. Таким чином, процес функціонування системи можна розглядати як послідовність дискретних подій, між якими встановлені причинно-наслідкові зв'язки.
Формалізований опис станів і переходів елементів системи в імітаційній моделі представлено у такий спосіб. У складі технологічної системи ГВС є безліч всього устаткування , де - порядковий номер модуля устаткування, незалежно від його типу.
Згрупувавши устаткування за ознакою однотипності виконуваних функцій, одержимо такі групи модулів: основного устаткування ; транспортування і нагромадження .
(1)
(2)
Модулі устаткування -ї групи характеризуються списком станів
(3)
де - число станів, у яких може знаходитися -й модуль -ї групи в процесі функціонування ГВС.
Сукупність станів вихідної номенклатури виробів у процесі їхнього виготовлення можна визначити через стани відповідних груп устаткування:
(4)
(5)
Критичну подію визначимо як закінчення перебування -го модуля устаткування в -му стані, що має відбутися в момент часу . Тоді в будь-який момент часу стан технологічної системи можна визначити в імітаційній моделі списком подій, пов'язаних з її модулями :
(6)
У результаті структурного синтезу моделі виявилося можливим виконати повний формалізований опис станів і переходів кожної групи елементів системи й остаточно об'єднати всі елементи системи в загальну модель.
Імітаційна модель виробничої системи побудована за модульним принципом (рис. ). Один з модулів імітаційної моделі є управляючим, інші модулі - базовими. Робота модульної програми зводиться до послідовного виконання своїх функцій базовими модулями, порядок включення яких у роботу визначається модулем управління.
Рис. 1. Структура імітаційної моделі
Модульна організація процесу обслуговування подій моделі, включаючи їхнє прогнозування, упорядкування й обробку, допускає необмежену деталізацію списку подій за бажанням користувача.
Робота імітаційної моделі починається з ініціалізації компонентів моделі, за якою завантажуються характеристики устаткування з урахуванням реального стану виробничої системи. Ця операція здійснюється “Модулем вводу і перетворення початкових даних” і “Модулем настроювання моделі”. Для опису об'єкта моделювання (виробничої системи) використовуються такі початкові дані:
- Номенклатура одиниць упакування, які вироблено за модельований інтервал часу з позначкою типів устаткування, часу циклу однієї заготівок на кожній операції технологічного маршруту.
- Склад основного устаткування (тип і число устаткування кожного типу).
- Склад складської системи (тип елементів і їхньої ємності).
- Тип транспортної системи, число і ємність транспортних засобів дискретного типу, час руху за кожним із можливих транспортних маршрутів.
- Закріплення засобів нагромадження і транспортування відповідно до засобів обробки й елементів ГВС у цілому.
- Витрати часу на передачу носіїв між засобами транспортування й іншими елементами, на тривалість циклів встановлення на носій і зняття з нього однієї одиниці упакування, на передачу носія з вхідного нагромаджувача основного устаткування і позицій комплектації на робочий стіл і назад, на зміну програми обробки.
- Безпосередньо після закінчення введення початкових даних і відповідно до них виконується автоматичне настроювання моделі: установка станів готовності елементів основного і транспортного устаткування; призначення початкових положень транспортних засобів.
Другий етап роботи модуля управління полягає в активізації черги. Сутність його полягає у такому:
1) Відповідно до встановленої черговості виконання кожної продуктооперації за групами основного устаткування, модулем здійснюється пошук і призначення устаткування на виконання поточної операції технологічного маршруту j-го продукту виробництва. Якщо необхідне устаткування вже задіяне, то виконується перехід до пошуку устаткування для наступної групи операцій. Всі обрані операції додаються в список поточного виконання, а устаткування позначається як закріплене за конкретною операцією.
2) Здійснюється розбивка операцій поточного виконання на дії транспортування та переналагодження обраного устаткування відповідно до виконання закріпленої операції й обробки на ньому.
3) Призначаються виконавці на транспортні операції і виконується настроювання адрес джерел і приймачів транспортування із розрахунком часу виконання кожної дії.
4) Виконується запис усіх готових до виконання дій у журнал виконання. Сортування дій проводиться у відповідності із часом їхнього виконання.
Після закінчення формування журналу модуль управління переходить на третій етап імітації виробничого процесу. Визначається час появи найближчої події за верхнім рівнем дії в журналі виконань. Зрушується модельний час. Обробляються всі події за часом виконання, що дорівнює нулю. Видаляються з журналу події, що здійснилися. Дана операція повторюється доти, поки не будуть виконані всі дії для будь-якої з операцій поточного виконання. Якщо ця умова виконана, то виконана операція видаляється зі списку, й алгоритм передає управління на п.1) першого етапу роботи модуля управління.
Умовою закінчення моделювання вважається відсутність інформації про невиконані операції технологічних маршрутів.
Функціонування алгоритму модуля управління завершується передачею управління підпрограмній одиниці обробки і видачі результатів, що реалізує п'ятий етап роботи модуля управління.
Модель ГВД виробництва полімерного упакування програмно реалізовано за допомогою мови візуального програмування Delphi 7.0.
У третьому розділі сформульовано підхід до вирішення завдання оптимізації роботи ГВД; обрано критерій ефективності; проведено теоретичне обґрунтування застосування генетичних алгоритмів разом з об'єктною моделлю ГВД [1] як методу оптимізації; розроблено засіб символьного подання інформації про досліджуваний об'єкт; запропоновано використання проблемно-орієнтованих операторів кросинговіру і мутації, а також схеми взаємодії генетичного алгоритму з імітаційною моделлю.
Відповідно до теорії розкладів завдання формування розкладу вважається заданим, якщо визначені:
1) роботи й операції, що підлягають виконанню;
2) кількість і типи машин, що виконують операцію;
3) порядок проходження виробничих одиниць по машинах;
4) критерії оцінки розкладів.
Постановка задачі починається з опису системи машин і множини робіт [9].
Нехай система складається з машин ( ), виробничим завданням випуску виробів є .
- плановий (директивний) термін виробництва. Ця величина є момент, до якого i-та робота повинна бути виконана. Іншими словами, є директивним часом закінчення операції, заданим деякими зовнішніми причинами стосовно системи, що розглянута раніше.
Для кожного виробу відома робота у вигляді послідовності необхідних операцій (визначена множина можливих операцій для ).
Кожній машині задано набір виконуваних операцій і інформація про переналагодження машини з однієї операції на іншу у вигляді матриці часу і вартості переналагодження:
; , (7)
де – кількість операцій j-го устаткування,
- загальна тривалість всіх операцій роботи i (тривалість роботи).
Завдання полягає у визначенні компонентів вектора (параметрів, що оптимізуються), які мінімізують цільову функцію за умовою виконання обмежень :
; (8)
, (9)
де - модель розкладу виконання замовлень (варіанти послідовностей запуску завдань у виробництво), - критерій оцінки якості рішень, , , - обмеження за термінами виробництва, необхідними операціями і устаткуванням.
Однією з основних проблем ОКП є вибір показників оптимальності рішення. Ці показники співвіднесені з кінцевим результатом – виконанням замовлень і договірних зобов'язань за номенклатурою, кількістю, якістю і термінами. Але виконання плану випуску продукції може бути досягнуте при різних витратах, частина яких залежить від якості ОКП, тому основним (глобальним) показником оптимальності ОКП має бути мінімум приведених витрат при виконанні виробничої програми підприємства.
Собівартість виробів знижується при збільшенні розміру партії за рахунок зменшення витрат на підготовчо-заключні роботи, що припадають на один виріб. Тривалість виробничого циклу, заділи, а також обсяг незавершеного виробництва збільшується зі збільшенням розміру партії. При урахуванні тільки цих найбільш істотних факторів оптимальним буде розмір партії, за якого досягається мінімум наведених витрат на виробництво одного виробу, обумовлених формулою (10):
(10)
де - собівартість i-го виробу, грн.; - норма ефективності капітальних вкладень, 1/роб. дн.; - обсяг незавершеного виробництва в процесі виготовлення партії із розрахунку на один виріб, грн.роб.дн./шт.
На пошук оптимальних розкладів за розглянутою цільовою функцією накладається єдине обмеження – термін закінчення заданих робіт, за яким виконується остаточна оцінка якості отриманих розкладів.
Як базовий підхід до вирішення завдання формування розкладів запропоновано використання еволюційних методів пошуку оптимального рішення, які спираються на метод спроб і помилок.
Еволюційні методи в даний момент ефективно використовуються для розв'язання задач штучного інтелекту і комбінаторно-логічних задач на графах. З усіх видів еволюційних методів обрано генетичні алгоритми (ГА) як найбільш пристосовані для пошуку розкладів у структурі складних процесів ГВС, оскільки вони дозволяють одночасно аналізувати підмножину рішень, вибираючи із них квазиоптимальні.
Для формування розкладів за допомогою генетичного алгоритму автором був розроблений метод кодування генотипу рішень, що відбиває інформацію про послідовність запуску всіх технологічних операцій на заданій безлічі устаткування.
Вирішення завдань оптимізації з використанням ГА, як правило, виконується шляхом бінарного кодування властивостей розв'язуваної задачі у вигляді хромосомного набору. Цей спосіб не ефективний для розв'язуваної нами задачі з тієї причини, що при застосуванні до хромосомного набору операторів модифікації, велика частина рішень є неприпустимими, а це призводить до додаткових операцій пошуку припустимих рішень і повторного формування хромосом.
Для усунення зазначеного недоліку автором розроблено оригінальний спосіб кодування ознак розв'язуваної задачі [5] на основі генів перемінної довжини, що дозволило врахувати особливості виробничого процесу, у якому устаткування підтримує паралельно-послідовний спосіб руху матеріальних потоків.
Запропонований спосіб кодування полягає у тому, що у зв'язку з наявністю взаємозамінного устаткування усі машини поділені на групи за виконуваними операціями. Відповідно, пошук оптимальної послідовності запуску необхідних технологічних операцій виконується не для кожної окремої машини, а для групи однотипного устаткування. Відобразивши цей принцип на ГА, маємо те, що кожен ген відповідає за кодування інформації про послідовність запуску технологічних операцій для визначеної групи устаткування. Кодування кожного гена хромосоми виконується в залежності від набору операцій, що підтримуються даною групою машин, а код кожного гена хромосоми має різну довжину (рис.2):
1-й ознака (група 1) | 2-й ознака (група 2) | 3-й ознака (група 3) | …
J1 | J3 | J2 | J1 | J2 | J5 | J6 | J3 | J7 | J4 | J1 | J3 | J2 | J4 | J5 | …
Рис. 2. Хромосоми з кодуванням у генах груп устаткування
Однак модифікація подання генної інформації призвела до необхідності розробки нових алгоритмів ідентифікації визначеного гена в структурі хромосоми [8].
Для спрощення роботи генетичного алгоритму з метою абстрагування від способу збереження генної інформації автором запропоновані об'єктні моделі реалізації гена і хромосоми. Таке подання гена і хромосоми дає можливість на рівні окремої хромосоми і популяції в цілому абстрагуватися від способу збереження генної інформації і тим самим спростити роботу генетичного алгоритму. Зміна способу подання генної інформації викликала і зміну основних генетичних операторів модифікації - кросинговера і мутації, у зв'язку з чим для ГА були розроблені проблемно-орієнтовані оператори кросинговера і мутації.
Для хромосом розроблено модифікацію двоточкового оператора кросинговера, у якому на першому кроці з усієї популяції вибираються два хромосоми-батьки. Далі випадковим чином визначаються дві точки кросинговера. Якщо при формуванні нащадка буде спроба використати вже задіяний у ньому елемент, то він буде замінений на наступний у ланцюжку перетворень. Це дозволяє уникнути некоректного подання хромосом (дублювання операцій для груп устаткування).
Крім того, додатково розроблено оператор мутації, функцією якого є внесення різноманіття у сферу пошуку рішень. У цьому операторі на першому кроці здійснюється випадковий вибір модифікованої хромосоми, а на наступному кроці відбувається обмін двох випадково обраних елементів хромосоми.
Оцінка ефективності розкладів, що формуються за допомогою генетичного алгоритму, виконується за допомогою імітаційної моделі функціонування технологічного процесу. У зв'язку з тим, що пошук рішення здійснюється генетичним алгоритмом в автоматичному режимі, був розроблений т.з. керуючий модуль (рис. 3), у завдання якого входить: одержання чергового варіанта розкладу від ГА у вигляді генотипу, перетворення цієї інформації у форму, що є зрозумілою для імітаційної моделі, запуск імітаційної моделі для оцінки ефективності досліджувального розкладу.
Рис. 3. Схема взаємодії ГА й імітаційної моделі
Така схема функціонування генетичного алгоритму реалізує процедуру пошуку квазиоптимальних рішень, за якої забезпечується оптимізація розкладу роботи устаткування ГВС полімерного упакування відповідно до обраного критерію ефективності.
У четвертому розділі розглянуто питання експериментальних досліджень методики формування субоптимальних розкладів на прикладі підсистеми оперативного календарного планування ГВД виробництва полімерного харчового упакування.
Особливість використання генетичних алгоритмів у задачах оптимізації полягає в індивідуальності настроювань параметрів алгоритму під конкретну задачу [4]. На ефективність пошуку оптимальних рішень генетичним алгоритмом впливають такі параметри ГА:
-
потужність популяції, що визначає кількість сформованих рішень на первинному етапі роботи алгоритму;
-
імовірність схрещування;
-
імовірність мутації.
За результатами експериментальних досліджень (рис. 4 - 7), що проведені з метою оцінки параметрів ГА, зроблено висновки:
1.
Максимальна ефективність пошуку генетичним алгоритмом квазиоптимальних рішень забезпечується при потужності популяції на рівні 1700 осіб.
2.
Імовірність операції кросинговера має знаходитися на рівні 0.8.
3.
Значення імовірності мутації має знаходитися на рівні 0.02.
4.
Середнє відхилення рішення від оптимального при даному поєднанні параметрів становить 3% ? 5%.
З метою значного скорочення часу формування календарних планів-графіків процес пошуку рішень поділено на етапи. На першому етапі виробляється пошук оптимального розкладу на ГА без урахування стохастичних процесів, що впливають на хід виробництва. У результаті першого етапу формування календарних планів-графіків синтезується деяка множина розкладів із кращими значеннями критерію оптимальності, що задовольняють обмеженню за часом випуску готової продукції. На другому етапі пошуку рішень оцінюється надійність кращих розкладів.
Ця оцінка виконується вже з урахуванням прогностичності виробничого процесу, тобто імовірності виконання розробленого плану за умови, що зовнішні вимоги залишаться незмінними. Отже, поняття оптимальності плану одержує вже стохастичний зміст, і планові рішення оцінюються не тільки з погляду прогнозованого значення критерію оптимальності, але і з позицій ступеня ризику при їх реалізації.
Таким чином, оцінка якості отриманого календарного плану виконується з урахуванням досягнутого рівня надійності виробничого процесу як на самому об'єкті управління, так і на підприємстві в цілому.
Для урахування зазначеного фактору запропоновано оцінювати надійність розкладів за такою методикою: на імітаційній моделі ГВС для кожного з альтернативних розкладів проводиться ряд експериментів з урахуванням імовірнісних оцінок виходу устаткування з ладу, його ремонту і переналагодження.
На основі отриманих результатів визначаються імовірнісні характеристики для всіх станів системи. На основі оцінки усіх варіантів субоптимальних розкладів робиться висновок про їхню відповідність обмеженню заданого критерію оптимальності. Після цього проводиться остаточний вибір розкладу з найкращим результатом за критерієм оптимальності і відсутності часового зсуву убік запізнювання, що є основою оперативного управління.
Для забезпечення виконання зазначених вимог при виробництві полімерного упакування запропоновано структуру системи управління ГВД, що включає підсистеми оперативного управління з такими функціями:
- Оперативне урахування, що включає опитування, збір і передачу первинної інформації про стан об'єкта управління.
- Оперативний контроль, тобто аналіз інформації, що надійшла, виявлення фактичних і, за можливістю, передбачених відхилень від плану, визначення причин відхилень.
- Оперативне управління, що полягає в прийнятті оперативних рішень, спрямованих на усунення невідповідності між запланованим і реальним ходом виробництва, а також в реалізації прийнятих рішень шляхом передачі управляючих впливів на об'єкт управління.
На основі проведеного аналізу об'єкта управління створено предметно-орієнтовану базу даних, підхід до проектування якої засновано на попередній ідентифікації об'єктів виробничої системи з визначенням їхніх взаємозв'язків і можливостей спільного використання об'єктів з різними функціональними завданнями.
У результаті проведених вище досліджень розроблено базу даних підтримки прийняття рішень у підсистемі оперативного календарного планування. Для фізичної реалізації бази даних обрана СУБД Interbase 6.5, що спрощує розробку розподілених інформаційних систем і знімає велику частину навантаження з клієнтської частини інформаційної системи, а також забезпечує можливість розробки процедур, що зберігаються у базі даних .
Реалізацію підсистеми оперативного календарного планування виконано у вигляді програмного комплексу “Календарне планування” на основі універсальної мови програмування Delphi 7.0.
До функцій програмного комплексу входить:
-
одержання з інформаційної системи завдання на виконання виробничої програми;
-
завантаження в імітаційну модель поточного стану виробничої системи;
-
пошук квазиоптимальних варіантів розкладів роботи дільничного устаткування;
-
проведення оцінки надійності розкладів з урахуванням стохастичності процесів, що відбуваються в системі;
-
завантаження в інформаційну систему розкладу, обраного оператором.
Методика і програмне забезпечення підсистеми оперативного календарного планування ГВС виробництва полімерного упакування прийнята до використання у виробничій діяльності науково-виробничого підприємства "Катран" для формування календарних планів-графіків завантаження устаткування дільниці виробництва полімерного упакування Ао "Возко, м. Вознесенськ. Це дало можливість підвищити ефективність функціонування гнучкої виробничої системи, аналізувати календарні плани підприємства, прогнозувати роботу устаткування і мінімізувати собівартість продукції, що випускається.
ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ
У дисертаційній роботі дано нове вирішення актуального наукового завдання підвищення ефективності функціонування гнучкої виробничої системи на прикладі ГВС виробництва полімерного харчового упакування.
У результаті досліджень, які виконані у дисертаційній роботі, отримані наступні нові наукові результати:
1.
Створено модель гнучкої виробничої ділянки полімерного упакування, побудованої на основі об'єктних моделей її типових компонентів: технологічного, транспортно-складського устаткування і системи управління, що дозволяє моделювати роботу системи з різним складом устаткування і його компонуванням.
2.
Обрано і обґрунтовано критерій оптимальності управління ГВС. Для забезпечення реалізації критерію виконана модифікація методу генетичного алгоритму комбінаторної оптимізації, у результаті чого отримана можливість визначення послідовностей випуску виробів, близьких до оптимального.
3.
Сформульовано обмеження, що накладається на результат обчислення цільової функції критерію оптимальності. Як обмеження прийнята надійність субоптимальних розкладів, оцінка якої виконується за допомогою розробленої методики, що враховує в моделі ГВС стохастичні процеси (відмовлення устаткування, відновлення його працездатності і переналагодження).
Наукова новизна роботи складається із таких положень:
1.
Застосовано новий оригінальний підхід до оперативного планування, який ґрунтується на динамічному синтезі розкладів, що дозволило удосконалити структуру системи управління оперативним календарним плануванням роботи гнучкої дільниці виробництва полімерного харчового упакування, мінімізувати склад устаткування і забезпечити високу ефективність його використання.
2.
Розроблено оригінальний метод подання інформації про послідовність виконання запланованих операцій для об'єктів досліджуваної ГВС, особливість якої полягає в багатоваріантності технологічних маршрутів виробництва виробів.
3.
Створено оригінальну методику символьного подання варіантів рішень у процесі отримання субоптимальних розкладів за допомогою генетичних алгоритмів.
4.
Модифіковано метод побудови розкладів шляхом застосування генетичних алгоритмів, дозволяючих забезпечити одержання квазиоптимальних графіків роботи устаткування за малі інтервали часу.
5.
Отримано теоретичні оцінки і сформульовано вимоги до надійності розкладів, що дозволяє враховувати стохастичність процесів, що відбуваються в системі, і визначати з високою точністю часові параметри початку і завершення усіх виконуваних операцій.
ПЕРЕЛІК ПУБЛІКАЦІЙ за ТЕМою ДИСЕРТАЦІЇ
1.
Войцев А.В. Оптимизация оперативных календарных планов в гибком производстве с помощью генетических алгоритмов. // Вісн. Східноукр. нац. ун-ту.2004. № (82). С. 3036.
2.
Войцев А.В. Оптимизация календарного планирования работы ГПС с целью снижения себестоимости продукции. // Системні технології. Міжвід. наук.-техн. зб. вип.2(31). Дніпропетровськ. 2004. С.115121.
3.
Войцев А.В. Модель эффективности подсистемы календарного планирования производства полиэтиленовой упаковки. // Наукові праці Донецького національного технічного університету. Серія "Обчислювальна техніка і автоматизація", вип. 74. 2004. С. 259263.
4.
Войцев А.В. Оценка надежности расписаний работы оборудования в ГПС. // Системні технології. Міжвід. наук.-техн. зб. вип. 4(33). Дніпропетровськ. 2004. С.142150.
5.
Войцев А.В. Модификация генетического алгоритма для нахождения субоптимальных расписаний. // Системні технології. Міжвід. наук.-техн. зб. вип. 5(34). Дніпропетровськ. 2004. С.2132.
6.
Войцев А.В., Коробецкий Ю.П. Модель прогнозирования параметров автоматизированного склада в гибком производстве. Збірн. наук. праць СНУ ім. В.Даля. Матеріали VII Міжнародної науково-практичної конференції "Університет і регіон". Луганськ: Вид-во Східноукр. нац. ун-ту, 2001. С. 99.
Особистий вклад автора в публікації: запропонована структура моделі прогнозування завантаження автоматизованої комірки у складі глобальної моделі ГВС.
7.
Войцев А.В. Оценка вероятности безотказной работы групп оборудования в структуре ГПС. Тези доповідей II Міжнародної науково-технічної конференції "Інформаційна техніка та електромеханіка". Луганськ: 2003. С. 77.
8.
Войцев А.В. Исследование скорости сходимости генетических алгоритмов в задачах обеспечения информационной безопасности. Матеріали I Всеукраїнської науково-практичної конференції "Інформаційні технології і безпека в керуванні". Луганськ: 2004. С. 87 94.
9.
Войцев А.В. Оптимізація календарного планування роботи ГВС. Тези доповідей наукової конференції професорсько-викладацького складу і наукових працівників СНУ ім. В.Даля "Наука - 2004". Луганськ: 2004. С. 113 114.
АНОТАЦІЯ
Войцев А.В. Підсистема оперативного календарного планування гнучкої виробничої системи. - Рукопис.
Дисертація на здобуття ученого ступеня кандидата технічних наук за фахом 05.13.20 – “Гнучкі виробничі системи”. Національний технічний університет України “КПІ”, м. Київ, 2005.
У дисертаційній роботі наведено нове вирішення актуального наукового завдання підвищення ефективності функціонування гнучкої виробничої системи на прикладі реалізації ГВС виробництва полімерного харчового упакування завдяки використанню підсистеми оперативно-календарного планування, яка забезпечує аналіз календарних планів підприємства, прогнозування роботи устаткування і мінімізацію собівартості продукції, що випускається. Застосовано новий оригінальний підхід до оперативного планування заснований на динамічному синтезі розкладів. Розроблено оригінальний метод подання інформації про послідовність виконання запланованих операцій для об'єктів досліджуваної ГВС, особливість якої полягає в багатоваріантності технологічних маршрутів виробництва виробів. Створено оригінальну методику символьного подання варіантів рішень у процесі формування субоптимальних розкладів за допомогою генетичних алгоритмів. Модифіковано метод побудови розкладів шляхом застосування генетичних алгоритмів, що дозволило забезпечити одержання квазиоптимальних графіків роботи устаткування за малі інтервали часу. Отримано теоретичні оцінки і сформульовано вимоги до надійності розкладів, що дозволяє враховувати стохастичність процесів, що відбуваються в системі, і визначати часові параметри початку і завершення усіх виконуваних операцій з високою точністю.
Ключові слова: гнучка виробнича система, генетичний алгоритм, критерій оптимізації, об'єктна модель, система підтримки прийняття рішень, надійність, календарне планування.
Аннотация
Войцев А.В. Подсистема оперативного календарного планирования гибкой производственной системы. - Рукопись.
Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.20 – “Гибкие производственные системы”. Национальный технический университет Украины “КПИ”, г. Киев, 2005.
В диссертационной работе дано новое решение актуальной научной задачи повышения эффективности функционирования гибкой производственной системы на примере реализации ГПС производства полимерной пищевой упаковки за счет использования подсистемы оперативно-календарного планирования, обеспечивающей анализ календарных планов предприятия, прогнозирования работы оборудования и минимизацию себестоимости выпускаемой продукции. Применен новый оригинальный подход к оперативному планированию основанный на динамическом синтезе расписаний, что позволило усовершенствовать структуру системы управления оперативным календарным планированием работы гибкого участка производства полимерной пищевой упаковки, минимизировать состав оборудования и обеспечить высокую эффективность его использования. Разработан оригинальный метод представления информации о последовательности выполнения запланированных операций для объектов исследуемой ГПС, особенность которой заключается в многовариантности технологических маршрутов производства изделий. Создана оригинальная методика символьного представления вариантов решений в процессе нахождения субоптимальных расписаний с помощью генетических алгоритмов. Модифицирован метод построения квазиоптимальных расписаний путем применения генетических алгоритмов, что позволило обеспечить получение квазиоптимальных графиков работы оборудования за малые интервалы времени. Получены теоретические оценки и сформулированы требования к надежности расписаний, что позволяет учитывать стохастичность процессов, происходящих в системе, и определять временные параметры начала и завершения всех выполняемых операций с высокой точностью.
Моделирование работы гибкой производственной системы позволяет получать оценки качества алгоритмов управления ГПС, а именно: формирования исходной очереди запуска, оперативного календарного планирования, а также диспетчирования заявок на обслуживание средствами транспортирования. В качестве содержательной части моделирования работы ГПС принята имитация движения компонентов материальных потоков по обрабатывающим ресурсам, под которыми понимается как их обслуживание (обработка и транспортировка), так и хранение в перерывах между обслуживаниями. В качестве показателя оптимальности формируемых расписаний выбран минимум приведенных затрат на производство одного изделия. На поиск оптимальных расписаний по предложенному критерию оптимальности накладывается единственное ограничение – сроки завершения заданных работ, по которому производится окончательная оценка качества получаемых расписаний.
Кодирование признаков решаемой задачи осуществляется на основе генов переменной длины, поскольку данный способ кодирования более точно отражает параметры решаемой задачи. Предложенное представление гена и хромосомы дало возможность на уровне отдельной хромосомы и популяции в целом абстрагироваться от способа хранения генной информации и тем самым упростить работу генетического алгоритма. Модификация способа
