Volume 13 Issue 5 Vol 13, Posebna številka Article 2 12-30-2011 Optimizacija procesa razreza po skupinah Mihael Cesar Mirko Gradišar Jure Erjavec Luka Tomat Follow this and additional works at: https://www.ebrjournal.net/home Recommended Citation Cesar, M., Gradišar, M., Erjavec, J., & Tomat, L. (2011). Optimizacija procesa razreza po skupinah. Economic and Business Review, 13(5). https://doi.org/10.15458/2335-4216.1229 This Original Article is brought to you for free and open access by Economic and Business Review. It has been accepted for inclusion in Economic and Business Review by an authorized editor of Economic and Business Review. 27 ECONOMIC AND BUSINESS REVIEW | LETNIK 13 | Posebna št. | 2011 | 27–40 OPTIMIZACIJA PROCESA RAZREZA PO SKUPINAH MihaeL cesaR1 MiRko gRadišaR 2 jURe eRjavec3 LUka ToMaT4 PovzeTek: V članku je predlagana metoda reševanja enodimenzionalnega problema raz- reza materiala po skupinah. Metoda je uporabna v primeru velikih naročil, ki jih zaradi tehnoloških in logističnih razlogov ni mogoče izpolniti v enem, temveč v več zaporednih korakih. Metoda ima dve stopnji. V prvi stopnji se izračunajo pari naročil, ki se v drugi stopnji združujejo v skupine. Metoda se izvaja v obliki računalniškega algoritma G-CUT in je preskušena na primeru iz prakse. ključne besede: operacijske raziskave, optimizacija, razrez jeL klasifikacija: C61 1. Uvod Enodimenzionalni razrez materiala nastopa v mnogih panogah od lesne (Venkateswar- lu, 2001; Manrique et al., 2011), papirne (Chauhan, Martel, & D'amour, 2008; Matsumo- to, Umetani & Nagamochi, 2011), tekstilne (Gradišar, Jesenko, & Resinovič, 1997) do kovinske (Cui, Gu, & Hu, 2009). Vsem tem panogam je skupen problem, kako iz daljših v splošnem različnih palic na zalogi narezati naročeno število krajših palic. Pri opti- mizaciji enodimenzionalnega razreza želimo najti odgovor na vprašanje, kako izvesti razrez, da bo čim manj izgub materiala oziroma ostankov, ki jih zaradi premajhnih in neuporabnih dimenzij zavržemo (Kantorovich, 1960; Gilmore & Gomory, 1961, 1963, 1965; Gass, 1985; Gradišar, 1999; Erjavec, Gradišar, Trkman, 2010; Gradišar, Erjavec, Tomat, 2011; ). Zmanjšanje neuporabnega ostanka oz. izgube materiala je večinoma glavni cilj optimi- zacije, vendar ni edini, kajti zaradi kombinacije tehnoloških, proizvodnih in poslovnih 1 Univerza v Ljubljani, Ekonomska fakulteta, Ljubljana, e-naslov: mihael.cesar@ef.uni-lj.si 2 Univerza v Ljubljani, Ekonomska fakulteta, Ljubljana,e-naslov: miro.gradišar@ef.uni-lj.si 3 Univerza v Ljubljani, Ekonomska fakulteta, Ljubljana,e-naslov: jure.erjavec@ef.uni-lj.si 4 Univerza v Ljubljani, Ekonomska fakulteta, Ljubljana, e-naslov: luka.tomat@ef.uni-lj.si ECONOMIC AND BUSINESS REVIEW | LETNIK 13 | Posebna št. | 201128 značilnosti, ki so od primera do primera različne, je treba upoštevati tudi dodatne ome- jitve. Vsaka dodatna omejitev sicer zmanjša število možnih rešitev in s tem teoretično skrajša čas iskanja najboljše, kljub temu pa je čas za iskanje najboljše rešitve, ki je ma- tematično opredeljena kot globalni minimum kriterijske funkcije, pri obsežnejših pri- merih predolg in pomeni ozko grlo za poslovni proces v podjetju. Razlog za časovno potratnost pri iskanju najboljše rešitve tiči v dejstvu, da je večina problemov razreza ??NP-polnih (Bischoff & Wäscher, 1995). Uporaba metod, ki najdejo zadovoljiv rezultat v določenem časovnem intervalu, je zato ključna za odpravljanje ozkih grl, čeprav vedno ne najdejo najboljše rešitve, je pa rešitev blizu optimalni. V praksi se podjetja srečujejo s specifičnimi problemi, kjer standardne metode ne pridejo v poštev, temveč jih je treba prilagoditi ali pa razviti nove. Kljub dokaj jasni definiciji pro- blema enodimenzionalnega razreza v poslovnem svetu obstaja veliko število raznovr- stnih primerov. Poleg zmanjšanja izgube materiala so cilji lahko tudi nižji stroški, krajši čas razreza, nižje število menjav ali nastavitev rezila, zmanjšanje zaloge, prilagoditev razreza za potrebe logistike in podobno (Trkman & Gradišar, 2003). Poseben izziv so obsežnejši primeri naročil, ki jih sestavlja veliko število kosov. V lite- raturi meja, ki loči manj in bolj obsežna naročila, ni jasno določena. Poleg števila kosov določajo velikost naročila tudi dimenzije, oblika profila, teža materiala, logistične in teh- nološke omejitve, ki izhajajo iz specifičnih pogojev v praksi. Osnovni problem je ta, da materiala iz skladišča za celotno naročilo ni možno hkrati prepeljati do stroja za rezanje. Tudi prostor za odlaganje materiala ob stroju na eni strani in narezanih kosov na drugi je navadno omejen. Poleg tega je treba narezane kose odlagati tako, da jih je kasnejše čim laže jemati s kupa oziroma sklada v vrstnem redu, ki ga zahtevajo nadaljnji tehnološki postopki in ki je praviloma različen od vrstnega reda rezanja, ki ga določa algoritem za minimizacijo ostanka. V literaturi še ni zaslediti niti splošnih metod za optimizacijo razreza pri velikih naro- čilih niti rešitve konkretnih praktičnih primerov. V tem prispevku sicer opisujemo ra- zvoj metode, ki je prilagojena potrebam konkretnega podjetja, vendar pa je sorazmer- no malo specifičnih omejitev. Zato lahko sklepamo, da bo predlagana metoda lahko služila kot vzorec rešitve tudi drugim podjetjem, ki se srečujejo s problemom velikih naročil. Predlagana metoda predvideva razdelitev velikega naročila v več manjših delov, pod- naročil oziroma skupin naročenih dolžin tako, da bi bila skupna izguba materiala vseh skupin najmanjša. Nadaljevanje članka sestavlja pet razdelkov. V drugem poglavju je definicija problema. Tretje poglavje opisuje metodo, ki rešuje problem. V četrtem poglavju sledi testiranje metode z realnimi podatki. Zadnje poglavje pa vsebuje sklepne misli in predloge nadalj- njega raziskovanja na tem področju. M. CESAR, M. GRADIŠAR, J. ERJAVEC, L. TOMAT | OPTIMIZACIJA PROCESA RAZREZA PO SKUPINAH ... 29 2. deFinicija PRoBLeMa Na zalogi imamo dovolj kosov enodimenzionalnega materiala – palic, da izpolnimo naročilo. Dolžina posamezne palice je v splošnem različna in izražena s celimi števili. Palice so lahko enake ali različne. Različne so zaradi tega, ker proizvajalec izdeluje več različnih standardnih dolžin, ker so pomembne razlike med deklariranimi standardni- mi dolžinami in dejansko izmerjenimi in ker obstajajo tudi nestandardne dolžine, ki so lahko dovolj veliki oziroma še uporabni ostanki prejšnjih naročil. Material iz zaloge uporabimo za izpolnitev naročila, ki ga sestavljajo krajše dolžine s točno določenim številom kosov. Zaradi velikosti naročilo razdelimo na r manjših skupin naročenih dolžin. r ni konstanta, ker morata biti tako velikost kot sestava po- samezne skupine v skladu z omejitvami. Gre za obraten problem kot pri združevanju naročil, ki morajo biti na primer izpolnjena do določenega datuma (Li, 1996), in po- doben kot pri izpolnjevanju naročil v zaporednih časovnih intervalih (Trkman & Gra- dišar, 2007), le da se v našem primeru zaloga materiala med izpolnjevanjem naročila ne spreminja. Ostanek, ki je dovolj dolg, da ga bomo lahko uporabili pri izpolnjevanju prihodnjih naročil, vrnemo v skladišče (Alfieri, 2004; Cherri, Areales, Yanasse, 2009; Gradišar, Kljajić, Resinovič, Jesenko, 1999). Problemi razreza, kjer je predvidena po- novna uporaba dovolj dolgih ostankov, se označujejo z angleško kratico CSPUL (Cut- ting Stock Problems with Usable Leftovers), ostanki, krajši od določenega praga D, pa predstavljajo izgubo. Naročilo izpolnimo tako, da minimiziramo skupno izgubo vseh skupin. Kriterijsko funkcijo in omejitve bomo sicer oblikovali v skladu s potrebami konkretnega podjetja, ki se ukvarja z izdelavo stebrov za visokonapetostne električne vode. Vendar pa je večina omejitev precej splošnih in je opisan problem najbrž podoben, kot ga imajo tudi druga podjetja, ki se srečujejo z velikimi naročili. Treba je minimizirati izgubo materiala celotnega naročila tako, da 1. se posamezna naročena dolžina nahaja samo v eni skupini, ker je rokovanje z nareza- nimi kosi ob stroju za rezanje tako mnogo lažje; 2. se lahko posamezna palica v skladišču uporabi samo v eni skupini, ker je rokovanje z ne do konca razrezanimi palicami tako mnogo lažje; 3. je v posamezni skupini največ ??P naročenih dolžin, kar olajšuje rokovanje z nareza- nimi kosi ob stroju za rezanje in tudi izbiranje palic, ki gredo v nadaljnji tehnološki postopek; 4. se lahko iz posamezne palice v skladišču reže največ N različnih naročenih dolžin, ker s tem omejimo število nastavitev dolžine rezanja na stroju in olajšamo rokovanje z delno razrezanimi palicami iz skladišča; 5. je velikost skupine omejena z M – največjo dovoljeno vsoto dolžin naročenih kosov v skupini. To olajšuje prevoz palic iz skladišča do stroja za rezanje, tako da se ena skupina prepelje hkrati in olajšuje rokovanje s palicami ob stroju za rezanje. ECONOMIC AND BUSINESS REVIEW | LETNIK 13 | Posebna št. | 201130 Problem razreza takole definiramo: li = dolžina naročene palice; i = 1, ..., n bi = zahtevana količina palic dolžine li Lj = dolžina palice na zalogi; j = 1, ..., m xij = število naročenih kosov dolžine li , ki so odrezani iz Lj ∂j = ostanek pri razrezu palice Lj Kriterijska funkcija: min (minimiziranje izgube celotnega naročila) z ozirom na: 1) (največja vsota dolžin vseh naročil v skupini) 2) (vsaka palica v skladišču se lahko uporabi le v eni skupini) 3) (vsako naročilo je lahko samo v eni skupini) 4) (največje število različnih naročil v skupini) 5) (z ene palice na skladišču lahko odrežemo le N različnih naročil) 6) (omejitev nahrbtnika) 7) (naročene dolžine so proizvedene v točno zahtevanem številu) 8) (samo en ostanek v skupini k je lahko daljši od max (li. hki)) 9) UBk = max (li ⋅ hki) ∀ k xij ≥ 0, celo število ∀ i, j tkj ≥ 0 ∀ j ∂j ≥ 0 ∀ j. ∑rk = 1∑mj = 1 tkj . gkj ∑ n i = 1 libihkj ≤ M ∀k ∑ r k = 1 gkj ≤ 1 ∀j ∑ r k = 1 hkj ≤ 1 ∀i ∑ n i = 1 hkj ≤ P ∀k ∑ n i = 1 yij ≤ N ∀j ∑ n i = 1 licij + ∂j = Lj ∀j ∑ rm j = 1 xij = bi ∀i ∑ m j = 1 zj . ukj ≤ 1 ∀k M. CESAR, M. GRADIŠAR, J. ERJAVEC, L. TOMAT | OPTIMIZACIJA PROCESA RAZREZA PO SKUPINAH ... 31 V navedenem modelu so uporabljene naslednje funkcije:  0 v primeru, ko xij = 0 ∀ i zj =   1 sicer kaže, če je palica Lj uporabljena v načrtu razreza,  1 v primeru, ko je Lj uporabljen v skupini k gkj =   0 sicer kaže, če je palica Lj uporabljena v skupini k,  1 v primeru, ko je li v skupini k hki =   0 sicer kaže, če je naročilo li v skupini k,  1 v primeru, ko gkj = 1 ∧ ∂j > UBk ukj =   0 sicer kaže, če je ostanek palice Lj, uporabljene v skupini k, večji od UBk, ∂j v primeru, ko gkj = 1 ∧ ∂j ≤ UBk tkj =   0 sicer predstavlja ostanek palice Lj v skupini k,  0 v primeru, ko xij = 0 yij =   1 sicer kaže, če se naročilo li reže iz palice Lj. V vsaki skupini je lahko le en ostanek daljši od max (li. hki) (8). Ostanki v skupini k, ki so daljši od max (li. hki), se ne štejejo kot izguba. Če bi bila zgornja meja dolžine ostankov v posamezni skupini UBk, ki jih smatramo kot izgubo (ker so prekratki, da bi jih lahko ponovno uporabili), postavljena nižje od max (li. hki), bi prišlo do naslednje situacije. Ob dovolj veliki zalogi bi algoritem generiral čim več ostankov, ki so manjši od max (li. hki) in večji od UBk, ker se ne bi šteli kot izguba. Na zalogi bi se tako nabiralo vedno večje število krajših kosov, ki bi povzročali večji ostanek pri prihodnjih naročilih. To bi se zgodilo tudi, če bi dovolili več kot en ostanek na skupino, daljši od max (li. hki). Ker tega ne želi- mo, nastavimo UBk na max (li. hki), po izvedeni optimizaciji pa lahko poljubno določimo mejo D, ki ločuje izgubo od še uporabnih ostankov, ki jih vrnemo v skladišče. 3. Razvoj RešiTve Skupine lahko v splošnem tvorimo na dva načina. Lahko optimiziramo naročilo kot celo- to, rezultate pa potem razdelimo v manjše skupine. V tem primeru posebne metode za op- timizacijo razreza ne potrebujemo, ker skupine oblikujemo, ko je načrt razreza že izdelan. Lahko pa najprej oblikujemo skupine in nato optimiziramo razrez. Če bi uporabili prvi način, v splošnem ne bi mogli zadovoljiti omejitve (3). Ker iz posamezne palice v skladišču ECONOMIC AND BUSINESS REVIEW | LETNIK 13 | Posebna št. | 201132 lahko odrežemo kose katerih koli naročenih dolžin, grupiranje palic, ki vsebujejo samo določena naročila, ne bi bilo možno. Razviti je torej treba novo metodo, ki bo omogočala obraten postopek, najprej oblikovanje skupin in nato minimizacijo ostanka. Ključna za obstoj problema optimizacije razreza po skupinah je torej omejitev (3). Od splošne de- finicije CSPUL (Gradišar et al., 1999) se naša definicija razlikuje le po tem, da ima poleg omejitve velikosti skupine (1) ali (4) samo dve dodatni omejitvi: (3) in (2). Omejitev (2) ni tako pomembna, lahko bi jo odpravili, a to ne bi pomembno vplivalo na predlagano metodo reševanja problema. Gre za to, da uporabni ostanki prejšnjih skupin niso na voljo naslednjim skupinam istega naročila, ampak se po izpolnitvi naročila vrnejo v skladišče. V dani praktični situaciji se je takšno obravnavanje uporabnih ostankov izkazalo kot pri- merno, v kakšnem drugem podjetju pa omejitev (2) morda ne bi bila potrebna. Predlagana hevristična metoda ima dva dela. V prvem delu celotno naročilo razdelimo v skupine, v drugem delu pa minimiziramo ostanke posameznih skupin. Delitev večjega naročila na manjše dele je možno izvesti na mnogo načinov. Izbrali bomo tistega, ki je primernejši za reševanje naročil, ki jih izpolnjujemo z velikim številom pa- lic iz skladišča. To se zgodi v primerih z majhnim razmerjem med povprečno dolžino palice v skladišču in povprečno dolžino naročila. To razmerje je majhno, če je na primer med 1 in 3. V teh primerih je število palic iz skladišča, ki jih potrebujemo za izpolnitev naročila, zelo veliko oziroma le malo manjše, kot je število kosov naročil. V nasprotnem primeru, ko je to razmerje večje, je možno naročilo izpolniti že z manjšim številom palic iz skladišča. S tem pa se v splošnem tudi zmanjša potreba po delitvi naročila na lažje obvladljive dele. Pri oblikovanju skupin torej domnevamo, da je večina praktičnih po- treb po razdelitvi naročila na manjše dele povezana s problemi, pri katerih iz ene palice v skladišču odrežemo kose le enega ali najpogosteje dveh različnih naročil, več pa le izjemoma. Takšno stanje je tudi v obravnavanem podjetju, zato smo razvoj nove metode prilagodili majhnim razmerjem med povprečno dolžino palic v skladišču in dolžino na- ročil. V praktičnih primerih, kjer je to razmerje večje od 3, zato predlagane metode ne bo možno uporabiti brez večjih prilagoditev. Predvidevamo pa lahko, da takšnih primerov v praksi ni veliko. Naročilo razdelimo v skupine v dveh stopnjah. V prvi iz naročil tvorimo pare, ki pred- stavljajo najmanjše možne skupine, v drugi pa iz parov oblikujemo končne skupine. Metoda temelji na predpostavki, da je najbolje, če v postopku razreza damo prednost daljšim dolžinam. Tako zmanjšamo učinek ostrejših pogojev proti koncu postopka (en- ding conditions) (Gradišar, 1999; Trkman & Gradišar, 2007) in povečamo verjetnost, da bomo našli zadovoljivo rešitev. V ta namen najprej tvorimo seznam naročil Sn, urejen po padajočih dolžinah, nato izberemo prvo oziroma najdaljšo dolžino iz seznama Sn in ji do- ločimo par. Če ima seznam Sn liho število naročil, ga dopolnimo do sodega števila tako, da mu na koncu dodamo še eno naročilo z dolžino maxint in številom kosov 1. maxint je največje celo število, ki je lahko predstavljeno v računalniku. Pri enojni natančnosti je to 32.767. Ker tako velikega naročila ne moremo realizirati oziroma kombinirati z drugimi naročili, na razrez ne vpliva. S tem smo zagotovili, da bo imelo vsako naročilo svoj par. M. CESAR, M. GRADIŠAR, J. ERJAVEC, L. TOMAT | OPTIMIZACIJA PROCESA RAZREZA PO SKUPINAH ... 33 Par določimo tako, da za vse možne kombinacije najdaljše dolžine s seznama Sn z ostalimi krajšimi dolžinami rešimo problem nahrbtnika ob upoštevanju vse razpoložljive zaloge. Izberemo tisti par, ki ima najmanjši povprečni ostanek. Povprečni ostanek izračunamo kot kvocient vsote ostankov uporabljenih palic iz skladišča, zmanjšane za ostanke, ki jih vrnemo v skladišče, in števila uporabljenih palic iz skladišča, zmanjšanega za število ostankov, ki smo jih vrnili v skladišče. Ko je par izbran, s seznama Sn črtamo obe dolžini, ki ga sestavljata, iz zaloge pa tiste palice, ki smo jih za ta par porabili skupaj z vrnjenimi ostanki. Postopek določanja parov ponavljamo, dokler so v seznamu Sn še razpoložljive dolžine. Rezultat tega postopka je n/2 parov. Vsakemu paru je pridružen povprečni osta- nek. Namesto parov bi lahko tvorili tudi podskupine iz večjega števila naročil, tako da bi bilo to čim bolj usklajeno s številom N pri omejitvi (5). Tudi predlagana metoda se v osnovi ne bi spremenila. Za pare smo se odločili, ker v primerih z majhnim razmerjem med povprečno dolžino palice v skladišču in povprečno naročeno dolžino kaj dru- gega ne bi imelo smisla in ker je število možnih kombinacij, ki jih moramo preveriti, najmanjše. Poleg tega imamo v nadaljevanju več možnosti pri oblikovanju končnih skupin. Dobljene pare uredimo po padajočem povprečnem ostanku v seznam Sr. Sr nato razde- limo na skupine parov tako, da se pomikamo od prvega proti zadnjemu. V vsaki sku- pini, razen morda v zadnji, je ravno toliko parov, da ne presežemo omejitve P ali M. Dobljene skupine parov v nadaljevanju obravnavamo kot samostojna naročila. Povezuje jih skupna zaloga palic, zato ni vseeno, v kakšnem vrstnem redu se bo izvajal razrez posameznih skupin. Prva skupina bo imela na voljo celotno zalogo palic. Tako bo pri optimizaciji razreza na voljo več možnih kombinacij, zato lahko pričakujemo manjši ostanek (Gradišar, 1999). Obratno pa bo pri optimizaciji kasnejših skupin na voljo samo še toliko zaloge, kot je je ostalo od razreza prejšnjih skupin. Možnih kombinacij bo torej manj, pričakovan ostanek pa večji. V drugem delu najprej določimo vrstni red razreza posameznih skupin. Pri tem izhaja- mo iz predpostavke, da je bolje, če pri razrezu damo prednost skupinam s pari, ki so višje na seznamu Sr in imajo torej višji pričakovani ostanek. Domnevamo, da bi se ostanek bolj povečal, če bi te skupine razrezali na koncu, kot bi se povečal, če na koncu režemo skupine z nižjim pričakovanim ostankom. Vrstni red razreza skupin je torej enak kot vrstni red njihovega tvorjenja. Optimizacijo razreza posamezne skupine lahko izvede- mo po kateri koli metodi za reševanje CSPUL. Izbrali smo metodo C-CUT (Gradišar & Trkman, 2005) v obliki programske rešitve, ki omogoča nastavljanje največjega števila naročenih dolžin, ki se režejo iz posamezne palice na zalogi in ki uporablja eksaktno metodo za manj obsežne skupine. Rezultat drugega dela je načrt razreza, ki vsebuje dve vrsti ostankov. Manjši od D so izguba, daljši pa se vrnejo v skladišče. Na sliki 1 sta oba dela predlagane metode predsta- vljena v obliki psevdokode. ECONOMIC AND BUSINESS REVIEW | LETNIK 13 | Posebna št. | 201134 Prvi del: določitev parov Razvrsti naročila po padajočih dolžinah v Sn (l1 > l2 > … >li> ... > ln). j ← 1, ..., n – 1; k ← 2, ..., n Rj,k← maxint ∀ j, k (začetne vrednosti povprečnih ostankov vseh parov) i ← 1 (začetna vrednost števca i) h← 1 (začetna vrednost indeksa parov z minimalnimi ostanki) ponavljaj dokler i < n – 1 p← i + 1 (začetna vrednost števca p) Rmin ← maxint (začetna vrednost minimalnega ostanka) c← 0 (začetna vrednost testne spremenljivke c) ponavljaj dokler p < n če li > 0 ∧ lp > 0 potem Izvedi proceduro KNAPSACK5 za li in lp. Izračunaj povprečni ostanek R. če je R < Rmin, potem Rmin ← R j← i k← p c← 1 (c testira, ali je vsaj enkrat veljalo R < Rmin) konec če konec če p← p + 1 konec ponavljanj če c = 1 potem Rh ← Rmin s1h ← j s2h ← k lj ← 0; lk← 0 (iz zaloge odstranimo palice, ki jih je porabil par lj in lk) h← h + 1 konec če i← i + 1 konec ponavljanj Drugi del: oblikovanje skupin Razvrsti povprečne ostanke Rh in pripadajoče številke parov po padajoči vrednosti Rh v sezname Sr (R1 > R2 > … > Rn/2), Sp1 (s11, s12 … s1n/2) in Sp2 (s21, s22 … s2n/2). h← 1 (začetna vrednost števca parov) a← 1 (trenutno število različnih naročil v skupini) b← 0 (trenutna skupna dolžina naročil v skupini) g1← 1 (trenutna spodnja meja skupine) 5 Procedura KNAPSACK je enaka kot v (Gradišar et al., 1999). M. CESAR, M. GRADIŠAR, J. ERJAVEC, L. TOMAT | OPTIMIZACIJA PROCESA RAZREZA PO SKUPINAH ... 35 ponavljaj dokler h ≤ n/2 i← g1 ponavljaj dokler i ≤ h a← a + 2 b← ls1i.bs1i + ls2i.bs2i i← i + 1 konec ponavljanj če a > P ∨ b > M potem g2← i - 2 (trenutna zgornja meja skupine) če g1 < g2, potem g1← g2 (Če že en sam par preseže omejitev P ali M, ga vseeno raz- režemo.) konec če Izvedi optimizacijo razreza skupine parov s1g1 do s1g2 in s2g1 do s2g2 s pro- gramom C-CUT6. g1← g2 + 1 h← h 1 konec če h← h + 1 konec ponavljanj Slika 1: Algoritem razreza po skupinah, izražen v psevdokodi Optimizacija razreza skupin je potrebna zaradi omejitve (8), po kateri je v vsaki skupini le en ostanek lahko daljši od max (li. hki). Brez te omejitve bi lahko uporabili že optimizi- rane pare, ki bi jih združevali v skupine. Predlagana metoda je implementirana v obliki računalniškega programa G-CUT, ki omogoča reševanje problema, definiranega v drugem razdelku, po predlagani metodi. Numeričen del je napisan v programskem jeziku Fortran, ki omogoča hitro procesiranje, vhod in izhod pa sta izvedena v 4GL (angl. Fourth-generation programming language, označuje programski jezik četrte generacije). Kot je razvidno iz slike 1, program G-CUT vsebuje tudi program C-CUT, ki omogoča optimizacijo razreza posamezne skupine s kombinacijo eksaktnega in hevrističnega algoritma. Za eksaktno reševanje uporablja programsko rešitev CPLEX. Z eksaktnimi metodami lahko optimiziramo naročila, ki ne presegajo določenih omejitev (Belov & Sheithauer, 2002; Alves & Carvalho, 2008). Večje skupine pa C-CUT optimira s hevrističnim algoritmom (Gradišar & Trkman, 2005). Omejitve programa G-CUT so: število naročil < 500 število kosov posameznega naročila < 500 število dolžin na zalogi < 500 število kosov posamezne dolžine na zalogi < 1000 6 Program C-CUT je enak kot v (Gradišar & Trkman, 2005). ECONOMIC AND BUSINESS REVIEW | LETNIK 13 | Posebna št. | 201136 4. RezULTaTi Za ilustracijo delovanja programa G-CUT bomo predstavili optimizacijo konkretnega praktičnega primera enodimenzionalnega razreza jeklenih profilov. Primer ima nasle- dnje omejitve: P = 8, N = 2, M = 150.000 in D = 2.500. Vse dimenzije so v milimetrih. Vhodni podatki so v tabeli 1. Tabela 1: Palice na zalogi in naročilo ZALOGA NAROČILO Dolžina palice (mm) Število kosov Dolžina palice (mm) Število kosov 12.965 11.965 10.965 6.945 6.465 7 10 37 2 4 9.940 9.450 8.480 7.530 6.910 6.145 6.000 5.710 5.600 5.280 4.825 420 4 2 2 2 4 2 4 2 12 8 12 18 Dolžine naročila so v skladu s predlagano metodo urejene po velikosti od najdaljše do najkrajše. Iz primera je razvidno, da naročilo brez vračunanih ostankov po skupni dolžini obsega 52 % materiala, ki je na zalogi. Razmerje med povprečno dolžino palice na strani zaloge in tisto na strani naročila je nizko in znaša 1,55. V povprečju se torej iz palic na skladišču odreže manj kot dva kosa naročila. Rezultat prvega dela metode je seznam parov, urejenih po padajočem povprečnem ostan- ku. Ker je naročenih dolžin 12, je parov 6. Prikazani so v tabeli 2. Tabela 2: Razdelitev parov na skupine Št. para 1. naročilo (mm) 2. naročilo (mm) povprečni ostanek (mm) 1 7.530 4.825 1.113 prva skupina 2 8.480 5.280 1.098 3 6.000 5.600 565 4 9.450 6.910 528 5 9.940 420 135 druga skupina 6 6.145 5.710 101 M. CESAR, M. GRADIŠAR, J. ERJAVEC, L. TOMAT | OPTIMIZACIJA PROCESA RAZREZA PO SKUPINAH ... 37 Zaradi omejitve P = 8 so pari razdeljeni na dve skupini. Prvo skupino tvorijo prvi štirje pari z osmimi naročenimi dolžinami in drugo zadnja dva s štirimi. S programom C- CUT optimiziramo najprej prvo skupino, ki jo tvorijo pari z večjim povprečnim ostan- kom, vendar pa imamo pri tem na voljo celotno zalogo palic. Rezultati so v tabeli 3. Z ostankom palic pa optimiziramo drugo skupino. Rezultati so v tabeli 4. Tabela 3: Načrt razreza prve skupine PODATKI ZALOGA NAROČILO Dolžina palice (mm) Število kosov Dolžina palice (mm) Število kosov 12.965 11.965 10.965 6.945 6.465 7 10 37 2 4 7.530 4.825 8.480 5.280 6.000 5.600 9.450 6.910 2 12 2 8 4 12 2 4 Tabela 4: Načrt razreza druge skupine PODATKI ZALOGA NAROČILO Dolžina palice (mm) Število kosov Dolžina palice (mm) Število kosov 12.965 11.965 10.965 6.465 3 10 17 4 9.940 420 6.145 5.710 4 18 2 2 NAČRT REZANJA Dolžina zaloge (mm) Št. kosov zaloge Vzorec rezanja naročil Ostanek (mm) 6.945 12.965 12.965 10.965 10.965 10.965 10.965 10.965 10.965 2 2 2 8 2 4 2 2 2 1 x 6.910 1 x 7.530, 1 x 4.825 1 x 6.000, 1 x 6.910 1 x 5.280, 1 x 5.600 1 x 4.825, 1 x 6.000 1 x 4.825, 1 x 5.600 2 x 4.825 1 x 9.450 1 x 8.480 35 610 55 85 140 540 1.315 1.515 2.485 NAČRT REZANJA Dolžina zaloge (mm) Št. kosov zaloge Vzorec rezanja naročil Ostanek (mm) 11.965 12.965 10.965 2 2 2 1 x 6.145, 1 x 5.710 1 x 9.940, 7 x 420 1 x 9.940, 2 x 420 110 85 185 ECONOMIC AND BUSINESS REVIEW | LETNIK 13 | Posebna št. | 201138 Iz rezultatov obeh skupin vidimo, da noben ostanek ni daljši od max (li. hki), ki znaša v prvi skupini 9.450 in v drugi 9.940. Vsi ostanki štejejo kot izguba, ker so manjši od 2.500. Prikazani primer je sicer vzet iz realnosti, vendar pa predstavlja izjemno majhno naro- čilo. Izbrali smo ga zato, ker je zaradi preprostosti lažje razumljiv in s tem primernejši za predstavitev metode. Ker je naročilo majhno in sta tudi obe skupini sorazmerno majhni, sta bili obe s programom C-CUT rešeni eksaktno. Za rešitev prikazanega primera je osebni računalnik (Intel Core 2 Duo) potreboval 2,5 sekunde. Podobno kot v (Gilmore & Gomory, 1961, 1963, 1965) tudi v tem primeru ne navajamo statistične analize ostankov izmišljenih ali z naključnim generatorjem ustvarjenih prob- lemov. Smisel takšne analize bi bila primerjava s podobnimi metodami, ki pa jih v litera- turi nismo zasledili. 5. zakLjUček V članku je predlagana hevristična metoda optimizacije enodimenzionalnega razreza v primeru, ko je treba zaradi tehnoloških in logističnih vzrokov razdeliti naročilo na več manjših delov. Te dele nato optimiziramo posebej, vendar tako, da je skupna izguba materiala čim manjša. Predlagana hevristična metoda je implementirana v obliki raču- nalniškega programa G-CUT. G-CUT omogoča oblikovanje skupin naročil in minimi- zacijo skupne izgube materiala. Uporaba programa je prikazana na preprostem primeru iz prakse. Predlagana metoda je primerna za reševanje problemov, kjer je razmerje med povprečno dolžino naročila in povprečno dolžino palice v skladišču sorazmerno majh- no. V teh primerih je število palic iz skladišča, ki jih potrebujemo za izpolnitev naročila, le malo večje, kot je število kosov naročil. Na osnovi tega lahko domnevamo, da je večina praktičnih potreb po razdelitvi naročila na manjše dele povezana s tovrstnimi problemi. Pri večjih razmerjih pa bi bilo treba metodo razširiti z možnostjo oblikovanja podsku- pin, sestavljenih iz treh ali več naročil. V nadaljevanju raziskovanja področja optimizacije razreza po skupinah bi bilo koristno nadomestiti minimizacijo izgube z minimizacijo stroškov tako kot na primer v (Erjavec, Trkman & Gradišar, 2008), pri čemer predmet optimizacije ne bi bila samo aktivnost razreza, ampak z njo povezane ostale aktivnosti, ki sestavljajo procese nabavljanja mate- riala (Trkman, McCormack, 2010), skladiščenja, logistike in proizvodnje. LiTeRaTURa Alfieri, A., van de Velde, S. & Woeginger, G. (2004). Roll cutting in the curtain industry, or: A well-solvable allocation problem. European Journal of Operational Research, 183 (3), 1397–1404. Alves, C. & de Carvalho, J. M. V. (2008). New integer programming formulations and an exact algorithm for the ordered cutting stock problem. Journal of the Operational Research Society, 59, 1520–1531. M. CESAR, M. GRADIŠAR, J. ERJAVEC, L. TOMAT | OPTIMIZACIJA PROCESA RAZREZA PO SKUPINAH ... 39 Belov, G. & Scheithauer, G. (2002). A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths. European Journal of Operational Research, 141, 274–294. Bischoff, E. E. & Wäscher, G. (1995). Cutting and packing. European Journal of Operational Research, 84 (3), 503–505. 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. Cherri A. C., Arenales, M. N. & Yanasse, H. H. (2009). The one-dimensional cutting stock problem with us- able leftover – A heuristic approach. European Journal of Operational Research, 196 (3), 897–908. 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. Erjavec, J., Trkman, P. & Gradišar, M. (2008). Renovation of the cutting stock process. International Journal of Production Research, 47 (14), 3979–3996. Erjavec, J., Gradišar, M. & Trkman, P. (2010). Assessment of stock size to minimize cutting stock production costs. Interantional Journal of Production Economics , 135 (1), 170–176. Gass, S. (1985). Linear programming methods and applications. New York: McGraw-Hill. Gilmore, P. C. & Gomory, R. E. (1961). A linear programming approach to the cutting stock-problem. Opera- tions Research, 9 (4), 849–859. Gilmore, P. C. & Gomory, R. E. (1963). A linear programming approach to the cutting stock problem – Part II. Operations Research, 11 (6), 863–888. Gilmore, P. C. & Gomory, R. E. (1965). Multistage cutting stock problems of two and more dimensions. Op- erations Research, 13 (1), 94–120. Gradišar, M., Erjavec, J. & Tomat, L. (2011). One-Dimensional Cutting Stock Optimization with Usable Lefto- ver: A Case of Low Stock-to-Order Ratio. International Journal of Decision Support System Technology , 13 (1). Gradišar M., Jesenko J. & Resinovic G. (1997). Optimization of roll cutting in clothing industry. Computers & Operations Research, 24, 945–953. Gradišar M. et al. M. (1999). A sequential heuristic procedure for one-dimensional cutting. European Journal of Operational Research, 114 (3), 557–568. Gradišar M., Trkman P. (2005). A combined approach for solution of general one-dimensional cutting stock problem. Computers & Operations Research, 32 (7), 1793–807. Kantorovich, L. V. (1960). Mathematical methods of organizing and planning production. Management Sci- ence, 6 (4), 366–422. Li, S. (1996). Multi-job cutting stock problem with due dates and release dates. Journal of the Operational Research Society, 47 (4), 490-510. Manrique, J. D., Al-Hussein, M., Bouferguene, A., Safouhi, H., & Nasseri, R. (2011). Combinatorial Algorithm for Optimizing Wood Waste in Framing Designs . Journal of Construction Engineering and Management , 137 (3), 188–198. Matsumoto, K., Umetani, S. & Nagamochi, H. (2011). On the one-dimensional stock cutting problem in the paper tube industry. Journal of Scheduling , 14 (3), 281–290. ECONOMIC AND BUSINESS REVIEW | LETNIK 13 | Posebna št. | 201140 Trkman, P. & Gradišar, M. (2003). Optimization of the cutting stock process. Journal of Mechanical Engineer- ing, 49 (9), 469–475. 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.