Оптимізація схем розкрою матеріалів на деталі шкіргалантерейних виробів

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

Київський Національний Університет Технологій та дизайну

Колиско Оксана Зенонівна

УДК 685.31

Оптимізація схем розкрою матеріалів на деталі шкіргалантерейних виробів

Спеціальність 05.18.18 - технологія взуття , шкіргалантерейних виробів і хутра

Автореферат

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

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

Київ-2009

ДИСЕРТАЦІЄЮ Є РУКОПИС

Робота виконана в Київському національному університеті технологій та дизайну Міністерства освіти і науки України

Науковий керівник:

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

Чупринка Віктор Іванович,

Київський національний університет технологій та дизайну,

доцент кафедри інформаційних технологій проектування

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

доктор технічних наук, професор

Нестеров Владислав Петрович,

Президент Української технологічної академії

доктор технічних наук, с.н.с.,

Опанасенко Володимир Миколайович,

Інститут кібернетики ім. В.М.Глушкова НАН України, провідний науковий співробітник відділу мікропроцесорної техніки.

Захист відбудеться « 26 » __листопада_2009_р. о 10-00 годині на засіданні спеціалізованої вченої ради Д 26.102.03 Київського національного університету технологій та дизайну за адресою: 01011, м. Київ 11, вул. Немировича-Данченка, 2., корпус 1.

З дисертацією можна ознайомитись у бібліотеці Київського національного університету технологій та дизайну за адресою: 01011, м. Київ-11, вул. Немировича-Данченка, 2.

Автореферат розісланий « 24 »_жовтня_2009р

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

спеціалізованої вченої ради, к.т.н., доц. Т.О. Полька

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

Актуальність роботи. Одним з головних факторів успіху діяльності підприємства в ринкових умовах є безперервне оновлення товарів при високій технології виробництва, іншими словами - створення, розробка, випробування, і освоєння нової продукції. Розв'язок питань підвищення конкурентноздатності і зниження собівартості продукції значною мірою пов'язані з автоматизацією робіт на етапі підготовчого виробництва. Одним з шляхів підвищення техніко-економічних показників в легкій промисловості є оптимізація розкрійного виробництва. Як відомо, вироби шкіргалантерейної промисловості належать до так званих матеріаломістких (де частка матеріалів в собівартості коливається в межах 80-90%), тому питанню економії матеріальних ресурсів приділяється багато уваги. Крім того в даний час дуже актуальною є задача зменшення (уникнення) забруднення природи. І оскільки виробництво натуральних шкір і штучних матеріалів, а особливо утилізація відходів виробництва і залишків синтетичних матеріалів, є шкідливими для навколишнього середовища, то нагальною є проблема економного використання матеріалів з метою зменшення залишків та певною мірою зменшення попиту на сировину.

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

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

Зв'язок роботи з науковими програмами, планами, темами.

Дисертаційна робота виконана в рамках наукової програми „Обладнання, системи управління технологічними процесами та контролю якості виробів” (держбюджетна тематика № н/н 05ч08, 2005-2008 р.р) у відповідності з планом науково-дослідних робіт Міністерства освіти і науки України.

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

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

- розробити математичні моделі та адаптований до них алгоритм введення в комп'ютер інформації про контури деталей і програмну реалізацію розробленого алгоритму;

- розробити та реалізувати математичні моделі та алгоритми для автоматизації щільного розміщення деталей на матеріалі;

- застосувати модифікацію генетичного алгоритму для вирішення задачі генерації секцій, дослідити властивості його програмної реалізації;

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

- застосувати алгоритми корегування розкрійних схем;

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

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

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

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

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

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

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

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

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

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

- створити програмні засоби з автоматизації підготовчо-розкрійного виробництва;

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

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

- підвищити коефіцієнт використання матеріалу в середньому на 1,3-4% збільшити кількість раціональних розкрійних схем в 1,3 рази;

- інтегрувати розроблені програмні модулі з вже існуючою системою ІРІС (підтримує інтеграцію в існуючі системи автоматизації і за рахунок своєї модульності має гнучкість впровадження);

- впровадити результати дисертаційної роботи в навчальний процес на кафедрі інформаційних технологій проектування Київського національного університету технологій та дизайну для студентів спеціальностей 7.080402, 8.080402, у відділ мікропроцесорної техніки Iнституту кібернетики ім. В.М. Глушкова НАНУ, ЗАТ ВКФ «Леся», ТОВ «Група компаній «Бумсервіс». Очікуваний економічний ефект становить 59 тис. грн. на рік.

Особистий внесок здобувача. Полягає у постановці та вирішенні основних теоретичних та експериментальних завдань. У працях, виконаних із співавторами, особистий внесок здобувача полягає у вирішенні основних теоретичних та прикладних задач [1-3, 7-12, 4(розділ 6)]. Автору належать основні ідеї, узагальнення та висновки при виконанні аналітичних та експериментальних досліджень, а також в обробці одержаних результатів. Стаття [6] написанa особисто автором.

Апробація результатів роботи.

Основні наукові і практичні результати дисертації доповідались, обговорювались і отримали позитивну оцінку на:

- наукових конференціях молодих вчених та студентів Київського національного університету технологій та дизайну в 2005-2009р;

- ювілейній міжнародній науково-технічній конференції «Інноваційні технології - майбутнє України» (м. Київ, КДУТД, 2005);

- науково-методичних семінарах кафедри інформаційних технологій проектування КНУТД в 2005-2009р; міжкафедральному науковому семінарі кафедри конструювання та технології виробів зі шкіри (листопад 2008р);

- в відділі мікропроцесорної техніки Iнституту кібернетики ім. В.М. Глушкова НАНУ; ЗАТ ВКФ «Леся»; ТОВ «Група компаній «Бумсервіс». Дисертація доповідалась повністю і одержала позитивну оцінку на:

- науковому семінарі кафедри інформаційних технологій проектування, КНУТД (березень 2009р);

- міжкафедральному науковому семінарі кафедри конструювання та технологій виробів зі шкіри, КНУТД (травень 2009р).

Публікації За темою дисертації опубліковано 12 наукових робіт, серед яких 6 наукових статей в у фахових виданнях, рекомендованих ВАК України та одна монографія.

Структура дисертації. Дисертація складається з вступу, чотирьох розділів, висновків, списку використаних джерел і додатків. Робота викладена на 128 сторінках, містить 42 малюнки, 22 таблиці, бібліографічний список з 137 найменувань та 55 сторінок додатків. Повний обсяг дисертації складає 183 сторінок.

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

У вступі обґрунтовано актуальність теми, сформульовано мету та основні задачі досліджень, визначено наукову новизну та практичну значимість роботи.

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

В підрозділі 1.1. проведено перегляд і аналіз структури та можливостей існуючих систем автоматизованого проектування в легкої промисловості. З розгляду систем таких відомих виробників як Gerber Technology Solutions (AccuMark і MicroMark), КОМТЕНС, САПРЛЕГПРОМ (Julivi) Investronica-Sistemas (Lectra), розробка КНУТД „ІРИС” та ін. зроблено наступні висновки:

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

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

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

Інтенсивний розвиток комп'ютерної техніки, наукові розробки колективів України, Росії та ін., роботи в цьому напрямку Фукіна В.О., Березненка М.П., Коновала В.П., Щербаня Ю.Ю., Орловського Б.В., Либи В.П. є передумовами розробки вітчизняних САПР для взуттєвої та шкіргалантерейної промисловості.

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

В підрозділі 1.3. розглядались методи подання інформації про зовнішні контури деталей. Було проаналізовано такі способи апроксимації як: аналітичний опис контуру через многочлени (сплайни, поліноми, R-функції) і дискретні способи опису (апроксимація колами, координатно-трапеційний спосіб, рецепторні матриці, радіусографічний спосіб, кусково-лінійна апроксимація). Кусково-лінійний спосіб апроксимації було обрано для подальшого використання в роботі через зручність як введення вихідної інформації так і подальшої візуалізації контурів і, в разі потреби, організації руху різального інструменту за заданою програмою.

Огляд робіт присвячених раціональному розкрою з його застосуванням в легкій промисловості проведено в підрозділі 1.4. Питання раціонального використання матеріалів розглядались в дослідженнях Шусторовича М.Л., Зибіна Ю.П., Іспіряна Г.П., Рожка В.Д., Фукіна В.Д. та ін. Основна увага приділялась оптимізаційним методам фігурного розкрою, починаючі роботами з покриття поверхні геометричними фігурами до вдосконалених економіко-математичних моделей планування розкрійних схем. Теоретичні основи оптимального розміщення деталей на матеріалові розроблені Рвачевим В.Л., Стояном Ю.Г., у взуттєвому виробництві в цьому напрямку проводились дослідження Нестеровим В.П., Скатерним В.А., Фесенко А.Г., Поповою Л.С., Свістуновою Л.Т. Аналіз інформаційних джерел показав, що спочатку в дослідженнях з раціонального розкрою обрахункові методи базувались на вхідній інформації про схеми суміщення деталей отриманій вручну, що не давало високої ефективності та якості розробок. Розвиток комп'ютерних технологій і комп'ютеризація виробничої діяльності дозволяють орієнтуватись на розробку більш швидких та якісних алгоритмів пошуку оптимальних або субоптимальних рішень. Саме до таких задач відносять задачі оптимізації проектування комбінованих розкрійних схем рулонних матеріалів з урахуванням технологічних аспектів. Поставлена задача є мультимодальною і багатовимірною, тобто містить багато параметрів. Для таких задач не існує жодного універсального методу, який дозволяв би достатньо швидко знайти абсолютно точне рішення. Для вирішення поставленої задачі запропоновано обрати модифікований щодо конкретних умов генетичний алгоритм. Генетичний алгоритм як комбінація переборного і градієнтного методів, дозволяє отримати наближене рішення, точність якого зростатиме при збільшенні часу розрахунку.

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

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

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

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

Вся інформація про створений комплект деталей находить своє відображення в файлі формату *.dgt. Структура файлу та її обґрунтування наведені в підрозділі 2.3.

В підрозділі 2.4. розглянуто алгоритми підготовчого етапу побудови розкрійних схем такі як: алгоритми щільного суміщення деталей і обрахунку лінійних ефектів при щільному суміщенні деталей. В пункті 2.4.1 визначались параметри подвійних решітчастих щільних укладок, а саме: вектори решітки a₁, a₂ та вектор зсуву решітки q з урахуванням можливості різної орієнтації деталей в ряду і в рядах. Оскільки кожна секція складається із смуг заповнених однаковими деталями, в яких застосовується прямолінійно-поступальна система (система паралелограма або решітчаста система) розміщення однакових деталей в ряду, то будуються щільні укладки та визначаються їх параметри при розташуванні :

а) без повороту деталі;

б) з поворотом деталі в ряду на 180 градусів по ширині схеми;

в) з поворотом деталі в ряду на 180 градусів по довжині схеми.

В пункті 2.4.2. наведено алгоритми визначення лінійних ефектів від щільного суміщення деталей в ряду і при щільному суміщенні рядів. Щоб забезпечити щільне укладання деталей необхідно врахувати лінійні ефекти від суміщення деталей по довжині матеріалу (в ряду) та один лінійний ефект по ширині (при суміщенні рядів). Для деталей без повороту в ряду матимемо один лінійний ефект, а з поворотом - два. Позначимо через та - лінійні ефекти від щільного суміщення деталей в ряду, а через- лінійний ефект від щільного суміщення рядів.

Тоді координати полюсів деталей першого ряду можна виразити наступними співвідношеннями:

де D₁ , (H₁) - довжина (ширина) описаного навколо деталі прямокутника,

L₁ (L₂) - перший (другий) лінійний ефект від суміщення.

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

Координати полюсів деталей будь-якого ряду можна виразити наступними співвідношеннями:

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

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

з множини допустимих схем розкрою для Kilk комплектів деталей S^k, знайти таку розкрійну схему довжина якої буде мінімальною, тобто довжина якої

,

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

В підрозділі 3.1. запропонована математична модель секції розкрійної схеми. При розкрою рулонних матеріалів секції розкрійної схеми представляють собою прямокутні області постійної ширини Sh та змінної довжини Dl_i щільно заповнені деталями і є варіантами можливих розв'язків задачі оптимізації корисної площі секції

,

де - відсоток використання площі і-тої секції з множини всіх допустимих секцій. Маємо комплект деталей виробу, що складається з p різних деталей. Треба створити множину різних розкладок даних деталей, де для кожної окремої розкладки виконуються наступні умови: кількість деталей в ній не перевищує потребу в даному типові деталей, процент використання матеріалу Vids_i задовольняє нормативам галузі Pv. В результаті генерування множини допустимих розкладок ми отримуємо матрицю , де t - кількість згенерованих розкладок, p - кількість різних деталей моделі. Тоді елемент матриці - це кількість k -тих деталей в і -тій розкладці. Умови до секції визначаються нерівностями:

де kil_det_k - потреба в k-тій деталі,

Vids_i Pv.

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

В підрозділі 3.2 проведена розробка і повний опис модифікованого генетичного алгоритму для вирішення задачі побудови розкладок, враховуючи специфіку деталей шкіргалантерейних виробів та рядну систему розташування деталей в секціях. Запропоновано модифікацію генетичного алгоритму яка полягає в наступному:

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

2) Кожна «особина» - розкладка кодується двома «хромосомами» одна з яких визначає кількість рядів різних деталей, друга задає кількість деталей (однакових) в ряду;

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

4) В процедурі розмноження приймає участь та хромосома що відповідає за кількість рядів деталей і забезпечує перебірну частину алгоритму. Процедурою розмноження передбачено ділення не цілої хромосоми на дві частини, а кожного гену хромосоми навпіл, що забезпечує обмін приблизно половинами заповненої ширини матеріалу. Отримуємо комбінацію для одного «нащадка» від кожної пари «батьків»:

hr1_n,k=hr1_p1,k div 2 + hr1_p2,k div 2, k=1,2..p,

де hr1_n,k - елемент вектора-хромосоми HR1 «нащадка» n;

hr1_p1,k , hr1_p2,k - відповідні елементи хромосоми HR1 «предків» p1 і p2;

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

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

В підрозділі 3.3 наведено структуру програмного модуля, що реалізує розроблений генетичний алгоритм для генерації секцій, запропоновано структуру даних, перераховано його основні процедури та надано приклади кодування і схематичні зображення секцій. В таблиці 1 в спрощеному вигляді представлено схематичне зображення секцій і послідовності процедур при створенні нових особин (початкова популяція, рекомбінація предків, можливі мутації і остаточний вигляд нащадка).

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

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

при наступних обмеженнях:

,

Де

- корисна площа матеріалу в і-ій секції;

- допустиме відхилення кількості деталей від плану задачі;

;

- цілі.

Традиційно при побудові раціональних схем застосовувалась економіко-математична модель з булевими змінними. В даному разі запропоновано :

- розкрійну схему Sh_i розглядати як набір з n різних секцій, який можна представити послідовністю з нулів та одиниць. Наприклад при n=10 схема може мати вигляд Sh_i=(1,1,0,0,0,1,0,1,0,0) де 1 - означає що секція входить до розкрійної схеми, а 0 - що не входить;

- для кожної розкрійної схеми обраховуються сумарні кількості окремих деталей (критерій якості схеми) та її загальна довжина;

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

система проектування розкрійний шкіргалантерейний

Таблиця 1

В таблиці 2 наведено приклади отриманих окремих секцій з 5-ти деталей та варіанти розкрійних схем складених з цих секцій

Таблиця 2

Деякі секції комплекту з 5-ти деталей отримані на етапі генерування
№ секц. Хромосома 1 Хромосома 2 % викор Довжина секції (мм) Ширина (мм) Кількість деталей в секції 1-ї 2ї 3 4 5 1 5 0 0 0 10 3 0 0 0 18 92,59 216 1500 15 0 0 0 180 2 0 1 3 4 0 0 5 8 16 0 91,97 256 1490 0 5 24 64 0 3 4 0 0 7 0 3 0 0 13 0 91,29 216 1480 12 0 0 91 0 4 7 0 0 3 0 3 0 0 13 0 92,96 216 1480 21 0 0 39 0 5 0 1 2 6 0 0 5 8 16 0 92,39 256 1490 0 5 16 96 0 6 3 1 1 3 5 3 5 8 16 18 98,67 256 1480 15 5 8 48 90
Приклади кодування розкрійних схем з наданих секцій
Хромосома Shemi	Довжина розкл	Кількість деталей в розкладці
[1,0,0,1,1,0]	216+216+256 =688	15+21+0= 36	0+0+5= 5	0+0+16= 16	0+39+96= 135	180+0+0= 180
[0,1,0,0,1,0]	256+216= 472	0+21= 21	5+0= 5	24+0= 24	64+39= 103	0+0= 0
[0,0,1,1,1,1]	216+216+256 +256=944	12+21+0 +15=48	0+0+5 +5=10	0+0+16 +8=24	91+39+96 +48=274	0+0+0 +90=90

Процедури побудови початкової популяції, селекції, кросоверу, мутації і оновлення популяції мають наступні особливості:

1) При створенні початкової популяції відбувається генерування послідовностей з 0 та 1 заданої довжини n (принцип „дробовика”) та проводиться оцінка пристосованості кожної особини.

2) Селекція відбувається методом аутбридінгу що забезпечує більш швидку сходимість алгоритму. Цей метод полягає в тому, що «батьками» стають особини максимально віддалені за признаками, пристосованість яких (критерій якості) в одного більша за порогову величину пристосованості по популяції, а в іншого - менша.

3). Принцип роботи одноточкового кросоверу показано в табл.3.

Таблиця 3

1 схема	2 схема
[0, 1, 0, 0, 1, 0]	[0, 0, 1, 1, 1, 1]
Показники якості (кількості деталей)
21	5	24	103	0	48	10	24	274	90
Точка розриву, обрана випадковим чином = 4
[0, 1, 0, 0 1, 0]	[0, 0, 1, 1 1, 1]
вигляд схем після кросоверу (обміну частинами)
[0, 1, 0, 0, 1, 1]	[0, 0, 1, 1, 1, 0]
Показники якості (кількості деталей)
15	15	48	208	90	33	5	16	207	0

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

4) Мутація може відбуватися в 2-х напрямках: для збільшення пристосованості випадковий 0 інвертується в 1, а для зменшення - навпаки 1 замінюють на 0. Принцип роботи операторів мутації показано в табл.4

Таблиця 4

Схема перед мутацією
[0, 0, 1, 1, 1, 1]
Показники якості (з табл.4):
48	10	24	274	90
При мутації «на зменшення» третій елемент інвертуємо в 0 [0, 0, 0, 1, 1, 1]
Показники якості особини:
36	10	24	183	90
Або - схема перед мутацією
[0, 0, 0, 1, 1, 1]
Показники якості:
36	10	24	183	90
При мутації «на збільшення» перший елемент інвертуємо в 1 [1, 0, 0, 1, 1, 1]
Показники якості особини :
51	10	24	183	270

5) Нова популяція створюється додаванням новоотриманих «нащадків» до попередньої популяції та виключенням з неї особин в яких наявне перевищення показників якості (надлишок деталей). Таким чином розмір популяції (бажана кількість раціональних схем) залишається незмінним.

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

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

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

Алгоритми коригування розкрійних схем отриманих в автоматичному режимі що передбачають додавання або виключення окремих деталей викладено в підрозділі 3.6:

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

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

- в пункті 3.6.3 наведено алгоритм визначення взаємного розташування двох деталей (деталі перетинаються чи ні) в якому для прискорення його роботи задачу розбиваємо на етапи:

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

2) в разі позитивної відповіді на попереднє питання починаємо розглядати точки одного з контурів на умову попадання в прямокутник описаний навколо другого контуру;

3) в разі позитивного результату починаємо перевіряти належність точки до іншого контуру застосовуючи метод променя.

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

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

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

Апробація програмного забезпечення при побудові розкрійних схем конкретних шкіргалантерейних виробів на рулонних матеріалах проведена в підрозділі 4.3. Було проведено побудову розкрійних схем для різних моделей таких виробів як портфелі, сумки, чемодани, вироби мілкої шкіргалантереї (гаманці, портмоне, футляри), папки. Отримані результати показали що для різних категорій шкіргалантерейних виробів відсоток використання матеріалу в побудованих схемах був вищій за нормативний в середньому на 1,5-4%.

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

Результати дисертаційної роботи проходили апробацію в відділі мікропроцесорної техніки Iнституту кібернетики ім. В.М. Глушкова НАНУ (методика обрахунку), ЗАТ ВКФ «Леся» (програмна реалізація), ТОВ «Група компаній «Бумсервіс» (програмна реалізація) де на практиці підтвердили результати теоретичних і експериментальних дослідів. Очікуваний економічний ефект становить 59 тис.грн. на рік.

ВИСНОВКИ

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

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

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

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

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

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

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

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

7. Розроблений програмний продукт дозволяє оперативно вносити корективи при зміні зовнішніх умов (матеріалів, обладнання, конструкції) з наступним автоматичним перерахунком.

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

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

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

1. Чупринка В.І., Колиско О.З. Алгоритм підготовки інформації для побудови розкрійних схем рулонних матеріалів на деталі взуття та шкіргалантерейних виробів / // Вісник КНУТД. - 2005. - №3. - С.19-24.

2. Колиско О.З., Чупринка В.І. Інтерактивне коригування розкрійних схем, що побудовані в автоматичному режимі // Вісник Хмельницького національного університету. Технічні науки. - 2006. - №1. - С.76-79.

3. Чупринка В.І., Колиско О.З. Омельченко П.В. Інтерактивна побудова схем розкрою натуральних матеріалів на деталі взуття та шкіргалантерейних виробів . // Вісник КНУТД. - 2006. - №1. - С.78-82.

4. САПР обладнання легкої та текстильної промисловості / [Щербань В.Ю., Щербань Ю.Ю., Колиско О.З. та ін.] - К.: КТІЛП, 2007. - 275с.

5. Колиско О.З., Чупринка В.І. Алгоритм побудови розкрійних схем рулонних матеріалів на деталі виробів дрібної шкіргалантереї // Вісник КНУТД . - 2008. - №1. - С.226-230.

6. Колиско О.З. Модифікація генетичного алгоритму для генерації секцій розкрійних схем / О.З. Колиско // Вісник КНУТД. - 2009. - №1. - С.14-17.

7. Яхно В.М., Колиско О.З. Алгоритм визначення оптимальної технології обробки виробів деталі яких утворюють розмірний ланцюг / В.М. Яхно, О.З. Колиско // Вісник КНУТД. - 2009. - №1. - С.54-56.

8. Чупринка В.І., Колиско О.З. Алгоритм щільного розміщення секцій при побудові розкрійних схем // Інноваційні технології - майбутнє України : міжн. Наук. Конф. 3-9 жовтня 2005р. : тези доповідей. - К., 2005 - т.1. С. 89-90.

9. Чупринка В.І., Колиско О.З. Автоматизована підготовка інформації про зовнішні контури деталей шкіргалантерейних виробів // Наукові розробки молоді на сучасному етапі : V Всеукраїнська наук. конф. : тези доповідей. - К., 2006. - С.61.

10. Колиско О.З., Чупринка В.І. Алгоритм генерування розкрійних схем для деталей шкіргалантерейних виробів // Наукові розробки молоді на сучасному етапі : ІV Всеукраїнська ювілейна наукова конференція молодих вчених та студентів : тези доповідей. - К., 2005. - т.2. - С.60.

11. Колиско О.З., Чупринка В.І. Алгоритм генерування секцій для побудови розкрійних схем деталей дрібної шкіргалантереї // Наукові розробки молоді на сучасному етапі : VІ Всеукр. наукова конф. 17-18.06.2007 : тези допов. - К., 2007. - т.2. - С.45.

12. Чупринка В.І., Колиско О.З. Алгоритм розміщення секцій при побудові розкрійних схем // Наукові розробки молоді на сучасному етапі : VІІ Всеукр. наук. конфер. 15-16.06.2008. : тези допов. - К., 2008. - т.2. - С.60.

АНОТАЦІЯ

Колиско О.З. Оптимізація схем розкрою матеріалів на деталі шкіргалантерейних виробів. - Рукопис.

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

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

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

АННОТАЦИЯ

Колиско О.З. Оптимизация схем раскроя материалов на детали кожгалантерейных изделий. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.18.18 - технология обуви, кожевенных изделий и меха, Киевский национальный университет технологий и дизайна, Киев, 2009.

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

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

Annotation

Kolisko O.Z. Optimization of materials cutting schemes into the leather and haberdashary items details. - Manuscript.

Dissertation for technical sciences candidate scientific degree, speciality 05.18.18 - technology of footwear, leather and fur, Kyiv National University of Technologies and Design, Kyiv, 2009.

Dissertation deals with the problems of optimization of automized cutting schemes construction of details of leather and haberdashary items on roll materials with regard to the details sets.

It was found that the main direction of scheme cutting improvement is getting of the computerised multiple technological decisions and choosing the optimal one. The performed analysis of the existing methods and euristics, limitating the quantity of variants under work. The problem was subdivided, mathematical models were created, algorithms and software were developed, and the construction of cutting schemes was devided into two parts: generation of separate details laying-out-sections and final schemes construction.

For problem solving it was developed the modifications of genetic algorithm which, combining oversorting and gradient methods, allow to reduce the limitations as to the number of details variants in section, to spread the search of rational cutting schemes. The chosen structures of information presentation assume the automized introduction of information as to the contours and their preserving, automatic calculations of linear effects due to the close details combining in schemes, and other parameters of close laying automatic maintaining of layed limitations, the possibility of visualization of cutting schemes or transferring of calculated results to the automatic cutting.

Structured mathematical model permitted to develop the special software for the automized construction of rational cutting schemes and their review and interactive correction. The use of software will give the possibility to raise the productivity of an engineer-technologist's work and the level of material use, to reduce the time for new items mastering.

Key words: cutting scheme, technological preparation of cutting production, linear effects, genetic algorithm, row placement, visualization.

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

...