Leikkausvarastongelma selitettynä yksinkertaisesti
Mitä leikkausvarastongelma on, miksi se on NP-vaikea, ja miten 1D- ja 2D-optimoijat (guillotine vs. vapaa sijoittelu) löytävät hyviä ratkaisuja nopeasti.
Mitä leikkausvarastongelma on?
Kun saatavilla ovat sahatavaran pituudet (tangot, lankut, levyt) ja lista tarvituista kappaleista, sahataan kaikki kappaleet mahdollisimman vähäisestä sahatavarasta. Kuulostaa triviaalilta; matemaattisesti se on NP-vaikea — yhdistelmien määrä räjähtää, kun kappalelista kasvaa.
1D, 2D ja guillotine-sahaukset
1D tarkoittaa yhtä ulottuvuutta: putket, profiilit, ratsut. 2D lisää leveyden — vaneri, lasi, ohutlevy. Guillotine-sahaukset kulkevat reunasta reunaan (levysahan tapa); vapaa sijoittelu sallii minkä tahansa kierron ja guillotine-asettelusta poikkeavat asettelut (laserin ja jyrsimen tapa).
Miksi tarkkoja ratkaisuja on harvoin
Vain pienet tapaukset voidaan ratkaista tarkasti (dynaamisella tai kokonaislukuehdoillisella optimoinnilla). Teollisuus nojaa heuristiikoihin — First Fit Decreasing, Best Fit Decreasing, hyllyalgoritmit — jotka yleensä osuvat muutaman prosentin päähän optimista millisekunneissa.
Sahausvara ja muut käytännön sudenkuopat
Jokainen sahaus kuluttaa materiaalia: 3 mm:n terän sahausvara lisää 3 mm per sahaus, ja 50 sausta syö huomaamatta 150 mm sahatavaraa. Tähteiden uudelleenkäyttö, syysuunta ja siistintähäviöt ovat yhtä tärkeitä kuin itse sijoittelu.
Kokeile omalla sahauslistallasi
Katkaisulaskuri (tangot) optimoi tanko- ja profiililistat; Levyjen katkaisulaskuri hoitaa guillotine-levysijoittelut kiertoineen ja sahausvaroineen. Liitä listasi ja vertaa sahatavaran kokonaismäärää ennen ja jälkeen.