Czym jest problem cięcia materiałów? Proste wyjaśnienie

Masz 20 arkuszy płyty Swiss Krono 2800×2070 mm i 85 elementów do wycięcia na zamówienie kuchenne. Jak ułożyć je tak, żeby zużyć jak najmniej materiału? Właśnie to opisuje problem cięcia materiałów — i każdy stolarz rozwiązuje go przy każdym zleceniu, często nawet o tym nie wiedząc.

Definicja problemu cięcia materiałów

Problem cięcia materiałów (ang. cutting stock problem, CSP) to zadanie optymalizacyjne: mając zestaw surowców o znanych wymiarach, należy wyciąć z nich wymagane elementy tak, aby łączny odpad był jak najmniejszy. Formalnie sformułował go Leonid Kantorowicz w 1939 roku, a rozwinęli Gilmore i Gomory w latach 60.

W praktyce warsztatowej problem wygląda tak: dostajesz zamówienie na 50 frontów, 30 boków i 20 półek z płyty meblowej. Każdy element ma inne wymiary, a płyta kosztuje 120–180 zł za arkusz. Każdy zmarnowany arkusz to realna strata.

Sama nazwa bierze się z papiernictwa, a nie ze stolarstwa. Pierwotnym zadaniem było cięcie szerokich wstęg papieru na węższe rolki zamawiane przez klientów: jeden surowiec o stałej szerokości, wiele różnych zamówień i pytanie, jakie zestawy cięć uruchamiać, żeby zmarnować jak najmniej wstęgi. Pomysł Gilmore’a i Gomory’ego polegał na tym, żeby nie wypisywać z góry wszystkich możliwych zestawów cięć, tylko dokładać kolejny dopiero wtedy, gdy rachunek pokazuje, że akurat ten się przyda. To ta sama idea, która dziś stoi za optymalizacją rozkroju płyty meblowej.

Warto też odróżnić problem cięcia od bin packingu, bo bywają mylone. Bin packing pyta, ile pojemników wystarczy na zbiór przedmiotów. Problem cięcia pyta, jak wyciąć elementy z materiału o danym wymiarze — i wnosi ze sobą szerokość rzazu, kierunek cięć oraz pytanie, czy maszyna jest w ogóle w stanie taki układ wykonać. To ostatnie ograniczenie nie występuje w wersji podręcznikowej, a w warsztacie decyduje najczęściej.

Dlaczego ręczne rozkładanie nie wystarczy

Przy 5 elementach na jednym arkuszu da się rozłożyć je na oko. Przy 50 elementach na 8 arkuszach liczba możliwych ułożeń przekracza miliony. Przy 200 elementach — jest ich więcej niż atomów we wszechświecie.

Ludzki mózg radzi sobie z rozpoznawaniem wzorców, ale nie z przeszukiwaniem miliardów kombinacji. Dlatego ręczne rozkładanie typowo daje 15–25% odpadu, podczas gdy algorytmy schodzą do 3–8%.

Różnica przy zleceniu na 30 arkuszy Kronospan po 150 zł? Ręcznie zużyjesz 30 arkuszy, algorytm — 26. To 600 zł oszczędności na jednym zamówieniu.

Formalnie problem należy do klasy NP-trudnych, co w praktyce znaczy jedną konkretną rzecz: nie jest znany sposób, żeby przy rosnącej liczbie różnych wymiarów sprawdzić wszystkie możliwości w rozsądnym czasie. Nie chodzi o to, że komputery są za wolne. Chodzi o to, że liczba wariantów rośnie szybciej, niż jakikolwiek wzrost mocy obliczeniowej jest w stanie nadążyć — dołożenie kilku formatek nie dokłada kilku układów, tylko je mnoży.

Człowiek przegrywa z tym w sposób, który warto rozpoznać u siebie. Układając ręcznie, poprawiamy to, co widać: przesuwamy formatkę, która wyraźnie źle leży, i zatrzymujemy się, gdy nic już nie kłuje w oczy. To jest szukanie lokalne. Kończy się w pierwszym układzie, w którym żaden pojedynczy ruch nie pomaga — a najlepszy układ zwykle wymaga przestawienia kilku formatek naraz i chwilowego pogorszenia sytuacji, zanim zrobi się lepiej. Ręka tego nie robi, bo nie ma powodu, żeby robić krok wstecz.

Wariant 1D — cięcie liniowe

W wariancie jednowymiarowym tniemy materiał wzdłuż jednej osi. Typowe zastosowania:

• Profile aluminiowe — ramy okienne, konstrukcje do zabudów
• Listwy przypodłogowe — standardowe długości 2,5 m lub 3 m
• Rury stalowe — instalacje hydrauliczne i gazowe
• Pręty zbrojeniowe — budownictwo

Tu liczy się tylko długość. Element 1200 mm trzeba wyciąć z pręta 6000 mm — i ułożyć obok inne elementy, żeby reszta była jak najkrótsza.

Handlowe długości są w tym wariancie ograniczeniem samym w sobie, bo materiał kupujesz w tym, co ma hurtownia, a nie w tym, co byłoby wygodne. Profil, listwa czy rura przychodzi w kilku standardowych długościach i to one wyznaczają, co da się wycisnąć z jednej sztuki. Dlatego przy cięciu liniowym tak dużo zależy od jednej decyzji: z której długości ciąć. Ten sam zestaw elementów z pręta 6000 mm i z pręta 3000 mm to dwa zupełnie różne zadania. Końcówka krótsza niż najkrótszy potrzebny element jest przy tym stracona niezależnie od tego, jak dobrze policzył algorytm — i to ona, a nie rzaz, zwykle stanowi większość odpadu w 1D.

Wariant 2D — cięcie arkuszowe

W wariancie dwuwymiarowym tniemy prostokątne elementy z płaskich arkuszy. To codzienność każdego meblarza i stolarza pracującego z płytami:

• Płyty meblowe — Swiss Krono, Pfleiderer, Kronospan (2800×2070 mm)
• Sklejka — 2500×1250 mm
• Szkło — formatki na wymiar
• Blacha — elementy do produkcji

Tutaj dochodzą dodatkowe ograniczenia: kierunek usłojenia (wzór dekoru musi pasować), szerokość rzazu piły (3–4 mm na każde cięcie) i typ cięcia (gilotynowe vs wolne).

Jak algorytmy rozwiązują ten problem

Nowoczesne optymalizatory stosują kilka podejść:

Algorytmy zachłanne (greedy) — szybkie, ale niedoskonałe. Układają największy element jako pierwszy, potem dopasowują mniejsze. Dają przyzwoite wyniki w ułamku sekundy.

Programowanie liniowe — metoda Gilmore’a-Gomory’ego. Traktuje problem jako układ równań i nierówności, szukając matematycznie optymalnego rozwiązania. Skuteczna przy dużych seriach.

Metaheurystyki — algorytmy genetyczne, symulowane wyżarzanie, przeszukiwanie tabu. Przeszukują przestrzeń rozwiązań sprytniej niż brute-force, ale nie gwarantują optimum. Dają bardzo dobre wyniki w rozsądnym czasie.

Hybrydowe — łączą powyższe metody. Np. start algorytmem zachłannym, potem poprawa metaheurystyką. Tak działa większość profesjonalnych narzędzi.

Podział, który ma w praktyce największe znaczenie, przebiega jednak gdzie indziej: między metodami dokładnymi a przybliżonymi. Metoda dokładna daje odpowiedź, o której da się udowodnić, że lepszej nie ma. Przy małym zleceniu jest to całkowicie wykonalne i wtedy naprawdę wiadomo, że rozkroju nie da się poprawić. Wraz ze wzrostem liczby różnych wymiarów czas potrzebny na taki dowód rośnie tak gwałtownie, że przestaje być praktyczny — dlatego narzędzia produkcyjne szybko szukają bardzo dobrego planu, zamiast powoli szukać idealnego.

Wiąże się z tym rzecz, która zaskakuje przy pierwszym kontakcie: dłuższe liczenie nie poprawia wyniku w nieskończoność. Większość zysku przychodzi wcześnie, w pierwszych ułamkach sekundy, a dalsze przeszukiwanie zwykle już tylko potwierdza, że posiadany plan trudno pobić. Szybka odpowiedź rzadko jest więc powodem, dla którego zlecenie marnuje materiał. Znacznie częściej powodem są dane wejściowe.

Na wynik wpływa jeszcze jedno rozstrzygnięcie, o którym podręczniki milczą: czy plan ma być wykonalny na pile panelowej. Cięcie gilotynowe wymaga, żeby każde cięcie przechodziło przez cały arkusz od krawędzi do krawędzi, co wyklucza część układów wyglądających lepiej na papierze. Algorytm liczący bez tego ograniczenia zaproponuje rozkrój ciaśniejszy i niewykonalny na maszynie, którą masz w warsztacie — i to jest najczęstszy powód, dla którego dwa narzędzia dają różne wyniki na tych samych danych.

Kluczowe parametry wpływające na wynik

Sam algorytm to połowa sukcesu. Równie ważne są dane wejściowe:

• Szerokość rzazu — każde cięcie zjada 3–4 mm materiału. Przy 30 cięciach na arkuszu to 90–120 mm straty
• Oklejanie krawędzi — jeśli element wymaga okleiny, trzeba doliczyć 0,5–2 mm na stronę
• Kierunek usłojenia — elementy z dekorem muszą mieć spójny wzór, co ogranicza możliwość obracania
• Wymiary arkusza — warto sprawdzić, czy producent oferuje inny format, który lepiej pasuje do zamówienia
• Resztki z magazynu — odpady z poprzednich zleceń mogą być surowcem dla nowych elementów

Tych pięć pozycji łączy jedno: żadna nie jest ustawieniem algorytmu, wszystkie opisują rzeczywistość warsztatu. Na tym polega różnica między zadaniem z podręcznika a zleceniem. W wersji podręcznikowej materiał jest jednorodny, cięcia nie mają grubości, a element wolno obrócić dowolnie. W warsztacie płyta ma dekor, piła ma tarczę o konkretnej grubości, część formatek trzeba okleić, a arkusz przychodzi w formacie, który wybrał producent, a nie Ty.

Praktyczna konsekwencja jest taka, że najwięcej daje poprawienie danych, a nie zmiana narzędzia. Rozczarowujący rozkrój prawie zawsze wynika z tego, że zlecenie policzono na innym formacie płyty niż kupowany, że usłojenie wymuszono również tam, gdzie materiał żadnego wzoru nie ma, albo że resztki z magazynu w ogóle nie weszły do rachunku, bo nikt nie zapisał ich wymiarów.

Ile można zaoszczędzić

Przejdźmy od teorii do złotówek. Typowy warsztat meblarski zużywa 50–100 arkuszy płyty miesięcznie.

Różnica między ręcznym a zoptymalizowanym cięciem: 600 zł miesięcznie, ponad 7 000 zł rocznie. Przy większej produkcji kwoty rosną proporcjonalnie.

Zastosowania poza stolarstwem

Problem cięcia materiałów pojawia się w wielu branżach:

• Hutnictwo — cięcie blach i profili
• Przemysł szklarski — formatki na zamówienie
• Przemysł tekstylny — krój tkanin
• Papiernictwo — cięcie rolek i arkuszy
• Budownictwo — profile, płyty gipsowe, izolacje

We wszystkich tych przypadkach zasada jest ta sama: zminimalizować odpad przy zadanym zestawie elementów.