Minimizing waste (off-cuts) using cutting stock model: the case of one dimensional cutting stock problem in wood working industry

Jou nal o Indus ial Enginee ing and Managemen JIEM, 2016 – 9(3): 834-859 – Online ISSN: 2013-0953 – P in ISSN: 2013-8423 h p://dx.doi.o g/10.3926/jiem.1653 Minimizing Was e (O -cu s) Using Cu ing S ock Model: The Case o One Dimensional Cu ing S ock P oblem in Wood Wo king Indus y Gbemileke A. Ogun an i1 , Ayodeji E. Oluleye2 1D exel Uni e si y (Uni ed S a es) 2Uni e si y o Ibadan (Nige ia) gao32@d exel.edu, [email protected] Recei ed: Augus 2015 Accep ed: Augus 2016 Abs ac : Pu pose: The main objec i e o his s udy is o de elop a model o sol ing he one dimensional cu ing s ock p oblem in he wood wo king indus y, and de elop a compu e p og am o i s implemen a ion. Design/me hodology/app oach: This s udy adop s he pa e n o ien ed app oach in he o mula ion o he cu ing s ock model. A pa e n gene a ion algo i hm was de eloped and coded using Visual basic.NET language. The cu ing s ock model de eloped is a Linea P og amming (LP) Model cons ained by nume ous easible pa e ns. A LP sol e was in eg a ed wi h he pa e n gene a ion algo i hm p og am o de elop a one - dimensional cu ing s ock model applica ion named GB Cu ing S ock P og am. Findings: Applying he model o a eal li e op imiza ion p oblem signi ican ly educes ma e ial was e (o -cu s) and minimizes he o al s ock used. The esul yielded abou 30.7% cos sa ings o company-I when he o al s ock ma e ials used is compa ed wi h he o me cu ing plan. Also, o e alua e he e iciency o he applica ion, Case I p oblem was sol ed using wo op comme cial 1D-cu ing s ock so wa e. The esul s show ha he GB p og am pe o ms be e when ela ed esul s we e compa ed. -834- Jou nal o Indus ial Enginee ing and Managemen – h p://dx.doi.o g/10.3926/jiem.1653 Resea ch limi a ions/implica ions: This s udy ound up he linea p og amming solu ion o he numbe o pa e n o cu . P ac ical implica ions: F om Manage ial pe spec i e, implemen ing op imized cu ing plans inc eases p oduc i i y by elimina ing calcula ing e o s and d as ically educing ope a o mis akes. Also, inancial bene i s ha can annually amoun o millions in cos sa ings can be achie ed h ough signi ican ma e ial was e educ ion. O iginali y/ alue: This pape de eloped a linea p og amming one dimensional cu ing s ock model based on a pa e n gene a ion algo i hm o minimize was e in he wood wo king indus y. To implemen he model, he algo i hm was coded using VisualBasic.ne and linea p og amming sol e called lpsol edll (dynamic link lib a y) was in eg a ed o de elop a one dimensional cu ing s ock P og am. Keywo ds: 1D-cu ing s ock p oblem, cu ing s ock model, pa e n gene a ion algo i hm, linea p og amming 1. In oduc ion A cu ing s ock p oblem (CSP) basically consis s o cu ing la ge pieces a ailable in s ock o p oduce smalle pieces (called i ems) in o de o mee a gi en demand. The cu ing is planned o minimize was e o he s ock ma e ial (o he objec i es may a ise). These objec i es may be o minimize im loss, he numbe o cu ing lines o p oduc ion cos , maximize p o i and so on. In a cu ing plan, he equi ed se o pieces om he a ailable s ock leng hs mus be ob ained. The objec i e is o minimize he numbe o used s ock leng hs o , equi alen ly, im loss (was e) (Mu a , U a & Ahme , 2011). This ype o p oblem occu s in se e al indus ies such as pape , aluminium, s eel, glass, and u ni u e indus y among o he s. Kall a h, Rebennack, Kall a h and Kusche (2014) sol ed cu ing s ock p oblem in he pulp and pape indus y wi h he objec i e o minimizing he numbe o olls and he pa e ns, he eby p e en ing o e p oduc ion. The one-dimensional cu ing s ock p oblem (1D-CSP) can be s a ed as ollows: Gi en a se o i ems I, each i em i ∈{1, ..., m} o leng h li and demand o bi pieces, o be cu ou o a i ually in ini e supply o s ock leng h L (whe e 0 < li ≤ L,  i  I), in o de o minimize he numbe o s ock objec s used (Ga a a, Salassa, Vanc oonenbu g, Be ghe & Wau e s, 2014). The p oblem conside ed in his pape is o -835- Jou nal o Indus ial Enginee ing and Managemen – h p://dx.doi.o g/10.3926/jiem.1653 ind a cu ing plan ha would minimize he was e ma e ial when a se o o de s di e en in leng h and quan i y is o be cu om a pack o s ocks wi h cons an leng h (Yang, Sung & Weng, 2006). The pu pose o his pape is o de elop a ma hema ical model o sol ing he one dimensional cu ing s ock p oblem in he wood wo king indus y and de elop a use iendly compu e p og am o i s implemen a ion. Many wood wo king companies a e seeking ways o minimizing p oduc ion was e (and maximize p o i ) bu aced wi h lack o echnical know-how and compe ency o so do. Thus, he e is need o a e y easy o ope a e and in e p e cu ing s ock p og am o imp o ing ope a ional e iciency. Based on he p oblem encoun e ed, a me hodology o in eg a ing he cu ing pa e ns gene a ion algo i hm wi h LP sol e was de eloped. In o de o achie e he was e minimiza ion objec i e, he cu ing s ock model was coded in o a compu e applica ion using Visual Basic.NET language. This pape is o ganized as ollows: sec ion 2 e iews he ela ed wo k on he cu ing s ock p oblem. In sec ion 3, he me hodology and solu ion app oach a e p esen ed. Sec ion 4 p o ides he p oblems sol ed o demons a e p ac ical applica ion o he model. Sec ion 5 p esen s esul s ob ained by applying he one dimensional cu ing s ock model. Finally, he las sec ion concludes he s udy and op imal cu ing using he 1D-cu ing s ock p og am was p oposed. 2. Li e a u e Re iew 2.1. Cu ing and Packing P oblems Cu ing and packing p oblems a e combina o ial op imiza ion p oblems. As wi h many o he p oblems o his kind, hey a e easy o s a e, and di icul o sol e. Ma sumo o, Ume ani and Nagamochi (2011) also e e ed o hese p oblems as NP ha d. The s anda d p oblem is de ined as ollows: gi en a se o small and la ge objec s, how he small objec s should be ob ained om he la ge ones in o de o op imize a gi en c i e ion. The ypical es ic ions o which a cu ing o packing plan is submi ed a e he impossibili y o he small objec s o o e lap, and he limi ed capaci y o leng h o he la ge objec s. The e a e wo main app oaches o sol e his p oblem: exac and heu is ic me hods. Exac algo i hms a e mainly based on linea /dynamic p og amming and b anch-and-bound echniques. Vande beck (1999) in oduced a b anch-and-p ice algo i hm based on column gene a ion app oach o sol ing he cu ing s ock p oblem. The au ho ocus on how s anda d b anch- and-bound enhancemen ea u es such as ea ly b anching, a iable ixing, and he use o cu ing planes can be inco po a ed in he b anch-and-p ice algo i hm. Then, how o selec app op ia e b anching p io i ies, and implemen a ounding heu is ic. -836- Jou nal o Indus ial Enginee ing and Managemen – h p://dx.doi.o g/10.3926/jiem.1653 Mo e ecen ly, Ka ak, Ripa i, Schei haue and Ku z (2014) used algo i hmic app oach based on exhaus i e enume a ion and in ege linea p og amming o sol e one-dimensional cu ing s ock p oblem (1CSP) wi h espec o he in ege ound-up p ope y (IRUP). Mo eo e , heu is ic me hods ha e g ea e lexibili y in aking in o accoun p oblem speci ic cons ain s and o e a ade-o be ween he quali y o a solu ion and i s compu a ional e o . They a e equi ed o p o ide good, bu no necessa ily op imal solu ions. Some o he new heu is ics me hods ound in he cu en li e a u e a e: (Dikili, Takinacı & Pek, 2008; Ma sumo o e al., 2011; A aujo, Poldi & Smi h, 2014; Che i, A enales & Yanasse, 2013; Ga a a e al., 2014; Cui, Zhong & Yao, 2015). A aujo e al. (2014) p esen s a heu is ics me hod based on gene ic algo i hm o sol e one-dimensional cu ing s ock p oblem by conside ing wo con lic ing objec i e unc ions: minimiza ion o bo h he numbe o objec s and he numbe o di e en cu ing pa e ns used. P e iously, Dyckho (1990) de ined a o mal ypology o cu ing and packing p oblems by sys ema ically in eg a ing a ious kinds o p oblems and no ions. This ypology was imp o ed by Wäesche , HauBne and Schumann (2007) wi h he de ini ion o new ca ego iza ion c i e ia. Table 1 shows he ypology ound in he li e a u e. Dyckho ’s C&P ypology Waesche ’s imp o ed C&P ypology Dimensionali y 1 2 3 N One-dimensional Two-dimensional Th ee-dimensional N-dimensional 1 2 3 N One-dimensional Two-dimensional Th ee-dimensional N-dimensional Kind o assignmen B V All la ge objec s and a selec ion o small objec s A selec ion o la ge objec s and all small objec s OM IM Ou pu alue maximiza ion Inpu alue minimiza ion Asso men o la ge objec s O I D One la ge objec Many iden ical la ge objec s Di e en la ge objec s O SO One La ge objec OA all Fixed dimensions OO one a iable dimension OM mo e a iable dimensions Se e al La ge objec s SI Iden ical La ge objec s SW weakly he e ogeneous asso men SS s ongly he e ogeneous asso men Asso men o small objec s F M R C Few small objec s o di e en igu es Many small objec s o many di e en igu es Many small objec s o ela i ely ew di e en igu es Many iden ical small objec s IS W S Iden ical small i ems Weakly he e ogeneous asso men S ongly he e ogeneous asso men Table 1. Dyckho ’s (1990) and Waesche ’s (2007) ypologies o C&P p oblems -837- Jou nal o Indus ial Enginee ing and Managemen – h p://dx.doi.o g/10.3926/jiem.1653 Dyckho classi ies he solu ion o one dimensional cu ing s ock p oblem in o wo: i em o ien ed and pa e n-o ien ed app oaches. I em o ien ed app oach is cha ac e ized by indi idual ea men o e e y i em o be cu . In he pa e n o ien ed app oach, a i s , o de leng hs a e combined in o cu ing pa e ns, o which - in a succeeding s ep - he cu ing equencies a e de e mined in o de o sa is y he demands. The cons ain s in he pa e n-o ien ed app oach a e based on he algo i hm o Gilmo e and Gomo y (1961, 1963). Howe e , a pa e n-o ien ed app oach is possible only when he s ock is o he same leng h o o se e al s anda d leng hs. An i em-o ien ed app oach is used when all s ock leng hs a e di e en and equencies canno be de e mined. 2.2. One Dimensional Cu ing and Packing Models In he li e a u e, esea che s ha e used di e en exac and heu is ics solu ion app oaches o suppo cu ing s ock decision making in he indus y (Kall a h e al., 2014). Mos ecen ly, Delo me, Io i and Ma ello (2016) p o ides a comp ehensi e e iew o he main ma hema ical models and algo i hms de eloped o exac ly sol ing he one-dimensional bin packing and cu ing s ock p oblems. The p oblems conside ed in hei e iew a e classi ied as 1-dimensional SBSBPP (Single Bin Size Bin Packing P oblem) and 1-dimensional SSSCSP (Single S ock Size Cu ing S ock P oblem). Also, a su ey o cu ing s ock p oblems wi h usable le o e s can be ound in Che i, A enales, Yanasse, Poldi and Vianna (2014) as hese p oblems does no i he classi ica ion based on he ypology p oposed by Wäsche e al. (2007). Mos o he app oaches o sol ing he s anda d cu ing and packing p oblems in a single dimension based on linea p og amming models ha ha e been p oposed can be di ided in o ou ca ego ies: a) The Assignmen Fo mula ions b) The Pa e n-O ien ed Fo mula ions c) The One-Cu Fo mula ions d) The Flow Models 2.2.1. The Assignmen Fo mula ions The i s in ege linea p og amming o mula ion was p oposed by Kan o o ich (1960), based on assignmen o a iables as ollows. (1) -838- Jou nal o Indus ial Enginee ing and Managemen – h p://dx.doi.o g/10.3926/jiem.1653 Subjec o: (2) (3) (4) (5) Whe e: he abo e model has bina y and gene al in ege a iables; wi h yj been he choice o oll j, Xij is he numbe o i ems o size wi assigned o oll j and Wi is he capaci y o he bin i. Equa ion 3 is he knapsack cons ain s, one o each oll, while equa ion 2 is he demand (bi) cons ain s wo king as he linking cons ain s. Whe e n is a known uppe bound on he numbe o olls needed, yj = 1, i oll k is used, and 0 o he wise, and a iable Xij is he numbe o imes i em i is cu in oll j. A lowe bound o he op imum can be ob ained om he op imum o i s LP elaxa ion, which esul s om subs i u ing he wo las cons ain s o 0 ≤ yj ≤ 1 and Xij ≥ 0. Ma ello and To h (1990) showed ha he lowe bound p o ided by he LP elaxa ion can be e y weak. This model’s main d awback is ha i p oduces poo lowe bound wi h la ge was e. Good quali y lowe bounds a e o i al impo ance when using LP based app oaches o sol e in ege p oblems (Ca alho, 2002). 2.2.2. The Pa e n-O ien ed Fo mula ions The pa e n o ien ed model o Gilmo e and Gomo y (1961) ollowed he assignmen o mula ion o Kan o o ich. Gilmo e and Gomo y (1961) o mula ed he cu ing s ock p oblem as an in ege p og amming p oblem. The cu ing s ock p oblem can be modelled as: (6) Subjec o: (7) -839- Jou nal o Indus ial Enginee ing and Managemen – h p://dx.doi.o g/10.3926/jiem.1653 (8) (9) (10) Whe e, L is he leng h o he objec s in s ock; li is he leng h o he i ems, i = 1, 2, …, m; bi ep esen s he demand o i em i, i = 1, 2, …, m; Aj = (a1j, …, aij, …, amj)T be a cu ing pa e n, i = 1, 2, …, n, whe e aij is he numbe o i ems i in he pa e n; Xj be he equency ha he pa e n j is cu . The di icul y in using his model is he la ge numbe o pa e ns o be enume a ed in p ac ical p oblems. Since, he possible pa e ns numbe s inc eases exponen ially as he numbe o di e en i ems and he demands inc eases. 2.2.3. The One-Cu Fo mula ions In he one-cu models, independen ly p oposed by Rao (1976) and Dyckho (1981), he p inciple is o de e mine how o apply a single cu (a one-cu ) on an o iginal o esidual piece o ma e ial. A one-cu di ides he aw ma e ial in wo pieces: an o de ed i em and a esidual objec as shown in he igu e below. Figu e 1. One-Cu -840- Jou nal o Indus ial Enginee ing and Managemen – h p://dx.doi.o g/10.3926/jiem.1653 The la e pa can be im loss, a po ion o be cu u he , o ano he o de ed wid h. The model p oposed by Dyckho conside s he case in which di e en s ock leng hs a e a ailable. In he sequel, D ep esen s he se o i em wid hs o cu om he s ock olls whose leng hs belong o S = {W1, ..., WK}. The se o esidual objec s whose leng h is su icien ly la ge o cu an i em is deno ed by R. The decision a iables yp,q indica e he numbe o imes a piece wi h leng h p is o be cu so as o p oduce an i em o wid h q, and a esidual objec o wid h p−q. The zk a iables indica e he numbe o s ock olls wi h leng hs Wk ha a e used. The Dyckho ’s model is as ollows: (11) Subjec o: (12) (13) (14) (15) (16) Whe e, S is he se o he (sizes o he) o iginal objec s, p ∈ {W1, W2, …, WK}  N R be he se o he (sizes o he) esidual pieces ob ained a e cu ing an i em om an objec o a esidual piece i sel D be he se o he (sizes o he) i ems q ∈{w1, w2, …, wm} ⊂N. We assume wi hou loss o gene ali y ha S ∩ D = Φ yp,q be he numbe o pieces o size p ha a e di ided in o a piece o size q, and a esidual piece o size p – q zk deno es he numbe o objec s o size Wk used Nq s ands o he demand o i ems o size q Bp is he numbe o objec s o size p in s ock, p = 1, 2, …, K. -841- Jou nal o Indus ial Enginee ing and Managemen – h p://dx.doi.o g/10.3926/jiem.1653 The majo disad an age o his model is he inc easing numbe o a iables as he numbe o i ems inc eases. The possible sizes o esidual pieces can be la ge and hey need o be enume a ed o sol e he p oblem. This model also canno be ex ended, a leas in a s aigh o wa d manne o bi-dimensional o mul idimensional cu ing s ock p oblems. 2.2.4. The Flow Models The a c low o mula ions a e based on low a iables. Le G = (V, A) be an acyclic di ec ed g aph wi h e ices V = {0, 1, 2,…, W} whe e W is he size o he objec in s ock and A = {(i, j ): 0 ≤ i < j ≤ W} is he se o a cs. The e exis s a di ec ed a c (i, j ) in his g aph G i he e is an i em d o size wd and j – i = wd. Ca alho (1999) modelled he one-dimensional cu ing s ock p oblem as an a c low model. In his model, a uni o low om node 0 o node W co esponds o a cu ing pa e n since i de ines a pa h om node 0 o node W whe e he addi ion o he sizes o he i ems in co espondence o he a cs in his pa h is smalle han he size o he objec . The ma hema ical o mula ion o he a c low model is gi en below: (17) Subjec o: (18) (19) (20) (21) (22) Whe e, Z is he low in a eedback a c, om e ex W o e ex 0 Xij is he low in a c (i, j ) bd is he demand o i em d, d = 1, 2, …, m. -842- Jou nal o Indus ial Enginee ing and Managemen – h p://dx.doi.o g/10.3926/jiem.1653 4. The op imal cu ing pa e n is now selec ed by sol ing he LP model (wi h ou applica ion) which minimizes he o al was e. 5. Clicking on sol e bu on on he GB cu ing s ock p og am, he esul s displays on wo di e en abs (Tex solu ion and Visual solu ion espec i ely). 6. The o al s ock ma e ials used (Summa ion o all Xj) is gi en as: (30) To al cos o s ock shee used is es ima ed using equa ion 31 s a ed below. (31) 7. F om he ex solu ion o he LP model, he o al was e (o -cu s) can be e alua ed om he alue o he objec i e unc ion o he model 8. A isual solu ion is p esen ed showing i ems and o -cu s (was e) on each op imal cu ing pa e n wi h di e en colou on he second esul ab. 4. Model Applica ion To demons a e he applicabili y o he model, wo p ac ical cases a e p esen ed in his pape . Case I ela es o he cu ing p oblem encoun e ed a a Fu ni u e and Joine y Company while Case II he cu ing p oblem a a gene al wood wo ks company in Nige ia. Bo h companies a e p i a ely owned. 4.1. Case I Twel e (12) lush doo s a e o be p oduced om 55mm wid h wood o s anda d leng h 12 (3660mm). Fi e 55mm wid h wood can be cu om a s anda d plank, since 10mm wid h is cu o o s aigh en he s anda d plank edges and he blade wid h akes abou 4mm away a each cu . -849- Jou nal o Indus ial Enginee ing and Managemen – h p://dx.doi.o g/10.3926/jiem.1653 Pa Numbe Pa Leng h(mm) Numbe Requi ed o a Doo To al Numbe Requi ed 1 2000 2 24 2 710 4 48 3 540 2 24 4 620 2 24 5 625 5 60 Table 2. Requi emen s o he O de F om he cu en p ac ice in he company I, hi een (13) planks we e used o ul il his ask. Since, a plank o dina ily yields i e 55mm wid h wood, he e o e a o al o six y- i e (65) 55mm wid h wood is equi ed. The cos pe uni o plank is one housand wo hund ed nai a (#1200). Fi e 55mm wid h wood can be ob ained om a plank; his implies ha a uni o 55mm wid h wood echnically cos s wo hund ed and o y nai a (#240). 4.2. Case II Two p oduc s we e selec ed ou o he da a collec ed om Company II. The p oduc s a e as ollows: 4.2.1. P oduc I: Con e ence Chai s Tables 3 and 4 summa ise he da a equi ed o p oduce 30 pieces o con e ence chai s as equi ed. Wid h Numbe Used Planks Used 9cm 32 11 7cm 10 3 5cm 12 2 To al Planks Used 16 Table 3. Numbe o s ock leng h used by cu en p ac ice o p oduce he chai s -850- Jou nal o Indus ial Enginee ing and Managemen – h p://dx.doi.o g/10.3926/jiem.1653 Pa s Componen Leng h (cm) Numbe pe Chai Numbe Used 9cm wid h 1 A ms 64 2 60 2 F on legs 58 2 60 3 C osses (F on & Back) 54 2 60 7cm Wid h 1 Sides 58 2 60 5cm Wid h 1 Back legs 68 2 60 Table 4. De ails o Pa s lis o he con e ence chai 4.2.2. P oduc II: Panel Doo s The s anda d size o a panel doo is 206cm X 84cm. Cu en p ac ice e ealed ha en (10) panel doo s a e p oduced om hi y (30) planks based on he p esen cu ing echnique. A panel doo consis s o h ee di e en ypes o he s ock ma e ial om which each equi ed leng h is ob ained. These a e o wid hs 28cm, 15cm and 10cm. The de ails o each equi ed componen is gi en on Table 5 below. Pa s Componen Leng h (cm) Numbe pe Doo Numbe Used 28cm wid h 1 Small panel 32 2 20 2 La ge panel 64 4 40 15cm Wid h 1 Up igh 206 2 20 2 C osses 76 3 30 10cm Wid h 1 C osses 76 3 30 2 V. small c oss 33 1 10 Table 5. De ails pa s lis o he Panel Doo s -851- Jou nal o Indus ial Enginee ing and Managemen – h p://dx.doi.o g/10.3926/jiem.1653 5. Resul s and Discussion The So wa e p esen s esul s in wo o ms: The ex solu ion and he isual solu ion. The ex solu ion gi es he desc ip ion o pa e ns o be cu , o al numbe o s ock o be used and i s cos ; while isual solu ion shows he diag am o how he op imal pa e n is o be cu . F om Table 6, he model ecommends he o al s ock (55mm wid h wood) o be used is 42. Since, i e pieces 55mm wid h wood a e ob ained om a plank; o y- wo (42) 55mm wid h wood will gi e 8.4planks (app oxima ely 9 s anda d size planks should be used). Nine planks yield o y- i e 55mm wid h wood, he eby allowing wo 55mm wid h wood o be kep as ese e in case o mis akes while cu ing. Figu e 4 shows he op imal cu ing pa e ns o be used. The esul s ob ained show ha 9 planks should be used ins ead o he cu en 13, which esul in a sa ing o 30.7%. 5.1. Tex Solu ion The ex solu ion ob ained om he model can be summa ized below: Pa e n No. ( j ) LP Solu ion ( Xj ) Numbe Cu Leng hs (mm) To al Was e( WjXj ) mm 2000 710 625 620 540 2 21.6 22 22 44 - - - 5280 8 2.4 2 2 - - - 8 120 9 0.96 1 - 5 - - - 110 35 15 15 - - 60 15 15 0 50 1.8 2 - - - 10 2 40 To al 41.76 42 24 49 60 25 25 5550 Table 6. Solu ion o Case I p oblem (Flush Doo ) Pa e n No. ( j ) LP Solu ion ( Xj ) Numbe Cu Leng h (cm) To al Was e ( WjXj ) cm 64 58 54 3 15 15 60 - 30 30 21 15 15 - 60 30 390 To al 30 30 60 60 60 420 Table 7. Numbe o 9cm wid h o be used o p oduce P oduc I (Case II) -852- Jou nal o Indus ial Enginee ing and Managemen – h p://dx.doi.o g/10.3926/jiem.1653 Pa e n No. ( j ) LP Solu ion ( Xj ) Numbe Cu Wid h (cm) To al Was e ( WjXj ) cm 9 7 5 1 3.17 4 12 - - 12 2 10 10 20 10 10 - 7 0.5 1 1 - 4 1 To al 13.67 15 33 10 14 13 Table 8. To al numbe o planks o be used o Case II P oduc I (Con e ence Chai s) Pa e n No. ( j ) LP Solu ion ( Xj ) Numbe Cu Leng h (cm) To al Was e ( WjXj ) cm 64 32 2 8 8 40 8 112 7 1.09 2 - 22 28 To al 9.09 10 40 30 420 Table 9. Numbe o 28cm wid h o be used o p oduce P oduc II (Case II) Pa e n No. ( j ) LP Solu ion ( Xj ) Numbe Cu Leng h (cm) To al Was e ( WjXj ) cm 206 76 1 5 5 5 - 800 2 15 15 15 30 120 To al 20 20 20 30 920 Table 10. Numbe o 15cm wid h o be used o p oduce P oduc II (Case II) Pa e n No. ( j ) LP Solu ion ( Xj ) Numbe Cu Leng h (cm) To al Was e ( WjXj ) cm 76 33 2 6.92 7 28 7 203 3 0.77 1 3 4 6 To al 7.69 8 31 11 209 Table 11. Numbe o 10cm wid h o be used o p oduce P oduc II (Case II) Pa e n No. ( j ) LP Solu ion ( Xj ) Numbe Cu Leng h (cm) To al Was e ( WjXj ) cm 28 15 10 1 10 10 10 - - 20 2 10 10 - 20 - 0 4 2.67 3 - - 9 0 To al 22.67 23 10 20 9 420 Table 12. Solu ion o Case II P oduc II (Panel Doo ) -853- Jou nal o Indus ial Enginee ing and Managemen – h p://dx.doi.o g/10.3926/jiem.1653 5.2. Visual Solu ion Figu e 4 p esen an illus a ion o he isual solu ion ab o he applica ion. This shows he numbe o each i em p oduced pe pa e n and he o – cu s (was e). Simila ly, GB Cu ing S ock P og am p o ides isual solu ion o all o he cu ing plan solu ions. In addi ion, implemen ing he cu ing pa e ns esul shown in Tables 7 and 8 espec i ely o he con e ence chai s e eals ha i een (15) planks mus be consumed as agains he 16 planks used. This gi es a sa ing o 6.25% o he o ganisa ion. In a la ge scale ope a ion, he sa ings could be subs an ial in mone a y e ms. Simila ly, implemen ing he cu ing pa e ns esul shown Tables 9-12 espec i ely o p oduce he panel doo s shows ha wen y- h ee (23) planks a e equi ed ins ead o hi y (30) planks used. This leads o a ne sa ing o 23.3% when compa ed o he numbe o planks used by he o me cu ing plan. Figu e 4. Op imal Cu ing Plans o he lush doo p oblem. -854- Jou nal o Indus ial Enginee ing and Managemen – h p://dx.doi.o g/10.3926/jiem.1653 5.3. Compa ison S udy To e alua e he e iciency o GB cu ing s ock p og am, wo comme cial so wa es ha ha e execu able ial e sion a ailable on he in e ne was used o sol e he p oblem p esen ed in case I. The summa y esul s ob ained a e as shown on Table 13. So wa e Ma e ials Used Pa e n Used To al Was e (mm) Ma e ials To al Cos (#) GB Cu ing P og am 42 5 5,550 10,080.00 A 42 6 6,300 10,080.00 B 44 6 13,620 10,560.00 Table 13. Numbe o ma e ials, pa e n used, o al was e and cos by each p og am The websi e o he comme cial so wa es a e lis ed on appendix I as A and B. Comme cial so wa e package A p oduce he same op imal esul as ou cu ing s ock p og am in e ms o ma e ial used and u ilized 6 pa e ns as shown in Figu e 5 o implemen he same esul . While comme cial so wa e package B used he same numbe o pa e ns wi h so wa e A bu mo e ma e ials han bo h GB cu ing p og am and A. The e o e, GB cu ing s ock is be e because i uses less numbe o pa e ns and educes ope a ion ime han A and B. See appendix II o op imal cu ing pa e ns solu ion using so wa e B. Figu e 5. Op imal Cu ing Plans gene a ed using package A -855- Jou nal o Indus ial Enginee ing and Managemen – h p://dx.doi.o g/10.3926/jiem.1653 Also, conduc ing p ice su ey on comme cial so wa e packages e eals ha i would cos wi hin $100 - $400 (20,000 - 78,000 local cu ency) o pu chase a license. This is cos ly o local woodwo k indus y in Nige ia which canno ansac in in e na ional cu ency. Thus, GB cu ing s ock p o ides easy o use p og am wi h no p io compu e knowledge o local woodwo king indus y. 6. Conclusion The cu ing s ock model and a pa e n gene a ion algo i hm we e de eloped. The algo i hm was coded using VisualBasic.ne and a ee linea p og amming sol e called lpsol edll (dynamic link lib a y) was in eg a ed o de elop a one dimensional cu ing s ock p og am named GB cu ing s ock p og am. The cu ing s ock model signi ican ly educes ma e ial was e, elimina es calcula ing e o s, d as ically educes ope a o mis akes and minimizes he o al s ock used, he eby imp o es p oduc i i y. Also, he esul s ob ained we e compa ed agains he bes solu ion gene a ed by wo comme cial so wa es o he same p oblem. I can be concluded ha GB cu ing s ock p og am yielded a e y good esul a easonable compu a ional ime and pe o ms be e han he comme cial so wa e in e ms o ope a ional e iciency ha is i equi es less ime o implemen esul s. Finally, due o i s a o dabili y; implemen ing ou esul yielded a signi ican cos sa ings o abou 30.7% o company-I when he o al s ock ma e ials used is compa ed wi h he o me cu ing plan. Acknowledgemen s We would like o hank he B i ish Council o suppo ing his wo k unde he AKTP (A ican Knowledge T ans e Pa ne ship) ini ia i e wi h a G an . We also hank he anonymous e e ees o hei help ul commen s and all hose who made sugges ions as o making he applica ion simple o use in p ac ice. Re e ences A aujo, S.A., Poldi, K.C., & Smi h, J. (2014). A Gene ic Algo i hm o he One Dimensional Cu ing S ock P oblem wi h Se ups. Pesquisa Ope acional, 34(2), 165-187. h p://dx.doi.o g/10.1590/0101- 7438.2014.034.02.0165 Ca alho, J.M.V. (1999). Exac solu ion o bin-packing p oblems using column gene a ion and b anch-and-bound. Annals o Ope a ions Resea ch, 86, 629-659. h p://dx.doi.o g/10.1023/A:1018952112615 -856- Jou nal o Indus ial Enginee ing and Managemen – h p://dx.doi.o g/10.3926/jiem.1653 Ca alho, J.M.V. (2002). LP Models o Bin Packing P oblem and Cu ing S ock P oblems. Eu opean Jou nal o Ope a ional Resea ch, 141, 253-273. h p://dx.doi.o g/10.1016/S0377-2217(02)00124-8 Che i, A.C., A enales, M.N., & Yanasse, H.H. (2013). The usable le o e one-dimensional cu ing s ock p oblem—a p io i y-in-use heu is ic. In e na ional T ansac ions in Ope a ions Resea ch, 20, 189-199. h p://dx.doi.o g/10.1111/j.1475-3995.2012.00868.x Che i, A.C., A enales, M.N., Yanasse, H.H., Poldi, K.C., & Vianna, A.C.G. (2014). The one-dimensional cu ing s ock p oblem wi h usable le o e s – A su ey. Eu opean Jou nal o Ope a ional Resea ch, 236(2), 395-402. h p://dx.doi.o g/10.1016/j.ejo .2013.11.026 Cui, Y., Zhong, C., & Yao, Y. (2015). Pa e n-se gene a ion algo i hm o he one-dimensional cu ing s ock p oblem wi h se up cos . Eu opean Jou nal o Ope a ional Resea ch, 243, 540-546. h p://dx.doi.o g/10.1016/j.ejo .2014.12.015 Delo me, M., Io i, M., & Ma ello, S. (2016). Bin packing and cu ing s ock p oblems: Ma hema ical models and exac algo i hms. Eu opean Jou nal o Ope a ional Resea ch, 255, 1-20. h p://dx.doi.o g/10.1016/j.ejo .2016.04.030 Dikili, A.C., Takinacı, A.C., & Pek, N.A., (2008). A new heu is ic app oach o one-dimensional s ock-cu ing p oblems wi h mul iple s ock leng hs in ship p oduc ion. Ocean Enginee ing, 35(7), 637-645. h p://dx.doi.o g/10.1016/j.oceaneng.2008.01.003 Dyckho , H. (1981). A New Linea P og amming App oach o he Cu ing S ock P oblem. Ope a ions Resea ch, 29(6), 1092-1104. Published by INFORMS S able URL: h p://www.js o .o g/s able/170363 h p://dx.doi.o g/10.1287/op e.29.6.1092 Dyckho , H. (1990). A ypology o cu ing and packing p oblems. Eu opean Jou nal o Ope a ional Resea ch, 44, 145-159. h p://dx.doi.o g/10.1016/0377-2217(90)90350-K Ga a a, M., Salassa, F., Vanc oonenbu g, W., Be ghe, G.V., & Wau e s, T. (2014). The one-dimensional cu ing s ock p oblem wi h sequence-dependen cu losses. In e na ional T ansac ions in Ope a ions Resea ch, 00, 1-20. Gilmo e, P.C., & Gomo y, R.E. (1961). A linea p og amming app oach o he cu ing s ock p oblem. Ope a ions Resea ch, 9, 849-859. h p://dx.doi.o g/10.1287/op e.9.6.849 Gilmo e, P.C., & Gomo y, R.E. (1963). A linea p og amming app oach o he cu ing s ock p oblem: Pa II. Ope a ions Resea ch, 11, 863-888. h p://dx.doi.o g/10.1287/op e.11.6.863 -857- Jou nal o Indus ial Enginee ing and Managemen – h p://dx.doi.o g/10.3926/jiem.1653 Kall a h, J., Rebennack, S., Kall a h, J., & Kusche, R. (2014). Sol ing eal-wo ld cu ing s ock-p oblems in he pape indus y: Ma hema ical app oaches, expe ience and challenges. Eu opean Jou nal o Ope a ional Resea ch, 238, 374-389. h p://dx.doi.o g/10.1016/j.ejo .2014.03.027 Kan o o ich, L.V. (1960). Ma hema ical models o o ganizing and planning p oduc ion. Managemen Science, 6, 366-422. T ansla ed om he Russian o iginal, 1939. h p://dx.doi.o g/10.1287/mnsc.6.4.366 Ka ak, V.M., Ripa i, A.V., Schei haue , G., & Ku z, S. (2014). Minimal p ope non-IRUP ins ances o he one-dimensional cu ing s ock p oblem. Disc e e Applied Ma hema ics, 187. h p://dx.doi.o g/10.2139/ss n.2440742 Ma ello, S., & To h, P. (1990). Lowe bounds and educ ion p ocedu es o he bin packing p oblem. Disc e e Applied Ma hema ics, 28, 59-70. h p://dx.doi.o g/10.1016/0166-218X(90)90094-S Ma sumo o, K., Ume ani, S., & Nagamochi, H. (2011). On he one-dimensional s ock cu ing p oblem in he pape ube indus y. Jou nal o Scheduling, 14(3), 281-290. h p://dx.doi.o g/10.1007/s10951-010-0164-2 Mu a , E.B., U a , N., & Ahme , Y. (2011). A so wa e o he one-dimensional cu ing s ock p oblem. Jou nal o King Saud Uni e si y (Science), 23(1), 69-76. h p://dx.doi.o g/10.1016/j.jksus.2010.06.009 Rao, M.R. (1976). On he cu ing s ock p oblem. Jou nal o he Compu e Socie y o India, 7, 35-39. Vande beck, F. (1999). Compu a ional s udy o a column gene a ion algo i hm o bin packing and cu ing s ock p oblems. Ma hema ical P og amming, 86, 565-594. h p://dx.doi.o g/10.1007/s101070050105 Waesche , G., HauBne , H., & Schumann, H. (2007). An Imp o ed Typology o Cu ing and Packing P oblems. Eu opean Jou nal o Ope a ional Resea ch, 183, 1109-1130. h p://dx.doi.o g/10.1016/j.ejo .2005.12.047 Yang, C., Sung, T., & Weng, W. (2006). An imp o ed abu sea ch app oach wi h mixed objec i e unc ion o one-dimensional cu ing s ock p oblems. Ad ances in Enginee ing So wa e Ad ances in Enginee ing So wa e, 37(8), 502-513. h p://dx.doi.o g/10.1016/j.ad engso .2006.01.005 -858-