Što je problem rezanja materijala? Jednostavni vodič

Ako ste ikada stajali pred hrpom ploča šperploče s listom dijelova i olovkom, crtajući pravokutnike na poleđini omotnice, već poznajete ovaj problem. Samo niste znali da ima formalno ime. Problem rezanja materijala nastaje kada velike sirove materijale trebate izrezati na manje potrebne komade uz što manje otpada. Riječ je o obliku pakiranja u spremnike — smještanja predmeta u spremnike uz minimalno preostalog prostora. Proizvođači, stolarske radionice i hobisti drvodjelci susreću se s njim svaki dan.

Problem koji svaki drvodjelac poznaje

Zamislite: gradite set kuhinjskih elemenata. Trebate 14 bočnih stranica, 7 polica, 7 leđa i 14 vratašca — ukupno 42 dijela, izrezanih iz standardnih ploča 2800×2070 mm. Svaki dio ima određene dimenzije. Kod nekih smjer vlakana mora ići po dužini, kod drugih nije bitno. Morate uračunati širinu reza (kerf) od 3 mm sa svoje stolne pile.

Sada izračunajte najmanji broj ploča koje morate kupiti da dobijete svih 42 dijela. Samo naprijed — pokušajte olovkom i papirom. Samo na raspored prve ploče potrošit ćete 20 minuta, brišući i ponovno crtajući. Do treće ploče izgubit ćete pregled nad time koje ste dijelove već rasporedili. I nakon svog tog truda, nemate načina saznati postoji li bolji raspored.

To je problem rezanja materijala sveden na svoju bit: uz zadani skup potrebnih komada i zalihu materijala standardne veličine, pronaći raspored koji koristi najmanje ploča uz najmanje otpada.

Matematika iza toga (pojednostavljeno)

Informatičari klasificiraju problem rezanja materijala kao „NP-težak“. U praksi to znači da broj mogućih rasporeda raste toliko brzo sa svakim dodatnim dijelom da nijedno računalo ne može u razumnom vremenu isprobati baš svaku opciju. Već samo poredak 40 dijelova daje 40 faktorijela nizova — broj s 48 znamenki — a to je prije nego što odlučite gdje na ploči svaki od njih pada ili koji će se od njih zarotirati. Kod 100 dijelova, otprilike jedne uklopljene kuhinje, poredaka je za više od sedamdeset redova veličine više nego atoma u vidljivom svemiru.

To je ista obitelj problema koju je prvi proučavao Kantorovič (1939.), a kasnije je riješena generiranjem stupaca zahvaljujući Gilmoreu i Gomoryju (1961.). Algoritmi ne isprobavaju svaku kombinaciju. Umjesto toga koriste heuristike — pametne prečace poput first-fit decreasing, generiranja stupaca ili genetskih algoritama — koje pronalaze gotovo optimalna rješenja u nekoliko sekundi. Neće uvijek pronaći apsolutno savršen raspored, ali dosljedno će nadmašiti svaki ljudski pokušaj s velikom razlikom.

Kompromis je jednostavan: malo vremena računanja u zamjenu za mjerljivo manje otpadnog materijala.

Odakle potječe problem rezanja materijala?

Formaliziran je unutar industrije, a ne na sveučilištu, od ljudi koji su pokušavali spriječiti da se skupi sirovi materijal pretvara u ostatke.

Kantorovič je napisao prvu verziju dok je savjetovao trust za šperploču o tome kako planirati proizvodnju uz najmanje otpada — rad kasnije nagrađen Nobelovom spomen-nagradom za ekonomiju. Praktična metoda rješavanja stigla je iz druge industrije dva desetljeća kasnije: tvornica papira proizvodi glavne role jedne fiksne širine i mora ih rezati na uže širine koje su naručili kupci. Svaka kombinacija širina koja stane po širini role jedan je uzorak rezanja, a popis mogućih uzoraka predug je da bi se zapisao. Odgovor Gilmorea i Gomoryja bio je da ga i ne zapisuju — generirati samo one uzorke koji rješenju zaista trebaju.

Taj rječnik i danas živi u vašoj radionici. Raspored na jednoj ploči je uzorak; plan rezanja je skup uzoraka plus koliko ploča izrezati po svakome. Kada optimizator izvijesti „tri ploče ovako, jedna onako”, pruža vam isti oblik odgovora koji je metoda iz 1961. davala tvornicama papira, primijenjen na šperploču.

Jedna dimenzija ili dvije — i zašto je to važno

Isti se problem pojavljuje u dva oblika, koji prestaju biti jednako teški onog trenutka kada ih pokušate izrezati.

U jednoj dimenziji bitna je samo dužina — šipke, cijevi, profili, dužine drveta, rola kant-trake. Postoji točno jedan način na koji dio može stajati na šipki, pa je cijela odluka koji rezovi dolaze s koje dužine materijala. To je izvorni oblik; problem uzdužnog rezanja u tvornici papira je 1D problem.

Dvije dimenzije daju dijelu širinu, visinu i često slobodu rotacije, pa jedna ploča ima golem broj rasporeda umjesto jednog poretka. Odatle dolazi gornja kombinatorna eksplozija.

Zatim stvarnost dodaje ograničenje koje udžbenička verzija nema: giljotinsko rezanje. Pila za ploče, a i stolna pila, mogu napraviti samo rezove koji idu od ruba do ruba preko one ploče koja je u tom trenutku na stolu. Ne možete izrezati usjek iz sredine ploče. Raspored koji se prekrasno slaže, ali treba rez koji staje na pola puta, nije plan — to je slika. Slobodno slaganje — dijelovi smješteni bilo gdje, u bilo kojoj orijentaciji — pripada CNC glodalici, koja svaki obris reže zasebno. To jedno ograničenje razlog je zašto raspored koji je optimalan na papiru može biti neizvediv u vašoj radionici. 1D vs 2D optimizacija rezanja objašnjava gdje se povlači granica.

Zašto ručni izračun uvijek troši više

Prođimo kroz konkretan primjer. Trebate 5 velikih ploča iz standardne europske ploče (2800×2070 mm):

• 2× bočne stranice: 2100×600 mm
• 2× police: 800×500 mm
• 1× leđna ploča: 2100×800 mm

Ručno, većina ljudi prvo postavlja najveće komade i uklapa manje u praznine. S tablicom možete pratiti iskorištenost površine, ali i dalje ne možete brzo isprobati rotacije ili alternativne rasporede. Algoritam optimizatora procijeni stotine varijacija rasporeda u manje od sekunde.

Ta razlika brzo postaje bitna. Uz 50–70 $ po ploči, ušteda i samo jedne ploče na kuhinjskom projektu odmah se isplati. Na proizvodnoj seriji od 50 elemenata, uštede se zbrajaju u tisuće dolara.

Primjeri iz stvarnog svijeta

Problem rezanja materijala pojavljuje se svugdje gdje se materijali režu iz standardnih veličina zaliha:

• Stolarija i proizvodnja namještaja — Melaminske, MDF i šperploča ploče izrezane na desetke veličina dijelova po projektu. Ograničenja smjera vlakana čine to težim.
• CNC slaganje — Automatizirani strojevi za rezanje trebaju datoteku s rasporedom. Optimizator ju generira izravno, uklanjajući ručno slaganje na upravljačkoj jedinici stroja.
• Obrada limova — Čelične i aluminijske ploče koštaju znatno više po kvadratnom metru, pa čak i smanjenje otpada od 3–5% znači ozbiljan novac.
• Rezanje stakla i pločica — Lomljivi materijali kod kojih se pogrešni rezovi ne mogu ponovno iskoristiti. Ispravan raspored iz prvog puta sprječava skupe pogreške.
• Linearno rezanje (1D) — Šipke, cijevi, profili i dužine drveta. Isti problem, jedna dimenzija manje. I dalje NP-težak uz dovoljno dijelova.

Kako softver za optimizaciju rezanja to rješava

Postupak je jednostavniji nego što biste očekivali. Unesete svoje potrebne dijelove — dimenzije, količine, smjer vlakana ako je primjenjivo. Odredite veličinu svoje ploče (ili više veličina ako ih vaš dobavljač nudi). Postavite širinu reza za svoj list pile, obično 3–4 mm. Zatim kliknete optimiziraj.

Iza kulisa softver pokreće niz algoritamskih prolaza. Isprobava različite položaje dijelova, rotacije (kada vlakna to dopuštaju) i rasporede ploča. Svaki raspored ocjenjuje po ukupnom postotku otpada i broju potrebnih ploča. U nekoliko sekundi vraća plan rezanja — vizualnu kartu točno gdje svaki dio ide na svakoj ploči.

Dobivate raspored za ispis, listu dijelova s položajima i jasne brojke o otpadu. Bez nagađanja, bez ponovnog crtanja, bez propuštenih dijelova.

Može li se riješiti savršeno?

Na malom poslu, da — i to se čak može dokazati. Na velikom, ne, a to je manje bitno nego što zvuči.

Dokaz proizlazi iz donje granice, koju optimizator može izračunati prije nego što išta rasporedi. Zbrojite površinu svakog dijela, podijelite s površinom jedne ploče, zaokružite naviše: to je najmanji broj ploča koji bi bilo koji plan mogao upotrijebiti, jer se materijal ne može stvoriti. Ako plan koji softver pronađe koristi točno toliko ploča, boljeg plana nema — ne „nije pronađen”, nego ne postoji. To je razlika između dobrog odgovora i dokazanog.

Kada plan završi iznad granice, razmak ima dva moguća objašnjenja i obično ne možete znati koje. Ili se bolji raspored tek treba pronaći, ili granica nikada nije bila dostižna za vaše veličine dijelova — zbroj površina nema pojma da tri dijela od 900 mm neće stati po širini ploče od 2070 mm ma kako ih okrenuli. Granica je pod, a ne obećanje.

Daje li duže traženje bolji plan? Do određene mjere. Veliki dobici stižu prvi, jer je očito bolje položaje najlakše pronaći; nakon toga traženje uglavnom potvrđuje da je ono što već ima teško nadmašiti. Sporo rješenje gotovo nikad nije razlog zašto je posao potrošio materijal. Razlog su ulazni podaci — pogrešna širina reza, dio koji nedostaje, veličina zalihe koju zapravo ne možete kupiti.