Optimization of wood cutting using dynamic programming

Abstract

Työssä käsiteltiin optimointiongelmia, joissa sahataan puusta sahattuja siivuja kahdessa ulottuvuudessa suorakulmaisiksi laudoiksi ottaen huomioon sahattavan puun muoto, muotovirheet eli kaarevuus sekä oksanreiät ja muut puutteet. Työssä tarkasteltiin kolmea erityyppistä ongelmaa, puun sahausta poikittain eli trimmausta, puun sahausta ensin pitkittäin ja sitten poikittain niin että sitä mahdollisesti myös kierretään aluksi, eli särmäysoptimointia, ja kolmantena useampaan kertaan vuorotellen pitkittäin ja poikittain sahausta niin, että kiertokulma pysyy muuttumattomana.

Ratkaisujen laskentaan kuluu useimmiten vain alle sekunti, ja ratkaisut ovat laadultaan myös melko hyviä. Tämä johtuu suurimmaksi osaksi siitä, että dynaamiseen ohjelmointiin perustuva knapsack-algoritmi löytää hyvin lähelle optimaalisia ratkaisuja polynomisessa ajassa. Myös yksittäisten lautojen pisteytykseen kehitetyt tehokkaat tietorakenteet parantavat ratkaisujen laatua suhteessa suoritusaikaan.

Knapsack-algoritmi soveltuu niin hyvin puiden sahaukseen juuri siksi, että koko puunpalan mitalle tehdyt sahaukset ovat myös luonteva tapa jakaa ongelma aliongelmiin dynaamista ohjelmointia varten. Koska koko ongelman ratkaisu voidaan tällä tavoin tehokkaasti taulukoida, metaheuristiikkoja kuten esim. geneettisiä algoritmeja ei edes kokeiltu.