МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

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

БУДІВНИЦТВА І АРХІТЕКТУРИ

СОБОЛЬ Олександр Миколайович

УДК 515.2+519.85

ОПТИМІЗАЦІЯ РОЗМІЩЕННЯ ВИКРОЙОК

З УРАХУВАННЯМ ГЕОМЕТРИЧНИХ ПАРАМЕТРІВ

РИСУНКА ТКАНИНИ

Спеціальність 05.01.01 –

Прикладна геометрія, інженерна графіка

А В Т О Р Е Ф Е Р А Т

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

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

Київ – 2001

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

Робота виконана в Академії пожежної безпеки України Міністерства внутрішніх справ України.

Науковий керівник: - доктор технічних наук,

старший науковий співробітник

Комяк Валентина Михайлівна,

професор кафедри фундаментальних дисциплін,

Академія пожежної безпеки України

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

Корчинський Володимир Михайлович,

професор кафедри автоматизації проектування,

Дніпропетровський національний університет;

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

Анпілогова Віра Онисимівна,

професор кафедри нарисної геометрії,

інженерної і машинної графіки,

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

будівництва і архітектури

Провідна установа: Таврійська державна агротехнічна академія,

кафедра прикладної математики

і обчислювальної техніки,

Міністерство аграрної

політики України (м. Мелітополь)

Захист відбудеться "28" березня 2001 р. о 1300 годині на засіданні спеціалізованої вченої ради Д .056.06 у Київському національному університеті будівництва і архітектури за адресою:

03037, Київ-37, Повітрофлотський проспект, 31, ауд. 466

З дисертацією можна ознайомитися в бібліотеці Київського національного університету будівництва і архітектури за адресою:

03037, Київ-37, Повітрофлотський проспект, 31

Автореферат розісланий "20" лютого 2001 р.

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

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

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

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

При створенні маловідхідних і безвідхідних технологій важлива роль приділяється задачі нерегулярного розміщення геометричних об'єктів, що є моделлю такої важливої практичної задачі, як оптимізаційне проектування карт розкрою промислових матеріалів. Основними труднощами при розв’язанні задачі нерегулярного розміщення геометричних об'єктів є формалізація обмежень геометричного характеру, а саме, умов взаємного неперетинання геометричних об'єктів (далі під термінами "геометричний об'єкт" чи "об'єкт" будемо розуміти викройку) і умови розміщення об'єктів у деякій області (під терміном "область" будемо розуміти тканину, що розкроюється). Великий внесок у розв’язання проблеми аналітичного опису умов взаємного неперетинання і розміщення геометричних об'єктів внесли такі вчені, як В.Л. Рвачов, Ю.Г. Стоян, М.І. Гіль, В.М. Комяк, С.В. Яковлєв, М.В. Новожилова. Суміжними питаннями стосовно геометричного і комп’ютерного моделювання займалися такі вчені, як В.Є. Михайленко, Л.М. Куценко, К.О. Сазонов, В.М. Корчинський, В.О. Анпілогова, В.М. Найдиш, А.В. Найдиш. Однак враховування тільки умов неперетинання і розміщення геометричних об'єктів не дозволяє охопити весь спектр задач, що виникають на практиці. Наприклад, якщо тканина, що розкроюється, має рисунок, то необхідно враховувати додаткову технологічну вимогу, а саме, вимогу збереження рисунка тканини або формування заданого рисунка при суміщенні деякої групи геометричних об'єктів. Першим кроком на шляху до розв’язання цієї проблеми є роботи В.М. Комяк, в яких намічені основні напрямки дослідження.

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційне дослідження виконане на кафедрі фундаментальних дисциплін Академії пожежної безпеки України в період з 1997 по 2000 роки відповідно до планів спільних досліджень з Інститутом проблем машинобудування (ІПМаш) НАНУ по НДР:

1.

2.

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

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

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

Методи дослідження: математичні методи геометричного проектування, математичне і геометричне моделювання явищ і процесів.

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

1)

2)

3)

4)

Наукова новизна отриманих результатів полягає в наступному: одержав подальший розвиток загальний підхід до розв’язання задач нерегулярного розміщення викройок з урахуванням геометричних параметрів рисунка тканини [1]; вперше досліджені і формалізовані додаткові технологічні вимоги, характерні для швейного і меблевого виробництва, що дозволило охопити більш широкий клас актуальних задач, що підлягають розв’язанню [2]; розроблено нову загальну математичну модель задачі оптимізаційного нерегулярного розміщення викройок з урахуванням геометричних параметрів рисунка тканин, що розкроюються. Це дозволило формалізувати задачі, що виникають на практиці, і одержувати їх точне рішення [2]; вперше отриманий аналітичний опис областей припустимих положень геометричних об'єктів, зв'язаних розглянутими в роботі технологічними вимогами, дана геометрична інтерпретація області припустимих рішень, що дозволило розробити ефективний метод і створити алгоритмічне і програмне забезпечення для розв’язання практичних задач [3, ]; вперше отримані теоретичні оцінки складності запропонованого методу, що дозволяють, в залежності від геометричної інформації про викройки і тканину, не розв’язуючи задачу, оцінити ступінь її складності.

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

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

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

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

Реалізація і впровадження. Практичне значення отриманих результатів підтверджується впровадженням моделей, методів і алгоритмів оптимізаційного розміщення викройок з урахуванням геометричних параметрів рисунка тканини в підготовчо-розкрійне виробництво українсько-американської меблевої фабрики СПЕКМІ"; у якості оптимізаційного ядра системи автоматизованого проектування карт розкрою промислових матеріалів, що розробляється науковою фірмою "ІНТЕАР ЛТД"; у навчальний процес НТУ "ХПІ".

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

Апробація роботи. Основні положення дисертаційної роботи доповідалися й обговорювалися на міжнародних науково-практичних конференціях "Сучасні проблеми геометричного моделювання" (м. Харків, 1998 р.; м. Мелітополь, 1999 р.; м. Донецьк, 2000 р.); VI міжнародній науково-практичній конференції "Інформаційні технології: наука, техніка, технологія, освіта, здоров'я" - MicroCAD'99 (м. Харків, 1999 р.); міжнародній конференції по математичному моделюванню МКММ'2000 (м. Херсон); науково-технічних семінарах Академії пожежної безпеки України (м. Харків, 1999 - 2000 р.р.); науковому семінарі відділу математичного моделювання і оптимального проектування Інституту проблем машинобудування НАН України під керівництвом д.т.н., чл.-кор. НАН України Ю.Г. Стояна (м. Харків, 2000 р.); науковому семінарі кафедри нарисної геометрії, інженерної і комп'ютерної графіки КНУБА під керівництвом д.т.н., проф. В.Є. Михайленка (м. Київ, 2000 р.).

Публікації. За темою дисертації опубліковано 8 робіт, з них: 5 статей у виданнях, рекомендованих ВАК України, 3 тези доповідей.

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

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

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

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

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

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

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

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

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

У роботі наведена формалізація додаткової технологічної вимоги для наступних випадків суміщення геометричних об’єктів:

1)

2)

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

(1)

тобто або , або ; .

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

(2)

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

Властивість . Аналітичний запис технологічної вимоги не залежить від просторової форми та метричних характеристик множини .

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

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

(3)

Тут ; ; ; , де - кількість об’єктів множини , що перетинають сторони суміщення об’єкта з об’єктами . Через те, що на параметри розміщення об’єкта впливає лише один об’єкт із множини , то індекс далі в моделі не розглядається.

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

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

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

У роботі вперше отримано аналітичний запис технологічної вимоги:

, (4)

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

Математична модель задачі записується в такому вигляді.

Визначити , (5)

де ,

область, що описується наступним чином:

. (6)

Тут ; , і - структури лінійних нерівностей, що описують умови взаємного неперетинання й умови розміщення об'єктів в області.

Досліджені особливості математичної моделі задачі (56). У залежності від геометричних параметрів рисунка тканини виділені 4 різновиди технологічної вимоги, що виконується у випадку суміщення як пари, так і групи геометричних об'єктів:

-

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

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

-

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

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

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

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

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

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

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

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

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

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

, (7)

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

, (8)

. (9)

Тут - максимальна кількість вершин геометричних об’єктів.

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

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

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

Отримані результати комп'ютерного моделювання практичних задач розкрою матеріалів у швейному і меблевому виробництві дозволяють зробити висновок про скорочення часу проектування карт розкрою за рахунок автоматизації процесу розміщення викройок на тканині, про збільшення, як правило, коефіцієнту використання матеріалу за рахунок розв’язання задачі оптимізації, оперативно враховувати зміни розміро-ростів різного асортименту викройок, геометричних параметрів рисунку та габаритних розмірів матеріалу, що підлягає розкрою. Практична значущість виконаної роботи підтверджується впровадженням моделей, методів і алгоритмів оптимізаційного розміщення викройок з урахуванням геометричних параметрів рисунка тканини в підготовчо-розкрійне виробництво українсько-американської меблевої фабрики СПЕКМІ"; у якості оптимізаційного ядра системи автоматизованого проектування карт розкрою промислових матеріалів, що розробляється науковою фірмою "ІНТЕАР ЛТД"; у навчальний процес НТУ "ХПІ".

ВИСНОВКИ

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

При цьому отримані наступні результати, що мають наукову і практичну цінність.

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

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

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

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

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

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

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

8. Практичне значення роботи підтверджується впровадженням розроблених методів і алгоритмів у підготовчо-розкрійному виробництві українсько-американської меблевої фабрики СПЕКМІ" (м. Київ). Розроблене програмне забезпечення використовується у якості блока одного з програмних комплексів, що розроблюється науковою фірмою "ІНТЕАР ЛТД" (м. Київ). Математична модель і метод розв’язання задачі оптимізаційного нерегулярного розміщення об'єктів з урахуванням геометричних параметрів рисунка матеріалу, що розкроюється, використовується у навчальному процесі Національного технічного університету "ХПІ" (м. Харків).

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

1.

2.

3.

4.

5.

6.

7.

8.

Соболь О.М. Оптимізація розміщення викройок з урахуванням геометричних параметрів рисунка тканини. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.01.01 – прикладна геометрія, інженерна графіка. – Київський національний університет будівництва і архітектури, Київ, Україна, 2001.

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

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

Соболь А.Н. Оптимизация размещения выкроек с учетом геометрических параметров рисунка ткани. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.01.01 – прикладная геометрия, инженерная графика. – Киевский национальный университет строительства и архитектуры, Киев, Украина, 2001.

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

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

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

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

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

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

SobolOptimization of pattern location and spacing with geometric parameters of the fabric texture taken into account. – Manuscript.

Thesis for the degree of candidate of technical sciences in field 05.01.01 – applied geometry, engineering graphics. – The Kyiv National University of Construction and Architecture, Kyiv, Ukraine, 2001.

The dissertation presents a solution for the problem of optimized pattern location and spacing with geometric parameters of the fabric texture taken into account. The solution is of great importance for the preparatory cutting manufacture of light industry. Technological requirements to the problem pertaining to garment ant furniture manufacture are analyzed, classified and formalized. A general mathematical model is constructed, its properties are analyzed. A geometric interpretation of the problem feasible solutions domain is obtained. A method to solve the problem is presented, its theoretical complexity estimates are obtained. Problem oriented models for the optimization problem of pattern location and spacing with geometric parameters of fabric texture taken into account. Practical problems of cutting out industrial materials pertaining to the garment and furniture manufacture and recommendations of their implementation are developed.

Key words: optimization of pattern location and spacing, geometric parameters of texture, technological requirement, mathematical model, preparatory cutting manufacture.