5 ECONOMIC AND BUSINESS REVIEW | LETN. 16 | POS. ŠT. | 2014 | 5–25 OPTIMIZACIJA ENODIMENZIONALNEGA RAZREZA Z UPORABNIM OSTANKOM PRI ZAPOREDNIH NAROČILIH LUKA TOMAT 1 , MIRKO GRADIŠAR 2 POVZETEK: V članku je predstavljena metoda za reševanje enodimenzionalnega proble- ma razreza z uporabnimi ostanki (1DPRUO), kjer se lahko ostanki trenutnega naročila uporabijo v prihodnosti, če so daljši ali enaki meji t. Krajši ostanki predstavljajo izgubo. Metoda obravnava problem določanja t. Pri nižjem t se na zalogi proizvede večje število uporabnih ostankov (UO), izguba materiala pri prihodnjih naročilih pa se posledično po- veča. Predlagana metoda TOP-ECOLA je sestavljena iz dveh algoritmov; TOP in ECOLA. TOP izračuna optimalen t in optimalno število UO na zalogi. ECOLA minimizira izgubo materiala in ohranja optimalno raven UO. Metoda je preizkušena z uporabo računalni- ških simulacij, kjer so UO prejšnjih naročil uporabljeni v naslednjem naročilu, namesto da bi bili ustvarjeni naključno. Dobljeni rezultati kažejo, da TOP-ECOLA zmanjšuje izgubo materiala pri zaporednih naročilih in preprečuje nenadzorovano rast UO na zalogi. Ključne besede: razrez, hevristične metode, simulacije, optimizacija, uporabni ostanek, minimiziranje izgube materiala JEL klasifikacija: C61 UVOD Enodimenzionalni problem razreza materiala (1DPR) se pojavlja v mnogih panogah, naj- pogosteje pa v kovinski (Cui, Gu, & Hu, 2009), papirni (Chauhan, Martel, & D‘amour, 2008), tekstilni (Gradišar, Jesenko, & Resinovič, 1997), lesni (Venkateswarlu, 2001) in jek- larski (Leăo et al., 2011) panoga. V vseh panogah je 1DPR v splošnem definiran kot razrez daljših palic v krajše, ki so podane v naročilu. Za izpolnitev naročila obstaja več možnosti, imenovanih načrti razreza, ki se med seboj razlikujejo po količini neuporabnega ostanka. Glavni cilj pri reševanju 1DPR je zmanjšanje izgube materiala (Gilmore in Gomory, 1961; Gradišar et al., 1999). Pogosto je potrebno upoštevati tudi druge cilje, ki se zaradi kombinacije tehnoloških, pro- izvodnih in poslovnih značilnosti od primera do primera razlikujejo (Trkman in Gradi- šar., 2007; Wäscher, Haußner, & Schumann, 2007; Arbib, Marinelli, & Pezzella, 2012; Cui 1 Univerza v Ljubljani, Ekonomska fakulteta, Slovenija, Ljubljana, e-pošta: luka.tomat@ef.uni-lj.si 2 Univerza v Ljubljani, Ekonomska fakulteta, Slovenija, Ljubljana, e-pošta: miro.gradisar@ef.uni-lj.si ECONOMIC AND BUSINESS REVIEW | LETN. 16 | POS. ŠT. | 2014 6 in Huang, 2011; Erjavec, Gradišar, & Trkman, 2012). Eden izmed njih je, da morajo biti palice narezane na natančno zahtevano število kosov. Posledično lahko po koncu procesa razreza ostane veliko število ostankov. Če so ostanki daljši ali enaki, kot neka meja, se v takšnem primeru običajno vrnejo na zalogo. Ker se lahko uporabijo kasneje, se imenuje- jo OU. Ostanki, krajši od te meje, predstavljajo izgubo materiala. Takšne vrste problem razreza materiala se imenuje 1DPRUO (Cherri, Areales, & Yanasse, 2009), kjer zaloga običajno sestoji iz palic standardnih in nestandardnih dolžin, ki so UO prejšnjih naročil. Podroben pregled literature s področja 1DPRUO je mogoče najti v Cui in Y ang (2010). Pri reševanju 1DPRUO se pojavi vprašanje, kako oblikovati kriterijsko funkcijo, saj mi- nimiziranje izgube materiala ne zadostuje. V takšnem primeru bi bile palice narezane do meje, ki predstavlja izgubo materiala in vrnjene na zalogo. Izgube materiala tako ne bi bilo, vendar bi zaloga neskončno dolgo naraščala. Visoka raven UO na zalogi zaradi viso- kih stroškov logistike in skladiščenja v splošnem ni sprejemljiva. Tako je prvo vprašanje povezano z oblikovanjem kriterijske funkcije z namenom preprečitve prekomerne proi- zvodnje UO. Ker pa uporaba UO namesto palic standardne dolžine v splošnem proizvede večjo izgubo materiala, je drugo vprašanje, kako doseči, da se bodo UO pri prihodnjih naročilih porabljali z enakim tempom, kot se ustvarjajo. Cui in Yang (2010) navajata, da v literaturi obstajajo tri primerljive metode za reševanje 1DPR z različnimi možnostmi nadzorovanja količine UO. Metoda COLA (kasnejši izbolj- šani verziji sta CUT in C-CUT) (Gradišar, Jesenko, Resinovič, 1997; Gradišar in Trkman, 2005) minimizira skupno število ostankov, vgrajena pa je tudi dodatna omejitev, ki pre- preči, da bi bil več kot en UO daljši od najdaljšega kosa na naročilu. Metoda RGR L (ver- zije 1, 2 in 3) (Cherri, Areales, & Yanasse, 2009) minimizira skupno dolžino UO, metoda RSHP (Cui in Yang, 2010) pa minimizira skupne stroške načrta razreza. Vendar pa pri nobeni od teh metod UO niso vključeni v kriterijsko funkcijo, zato nobena ni uspešna pri nadzorovanju količine proizvedenih in porabljenih UO. Podobno ugotovitev je mogoče najti v Cui in Y ang (2010) kot predlog za prihodnje raziskave. Naslednje odprto vprašanje je, kako testirati in primerjati različne metode za reševanje 1DPR. Primerjava metod bi lahko temeljila na uporabi enakih kriterijev in enakih pri- merov. Kljub številnim kriterijem in primerom pa metode testiranja v literaturi ne zago- tavljajo točnih in popolnih informacij o učinkovitosti različnih metod. Glavna težava je v tem, da so primeri problemov ustvarjeni neodvisno en od drugega in da vsebujejo tako podatke o naročilu kot o zalogi, to pa ni v skladu z osnovno značilnostjo 1DPRUO, da se UO iz prejšnjih naročil uporabijo za izpolnjevanje prihodnjih. Obstoječe metode testi- ranja upoštevajo število porabljenih in proizvedenih UO, vendar pa uporabljeni UO ne izhajajo iz prejšnjih naročil – tako je najpomembnejši kriterij, to je razlika med porablje- nimi in proizvedenimi UO, spregledan. V kolikor vsako naročilo vsebuje le en proizveden UO več, kot je porabljenih, je po 100 izpolnjenih naročilih na zalogi že 100 palic več, kar z gotovostjo vpliva na ustvarjanje novih UO. Namesto, da bi se osredotočale na to razliko in porabljale UO iz prejšnjih naročil, pa obstoječe metode temeljijo na uporabi primerov, kjer je na zalogi vedno enako število UO, ki so ustvarjeni z generatorjem naključnih števil. Namen tega članka je: L. TOMAT, M. GRADIŠAR | OPTIMIZACIJA ENODIMENZIONALNEGA RAZREZA Z UPORABNIM... 7 (1) Preoblikovati 1DPRUO; (2) Predlagati takšno metodo za reševanje 1DPRUO, ki bo omogočala boljše nadzorova- nje UO; (3) Predlagati bolj natančno metodo za testiranje algoritmov za reševanje 1DPRUO. Pričujoči članek ima pet poglavij. V poglavju 2 je podana definicija problema, v poglavju 3 razvoj rešitve problema, poglavje 4 pa zajema testiranje metode. V 5. poglavju so podane ključne ugotovitve in možnosti nadaljnjega raziskovanja. 1 DEFINICIJA PROBLEMA Za izpolnjevanje vsakega naročila je na zalogi na voljo določeno število palic, ki so lahko standardnih ali pa nestandardnih dolžin. Palice nestandardnih dolžin so običajno UO iz prejšnjih naročil. Na zalogi je vedno zadostno število palic standardne zaloge za izpolnitev naročila. Pri izpolnjevanju naročila je potrebno, da se število kosov, določenih na naročilu, iz palic na zalogi razreže tako, da sta izguba materiala in dolžina UO minimizirana. Ker je izpolnjevanje prihodnjih naročil odvisno od UO iz prejšnjih naročil pa minimizacija ne mora biti omejena le na eno naročilo, temveč mora biti razširjena na zaporedje naročil. Na začetku so na zalogi le palice standardnih dolžin. Vse dolžine so izražene s celimi števili. Uporabljena je naslednja notacija: r = število naročil v zaporedju. l si = dolžine naročil v s-tem naročilu; i = 1, ... , n s . p si = zahtevano število palic lsi. L sj = dolžine palic v s-tem naročilu; j = 1, ... , m. δ sj = ostanek od L sj . x sij = število palic l si odrezanih od L sj . t = meja za izgubo materiala. Ostanki, ki so višji ali enaki meji t se smatrajo kot UO. Ostanki, ki so manjši od meje t, predstavljajo izgubo. f = faktor, za katerega je strošek izgube materiala večji od stroška razlike med proizve- denimi in porabljenimi UO. Kriterijska funkcija za obravnavani 1DPRUO je definirana na naslednji način: r m min ∑ ∑ (f · δ sj · (w sj + z sj ) + δ sj · u sj − L sj · z sj − (L sj – δ sj ) · v sj ) (1) s=1 j=1 (minimiziranje izgube materiala in razlike med proizvedenimi in porabljenimi UO v r zaporednih naročilih) z oziroma na: Ls j = ds − 1 j če us − 1 j = 1 ∨ vs − 1 j = 1, ∀ j; sicer Ls j = L1 j (2) (omejitve zaloge: standardne dolžine palic in UO, porabljeni v prejšnjem naročilu so bodi- si vrnjeni na zalogo kot novi UO, bodisi so nadomeščeni s standardnimi palicami enakih dolžin. Kapaciteta skladišča je omejena na m palic) ECONOMIC AND BUSINESS REVIEW | LETN. 16 | POS. ŠT. | 2014 8 n s ds j = Ls j − ∑ ls i × xs ij ∀ j (3) i=1 (omejitev nahrbtnika) m ∑ xs ij = ps i ∀ i (4) j=1 (omejitev naročila) t ≥ l min (5) (omejitev ponovne uporabe) xs ij ≥ 0, celo število ∀ i, j ds j ≥ 0 ∀ j. Za predstavljeni model so uporabljene naslednje funkcije: us j = 1 if ds j < Ls j ∧ ds j ≥ t ∧ Ls j = L1 j , ∀ j; sicer us j = 0 (za označevanje UO, proizvedenih iz palic standardnih dolžin) vs j = 1 if ds j < Ls j ∧ ds j ≥ t ∧ Ls j < L1 j , ∀ j; sicer vs j = 0 (za označevanje novih UO, proizvedenih iz prejšnjih UO) ws j = 1 if ds j < Ls j ∧ ds j < t ∧ Ls j = L1 j , ∀ j; sicer ws j = 0 (za označevanje izgube materiala, pridobljene iz palic standardnih dolžin) zs j = 1 if ds j < Ls j ∧ ds j < t ∧ Ls j < L1 j , ∀ j; sicer zs j = 0 (za označevanje izgube materiala, pridobljene iz UO) Zgornja formulacija minimizira izgubo materiala in razliko med proizvedenimi in porab- ljenimi UO v r zaporednih naročilih in tako predstavlja dvo-kriterijski problem. Več-kri- terijske probleme 1DPRUO je mogoče rešiti z uporabo koncepta Paretove optimalnosti (Golfeto, Moretti, & Salles Neto, 2009) ali z uporabo strategije tehtane vsote (bolj pogosto) (Diegel et al., 1996). Izbrali smo uporabo modela tehtane vsote, kjer f predstavlja utež izgube in 1 razliko med proizvedenimi in porabljenimi UO. Predlagana definicija proble- ma preprečuje porast števila UO na račun naraščajočih skladiščnih stroškov. Na začetku zaporedja (s = 1) zaloge ne vsebuje UO iz prejšnjih naročil. Sčasoma število UO na zalogi narašča, dokler število in raznolikost UO ne omogočata, da se porabi enako število UO, kot se jih proizvede. r mora biti zadostno velik, da takšno situacijo omogoča. L. TOMAT, M. GRADIŠAR | OPTIMIZACIJA ENODIMENZIONALNEGA RAZREZA Z UPORABNIM... 9 2 RAZVOJ REŠITVE Način, na katerega je problem opredeljen, ne omogoča implementacije v nobenem mate- matičnem modelirnem programskem okolju, kot je npr. LINDO, GAMS ali CPLEX. Zato je potreben razvoj procedure, ki temelji na hevrističnem pristopu. Da bi bil dobljeni rezultat čim bližje minimumu kriterijske funkcije v r zaporednih naro- čilih, je potrebno obravnavati dve ključni vprašanji: 1. Kako razviti učinkovito metodo, ki bi za optimiranje posameznega naročila zagota- vljala minimalno izgubo materiala in razliko med proizvedenimi in porabljenimi UO? 2. Kako optimirati količino UO na zalogi? Količina UO na zalogi je kot posledica opti- mizacijske metode določenega naročila deloma odvisna od razlike med proizvedenimi in porabljenimi UO, večinoma pa od meje t. Če je t prenizek, potem je količina UO velika. V izjemnih okoliščinah (skladno z omejitvijo (2)) lahko UO predstavljajo velik del zaloge. To se odraža v nizkem razmerju med povprečno dolžino palic na zalogi in povprečno dolžino kosov na naročilu (o) in v višji izgubi materiala, ki je posledica nižjega števila možnih rešitev. Če je t previsok se poveča izguba materiala, saj preveč ostankov, ki bi lahko bili porabljeni v kasnejših naročilih, postane izguba. V obeh pri- merih se vrednost kriterijske funkcije poveča (slika 1). Tako se pojavlja podvprašanje, kako poiskati takšno mejo t m , da bo vrednost kriterijske funkcije minimalna. 3. Kot odgovor na prvo vprašanje predlagamo algoritem za optimiranje s-tega (s = 1, ... , r) posameznega naročila, ki sestoji iz dveh korakov. V prvem koraku se minimizirajo vsi ostanki, v drugem pa se na račun nižje izgube materiala povečajo UO. Slika 1: Kriterijska funkcija v odvisnosti od t t t m 6 količina UO velika. V izjemnih okoliščinah (skladno z omejitvijo (2)) lahko UO predstavljajo velik del zaloge. To se odraža v nizkem razmerju med povprečno dolžino palic na zalogi in povprečno dolžino kosov na naročilu (o) in v višji izgubi materiala, ki je posledica nižjega števila možnih rešitev. Če je t previsok se poveča izguba materiala, saj preveč ostankov, ki bi lahko bili porabljeni v kasnejših naročilih, postane izguba. V obeh primerih se vrednost kriterijske funkcije poveča (slika 1). Tako se pojavlja podvprašanje, kako poiskati takšno mejo t m, da bo vrednost kriterijske funkcije minimalna. 3. Slika 1: Kriterijska funkcija v odvisnosti od t Kot odgovor na prvo vprašanje predlagamo algoritem za optimiranje s-tega (s = 1, ... , r) posameznega naročila, ki sestoji iz dveh korakov. V prvem koraku se minimizirajo vsi ostanki, v drugem pa se na račun nižje izgube materiala povečajo UO. Za minimizacijo ostankov v prvem koraku se lahko uporabi katerakoli obstoječa metoda za reševanje 1DPRUO. Izbrana je bila metoda COLA (Gradišar, Jesenko, & Resinovič, 1997), saj v primerjavi z ostalimi metodami porabi največje število UO iz prejšnjih naročil (Cherri, Areales, & Yanasse, 2009; Cui in Yang, 2010). Uporabljena je bila zadnja različica računalniške aplikacije COLA, ki je sposobna obdelati do 900 naročenih dolžin z do 900 različnih kosov. Reševalec CPLEX je bil dodan za pridobitev eksaktne rešitve pri majhnih naročilih, aplikacija LCUT pa za primere nizkega o (Gradišar, Erjavec, & Tomat, 2011). t Kriterijska funkcija t m ECONOMIC AND BUSINESS REVIEW | LETN. 16 | POS. ŠT. | 2014 10 Za minimizacijo ostankov v prvem koraku se lahko uporabi katerakoli obstoječa metoda za reševanje 1DPRUO. Izbrana je bila metoda COLA (Gradišar, Jesenko, & Resinovič, 1997), saj v primerjavi z ostalimi metodami porabi največje število UO iz prejšnjih naročil (Cherri, Areales, & Y anasse, 2009; Cui in Y ang, 2010). Uporabljena je bila zadnja različica računalniške aplikacije COLA, ki je sposobna obdelati do 900 naročenih dolžin z do 900 različnih kosov. Reševalec CPLEX je bil dodan za pridobitev eksaktne rešitve pri majhnih naročilih, aplikacija LCUT pa za primere nizkega o (Gradišar, Erjavec, & Tomat, 2011). V drugem koraku se število UO na račun izgube materiala povečuje toliko časa, dok- ler se zmanjšuje vrednost kriterijske funkcije za posamezno naročilo. Izguba materiala je zmanjšana na način, da se ne porabi večjega števila palic. Postopek je odvisen od raz- položljivosti daljših palic, ki nadomestijo krajše, ki proizvajajo visoko izgubo materiala. Visoka izguba materiala je tako preoblikovana v UO. V nadaljevanju je prikazan drugi korak algoritma v psevdo kodi. razvrsti ws j × δs j v nenaraščajočem redu do W (W 1 ≥ W 2 ≥ … ≥ W m ) in naredi L q (L q1 , L q2 , … , L qm ) pripadajočih dolžin palic Ls j razvrsti (1 − us j ) × (1 − ws j ) × Ls j v naraščajočem redu do L n (L n1 ≤ L n2 ≤ … ≤ L nm ) h ← 1 (števec izgube materiala) k ← 1 (števec neuporabljenih palic) dokler h ≤ m dokler k ≤ m če (L nk – L qh ) > (t –W h ) ∧ (W h + L nk – L qh ) < f × W h potem W h ← W h + L nk – L qh (W h je večji od t in postane UO) a ← L qh ; L qh ← L nk ; L nk ← a (nadomesti palice iz L n in L q ) končaj če k ← k + 1 končaj dokler h ← h + 1 k ← 1 končaj dokler Drugi korak zajema razširitev algoritma COLA, zato se predlagani algoritem imenuje ECOLA (razširjena COLA). Predlagani algoritem se lahko uporablja tudi v kombinaciji z drugimi metodami za reševanje 1DPRUO. Odgovor na drugo vprašanje – kako optimirati količino UO na zalogi – je podan s predlo- gom hevrističnega algoritma za določanje meje t opt in ustrezno število UO na zalogi UO pt , kjer je vrednost kriterijske funkcije minimalna ali blizu minimumu. Algoritem se imenuje TOP (T OPtimalen) in vsebuje ECOLO. Podan je prikaz v psevdo kodi. h 0 ← maxint (maxint je največja vrednost celega števila) (h 0 je začetna vrednost kriterijske funkcije) h 1 ← 0 (h 1 je začetna vrednost kriterijske funkcije prvega poskusa) nastavi e (e je začetna vrednost meje t in mora biti manjša od t m , vendar ne manjša kot l min ) t ← e L. TOMAT, M. GRADIŠAR | OPTIMIZACIJA ENODIMENZIONALNEGA RAZREZA Z UPORABNIM... 11 nastavi r (r predstavlja število naročil v poizkusu. r mora biti dovolj velik, da bo dosežena točka, kjer je v posameznem primeru število proizvedenih UO enako številu porabljenih) g ← 0 (števec poizkusov) dokler h g − 1 > h g (Poizkusi se ponavljajo, medtem ko vrednost kriterijske funkcije pada. Ko prične naraščati, je bil pri h g − 1 z mejo t opt dosežen njen splošni približni minimum) g ← g + 1 izprazni zalogo nestandardnih palic (UO) nastavi zalogo standardnih palic ponovi r-krat ustvari novo naročilo zaženi ECOLO in shrani rezultate ustvari novo pošiljko standardnih palic in jih dodaj na zalogo dodaj UO na zalogo končaj ponovi izračunaj vrednost kriterijske funkcije h g izračunaj število UO na zalogi (U g ) t ← t + ∆ (∆ predstavlja razmik, za katerega se poveča meja t v vsakem poizkusu) končaj dokler t opt = e + (g − 1) × ∆ UL pt = U g – 1 t opt in UO pt sta rezultat zaporedja poizkusov, kjer je vsak poizkus sestavljen iz r naključno ustvarjenih naročil, ki se iz zaloge izpolnijo iz standardnih palic in UO iz prejšnjih naročil. V splošnem t opt in UO pt ne predstavljata minimuma kriterijske funkcije, temveč vrednost, ki mu je blizu. Kako blizu minimuma se nahaja, je v veliki meri odvisno od uporabljene metode za reševanje 1DPRUO ter od ∆. Vse tri obstoječe metode, vključno z ECOLO, te- meljijo na hevrističnem pristopu in ne zagotavljajo optimalne rešitve. Poleg tega mora biti ∆ dovolj velik, da se prepreči nesprejemljivo dolg računski čas. Večji ∆ pa pomeni manj natančne rezultate, zato se lahko vrednosti t opt in UO pt v navezavi s predlagano kriterijsko funkcijo z matematičnega vidika smatrata kot primerne in ne kot optimalne. Predlagana metoda za reševanje predstavljenega problema sestoji iz algoritmov TOP in ECOLA in se imenuje TOP-ECOLA. Sestavljena je iz dveh faz. Faza 1: za uporabo metode TOP-ECOLA je proučevana praktična situacija. Na eni stra- ni so določene osnovne karakteristike naročila: interval, na katerem se nahajajo dolžine kosov, število kosov in število različnih dolžin kosov, na drugi strani pa število različnih standardnih palic na zalogi, njihova dolžina in število palic. Na podlagi razpoložljivih podatkov se v okviru algoritma TOP ocenita e in r, določijo standardne palice in izberejo parametri za ustvarjanje naročila. Izvede se algoritem TOP , rezultat pa sta t opt in UO pt , ki se lahko uporabita, če standardne palice in naključno ustvarjena naročila v nizu poizku- sov z vidika zaloge v prihodnosti in prihodnjih naročil dovolj dobro predstavljata realno situacijo. ECONOMIC AND BUSINESS REVIEW | LETN. 16 | POS. ŠT. | 2014 12 Faza 2: ECOLA se uporablja za izračun načrtov razreza, dokler se dejansko število UO na zalogi bistveno ne razlikuje od UO pt . V takšnem primeru se ponovno izvede 1. korak predlagane metode TOP-ECOLA. Odločitev o tem, kdaj je omenjena razlika dovolj velika, je prepuščena odločevalcu. 3 REZULTATI Pričujoče poglavje vsebuje štiri podpoglavja. Razdelek 4.1 prikazuje oba koraka ECOLE pri reševanju manjšega praktičnega primera. V razdelku 4.2 je podan prikaz računalniških simulacij kot testne metode v primerjavi z metodo, pri kateri so UO ustvarjeni naključno. V razdelku 4.3 prikazuje primerjavo COLE in ECOLE. Algoritem TOP je preizkušen v razdelku 4.4. V razdelku 4.5 je prikazana uporaba TOP-ECOLE. 3.1 Praktični primer uporabe ECOLE Za enostaven prikaz delovanja ECOLE je bil izbran manjši praktični primer razreza jekle- nih palic v velikem multinacionalnem podjetju, ki proizvaja visoko napetostne stolpe. Razmerje o je majhno. Iz ene palice sta v povprečju odrezana manj kot dva kosa. Podatki in rezultati prvega koraka so podani v tabeli 1. t opt = 2,500 in f = 2. f je nastavljen tako nizko z namenom, da se poveča pomen UO in da je problem težje rešljiv. Rezultati kažejo, da vsi ostanki predstavljajo izgubo materiala, saj so krajši od t opt . Rezul- tati v tabeli 1 bi lahko predstavljali končno rešitev, vendar lahko uporaba drugega koraka ECOLE bistveno izboljša rezultate, brez da bi se pri tem spremenilo število porabljenih palic. PODATKI ZALOGA NAROČILO Dolžine palic Število palic Dolžine naročil Število kosov 12,965 7 9,450 2 11,965 10 8,480 2 10,965 37 7,530 2 6,945 2 6,910 4 6,465 4 6,000 4 5,600 12 5,280 8 4,825 12 L. TOMAT, M. GRADIŠAR | OPTIMIZACIJA ENODIMENZIONALNEGA RAZREZA Z UPORABNIM... 13 NAČRT RAZREZA Dolžina palice Število palic Vzorci razreza Ostanek 6,945 2 6,910 35 10,965 8 5,280; 5,600 85 10,965 4 4,825; 6,000 140 11,965 2 4,825; 6,910 230 10,965 4 4,825; 5,600 540 12,965 2 7,530; 4,825 610 10,965 2 9,450 1,515 10,965 2 8,480 2,485 Tabela 1: Rezultati prvega koraka (dolžine palic so v milimetrih) Z izvedbo postopka drugega koraka, sta bile dve porabljeni palici z začetno dolžino 10,965 in izgubo 2,485 zamenjani z dvema neuporabljenima palicama z začetno dolžino 11,965. Izguba se poveča na 3,485 in tako postane UO. Podobno se ostanek dolžine 1,515, ki se smatra kot iz- guba, spremeni v ostanek z dolžino 2,515 in tako postane UO. Vse ostale izgube so premajhne, da bi bile v primeru nadomestitve z daljšimi palicami daljše od meje 2,500. Rezultat drugega koraka je nov načrt razreza, ki je predstavljen v tabeli 2. Štirje ostanki so daljši od 2,500 in se smatrajo kot UO. Skupna izguba se tako zmanjša iz 12,990 na 4,990, kar predstavlja 62% zniža- nje. Po drugi strani pa se skupna dolžina UO, ki jih predstavljajo štiri palice, poveča iz začetnih 0 na 6,000. Kljub bistvenemu znižanju vrednosti kriterijske funkcije v predstavljenem naročilu pa ni gotovo, da bodo te koristi pri prihodnjih naročilih prevladale nad negativnim vplivom dodatno proizvedenih UO. Ta vpliv je preverjen v naslednjem podpoglavju. NAČRT RAZREZA Dolžine palic Število palic Vzorci razreza Ostanek 6,945 2 6,910 35 10,965 8 5,280; 5,600 85 10,965 4 4,825; 6,000 140 11,965 2 4,825; 6,910 230 10,965 4 4,825; 5,600 540 12,965 2 7,530; 4,825 610 11,965 2 9,450 2,515 11,965 2 8,480 3,485 Tabela 2: Rezultat drugega koraka (dolžine palic so v milimetrih) 4.1 Metoda testiranja Učinkovitost predlagane metode za razrez je mogoče ugotoviti s primerjavo z ostalimi metodami. Primerjava metod je bila že opravljena v Cui in Y ang (2010), rezultati pa kaže- ECONOMIC AND BUSINESS REVIEW | LETN. 16 | POS. ŠT. | 2014 14 jo, da v splošnem metoda RSHP prekaša ostale. Primerjava temelji na mnogih kriterijih: skupna dolžina palic, stopnja izkoriščenosti materiala, število standardnih palic, število UO, skupna dolžina UO, skupna izguba materiala, povprečno število UO, povprečna dol- žina UO, povprečen računski čas in število vzorcev razreza. Vendar pa nobena od testira- nih metod (med njimi je tudi COLA) ne izpolnjuje najbolje vseh naštetih kriterijev. Predlagana metoda bi bila lahko testirana z uporabo enakih kriterijev in enakih primerov, vendar pa rezultati najverjetneje ne bi bili uporabni, saj s tem ne bi odgovorili na ključno vprašanje, to je kako bodo skozi čas UO na zalogi naraščali in vplivali na izpolnjevanje prihodnjih naročil. Zato predlagamo novo metodo za testiranje, ki temelji na konceptu, predstavljenem v Trkman in Gradišar (2007), kjer so UO, ustvarjeni v prejšnjem naročilu uporabljeni za izpolnjevanje trenutnega in UO, ustvarjeni v trenutnem naročilu, upora- bljeni pri naslednjem in tako naprej. Namesto, da bi bili UO na zalogi ustvarjeni naključ- no, tako kot v Cherri, Areales, & Yanasse (2009) in v Cui in Yang (2010), je pri vsakem naročilu uporabljena metoda računalniških simulacij. Nivo UO na zalogi je simuliran na način, da narašča tako, kot bi v realnosti, če bi bilo zaporedje ustvarjenih naročil izpolnje- no na podlagi zaporednih ustvarjenih pošiljk palic standardnih dolžin. Da bi prikazali delovanje predlagane metode testiranja, smo analizirali štiri različne pri- mere z različnimi o (tabela 3). V primeru 1 in primeru 2 so naročila ustvarjena z uporabo generatorja problemov CUTGEN1 (Gau in Wäscher, 1995). Uporabljeni so enaki parame- tri kot v Cherri, Areales, & Yanasse (2009) in v Cui in Yang (2010) in enaka količina ma- teriala na zalogi, ki sestoji iz dveh standardnih dolžin (1,000 in 1,100), vsake po 100 palic. Primera 2 in 3 sta dodana na tak način, da je razmik med primerom 1 in 2 enakomerno zapolnjen. V vseh štirih primerih je t nastavljen na ls i . Število zaporednih naročil v Cherri, Areales, & Yanasse (2009) in Cui in Yang (2010) se giblje med 10 in 40, v naših primerih pa je izbrano število 30. Primer 1 Primer 2 Primer 3 Primer 4 Število različnih dolžin 20 20 20 20 Interval, na katerem se vsak kos nahaja [5, 83] [6, 146] [8, 209] [11, 335] Število kosov 125 102 79 34 Število zaporednih naročil 30 30 30 30 Tabela 3: Parametri za ustvarjanje naročila Parametri za ustvarjanje naročila, standardne palice in t so enaki kot v literaturi z na- menom, da je omogočena primerjava med različnimi metodami testiranja. Iz enakega razloga je najprej testirana metoda COLA. Namen uporabe metode simulacij namesto na- ključno ustvarjenih UO je pridobitev informacij o dejanski količini UO na zalogi. Visoka raven UO bi lahko povzročila večjo izgubo materiala in večje skladiščne stroške (tabela 4). L. TOMAT, M. GRADIŠAR | OPTIMIZACIJA ENODIMENZIONALNEGA RAZREZA Z UPORABNIM... 15   PRIMER 1 PRIMER 2 PRIMER 3 PRIMER 4 s Izguba UL na zalogi (število palic) Razlika med proi- zvedenimi in porab- ljenimi UL Izguba UL na zalogi (število palic) Razlika med proizve- denimi in porablje- nimi UL Izguba UL na zalogi (število palic) Razlika med proizve- denimi in pora- bljenimi UL Izguba UL na zalogi (število palic) Razlika med proi- zvedenimi in porablje- nimi UL 1 2 2 1,022 23 2 341 63 20 3,863 121 2 536 2 1 3 98 134 6 419 181 9 −2,662 443 10 189 3 0 2 −593 69 10 −553 88 36 2,658 142 49 1,540 4 1 1 −169 10 10 809 105 25 −1,184 160 61 459 5 1 2 433 36 23 1,277 166 19 −1,757 400 59 200 6 20 1 −589 51 13 -1,341 316 22 894 452 70 397 7 1 2 761 21 23 1,098 86 38 378 223 80 2,475 8 1 2 −378 22 6 −1,758 70 44 927 115 78 −109 9 16 2 43 49 3 675 138 71 1,112 498 68 −1,338 10 0 2 217 73 2 −369 426 58 −1,370 460 68 −87 11 24 2 −10 49 6 −223 202 60 352 754 63 −186 12 2 1 −399 46 18 1,547 117 67 −257 240 74 −569 13 1 2 422 78 11 −1,354 123 95 2,057 264 126 2,910 14 1 2 −399 25 9 138 133 111 502 162 151 −419 15 1 1 −155 35 20 929 109 118 1,241 106 165 1,913 16 0 2 −21 93 28 −221 410 102 −2,727 458 188 2,165 ECONOMIC AND BUSINESS REVIEW | LETN. 16 | POS. ŠT. | 2014 16 17 1 2 198 21 20 −703 51 104 −83 164 188 −502 18 1 3 288 16 20 360 78 102 −565 40 195 −819 19 0 1 −771 24 19 252 259 97 131 291 198 −295 20 3 2 601 21 10 −615 85 115 2,153 206 196 −700 21 0 2 −255 35 9 217 193 100 −2,712 311 195 302 22 3 2 171 21 22 93 63 129 779 160 198 −888 23 0 2 566 20 11 −467 25 129 −96 66 185 −215 24 0 2 −326 43 8 555 210 134 794 150 183 −619 25 5 3 −41 21 6 −540 95 153 972 262 191 2,028 26 0 1 −618 51 13 −275 78 148 −451 236 192 −828 27 0 2 777 61 13 385 99 156 725 371 188 −482 28 0 2 −598 60 7 −524 215 163 −140 263 192 2,733 29 0 2 648 8 8 530 255 154 −493 126 213 −851 30 5 1 −290 53 6 32 122 145 294 355 210 −148 Vsota 90 648 1,269 714 4,561 5,335 7,999 8,855 Tabela 4: Testiranje COLE z uporabo simulacij L. TOMAT, M. GRADIŠAR | OPTIMIZACIJA ENODIMENZIONALNEGA RAZREZA Z UPORABNIM... 17 Najpomembnejši parameter z vidika izgube materiala je o. V splošnem se pri nižjem o proizvede večja izguba. Od primera 1 do primera 4 o pada, zato se izguba materiala poveča iz 90 v primeru 1 do 7,999 v primeru 4. Dodaten razlog za višjo izgubo materiala je veliko število UO na zalogi. Ugotovitve v literaturi niso dovolj podrobne, da bi bilo mogoče na- tančno ugotoviti, kako UO prispevajo k izgubi materiala. Iz eksperimenta je razvidno, da se v primeru 1 in v primeru 2 UO na zalogi ne kopiči- jo, temveč so porabljeni. Kumulativno število UO na zalogi po 30 obdobjih je v prvem primeru 1, v drugem pa 6. V drugem primeru količina UO na zalogi na začetku naraste, vendar se po petem zaporednem obdobju ustali. To nakazuje, da je bila točka, kjer se UO porabljajo z enakim tempom, kot so proizvedeni, dosežena pri nizkem nivoju UO. Vendar pa preprečevanje prekomernega kopičenja UO ni bilo uspešno v primeru 3 in primeru 4, saj je točka, ko se količina UO na zalogi ustali, v primeru 3 med 25. in 30. zaporednim ob- dobjem, v primeru 4 pa je verjetno višja od 30. Razlog, da število UO na zalogi ne narašča neprestano, je v tem, da se v primeru, ko število UO doseže določen nivo, poveča število možnih načrtov razreza, kar omogoča lažje iskanje boljše rešitve, produkcija UO pa se zmanjša. Na takšnem nivoju se število proizvedenih in porabljenih UO izenači. PRIMER 1 PRIMER 3 s Izguba UL na zalogi (število palic) Razlika med proizvedenimi in porabljenimi UL Izguba UL na zalogi (število palic) Razlika med proizvedenimi in porabljenimi UL 1 5 1 474 113 2 491 2 0 1 −452 259 2 238 3 2 2 500 188 18 987 4 0 1 −323 156 17 −481 5 0 2 482 78 15 −9 6 5 3 −41 233 22 775 7 0 2 −326 28 18 −224 8 3 2 171 71 45 −347 9 0 2 −255 203 45 −510 10 2 2 602 145 62 2,072 11 0 1 −771 364 56 −892 12 16 2 472 84 50 −558 13 1 3 288 32 64 138 14 0 2 199 508 69 431 15 6 2 −27 124 84 1,433 16 0 2 −154 103 79 −527 17 2 2 −385 122 100 1,265 ECONOMIC AND BUSINESS REVIEW | LETN. 16 | POS. ŠT. | 2014 18 18 1 2 404 93 103 −233 19 0 2 −297 225 98 −347 20 19 1 −16 413 89 −19 21 0 2 217 180 114 2,170 22 16 2 40 79 117 948 23 0 2 −374 97 105 −1863 24 0 1 −338 316 107 −225 25 7 2 514 132 107 192 26 1 2 −567 60 120 −951 27 6 3 926 108 143 3,728 28 1 2 −594 170 142 −2,151 29 1 3 98 87 158 2,739 30 1 2 −147 90 148 −1,028 Vsota 95 320 4,761 7,242 Tabela 5: Primer 1 in primer 3 iz tabele 4 – ponoven izračun z uporabo obratnega zapored- ja in enakega nabora naročil Proučili smo tudi odvisnost rezultatov od obratnega zaporedja z istim naborom naročil (tabela 5). Za primer 1 in primer 3 iz tabele 4 so bili rezultati izračunani ponovno. Upo- rabljen je bil isti nabor naročil, zaporedje pa je bilo obratno. Iz primerjave rezultatov je razvidno, da sta izguba materiala in količino UO na zalogi v obeh primerih podobni. V primeru 1 se je vsota izgube materiala povečala iz 90 na 95, število UO pa iz 1 na 2. V primeru 3 se je vsota izgube materiala povečala iz 4,651 na 4,761, število UO pa iz 145 na 148. Razlika med proizvedenimi in porabljenimi UO pa je v obeh primerih znatnejša. V primeru 1 se ta razlika zmanjša iz 648 na 320, v primeru 3 pa se poveča iz 5,335 na 7,242. Čeprav razliki znašata 328 in 1,907, pa sta v obeh primerih še vedno precej nižji od naj- večjih razlik med proizvedenimi in porabljenimi UO v dveh zaporednih obdobjih. Zato je mogoče sklepati, da je odvisnost rezultatov od obratnega zaporedja pri istem naboru naročil tako majhna, da se jo lahko zanemari. Za predlagano metodo za testiranje se lahko smatra, da je boljša od obstoječih metod, saj je bolj točna in zagotavlja dragocene informacije o višini UO na zalogi po izpolnitvi določenega števila naročil. Na podlagi rezultatov COLE je mogoče sklepati, da je vsaj v primerih 3 in 4 ob uporabi drugih metod za reševanje 1DPRUO mogoče pričakovati ne- sprejemljivo visoko število UO na zalogi. 3.2 Primerjava med COLO in ECOLO Primerjava med COLO in ECOLO je narejena za primera 1 in 2. Primera 3 in 4 nista bila obravnavana, saj v teh primerih število UO na zalogi prekomerno narašča. Tako, kot v podpoglavju 4.1, je f nastavljen na 2. Rezultati so podani v tabeli 6. L. TOMAT, M. GRADIŠAR | OPTIMIZACIJA ENODIMENZIONALNEGA RAZREZA Z UPORABNIM... 19 s PRIMER 1 PRIMER 2 COLA ECOLA COLA ECOLA Izguba UL na zalogi (število pa- lic) Razlika med proizvedeni- mi in porab- ljenimi UL Izguba UL na zalogi (število palic) Razlika med proizvedenimi in porabljeni- mi UL Izguba UL na zalogi (šte- vilo palic) Razlika med proizvedenimi in porabljenimi UL Izguba UL na zalogi (šte- vilo palic) Razlika med proizvedenimi in porabljenimi UL 1 2 2 1,022 2 2 1,022 23 2 341 23 2 341 2 1 3 98 1 3 98 134 6 419 134 1 319 3 0 2 −593 0 2 −593 69 10 −553 69 5 −553 4 1 1 −169 1 1 −169 10 10 809 18 3 801 5 1 2 433 1 2 633 36 23 1,277 39 14 137 6 20 1 −589 20 1 −599 51 13 −1,341 52 8 −85 7 1 2 761 0 1 −338 21 23 1,098 10 3 9 8 1 2 −378 0 2 726 22 6 −1,758 38 2 −674 9 16 2 43 16 5 449 49 3 675 42 3 664 10 0 2 217 0 2 −883 73 2 −369 71 2 −367 11 24 2 −10 21 2 −7 49 6 −223 43 5 −225 12 2 1 −399 0 1 −297 46 18 1,547 46 17 1,547 13 1 2 422 2 3 718 78 11 −1,354 68 11 −1,337 14 1 2 −384 0 2 −183 25 9 138 27 12 165 15 1 1 −155 3 1 −157 35 20 929 42 28 942 16 0 2 −21 0 2 −21 93 28 −221 90 37 −647 ECONOMIC AND BUSINESS REVIEW | LETN. 16 | POS. ŠT. | 2014 20 17 1 2 198 0 2 199 21 20 −703 19 32 839 18 1 3 288 1 3 288 16 20 360 14 31 −138 19 0 1 −771 1 2 −572 24 19 252 27 26 −858 20 3 2 601 1 2 603 21 10 −615 18 8 −622 21 0 2 −255 0 2 −255 35 9 217 33 9 219 22 3 2 171 5 2 169 21 22 93 27 21 1,187 23 0 2 566 0 2 −434 20 11 −467 33 11 −480 24 0 2 −326 1 1 −327 43 8 555 24 9 −556 25 5 3 −41 0 4 1,064 21 6 −540 31 4 −520 26 0 1 −618 4 2 −622 51 13 −275 49 12 927 27 0 2 777 0 1 −323 61 13 385 49 9 −707 28 0 2 −598 1 2 501 60 7 −524 42 7 603 29 0 2 648 0 1 −452 8 8 530 5 8 −567 30 5 1 −290 5 2 474 53 6 32 51 5 34 Vsota 90 648 86 529 1,269 714 1,234 398 Vrednost kriterijske funkcije 828 701 3,252 2,866 Tabela 6: Primerjava med COLO in ECOLO L. TOMAT, M. GRADIŠAR | OPTIMIZACIJA ENODIMENZIONALNEGA RAZREZA Z UPORABNIM... 21 V primerjavi s COLO rezultati kažejo, da ECOLA zagotavlja boljše rešitve v obeh prime- rih. V primeru 1 je ECOLA proizvedla izgubo materiala v višini 86, kar je 4,45% manj kot s COLO, skupna razlika med proizvedenimi in porabljenimi UL pa je znašala 701, kar je 18,36% manj, kot pri uporabi COLE. V primeru 2 je izguba materiala nižja za 2,76%, sku- pna razlika med proizvedenimi in porabljenimi UL pa je nižja za 44,28%. Tudi vrednost kriterijske funkcije je v obeh primerih nižja in sicer za 18,11% v primeru 1 in za 13,47% v primeru 2. Rezultati ECOLE bi bili verjetno še boljši, če bi bilo na zalogi več različnih standardnih palic z večimi različnimi dolžinami. Razlika med računskim časom COLE in ECOLE je zanemarljiva. 3.3 Rezultati TOP Za testiranje algoritma TOP so bili uporabljeni vsi štirje primeri kreiranja naročil (tabela 3) z enakimi standardnimi palicami na zalogi in enako vrednostjo f in r kot v ostalih pod- poglavjih. Cilj je najti optimalno mejo t in optimalno število UL na zalogi. V primer 1 ∆ znaša 5, v primerih 2,3 in 4 pa zaradi višjih vrednosti parametrov 10. e enak 20 v primerih 1 in 2, 80 v primeru 3 in 100 v primeru 4. Rezultati so podani v tabeli 7. V vseh štirih primerih je TOP uspešno našel t opt in UO pt . UO pt se od primera 1 do primera 4 spreminja in je razmeroma majhen zaradi nizke vred- nosti f. t opt se giblje od 35, kjer je vrednost kriterijske funkcije enaka 907, do 150, kjer je vrednost kriterijske funkcije enaka 16,320. Vrednost kriterijske funkcije od primer 1 do primera 4 stalno narašča, saj se o manjša, zaradi česar je problem razreza težje rešljiv. Primer 1 t 20 25 30 35 40 45 Število UL na zalogi 3 3 3 3 3 3 Vrednost kriterijske funkcije 1,782 1,745 1,745 907 907 1,750 Primer 2 t 20 30 40 Število UL na zalogi 1 1 1 Vrednost kriterijske funkcije 2,857 2,461 2,485 ECONOMIC AND BUSINESS REVIEW | LETN. 16 | POS. ŠT. | 2014 22 Primer 3 t 80 90 100 Število UL na zalogi 14 1 2 Vrednost kriterijske funkcije 11,380 8,764 9,129 Primer 4 t 120 130 140 150 160 Število UL na zalogi 18 8 6 4 5 Vrednost kriterijske funkcije 18,667 18,295 17,822 16,320 17,527 Tabela 7: Rezultati TOP 3.4 Primer uporabe TOP-ECOLA TOP-ECOLA sestoji iz dveh faz, ki se izmenično izvajata. V prvi fazi je proučevana prak- tična situacija. V našem primeru se domneva, da primer 4 predstavlja takšno praktično situacijo, saj je od vseh najtežje rešljiv. Prvi korak je rešen z algoritmom TOP. Rezultata sta t opt in UO pt . Ti vrednosti v primeru 4 znašajo 150 in 4 palice, kot je prikazano v tabeli 7. V drugi fazi je t opt uporabljen kot vhodni parameter za ECOLO, ki se uporabi za izpolnje- vanje zaporednih naročil. Naročila v drugi fazi morajo imeti enake parametre kot naročila v prvi fazi. Parametri za primer 4 so prikazani v tabeli 3, se pa lahko predvidena naročila od dejanskih precej razlikujejo. Rezultat je večja razlika med UO pt in dejanskim številom UO na zalog v daljšem časovnem obdobju. Odločevalec se odloči, kdaj je ta razlika tako velika, da se ustavi izvajanje druge faze in vrne k prvi, da se poišče nov t opt in UO pt . Da bi preizkusili, kaj se zgodi, če so parametri dejanskih naročil drugačni od predvidenih, so bila v primeru 4 naročila v drugi fazi ustvarjena z rahlo spremenjenimi parametri. Interval, na katerem se vsak kos nahaja, je bil spremenjen iz [11, 335] v [15, 400]. Vsi ostali parametri so ostali enaki. Ustvarjeno zaporedje 30. naročil je bilo rešeno z uporabo metode ECOLA. Rezultati so predstavljeni v tabeli 8. L. TOMAT, M. GRADIŠAR | OPTIMIZACIJA ENODIMENZIONALNEGA RAZREZA Z UPORABNIM... 23 s Izguba UL na zalogi (število palic) Razlika med proizvedenimi in porabljenimi UL Vrednost kriterijske funkcije 1 1,427 4 911 3,765 2 738 1 −781 1,606 3 197 16 4,830 5,354 4 308 2 −4,104 1,472 5 1,078 1 −538 2,474 6 624 2 789 2,355 7 624 2 −278 2,077 8 774 1 −201 2,176 9 185 4 1,039 2,037 10 1,412 11 851 5,342 11 1,300 1 −2,336 2,782 12 366 10 2,143 3,057 13 333 10 293 3,284 14 377 2 −2,078 1,294 15 289 9 2,824 3,942 16 141 12 684 4,330 17 192 4 −2,675 1,757 18 90 12 1,848 3,601 19 493 10 −1,269 2,938 20 207 18 4,270 6,636 21 756 29 4,128 11,862 22 139 34 −3,956 6,672 23 225 26 1,614 8,458 24 369 12 −3,399 5,347 25 589 12 −2,395 3,392 26 251 24 1,864 4,580 27 135 51 11,314 13,782 28 876 34 −4,291 10,973 29 629 72 14,976 25,455 30 1,091 83 3,906 30,285 Tabela 8: Rezultati drugega koraka ECONOMIC AND BUSINESS REVIEW | LETN. 16 | POS. ŠT. | 2014 24 Rezultati kažejo, da začne med 20. in 30. zaporednim naročilom število UO na zalogi močno naraščati, saj se poveča iz 18 na 83. Optimalno število UO je štiri. Velika razlika med optimalnim in dejanskim številom UO na zalogi je znak za odločevalca, da se je potrebno vrniti v začetno, prvo fazo. Nova optimalna vrednost bo omogočala število UO blizu optimuma in ohranjala nizko vrednost kriterijske funkcije. 4 ZAKLJUČEK Predlagana metoda za reševanje problema 1DPRUO TOP-ECOLA je sestavljena iz dveh algoritmov: TOP in ECOLA. Algoritma sta bila v članku podrobno opisana. TOP izraču- na optimalni t in optimalno število UO na zalogi. ECOLA minimizira izgubo materiala in ohranja optimalno raven UO. Metoda TOP-ECOLA ni omejena na optimizacije po- sameznega naročila, temveč minimizira izgubo materiala in razliko med proizvedenimi in porabljenimi UO v večih zaporednih naročilih. Za razširitev optimizacije na zaporedje naročil in za boljše nadzorovanje UO je bil 1DPRUO preoblikovan. Preprečeno je bilo povečano število UO na račun višje izgube materiala pri prihodnjih naročilih in narašča- joči stroški skladiščenja. Predlagana je bila tudi nova metoda za testiranje algoritmov za reševanje 1DPRUO. TOP-ECOLA je bila testirana z uporabo računalniških simulacij, kjer so bili UO iz prejšnjega naročila uporabljeni pri naslednjem, namesto da bi bili ustvarjeni naključno. Računalniški rezultati kažejo, da v primerjavi s COLO TOP-ECOLA zmanjšuje izgubo materiala pri zaporednih naročilih in preprečuje nenadzorovano rast UO na zalogi. Za nadaljnje raziskave na področju 1DPRUO bi bilo koristno tudi ostale obstoječe meto- de prilagoditi za reševanje večih zaporednih naročil. Parameter f je pretežno odvisen od ekonomike skladišča in ni odločitvena spremenljivka, vendar bi bilo zanimivo videti, kako sprememba f vpliva na rezultate. Prav tako bi bilo koristno, če bi bilo tako kot v Erjavec, Trkman in Gradišar (2008) minimiziranje izgube združeno z minimizacijo stroškov, kjer poudarek ne bi bil le na aktivnosti razreza, temveč tudi na drugih povezanih dejavnosti, ki tvorijo procese naročanja materiala (Trkman in McCormack, 2010). Z A H VA L A Avtorja sta bila delno podprta s strani Ministrstva RS za visoko šolstvo, znanost in tehno- logijo po pogodbi P2-0037. LITERATURA Arbib, C., Marinelli, F. & Pezzella, F. (2012). An LP-based tabu search for batch scheduling in a cutting pro- cess with finite buffers. International Journal of Production Economics, 136(2), 287-296. Chauhan, S. S., Martel, A. & D'amour, S. (2008). Roll assortment optimization in a paper mill: An integer programming approach. Computers & Operations Research, 35(2), 614–627. L. TOMAT, M. GRADIŠAR | OPTIMIZACIJA ENODIMENZIONALNEGA RAZREZA Z UPORABNIM... 25 Cherri, A. C., Areales, M. N. & Yanasse, H. H. (2009). The one-dimensional cutting stock problem with usable leftover – A heuristic approach. European Journal of Operational Research, 196(3), 897–908. Cui, Y. & Huang, B. (2012). Reducing the number of cuts in generating three-staged cutting patterns. Euro- pean Journal of Operational Research, 216(2), 358-365. Cui, Y., Gu, T. & Hu, W. (2009). A cutting-and-inventory control problem in the manufacturing industry of stainless steel wares. Omega, 37(4), 864–875. Cui, Y. & Yang, Y. (2010). A heuristic for the one-dimensional cutting stock problem with usable leftover. European Journal of Operational Research, 204 (2), 245–250. Diegel, A., Montocchio, E., Walters, E., Schalkwyk, S. & Naidoo, S. (1996). Setup minimising conditions in the trim loss problem. European Journal of Operational Research, 95(3), 631-640. Erjavec, J., Gradišar, M. & Trkman, P. (2012). Assessment of stock size to minimize cutting stock production costs. International Journal of Production Economics, 135(1), 170–176. Erjavec, J., Trkman, P. & Gradišar, M. (2008). Renovation of the cutting stock process. International Journal of Production Research, 47(14), 3979–3996. Gau, T. & Wäscher, G. (1995). CUTGEN1: A problem generator for the standard one-dimensional cutting stock problem. European Journal of Operational Research, 84(3), 572–579. Gilmore, P. C. & Gomory, R. E. (1961). A linear programming approach to the cutting stock-problem. Opera- tions Resarch, 9(4), 849–859. Golfeto, R. R., Moretti, A. C. & Salles Neto, L. L. (2009). A genetic symbiotic algorithm applied to the cutting stock problem with multiple objectives. Advanced Modeling and Optimization, 11(4), 473-501. Gradišar, M., Jesenko J. & Resinovič, G. (1997). Optimization of roll cutting in clothing industry. Computers & Operations Research, 24(10), 945–953. Gradišar, M., Resinovič, G., Jesenko, J. & Kljajić, M. (1999). A sequential heuristic procedure for one-dimen- sional cutting. European Journal of Operational Research, 114(3), 557–568. Gradišar, M. & Trkman, P. (2005). A combined approach to the solution to the general one-dimensional cut- ting stock problem. Computers & Operations Research, 32(7), 1793–1807. Gradišar, M., Erjavec, J. & Tomat, L. (2011). One-dimensional cutting stock optimization with usable leftover: a case of low stock-to-order ratio. International journal of decision support system technology, 3(1), 54-66. Leăo, A. A. S., Santos, M. O., Hoto, R. & Arenales, M. N. (2011). The constrained compartmentalized knap- sack problem: mathematical models and solution methods. European Journal of Operational Research, 212(3), 455–463. Trkman, P. & Gradišar, M. (2007). One-dimensional cutting stock optimization in consecutive time periods. European Journal of Operational Research, 179(2), 291–301. Trkman, P. & McCormack, K. (2010). Estimating the benefits and risks of implementing e-procurement. IEEE Transactions on Engineering Management, 57(2), 338–349. Venkateswarlu, P. (2001). The trim loss problem in wooden container manufacturing company. Journal of Manufacturing Systems, 20(3), 166–176. Wäscher, G., Haußner, H. & Schumann, H. (2007). An improved typology of cutting and packing problems. European Journal of Operational Research, 183(3), 1109–1130.