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

ФОНОТОВ АНАСТАС МИХАЙЛОВИЧ

УДК 681.518

АВТОМАТИЗОВАНА СИСТЕМА ГІЛЬЙОТИННОГО РОЗКРОЮ НА ОСНОВІ ГЕНЕТИЧНОГО ПРОГРАМУВАННЯ
(НА ПРИКЛАДІ МЕБЛЕВОГО ВИРОБНИЦТВА)

Спеціальність 05.13.07 -“

Автоматизація технологічних процесів”

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

Донецьк - 2006

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

Робота виконана в Донецькому національному технічному університеті Міністерства освіти та науки України.

Науковий керівник: | доктор технічних наук, професор

Скобцов Юрій Олександрович,

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

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

Бойко Віталій Іванович,

завідувач кафедри “Електроніка й автоматика” Дніпродзержинського державного технічного університету, м. Дніпродзержинськ;

кандидат технічних наук, доцент

Бессараб Володимир Іванович,

завідувач кафедри “Автоматика й телекомунікації” Донецького національного технічного університету, м. Донецьк

Провідна організація: | Національний технічний університет –

"Харківський політехнічний інститут", кафедра “системного аналізу та управління” Міністерства освіти та науки України, м. Харків

Захист відбудеться 8 червня 2006 р. у 14 годин на засіданні спеціалізованої вченої ради К11.052.03 Донецького національного технічного університету за адресою: 83000, вул. Артема, 58, корп. 8, ауд. 704.

З дисертацією можна ознайомитися в бібліотеці Донецького національного технічного університету за адресою: 83000, вул. Артема, 58, корп. 2.

Автореферат розісланий “06” травня 2006 р.

Учений секретар спеціалізованої

вченої ради К11.052.03

кандидат технічних наук, доцент Г. В. Мокрий

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

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

Вагомий внесок у рішення проблеми оптимального розкрою матеріалів внесли Канторович Л.В., Мухачева Е.О., Стоян Ю.Г., Бабаєв Ф.В., Бєлякова Л.Б., J. Riehme, G. Scheithauer, P.Y. Wang й інші вчені.

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

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

Зв'язок з державними програмами, планами, темами. Дисертаційна робота виконана у рамках держбюджетної теми Д-11-04 (№0104U002394) Донецького національного технічного університету “Розробка й дослідження нейромережевих й еволюційних методів створення систем прийняття рішень”, у якій автор брав особисту участь як виконавець.

Результати дисертації використані в навчальному процесі під час курсового й дипломного проектування на кафедрі “Автоматизовані системи управління” ДонНТУ.

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

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

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

- Обґрунтувати метод і розробити генетичний алгоритм (ГА) оптимізації технологічних карт розкрою деревинностружкових та деревинноволокнистих плит з урахуванням накладених обмежень (устаткування, геометричні розміри заготівок, часові).

- Розробити об’єктно-орієнтовану модель системи автоматизації процесу гільйотинного розкрою в умовах дрібносерійного меблевого виробництва за допомогою уніфікованої мови моделювання (UML).

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

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

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

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

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

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

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

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

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

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

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

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

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

Практичне значення отриманих результатів:

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

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

3. Застосування модифікованого генетичного алгоритму дозволило робити пошук оптимального рішення для задач дуже великої розмірності (кількість деталей різної розмірності більше 300). У результаті роботи методу збільшений коефіцієнт використання матеріалів, скорочена кількість операцій на форматно-розкрійному верстаті.

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

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

Використання результатів роботи. Розроблена автоматизована система гільйотинного розкрою прийнята до використання в технологічному процесі виготовлення меблів Донецькою обласною фабрикою КП “РЕММЕБЕЛЬ” та впроваджена в цеху складання меблів ВАТ “Синтез”.

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

Апробація результатів дисертації. результати дисертаційної роботи освітлені на двох міжнародних конференціях: 5-та науково-практична міжнародна конференція “Інформаційні технології в освіті й управлінні” (НКПІ, м. Нова Каховка, Україна, 2003 р.), 5-й міжнародний науково-практичний семінар “Практика й перспективи розвитку партнерства в сфері вищої школи” (ТРТУ, Таганрог, Росія, 2004 р.). Дисертація розглянута й у цілому схвалена на розширеному засіданні кафедр факультету “Комп'ютерні інформаційні технології й автоматика”.

Публікації. За темою дисертації опубліковано 6 наукових праць, у тому числі 5 у провідних науково-технічних збірниках, затверджених ВАК України, й в одній доповіді на конференції. Три наукові праці написані без співавторів.

Структура й обсяг дисертації. Дисертація складається із вступу, п'яти розділів і висновку. Вона включає 159 сторінок друкованого тексту, у тому числі 125 сторінок основної частини, 48 рисунків й 24 таблиці, список використаної літератури з 81 найменування на 7 сторінках, 7 додатків на 15 сторінках.

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

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

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

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

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

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

У другому розділі “Розробка математичної моделі технологічного процесу гільйотинного розкрою матеріалу в умовах меблевого виробництва” виконано аналіз технологічного процесу гільйотинного розкрою. Основними факторами, які впливають на задачу розкрою, є: наявність сировинних потужностей, виробничі можливості, часові обмеження, технологічні обмеження. Сировинні потужності обмежуються розмірами й номенклатурою складів. Виробничі можливості обумовлюються максимальними об'ємами випуску готової продукції. Технологічні обмеження обумовлені різними типами використовуваних у виробництві форматно-розкрійних верстатів. Кожний форматно-розкрійний верстат характеризується вектором V{?l1, Дl2, Дг, Hmax, Wmax}, де ?l1, Дl2 – відступи від країв заготівки, лівого, правого й верхнього і нижнього відповідно, ?г – товщина пропилу, Hmax, Wmax – максимальна довжина шляху різального інструмента.

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

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

Рис. 1 - Блок схема алгоритму виконання елементарної операції

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

Кількість елементарних операцій для будь-якого плану розкрою задовольняє нерівності 1.

, (1)

де m – кількість деталей, а - кількість елементарних операцій для розкрою .

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

Обмеження форматно-розкрійного верстата на розмір мірних залишків і заготівель (2, 3).

, | (2)

. | (3)

Обмеження мінімальної ширини від краю до шляху ходу циркулярної пилки, при обліку цього параметра розглядають w1, w2 – ширина частин, отриманих у результаті розпила, й h1, h2 – відповідно довжини цих частин.

(4)

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

. | (5) | Необхідність обліку наявності сировинних ресурсів ураховується обмеженням (6).

(6) | На карту розкрою, крім технологічних обмежень, накладаються геометричні обмеження на не перетинання деталей між собою й із межею заготівлі. Ураховується також варіант, при якому дозволений поворот деталі на 90, .

(7)

(8) | З обліком виділених технологічних обмежень математична модель процесу гільйотинного розкрою запишеться у такий спосіб:

, (9)

де F1 - мінімізація відходів, F2 - мінімізація кількості немірних залишків, F3 - мінімізація довжини маршруту різу, F4 - мінімізація кількості елементарних операцій, T - облік обмежень за тимчасовими характеристиками, F5 – тимчасове обмеження на строки формування комплектів для розкрою.

При цьому на систему рівнянь 9 накладаються обмеження 1..8:

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

, (10)

де , , , - коефіцієнти функції оптимальності.

Виконано аналіз класичної структури генетичного алгоритму. Прийнято рішення використати функцію як фітнес-функції генетичного алгоритму гільйотинного розкрою.

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

Рис. 2 Показ гільйотинного розкрою у вигляді дерева

Дерево кодується чотирма векторами: - множина заготівель, розміром – m; – напрямок розрізу в поточному вузлі, розміром 2*n; – визначає послідовність розгляду деталей алгоритмом розміщення (кожен ген цієї хромосоми містить відомості про лінійні розміри деталі, можливість її повороту на 90 і ознаку входження деталі в блок деталей), розміром n; – задає орієнтацію деталей, розміром n. Де m - кількість заготівель, а n - потужність задачі розкрою.

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

Оцінка особин проводиться на основі фітнес-функції (10). Формування нової популяції проводиться за допомогою класичних і проблемно-орієнтованих операторів схрещування та мутації.

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

Другий нащадок формується аналогічно першому, тільки тепер основним є другий батько. Кількість особин, які формуються цим оператором на етапі створення нової популяції, досягає 80%. Приклад наведений на рис. 3.

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

Виконано експериментальні дослідження з метою встановити залежність швидкості збіжності алгоритму й ефективності розкрою від: розміру популяції ГА, оператора редукції, N - кількості заготівель.

У результаті експериментів було встановлено, що оператор редукції, який використовує спосіб елітарної заміни, у середньому на 10% ефективніше способу чистої заміни й на 2% ефективніше способу випадкової заміни.

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

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

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

Таблиця 1.

Дослідження проблемно-орієнтованого оператора схрещування

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

40 | 100 | 300 | 500 | 1000 | 2000

5 | щільність заповнення, % | 82,3 | 81,9 | 83,5 | 88,7 | 90,1 | 90,5

ітерації | 285 | 335 | 453 | 507 | 682 | 717

10 | щільність заповнення, % | 82,2 | 82,3 | 84,5 | 88,9 | 89,8 | 90,3

ітерації | 258 | 294 | 442 | 523 | 598 | 672

15 | щільність заповнення, % | 80,5 | 80,6 | 81,7 | 89,5 | 90 | 89,7

ітерації | 267 | 289 | 406 | 487 | 548 | 595

20 | щільність заповнення, % | 80,9 | 80,6 | 80,6 | 83,7 | 85,7 | 84,9

ітерації | 185 | 229 | 289 | 305 | 386 | 367

25 | щільність заповнення, % | 78,9 | 79,4 | 80,4 | 84,8 | 85,4 | 85,7

ітерації | 160 | 235 | 324 | 287 | 356 | 342

Експериментально визначена межа використання проблемно-орієнтованого оператора схрещування, результати досліджень у таблиці 1. Кращі результати досягаються при ймовірності застосування спеціального оператора схрещування 5-15% особин, інакше можливе виродження популяції. Рекомендується застосовувати цей оператор, після того як для середнього індивіда популяції середня щільність 15% заготівель, що розкроюються, буде перевищувати 80%.

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

У четвертому розділі “Розробка й дослідження паралельного генетичного алгоритму гільйотинного розкрою” проведено обґрунтування і вибір моделі паралельного генетичного алгоритму. Розроблено паралельний генетичний алгоритм на основі моделі островів, що дозволило вирішувати задачі великої розмірності й скоротити втрати матеріалу до 5%, кількість операцій, виконуваних на форматно-розкрійному обладнанні на 7%, при цьому загальний час пошуку рішення у порівнянні з генетичним алгоритмом гільйотинного розкрою скоротилося на величину від 450% до 50% в залежності від розміру задачі.

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

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

Рис. 4а Графік залежності часу рішення від розміру задачі розкрою | Рис. 4б Залежність щільності заповнення заготівель від розміру задачі розкрою

Таблиця 2

Щільність заповнення Q і час рішення t, отримані методами ПГАГР-МО, ПГПГР-РХ, Астра 4.2, BestCut2 й cutting3 1.38

Кількість деталей m | ПГАГР-МО | ПГПГР-РХ | Астра 4.2 | BesCutt2 | cutting3 1.38

Q | t, c | Q | t, c | Q | t, c | Q | t, c | Q | t, c

400 | 87,54 | 134 | 86,24 | 84 | 87,78 | 24 | 86,50 | 57 | 87,24 | 85

800 | 90,25 | 338 | 89,47 | 177 | 88,17 | 55 | 87,47 | 107 | 89,24 | 121

1200 | 91,68 | 456 | 89,74 | 244 | 88,78 | 127 | 89,38 | 224 | 89,54 | 234

1600 | 92,04 | 478 | 90,12 | 301 | 89,24 | 234 | 89,44 | 308 | 90,12 | 381

3200 | 91,94 | 498 | 89,42 | 458 | 89,55 | 548 | 89,74 | 452 | 90,45 | 474

4800 | 92,12 | 537 | 91,25 | 647 | 89,38 | 685 | 89,96 | 507 | 91,18 | 567

6400 | 92,33 | 596 | 91,86 | 856 | 89,84 | 716 | 90,27 | 558 | 91,44 | 629

Отримані результати, було проаналізовано і зроблено наступні висновки:

З модифікацій алгоритму ГАГР кращі результати виявив паралельний генетичний алгоритм на основі моделі островів. Це можна пояснити тим, що алгоритм ПГАГР-РХ працює в режимі реального часу, тому формування оптимального розкрою відбувається поетапно, що може відтинати частину рішень.

Алгоритми, реалізовані в системах розкрою Астра 4.2, BestCut2 й cutting3 1.38, мають кращий час рішення для задач розкрою з числом деталей менше 1600, однак для задач більшої розмірності ПГАГР-РХ і ПГАГР-МО перевершують їх за швидкістю.

Така ж ситуація спостерігається й зі щільністю заповнення заготівель; для задач розмірністю менше 1000 різниця в щільності заповнення менше 1%, але при збільшенні кількості деталей у задачі розкрою перевага алгоритму ПГАГР-МО зростає на 2-3%, а на окремих задачах - до 5%.

У п'ятому розділіі “Розробка автоматизованої системи гільйотинного розкрою” для перевірки адекватності математичної моделі розроблена модель автоматизованої системи гільйотинного розкрою засобами уніфікованої мови моделювання UML, що описує систему у всіх аспектах її існування: функціональному, динамічному, статичному, фізичному. Розроблена модель дозволяє виконати проектування автоматизованої системи гільйотинного розкрою. Основним блоком в автоматизованій системі гільйотинного розкрою є алгоритм оптимізації ПГАГР, що відповідає за пошук оптимального плану розкрою.

У методології UML функції системи подаються на діаграмі варіантів використання. Для системи були виділені наступні діючі особи: замовник, оператор, майстер цеху, інженер-планувальник, алгоритм розкрою (ПГАГР), складська система, база даних замовлень, керуюча система форматно-розкрійного верстата (ФРВ), виріб (тому що ми розглядаємо тільки задачу розкрою, а складання виробу не розглядається).

Рис. 5 Головна діаграма варіантів використання автоматизованої системи гільйотинного розкрою.

Система розділена на чотири підсистеми, кожна з яких представлена окремим пакетом (див. рис. 5). Пакети зв'язані між собою завдяки спільним для всієї системи діючим особам: майстер цеху, база даних замовлень і складська система.

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

На основі збудованої UML-моделі виконана розробка архітектури й алгоритмів функціонування автоматизованої системи гільйотинного розкрою на базі генетичних алгоритмів.

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

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

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

ВИСНОВКИ

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

У ході виконання дисертаційної роботи були отримані наступні основні результати:

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

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

3. Розроблені й досліджені проблемно-орієнтовані: цільова функція, оператори схрещування й мутації, метод кодування задачі розкрою в хромосомі. Проведено експериментальні дослідження розроблених проблемно-орієнтованих операторів. Показано, що використання розроблених операторів схрещування й мутації призводить до підвищення ефективності розкрою до 5% і скороченню обчислювальних витрат на 30-40%.

4. Розроблено паралельний ГА на основі моделі островів, що дозволяє провадити пошук технологічних карт розкрою для задач великої розмірності. Експериментально показано, що використання розробленого генетичного алгоритму в якості ядра підсистеми оптимізації технологічних карт розкрою дозволяє скоротити втрати матеріалу до 5%.

5. Виконано розробку архітектури й алгоритмів функціонування автоматизованої системи гільйотинного розкрою на базі генетичних алгоритмів. Автоматизована система гільйотинного розкрою складається з підсистем: уведення й зберігання нормативної й довідкової інформації, формування задачі розкрою, попередньої перевірки задачі розкрою, розрахунку параметрів паралельного ГАГР, пошуку оптимального рішення за допомогою ГАГР, друку оптимальної технологічної карти розкрою, кодування знайденого плану розкрою в необхідний формат форматно-розкрійного верстата з ЧПУ. Показано, що доцільно виконати побудову такої системи з використанням принципу модульності, а генетичний алгоритм побудувати з використанням технологій ООП.

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

7. Розроблена математична модель системи, алгоритми розкрою, інформаційне й програмне забезпечення - передані ВАТ “Синтез” м. Донецьк і використані для скорочення ресурсовитрат цеху виробництва корпусних меблів. Впровадження автоматизованої системи гільйотинного розкрою дозволило підвищити відсоток використання матеріалу на 4%, скоротити час переходу від процесу формування карт розкрою до розкрою деревинностружних плит за рахунок використання підсистеми оптимізації карт розкрою в режимі реального часу.

8. Результати, отримані в дисертаційній роботі, використані в держбюджетній темі Донецького національного технічного університету Д- 11-04 , а також у навчальному процесі кафедри “Автоматизовані системи управління” Донецького національного технічного університету.

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

1. Скобцов Ю.А., Фонотов А.М. Эволюционный подход к решению задачи раскроя листа гильотинным резом. // Наукові праці Донецького національного технічного університету. Серія: Обчислювальна техніка та автоматика, випуск 64: Донецьк: ДонНТУ - 2003. – С. 248-259.

2. Скобцов Ю.А., Фонотов А.М. Решение задачи раскроя на основе генетического программирования // Вестник Херсонського государственного технического университета. № 2(18), Херсон - 2003. – С. 137-142.

3. Фонотов А.М. Построение модели системы автоматизации гильотинного раскроя с помощью UML – диаграмм. // Наукові праці Донецького національного технічного університету. Серія: Обчислювальна техніка та автоматика, випуск 74: Донецьк: ТОВ “Лебідь”, ДонНТУ - 2004. – С. 186-191.

4. Фонотов А.М. Построение и исследование параллельного генетического алгоритма гильотинного раскроя на основе модели островов // Наукові праці Донецького національного технічного університету. Серія: Інформатика, кібернетика та обчислювальна техніка, випуск 93: Донецьк: ДонНТУ - 2005. – С. 136-144

5. Фонотов А.М. Параллельный генетический алгоритм оптимизации гильотинного раскроя в режиме реального времени // Вісник Донецького Університету. Серія А: природничі науки, Випуск 2/2005, Частина 2: Донецьк ДонНУ - 2005, -С. 370-374

6. Скобцов Ю.А. Фонотов А.М. Исследование проблемно-ориентированных операторов ГА для задачи гильотинного раскроя. // Известия ТРТУ-ДонНТУ. Материалы пятого международного научно-практического семинара “Практика и перспективы развития партнерства в сфере высшей школы”. В 2-х кн. –Таганрог. Изд-во ТРТУ. Кн. 2. 2004, №4.,
-С 160-169.

Особистий внесок автора в публікаціях, написаних у співавторстві:

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

Анотація

Фонотов Анастас Михайлович. Автоматизована система гільйотинного розкрою на основі генетичного програмування (на прикладі меблевого виробництва). Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.07 - “Автоматизація технологічних процесів” - Донецький національний технічний університет, Донецьк, 2006.

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

Ключові слова: гільйотинний розкрій, паралельний генетичний алгоритм, хромосома, генетичні оператори, математична модель, форматно-розкрійній верстат, технологічна карта розкрою.

Аннотация

Фонотов Анастас Михайлович. Автоматизированная система гильотинного раскроя на основе генетического программирования (на примере мебельного производства). –Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.07 – “Автоматизация технологических процессов” - Донецкий национальный технический университет, Донецк, 2006.

В диссертационной работе дано новое решение актуальной научной задачи – повышению эффективности технологической подготовки мебельного производства и производственных процессов при раскрое мебельных заготовок путем усовершенствования подсистемы поиска оптимальных технологических карт раскроя, формированию маршрута реза, автоматического учету мерных остатков и работы автоматизированной системы в режиме реального времени. Получила дальнейшее развитие математическая модель процесса гильотинного раскроя материалов (пиломатериалов, древесностружечных плит, древесноволокнистых плит), которая отличается от известных тем, что учитывает технологические ограничения процесса раскроя, трудозатраты оператора форматно-раскроечного станка и длину маршрута реза. Разработан параллельный генетический алгоритм раскроя на основе модели островов, в котором предложены новая фитнесс-функция, способ кодирования решения в хромосом, проблемно-ориентированные генетические операторы. Это позволило сократить потери материала на величину до 5%, число операций выполняемых на форматно-раскроечном оборудовании на 7%.

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

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

The summary

A.M. Fonotov. The automated system of guillotine cutting on basis of genetic programming (on the example of furniture manufacture). – Manuscript.

The PhD dissertation speciality 05.13.07 - “Automation of technological processes” - Donetsk national technical university, Donetsk, 2006.

In this the new decision of an actual scientific problem- is given to increase an efficiency of technological preparation of furniture manufacture at furniture preparations cutting. For this purpose the subsystem of search of optimum technological cutting, formations of a cutting line, the automatic calculator of the measured remains is developed. The parallel genetic algorithm of cutting on basis of model of islands is developed. New fitness-function, a way of coding of the decision in the chromosomes, the problem-oriented genetic operators are offered. The method proposed allowes to reduce material losses by 5 %, number of operations carried out on cutting equipment by 7 %. The parallel genetic algorithm based on “worker-master” model allows to generate cutting maps in real time.

The application programming interface for technological cutting maps generating.

· Key words: guillotine cutting, parallel genetic algorithm, a chromosome, genetic operators, mathematical model, cutting tool, a technological cutting map.

Віддруковано на ризографі

ТОВ фірма “Друк-ІНФО”

Підп. До друку 06.05.2006 р.

Ум. -друк. Арк. 1,0.

Тираж 100 прим. Замовлення №1355

83000, м. Донецьк, вул. Артема, 58, к. 113