ДонНТУ   Портал магистров

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

Зміст

  Анотація

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

Введення

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

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

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

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

  •  ребра предметів паралельні ребрам смуги;
  •  предмети не перетинаються один з одним;
  •  предмети не перетинаються зі сторонами смуги;

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

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

  2. Постановка завдання

  Поставлену задачу, яку необхідно вирішити в даній роботі можна сформулювати наступним чином: є вихідний матеріал D = {W, L} напівнескінченної прямокутної форми, тобто ширина має фіксований розмір W = const, а довжина являєся умовно нескінченної L ≈ ∞, а також вектори типорозмірностей прямокутних деталей d = {d 1(w 1, l 1) , d 2(w 2, l 2), … , d i(w i, l i), … , d k-1(w k-1, l k-1), d k(w k, l k)} і їх кількість n = {n 1, n 2, … , n i, … ,n k-1, n k}. ННеобхідно оптимально розмістити деталі d на поверхні матеріалу D з дотриманням наступних умов:

  wi паралельно або перпендикулярно (якщо передбачається поворот деталі на 90°) W – умова прямокутності різів;[1]

  • d i∩ d j = {l;∅ }, де l – відрізок, - деталі не перетинаються один з одним;
  • d i∩ D = d i – деталі не виходять за межі вихідного матеріалу.

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

  1. Оптимальними будуть такі послідовності P i розміщення деталей, при яких L'(P i) > min, де L' – довжина використаного початкового матеріалу L.
  2. З відібраних за першим пріоритетом оптимальними будуть такі послідовності K i, при яких K(P i) > min, де K' – кількість необхідних різів.
 3. З відібраних за другим пріоритетом оптимальними будуть такі послідовності O i, при яких O(K i) > min, де O – площа отриманих відходів.

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

  • можливість збільшення типорозміру деталей в заданих межах для мінімізації кількості відходів і різів;
  • обмеження на кількість деталей в подкошику (одна або декілька);
  • можливість поворотів деталей 90° ;
  • учет величины кромки, как для деталей, так и для материала.

 3. Можливі методи рішення

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

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

  Точне рішення поставленої задачі можна отримати тільки методом повного перебору перестановок деталей на поверхні початкового матеріалу всіх можливих послідовностей роз-міщення. Цей метод має сенс застосувати при невеликій кількості деталей. Але коли мова йде про реальні масштаби виробництва, застосувати цей метод стає проблематичним, тому що для такого рішення необхідно обробити дані, розмір яких дорівнює факторіали від кіль-кості деталей, що є в принципі неможливим через обмеженість обчислювальних ресурсів ЕОМ . Так, наприклад, маючи N різних деталей, ми отримуємо N! перестановок, а якщо де-талі можуть бути орієнтовані двома способами, число перестановок буде дорівнює (2N)!, тобто застосовується кожна з них з поворотом на 90 ° предметами [8]. предметами. Однак, якщо все N деталей одного типорозміру, то результат укладки всіх перестановок, очевидно, будуть однаковим, тобто число дійсно різних перестановок дорівнює 1. У загальному випадку кількість перестановок для знаходження точного рішення поставленої задачі без урахування повторюваних за рахунок однакової типорозмірності деталей буде (n 1 + n 2 + … + n k )! / (n 1!+ n 1! + … + n 1! ), що є оцінкою поля для пошуку рішення [9]. Алгоритм генерації таких перестановок ґрунтується на формуванні черговий лексограмми такою, що менше її може бути тільки попередня.

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

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

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

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

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

pic1
Малюнок 2 – Використання евристик «перша підходяща корзина» і «краща кошик»
(анімація: 6 кадров, 7 циклов повторення, 19.4 килобайт)

 Для реалізації рішення, при якому допускається поворот деталі можна ген представити у вигляді пари {i, j}, де i - порядковий номер деталі, а j - аллель {0,1}, де 0 - без повороту, 1 - з поворотом. Однак при такому підході, по-перше, різко зростає генофонд, а по друге варіанти кроссинговера є не настільки очевидними.[1]. Крім того, якщо умовою буде поворот всіх деталей певного типу, то таке подання буде надлишковим.

 Другим варіантом подання хромосоми є послідовна зчіпка двох векторів: вектора порядків і вектора положень (далі будемо називати таку хромосому послідовної). Наприклад, 1-3-4-2-5 | 0-1-1-0-1 означає, що деталь № 1 укладається без повороту, наступна за нею деталь № 3 - з поворотом і т.д. При цьому кросинговер і мутація виконується окремо для кожного з векторів. Наприклад, для першого вектора кросинговер типу PMX (частково відображаєть-ся), а для другого вектора - вичайний бінарний однокрапковий або двокрапковий кросинго-вер. Варто, однак, зауважити, що якщо деталь № 1 та № 2 є одного типу, то хромосома 2-3-4-1-5 | 0-1-1-0-1 - суть одного й того ж розкрою.

Третім варіантом подання буде модифікація другого, де геном вектора порядків виступає порядковий номер типу деталі, а вектор положень повертає всі деталі даного типу [5]. Наприклад, задані деталі d = {d 1(w1, l1) , d2(w2, l2), d3(w3, l3)} і їх кількість n = {1, 2, 3} тоді хромосома 2-3-3-1 - 3-2 | 0-1-1 означає, що першою укладається деталь 2-го типу, другий - 3-го типу і т.д., причому деталі 2-го і 3-го типу розміщуються з поворотом. Не важко помітити, що вектор положення можна інтерпретувати як число з системою числення рівної кількості типів і розрядністю рівною кількістю деталей, а вектор n вказує скільки разів повинна використовуватися кожна цифра в цьому числі. Очевидно, що таким чином різко скорочується поле пошуку, крім того особини хромосоми яких виражені як число легко порівнюються і якщо в популяції присутня така ж розрахована особина, то немає необхідності проводити обчислення фітнес-функції повторно (а це найбільш значне навантаження на обчислювальні ресурси). Для даного подання хромосоми належить розробити відповідні оператори кросинговеру і мутації, що є новим в реалізації поставленого завдання.

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

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

  Новим так же в постановці завдання є використання ступінчастою фітнес-функції, яка розраховується наступним чином:

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

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

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

  Висновки

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

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

Cписок літератури

1. Мухачева A.C., Ширгазин P.P. Задачи упаковки прямоугольников: рандомизиро-ванная эвристика на базе двойственной схемы локального поиска оптимума // Информационные технологии. 2003. №5. С. 18-23.
2. Мухачева A.C., Чиглинцев A.B. Генетический алгоритм поиска минимума в задачах двумерного гильотинного раскроя // Информационные технологии. 2001 №3. С. 27-32.
3. Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации. // Информационные технологии. 1999. №1. С. 2-7.
4. Валиахметова Ю.И., Карамова Е.В. Расширение генетического алгоритма комбинирование эвристик для решения задачи прямоугольной упаковки // Вестник ВЄГУ № 2, 2009. С. 40. [Электронный ресурс] – http://www.work.vegu.ru/vegu...
5. Балабанов В.Н. Многокритериальная задача рационального ппланирования продольного раскроя рулонного материала //Проблемы информационных технологий. – 2009. – №2 С. 206. [Электронный ресурс] – http://www.nbuv.gov.ua/portal
6. Петров Ю. Ю. Регуляция вероятностей кроссинговера и мутации /Инфотелекоммуникационные технологии в науке, производстве и образовании // Первая международная научно-техническая конференция. Ставрополь: СевКавГТУ, 2004.
7. Применение распределённого генетического алгоритма при решении задачи об упаковке в контейнеры / Ю. А. Бюргер, В. Й. Гнатюк, В. И. Литвиненко, А. А. Ткачук // Перспективные информационные технологии и интеллектуальные системы, 2003.
8. Данилина И.И. Алгоритмы перебора. [Электронный ресурс] – http://inf.1september.ru/2000...
9. Мастяева И.Н., Семенихина О.Н. Методы оптимизации. [Электронный ресурс] – http://www.google.com.ua/...
10. Скурихин А.Н. Генетические алгоритмы // Новости искусственного интеллекта № 4. – Москва 1995. – С. 6–46.