Реферат за темою випускної роботи

Зміст

Вступ

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

Завдання такого роду об'єднані під терміном «завдання розкрою-упаковки» і відносяться до класу NP-важких (Nondeterministic polynomial), тобто переборного обчислювальна складність завдання не дозволяє знаходити точне рішення для достатньої кількості геометричних об'єктів за прийнятний час.

1. Актуальність теми

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

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

2. Мета і завдання дослідження, плановані результати

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

Основні завдання дослідження:

  1. Аналіз існуючого програмного забезпечення оптимального розкрою.
  2. Аналіз класів задач плоского розкрою і їх оцінка з точки зору обчислювальної складності.
  3. Розробка математичних моделей вирішуваних завдань.
  4. Розробка алгоритмів і методів рішення.
  5. Візуалізація вихідних даних і результатів.
  6. Оцінка ефективності розробленого ПЗ і використовуваних алгоритмів, дослідження працездатності.
  7. Документування, створення програмного комплексу і оцінка роботи.

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

Предмет дослідження: методи і алгоритми створення карт оптимального плоского розкрою.


В рамках магістерської роботи планується отримання актуальних наукових результатів за наступними напрямками:

  1. Створення карт розкрою.
  2. Дослідження існуючих алгоритмів розкрою.
  3. Розробка власних алгоритмів.
  4. Оцінка ефективності алгоритмів.

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

3. Огляд досліджень та розробок

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

  3.1 Огляд міжнародних джерел

Огляд робіт з проблеми упаковки / розміщення тривимірних геометричних об'єктів (ГО), яка користується попитом у багатьох областях людської діяльності (компоновка [1], упаковка вантажів, розкрій кристалів і т.д.), дозволяє зробити висновок, що складність вирішення даної задачі обумовлює відсутність ефективних алгоритмів її рішення. Більшість робіт зводиться до розміщення простих геометричних фігур (паралелепіпедів, циліндрів, сфер і т.д.). Тому пошук нових підходів і алгоритмів для вирішення задачі розміщення тривимірних ГО залишається актуальним [2, 3, 4, 5].

  3.2 Огляд національних джерел

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

У своїй статті Р. Т. Мурзакаев, В. С. Шилов та А. В. Буркова [7] проаналізували основні методи розв'язання задачі фігурної нерегулярної укладання плоских деталей.

  3.3 Огляд локальних джерел

У Донецькій національному технічному університеті розроблялися наукові статті, присвячені оптимізації алгоритмів розкрою. У статті Шатат Ахмед Фуад [8] наводиться приклад гільйотини розкрою рулонних матеріалів.

4. Реалізація алгоритму розкрою

  4.1 Загальна постановка проблеми

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

Також прямокутний розкрій може бути гільйотинний (мал. 1а) і не гільйотинний (мал. 1б). Під гільйотинних розуміється розкрій, реалізований послідовністю наскрізних різів, паралельних кромок матеріалу (мал. 1а) [9]. На мал. 1б представлений не гільйотинний розкрій. Розкрій, про який піде мова в даній статті буде прямокутним, гільйотинних і рулонних (розмір смуги: ширина = const, довжина = ∞ ).

pic1
Малюнок 1 - Прямокутний розкрій

  4.2 Постановка завдання

Поставлену задачу, яку необхідно вирішити в даній роботі можна сформулювати наступним чином: є вихідний матеріал D = {W, L} напівнескінченної прямокутної форми. Ширина має фіксований розмір W = const, а довжина є умовно нескінченної L ≈ ∞, а також вектори типорозмірностей прямокутних деталей d = {d1(w1, l1), d2(w2, l2), … , di(wi, li), … , dk-1(wk-1, lk-1), dk(wk, lk)} і їх кількість n = {n1, n2, … , ni, … ,nk-1, nk}. Необхідно оптимально розташувати деталі d на поверхні матеріалу D з дотриманням наступних умов:

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

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

  4.3 Можливі шляхи вирішення.

Завдання розкрою-упаковки належить до класу NP-важких завдань, тобто для її точного рішення не існує алгоритму поліноміальної складності. Більш того, дана задача є NP-важкою в сильному сенсі, так як містить NP-важке завдання як підзадачі. До сих пір не розроблено ефективних і досить точних способів розрахунку нижніх меж для даного завдання, що дозволяють визначити досягнення оптимуму. Таким чином, точні алгоритми зводяться до повного перебору варіантів. У зв'язку з цим, використання точних алгоритмів для вирішення задачі розкрою-упаковки часто виявляється недоцільним і неможливим через великі витрат часу. Тому велике значення приділяється розробці і дослідженню евристичних методів оптимізації [10].

Так, наприклад, маючи N деталей, ми отримуємо N! перестановок, а якщо деталі можуть бути орієнтовані двома способами, число перестановок буде дорівнює (2N) !, т. е. застосовується кожна з них з поворотом на 90 ° предметами. Однак, якщо все N деталей одного типорозміру, то результат укладання всіх перестановок, очевидно, будуть однаковим, тобто число дійсно різних перестановок одно 1. У загальному випадку кількість перестановок для знаходження точного рішення поставленого завдання без урахування повторюваних за рахунок однакової Типорозмірний деталей буде (n1 + n2 + … + nk)! / (n1! + n1! + … + n1! ), що є оцінкою поля для пошуку рішення.

На даний момент для вирішення задач дискретної оптимізації найбільш активно використовуються генетичні алгоритми. Також широкого поширення набули метаеврістікі «Пошук із заборонами», «Імітація відпалу» і «мурашиної колонії». Крім обраної методики і особливостей її реалізації конкретним автором, великий вплив на якість і швидкість отримання результату надає вибір процедури декодера. Під декодером зазвичай розуміється процедура, яка дозволяє на основі абстрактної інформації (наприклад, пріоритетний список предметів), однозначно визначити взаємне положення предметів і побудувати карту розкрою. Вибір декодера є важливим питанням при проектуванні нового методу.

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

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

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

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

Важливою складовою алгоритму є фізичне розміщення деталей на поверхні матеріалу. Тобто необхідно отримати однозначну інтерпретацію хромосоми як об'єкта можливого рішення не схильного до колізій тлумачення. Для такої мети можуть підійти деякі відомі евристики такі як «перша підходяща», «найкраща» кошика (мал. 2). «Перша відповідна» евристика розміщує i-ю деталь, представлену в хромосомі в найближчу j-го кошика, розміри якої не менше розміру деталі. «Краща» евристика шукає кошик з мінімальним залишком матеріалу після розміщення в ній деталі. Вибір евристики не є очевидним, так як при всій привабливості «кращої кошика» існують побоювання передчасної збіжності алгоритму в локальному екстремуму. З цієї причини не передбачається використання «жадібного» алгоритму.

pic1
Малюнок 2 - Використання евристик «перший відповідний кошик» і «найкращий кошик»

Висновки

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

Подальші дослідження спрямовані на наступні етапи:

  1. Проектування і реалізація програмного комплексу для візуалізації та обчислення ефективності розрахунків.
  2. Оцінка існуючих методів для реалізації алгоритму розкрою.
  3. Обґрунтування обраного критерію ефективності алгоритму.

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

Список джерел

  1. Stoyan Y., Gil N., Scheithauer G. Packing of convex polytopes into a parallelepiped // Preprint.-Dresden.- MATH-NM-06-2004.-2004 - 32C.
  2. Sykora A.M. Nesting problems: exact and heuristic algorithms. / A.M. Sykora// A Thesis for the degree of Doctor of Philosophy in the University of Valencia. 2010. Valence / – 187 c.
  3. Lamousin H., Waggenspack W. Nesting of two-dimensional irregular parts using a shape reasoning heuristic // Computer-Aided Design. 1997. Vol. 29, N. 3.
  4. Milenkovic V.J., Daniels K. Translational polygon containment and minimal enclosure using mathematical programming.-ITOR special issue with papers from IFORS'96, 1996, 30p.
  5. Dykhoff, H. A typology of cutting and packing problems / H. Dykhoff //Evropean Journal of Operational research. – 1990. – Vol. 44. – P. 145-159.
  6. Месягутов, М. А. Задача двухмерной ортогональной упаковки: поиск нижней границы на базе решения одномерной продолженной упаковки / М. А. Мясогутов // Информационные технологии. – М., 2010. – №6. – С. 13 – 23.
  7. Основные методы решения задачи фигурной нерегулярной укладки плоских деталей [Електронний ресурс] / Р. Т. Мурзакаев, В. С. Шилов, А. В. Буркова // Электронный научный журнал : Инженерный вестник Дона. – 2013. // [Электронный ресурс]. — Режим доступа: http://www.ivdon.ru/magazine/archive/n4y2013/2043
  8. Шатат Ахмед Фуад Задача рулонного раскроя / М. А. Мясогутов // Информационные технологии. – М., 2005. // [Электронный ресурс]. — Режим доступа: http://masters.donntu.ru/2005/kita/shatat/
  9. Мухачева A.C., Чиглинцев A.B. Генетический алгоритм поиска минимума в задачах двумерного гильотинного раскроя // Информационные технологии. 2001 №3. С. 27-32.
  10. Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации. // Информационные технологии. 1999. №1. С. 2-7.