Завдання розкрою
Завдання розкрою- це NP-повне завдання оптимізації, по суті, що зводиться до задачі про ранець. Завдання є завданням цілісного лінійного програмування. Завдання виникає у багатьох галузях промисловості. Уявімо, що ви працюєте на целюлозно-паперовому підприємстві, і у вас є кілька рулонів паперу фіксованої ширини, але різним замовникам потрібні різні кількості рулонів різної ширини. Як розрізати папір, щоб мінімізувати відходи?
За даними Конфедерації європейських виробників паперу [en] [1] , у 2012 році 1331 папероробних машин у регіоні виробляють у середньому відходів на 56 млн євро (приблизно 73 млн доларів США) кожна. Економії навіть 1% буде дуже суттєвою.
Зміст
Таке формулювання завдання можна застосувати не тільки до одновимірного випадку. Можливо багато варіацій, наприклад, мета - не мінімізація втрат, а максимізація загальної кількості виробленого товару.
У цілому нині, кількість можливих карт зростає експоненційно відm, числа замовлень. При зростанні числа замовлень може виявитися непрактичним перераховувати можливі карти розкрою.
Вихідний метод Гілмору і Гоморі не був цілочисленним, так що рішення могло містити дробові складові, наприклад, деяка карта мала використовуватися 3,67 разів. Округлення до найближчого цілого часто не працює, в тому сенсі, що це призводить до підоптимального рішення та недовиробництва або надвиробництва для деяких замовлень (і можливе порушення обмежень, якщо вони двосторонні). Цей недолік подоланий у нових алгоритмах, які дозволяють знаходити оптимальні рішення (у сенсі знаходження рішення з мінімальними відходами) дуже великих завдань (загалом великих, ніж потрібно на практиці [4] [5] ).
Завдання розкроючасто є вкрай виродженою, оскільки можливе велике число рішень з тим самим кількістю втрат. Це виродження виникає через можливість переставляти частини, створюючи нові карти розкрою, але не змінюючи результуючі втрати. Це дає цілу колекцію супутніх завдань, що задовольняють тим самим обмеженням, таких як:
Папероробна машина може виробляти необмежену кількість рулонів (заготовок), кожна шириною 5600 мм. Потрібно отримати наступні 13 кінцевих рулонів:
| 1380 | 22 |
| 1520 | 25 |
| 1560 | 12 |
| 1710 | 14 |
| 1820 | 18 |
| 1880 | 18 |
| 1930 | 20 |
| 2000 | 10 |
| 2050 | 12 |
| 2100 | 14 |
| 2140 | 16 |
| 2150 | 18 |
| 2200 | 20 |
Є 338 можливих карт розкрою для цієї маленької задачі. Оптимальне рішення вимагає 73 вихідних рулонів і має 0,401% відходів. Можна показати, що мінімальна кількість карт розкрою для такої кількості відходів дорівнює 10. Можна також обчислити, що існує 19 таких різних рішень, кожне з 10 картами розкрою та 0,401% відходів. Одне з таких рішень показано нижче та на малюнку:
| 2 | 1820+1820+1820 |
| 3 | 1380+2150+1930 |
| 12 | 1380 + 2150 + 2050 |
| 7 | 1380 + 2100 + 2100 |
| 12 | 2200+1820+1560 |
| 8 | 2200+1520+1880 |
| 1 | 1520 + 1930 +2150 |
| 16 | 1520+1930+2140 |
| 10 | 1710+2000+1880 |
| 2 | 1710+1710+2150 |
| 73 |
Завдання розкрою можна класифікувати у різний спосіб [9] . Один шлях - розмірність розкрою: вище наведений приклад ілюструє одномірний розкрій (1D). Інші промислові застосування 1D розкрою — різання труб, кабелів та сталевих прутків. Двовимірні (2D) завдання застосовуються при виробництві меблів, одягу та скла. Існує не так багато тривимірних (3D) застосувань розкрою, проте близькі 3D завдання упаковки мають багато промислових додатків, зокрема, розподіл об'єктів у контейнери для водного транспорту (дивіться, наприклад, Контейнерні перевезення, близька до неї завдання упаковки куль вивчалася з 17- го століття (Гіпотеза Кеплера)).
Промислове застосування задачі розкрою для підприємств з масовим випуском продукції виникає, коли основний матеріал виробляється у великих рулонах, а потім ріжеться на дрібніші частини (див. зліттинг). Це відбувається, наприклад, у паперовому виробництві та при отриманні полімерних плівок, а також при виготовленні плоских металевих (залізних або бронзових) листів. Існує багато варіантів та додаткових обмежень, викликаних особливостями виробництва чи обмеженнями процесу, вимогами замовників та питаннями якості. Деякі приклади:
- Двостадійний процес, коли рулон проводиться на першій стадії, а потім надходить в обробку ще раз на іншій машині. Наприклад, весь офісний папір (наприклад, формат A4 у Європі, Letter у США) виробляється у такому процесі. Проблеми виникають через те, що машини для другого процесу вже машин першого. Ефективне використання обох стадійпроцесу важливо (як з погляду економії матеріалу, так і економії енергії) і те, що ефективно для першої стадії може виявитися неефективним для другої, і доводиться шукати компроміс. Металізована плівка [en] (використовується для пакування продуктів харчування) і папір (пакувальний картон для рідин [en] , наприклад, для пакування соків) — інші приклади таких процесів.
- Мотальні машини обмежують розрізання фізично або логічно: загальні обмеження виникають з того, що лише певна кількість ножів допустима, так що карта розкрою не повинна містити ножів більше за деяку величину. Оскільки мотальні машини не стандартизовані, виникає багато додаткових обмежень.
- Як додаткове обмеження можна привести, наприклад, обмеження на напрямок розрізання - різні краї листа можуть мати велику відмінність у товщині і деякі додатки дуже чутливі до цього.
- Як приклад впливу вимог якості можна навести випадок, коли основний рулон містить дефекти, які слід вирізати. Дорогі матеріали з високими вимогами до якості матеріалу, такі як фотопапір або тайвек, слід ретельно оптимізувати, щоб мінімізувати відходи.
- Багатомашинні завдання виникають, коли замовлення можна зробити більш ніж на одній машині і ці машини мають різну ширину. В основному доступність декількох вихідних рулонів з різною шириною зменшує кількість відходів. Насправді, проте, доводиться враховувати додатковий порядок розрізання.
- Є також завдання, коли результуючі рулони не обов'язково мають бути одного діаметра, а можуть бути в межах деякого інтервалу. Іноді це завдання називаютьзавданням1½ розмірності. Цей варіант з'являється, наприклад, при виробництві гофрокартону.
- У сталепрокатної промисловості відмінною особливістю і те, що вихідні рулони, переважно, різняться як у ширині, і по довжині. Таким чином, виникає схожість з багатомашинним варіантом, описаним вище. В цьому випадку відходи можуть виникати як за шириною, так і за довжиною.
Програмне забезпечення для вирішення завдань розкрою для паперової промисловості постачають ABB Group, Greycon, Honeywell та Tieto.
Алгоритм розкрою для сталепрокатної промисловості сформульований Робертом Гонгорра (Robert Gongorra) у 1998 році та S.O.N.S (Steel Optimization Nesting Software) розробив програмне забезпечення для покращення використання сталевого листа та зменшення відходів.
Завдання гільйотинного розкрою - це завдання різання листів скла на прямокутники певних розмірів, використовуючи тільки розрізи, що проходять по всій довжині (або ширині) листа.
Пов'язане завдання визначення (для одновимірного випадку) найкращого розміру вихідного рулону, який відповідає вимогам; відома як завдання асортименту [7] [10] .
Завдання розкрою вперше сформульовано Канторовичем в 1939 [11] . У 1951 році, ще до того, як комп'ютери стали широко доступними, Л. В. Канторович і В. А. Залгаллер запропонували [12] спосіб вирішення завдання економного використання матеріалу при розкрої за допомогою лінійного програмування. Запропонована техніка пізніше отримала назвуМетод генерації стовпців.