LES wood 51 (1999) 7-8 Raziskave in razvoj 212 UDK: 674.093:65.012.2 Pregledni znanstveni ~lanek - Preview Scientific Paper Planiranje zalog z metodo diskretnega deterministi~nega dinami~nega programiranja Stock planning with discrete deterministic dynamic programming method Denis JELA^I]*, Leon OBLAK** Izvle~ek Abstract V ~lanku je prikazana optimizacijska metoda diskretnega In the article the discrete deterministic dynamic programming opti-deterministi~nega dinami~nega programiranja, ki jo lahko misation method is described, which may be used for solving difficult uporabimo tudi za reševanje zahtevnih proizvodnih proble- production problems also. On the case of hipotetical sawmill the mov. Na primeru hipoteti~nega `agarskega obrata je method for stock managing problem is presented. metoda predstavljena za problem upravljanja z zalogami. Klju~ne besede: zaloge, planiranje, diskretno determi- Keywords: stock, planning, discrete deterministic dynamic pro-nisti~no dinami~no programiranje, lesna industrija, `agar- gramming, wood industry, sawmill ski obrat 1. UVOD problem obravnavati z vidika maksi- dalo optimalen učinek oziroma rezul- miranja dobička v nekem časovnem tat. Izbrani proces ima končno število Planiranje zalog je vedno aktualen obdobju. Za reševanje takih proble- faz, vse množice, ki v procesu nasto- problem v industriji. Z njim se srečuje- mov je potrebno uporabiti ustrezno pajo, pa so diskretne in končne (imajo jo tudi slovenska lesnoindustrijska optimizacijsko metodo. Ker je prob- končno število elementov). Tako bo podjetja. V zadnjem času je bilo slišati lem zalog dinamičen problem, hkrati izhod iz ene faze vhod v naslednjo veliko ‘pro et contra’ argumentov, ko pa mu lahko definiramo končno šte- fazo. Vsako fazo določajo [3]: se je razpravljalo o prednostih in sla- vilo faz, smo se v obravnavanem hi- bostih upravljanja z zalogami pri tra- patetičnem primeru odločili za meto- * množica vseh možnih stanj (zaloga v dicionalni proizvodnji in tako imeno- do diskretnega determinističnega di- količinskih enotah) na začetku faze: vani ‘just-in-time’ proizvodnji. namičnega programiranja. X|_i = {Xi_i i,Xi.-| 2 , ••• , x,.-, } Tradicionalna filozofija pravi, da zalo- 2. DISKRETNO DETERMINISTI- ge varujejo proizvodni proces pred ČNO DINAMIČNO PROGRAMI- * množica vseh možnih stanj na koncu defekti in drugimi problemi. Pomanj- RANJE faze: kanje delov, zapoznele dobave in drugi problemi namreč lahko prekinejo Z diskretnim determinističnim dina- X,- = {x; }, xi2, ■■■ , X; p} delovni proces. Zaloge so kot mazilo, mičnim programiranjem lahko rešuje- ki procesu omogoča, da kljub teža- mo probleme optimalnosti pri zveznih * v vsakem stanju x, } ■ , j=1, ... , m vam deluje nemoteno. Po filozofiji in diskretnih procesih. Tako lahko gle- ... in množica vseh možnih odločitev: ‘just-in-time’ proizvodnje pa zaloge ne de na izbrani kriterij poiščemo opti- le zavzemajo prostor in povzročajo malno vodenje procesa (v našem pri- D(x, } ■) = {d; , : ,, d, } ■ 2, ... , d, } ■ n}. stroške, ampak pogosto tudi povzro- meru je to upravljanje z zalogami), ki čajo prikrite probleme [2]. poteka v več fazah, etapah ali ko- Iz te množice je potrebno izbrati od- rakih. V vsaki fazi posebej se je po- ločitev in na podlagi te odločitve pro- Zelo zanimiv pogled na planiranje trebno odločiti, kako bo potekal na- ces pripeljati iz nekega začetnega zalog pa je lahko tudi ta, da skušamo daljnji proces. Odločanja v posamez- stanja x, ] ■ faze i v neko končno stan- nih fazah niso med seboj neodvisna, je x, s faze i oziroma začetno stanje pač pa odločitev v neki fazi vpliva na faze'i + 1. * d d Šuki fk| d odločitev v poznejših fazah. Odločitve dLiy^^mun Zavod 25 za organizaciju proizvonje u ie torei potrebno sprejemati dinamič- Korist oziroma izguba, strošek, dobi- ** dr., Biotehniška fakulteta, Oddelek za lesarstvo, Ro`na dolina, no (drugo za drugo), pri tem pa išče- ček ali kaj podobnega, pri diskretnem C. VIII/34, Ljubljana mo tako zaporedje odločitev, ki bo determinističnem dinamičnem pro- LES wood 51 (1999) 7-8 Raziskave in razvoj 213 gramiranju imenujemo donesek in ga označimo z: n-i (i,k). Tako definirani donesek je odvisen samo od začetnega stanja x, } ■ iz množice XM in izbrane odločitve d'k(xj. 1(j) = cdj_n f k iz množice D(xj_1(i). Tako nam odločitev dM , k e Dfx, ] ,) v stanju Xj.^jeXj.! da donesek r^ p). Transformacija Tj_-,, prevede stanje Xj. ] : iz množice X,.-, v stanje x, s iz množice X, pri odločitvi d, ! ik iz množice D(xi-l,j)- Velja torej: Xi = T^ (X^, D^) za vsak element iz množic X| }, X| in D| }. Ta enačba se imenuje enačba prehoda. Prehod iz ene faze v naslednjo fazo je korak. Število vseh korakov se imenuje horizont, ki ga označujemo s črko N. l-ti rep procesa je del procesa, ki mu manjka do konca še N-i korakov. V začetku procesa, ko je i = 0, manjka do konca procesa še N korakov ter rep obsega še celoten proces. če pa je i = N-l, obsega rep procesa samo še en korak. Ko pa je i = N, je proces končan. 3. PROBLEM ZALOG KOT PRIMER DISKRETNEGA DETERMINISTIČNEGA DINAMIČNEGA PROGRAMIRANJA Za ponazoritev metodologije reševanja takih problemov bomo prikazali enostaven hipotetični primer. Podjetje (manjši žagarski obrat) skuša optimi-rati nabavo hlodovine v smislu maksimalnega dobička v naslednjih treh tednih, pozna pa nabavne in prodajne cene ter povpraševanje po žaganem lesu za to obdobje. Ključno vprašanje, ki se zastavlja, je: kdaj in koliko m3 hlodovine naj žagarski obrat nabavi, da bo lahko zadovoljil povpraševanje po žaganem lesu in ob znanih nabavnih in prodajnih cenah dosegel največji dobiček? Podatki o povpraševanju po žaganem lesu (v m3) v naslednjih treh tednih, o prodajni ceni za m3 žaganega lesa, nabavni ceni za m3 hlodovine in ceni transporta na 100 m3 hlodovine v posameznih tednih so podani v preglednici 1. Pri kalkulaciji moramo upoštevati izkoristek `aganega lesa za izbrano drevesno vrsto in na~in raz`agovanja. Normalni izkoristek se giblje od 50 do 80 %, lahko pa je tudi ve~ji ali manjši, odvisno od razli~nih dejavnikov kot npr. dimenzije hlodovine, na~ina `a-ganja, obdelave `aganega lesa in drugih dejavnikov [1]. Zaradi la`je ponazoritve bo izkoristek hlodovine v našem primeru kar 50 %. Na za~etku tritedenskega ciklusa je na skladiš~u 300 m³ hlodovine, vrednost m³ hlodovine na koncu tretjega tedna pa bo 12.000 SIT. Obrat se zaradi organizacijskih in transportnih stroškov lahko vsak teden odlo~a le med štirimi alternativami nabave: 1. ne nabavi ni~ hlodovine, 2. nabavi 100 m³ hlodovine, 3. nabavi 200 m³ hlodovine, 4. nabavi 300 m³ hlodovine. Pri tem je potrebno upoštevati povpraševanje v posameznih tednih. @agar-ski obrat namre~ lahko izbira samo Preglednica 1. Podatki, potrebni za reševanje problema zalog med tistimi alternativami, ki zadovoljijo povpraševanje po `aganem lesu (preglednica 1). Problem rešimo z uporabo metode diskretnega deterministi~nega dinami~-nega programiranja, kot je prikazano na sliki 1. S pravokotniki so predstavljena stanja. Na za~etku prvega tedna je na skla-diš~u 300 m³ hlodovine, kar glede na predvideni 50 % izkoristek zadostuje za izdelavo 150 m³ `aganega lesa. Zato je za~etno stanje v to~ki Xi,j, kar pomeni i=1, j=300. di(j,k)=di,j,k pomeni odlo~itev, ko se v stanju Xi,j odlo~amo za eno od štirih mo`nih alternativ (naro~il): k=0, 100, 200 ali 300 in je odvisna od obstoje~e zaloge in povpraševanja. Ker je povpraševanje po `aganem lesu v prvem tednu 100 m³, bi teoreti~no lahko izbirali med vsemi štirimi alternativami, vendar pa bi nas prva odlo~itev (k=0) pripeljala v polo`aj, ko v tretjem tednu na bi bili v stanju zadovoljiti povpraševanja. Zato jo izlo~imo, v grafu pa izpustimo. Podatki Teden Enote 1. (I=1) 2. (I=2) 3. (i=3) Povpraševanje po žaganem lesu m3 100 200 200 Prodajna cena žaganega lesa SIT/m3 40.000 41.000 43.000 Nabavna cena hlodovine SIT/m3 14.000 15.000 16.000 Transportni stroški SIT/100 m3 200.000 200.000 220.000 Novo stanje zalog hlodovine Xi-1,s je torej dolo~eno s številom obstoje~ih m³ hlodovine (j), številom naro~enih m³ hlodovine (k) in povpraševanjem po `aganem lesu x 2 (p) v teko~em tednu: s = j + k - p. Slika 1. Iskanje optimalnih zalog z metodo diskretnega deterministi~nega dinami~nega programiranja LES wood 51 (1999) 7-8 Pri nabavni količini hlodovine moramo upoštevati 50 % izkoristek, zato povpraševanje po žaganem lesu množimo z 2. V prvem tednu ima žagarski obrat tako na voljo tri alternative: 1. nabavi 100 m3 hlodovine ^ s = i + k - p ^> s = 300 + 100 - 200 = 200, 2. nabavi 200 m3 hlodovine => s = j + k - p => s = 300 + 200 - 200 = 300, 3. nabavi 300 m3 hlodovine => s = j + k - p => s = 300 + 300 - 200 = 400. Možna (nova) stanja zaloge hlodovine v prvem tednu so torej 200 m3, 300 m3 in 400 m3. Na enak način računamo tudi stanja v drugem in tretjem tednu. Vedno upoštevamo samo alternative, ki zadovoljijo povpraševanje po žaganem lesu v naslednjem tednu. Donesek (dobiček) rT k) je določen s prodajno ceno za m3'žaganega lesa, nabavno ceno za m3 hlodovine in ceno transporta na 100 m3 hlodovine v posameznem tednu. Izračunamo ga po enačbi: x = (povpraševanje po žaganem lesu x prodajna cena žaganega lesa) - (nabavna količina hlodovine x nabavna cena hlodovine) - transportni stroški x, = (100 m3 x 40.000 SIT/m3) - (100 m3 x 14.000 SIT/m3) - 200.000 SIT = + 2.400.000 SIT, x2= (100 m3 x 40.000 SIT/m3) - (200m3x 14.000 SIT/m3) - 400.000 SIT = + 800.000 SIT, x3 = (100 m3 x 40.000 SIT/m3) - (300 m3 x 14.000 SIT/m3) - 600.000 SIT = - 800.000 SIT, x4 = (200 m3 x 41.000 SIT/m3) - (300 m3 x 15.000 SIT/m3) - 600.000 SIT = H- 3.100.000 SIT, x5= (200 m3 x 41.000 SIT/m3) - (200m3 x 15.000 SIT/m3) - 400.000 SIT = + 4.800.000 SIT, x6 = (200 m3 x 41.000 SIT/m3) - (300 m3 x 15.000 SIT/m3) - 600.000 SIT = H- 3.100.000 SIT, x7 = (200 m3 x 41.000 SIT/m3) - (100 m3 x 15.000 SIT/m3) - 200.000 SIT = + 6.500.000 SIT, x8 = (200 m3 x 41.000 SIT/m3) - (200 m3 x 15.000 SIT/m3) - 400.000 SIT = + 4.800.000 SIT, Raziskave in razvoj x, = (200 m3 x 41.000 SIT/m3) - (300 m3 x 15.000 SIT/m3) - 600.000 SIT = H- 3.100.000 SIT, x10 = (200 m3 x 43.000 SIT/m3) - (300 m3 x 16.000 SIT/m3) - 660.000 SIT = H- 3.140.000 SIT, x,, = (200 m3 x 43.000 SIT/m3) - (200 m3 x 16.000 SIT/m3) - 440.000 SIT = + 4.960.000 SIT, x12 = (200 m3 x 43.000 SIT/m3) - (300 m3 x 16.000 SIT/m3) - 660.000 SIT = H- 3.140.000 SIT, x13 =(200 m3 x 43.000 SIT/m3) - (100 m3 x 16.000 SIT/m3) - 220.000 SIT = + 6.780.000 SIT, x14 = (200 m3 x 43.000 SIT/m3) - (200 m3 x 16.000 SIT/m3) - 440.000 SIT = + 4.960.000 SIT, x15 = (200 m3 x 43.000 SIT/m3) - (300 m3 x 16.000 SIT/m3) - 660.000 SIT = H- 3.140.000 SIT. Kot je razvidno iz slike 1, ima žagarski obrat tri možna stanja ob koncu tretjega tedna - končna stanja (O, 1.200.000 SIT in 2.400.000 SIT). Vrednost stanj je določena s številom m3 hlodovine, ki ostanejo na zalogi (skladišču), vsak m3 hlodovine pa je vreden 12.000 SIT. V procesu diskretnega determinističnega dinamičnega programiranja idealno strategijo (pot) iščemo tako, da doneske (v našem primeru dobičke) računamo iz končnega proti začetnemu stanju. Izračunamo doneske za vse možne strategije, v pravokotnike pa vpišemo tistega z največjo vrednostjo. Na primer: v stanje X, ; (i=2, j=300), kar pomeni 300 m3 hlodovine na skladišču v drugem tednu, lahko pridemo po treh poteh, in sicer s strategijami x13, x14 in x15. Strategija x13 da vrednost 6,78 mio SIT (O + 6,78), strategija x14 vrednost 6,16 mio SIT (1,2 + 4,96), strategija x15 pa vrednost 5,54 mio SIT (2,4 + 3,14). Največjo vrednost (dobiček) da strategija x13, zato to vrednost vpišemo v pravokotnik, optimalno pot do njega pa poudarimo z odebeljeno črto. Na enak način računamo optimalne poti do vseh narisanih pravo-kotnikov (stanj) in tako dobimo optimalno pot procesa (na sliki 1 je označena z odebeljenimi puščicami), ki hkrati pomeni optimalno strategijo upravljanja z zalogami, z vidika stroškov in prihodkov, za ta žagarski obrat. 214 Maksimalni dobi~ek torej dose`emo, ~e prvi teden nabavimo 300 m³, drugi teden 300 m³ in tretji teden 100 m³ hlodovine. Pri tem bo dobi~ek znašal 8.150.000 SIT. 4. POVZETEK Z diskretnim deterministi~nim dina-mi~nim programiranjem lahko rešujemo probleme optimalnosti pri procesih, kjer je odlo~itve potrebno sprejemati dinami~no (drugo za drugo), pri tem pa iš~emo tako zaporedje odlo-~itev, ki bo dalo optimalen u~inek oziroma rezultat. Tako lahko glede na izbrani kriterij poiš~emo optimalno vodenje procesa, ki poteka v ve~ fazah. V vsaki fazi posebej se je potrebno odlo~iti, kako bo potekal nadaljnji proces. Veliko problemov, ki se pojavljajo v proizvodnji, je prav takih. V ~lanku je predstavljen primer planiranja zalog z metodo diskretnega deterministi~nega dinami~nega programiranja. Hipoteti~en primer je enostaven in vsebuje majhno število podatkov, saj je namen ~lanka prikazati predvsem metodologijo reševanja podobnih problemov. 5. LITERATURA 1. Gornik Bu~ar, D. / Merzelj, F. 1998. @agarski praktikum. Ljubljana, Univerza v Ljubljani, Biotehniška fakulteta, Oddelek za lesarstvo, 151 s. 2. Pape`, M. 1997. Just in time proizvodnja. Lesarski utrip, 3, 9, Ljubljana, Revizor consulting, s. 7-8. 3. Zadnik Stirn, L. 1983. Operacijska raziskovanja. Ljubljana, Biotehniška fakulteta, VTOZD za gozdarstvo, 175 s.