Problem krojenja 1D
Problem jednodimenzionalnog rezanja spada u skupinu problema rezanja i pakiranja (engl. Cutting and Packing Problems, skraćeno C&P problemi). Problem rezanja je problem kombinatoričke optimizacije koji uključuje rezanje raspoloživog materijala (engl. stock) u potrebne manje komade (zahtjeve za rezanjem, engl. item) s ciljem da se minimalizira broj korištenih komada raspoloživog materijala i količina otpada (materijala koji se više ne može koristiti). Za rješavanje se općenito koriste 2 pristupa: fokusiranje na objekte i fokusiranje na uzorke. Prvi pristup direktno pridružuje zahtjeve za rezanjem komadima raspoloživog materijala, dok drugi pristup prvo generira uzorke rezanja raspoloživog komada, a zatim kombinira dobivene uzorke da bi se ostvarili svi zahtjevi za rezanjem.
U sklopu projekta se rješavao problem rezanja koji se prema tipologiji C&P problema koju je H. Dyckhoff [1] postavio karakterizira sa 1/V/D/M :
1 - jednodimenzionalni problem
V - problem biranja izvornog materijala da se ostvare svi zahtjevi za rezanjem
D - raspoloživo je više veličina izvornog materijala
M - velika količina zahtjeva za rezanjem u puno različitih duljina
Problem se može matematički formulirati na idući način:
n - broj različitih duljina zahtjeva za rezanjem
m - broj iskorištenih komada raspoloživog materijala
wj - otpad nakon rezanja j-tog komada materijala
Lj - duljina j-tog komada raspoloživog materijala
xij - broj komada i-tog zahtjeva za rezanjem koji se režu od j-tog komada materijala
li - duljina i-tog zahtjeva za rezanjem
Ni - ukupan broj komada i-tog zahtjeva za rezanjem
Također je zadano da se preferiraju rješenja koje koriste raspoložive materijale kojih ima konačan broj (ostatci od prijašnjih rješavanja zadataka).
Zbog očekivanja više različitih duljina raspoloživog materijala, pristup fokusiranjem na uzorke nije prikladan za rješavanje problema zbog količine uzoraka koje bi se trebalo generirati. Zbog toga je za rješavanje problema odabran pristup fokusiranjem na objekte.
