Article Preview
TopIntroduction
One-dimensional cutting stock problem (CSP) occurs in different industrial processes (Abuabara & Murabito, 2009; Alfieri, van de Velde, & Woeginger, 2007; Arbib, Marinelli, Rossi, & di Iorio, 2002; Hajizadeh & Lee, 2007; Stadtler, 1990; Tsai, Hsieh, & Huang, 2009). Many exact or heuristic methods based on item-oriented (Gradisar, Resinovic, Jesenko, & Kljajic, 1999a), pattern-oriented (Gilmore & Gomory, 1961; Umetami, Yagiura, & Ibaraki, 2003) or mixed (Gradisar, Kljajic, & Resinovic, 1999b) approach for solving CSP have been developed. Exact methods (Alves & de Carvalho, 2008; Amor, Desrosiers, & de Carvalho, 2006; Cordeau 2006) offer optimal solutions but they can be used to solve only small-size instances.
The cutting stock problem with usable leftover (CSPUL) is CSP where is assumed that leftovers larger than some minimal length defined by decision maker are returned to stock in order to be used in future cutting plans. The most comprehensive description of methods for solving CSPUL is offered by Cherri, Arenales and Yanasse (2009). They introduced modifications in some well-known heuristics to solve the one dimensional CSPUL. The heuristics are divided in two groups. The first group contains four constructive heuristics based on the exhaustive repetition (Hinxman, 1980) and the second ten residual heuristics which find an integer solution from the linear relaxation of the integer programming problem, proposed by Gilmore and Gomory (1963). They carried out an extensive comparison of modified traditional methods with two existing methods for CSPUL: COLA (Gradisar, Jesenko, & Resinovic, 1997) and CUT (Gradisar et al., 1999a). Both are item-oriented method based on the exhaustive repetition. CUT is later and more generalized version of COLA. CUT and COLA are estimated as acceptable solutions especially for solving problems of moderate sizes because they are more computationally time consuming than other comparable methods. From modified traditional methods the best results can be expected from RGR method (Cherri et al., 2009) of the second group. The most recent CSPUL method was proposed by Cui and Yang (2010) but is not directly comparable with CUT because it assumes that there can be several leftovers in the cutting plan longer than the longest order.
Currently available methods for solving CSPUL can lead to results with a very low trim loss (Cui & Yang, 2010) which means that further considerable trim loss reductions are hardly possible. For example the enhancement of the method developed in Gradisar and Trkman (2005) leads to the reduction of trim loss from 0.025% to 0.015%. Although the improvement is 60% it presents very small contribution in reduction of company costs.
The trim loss does not depend only on optimization method but also on the nature of the problem. In practical case described in Erjavec, Trkman and Gradisar (2009) one-dimensional CSPUL with an average trim loss of 15% can be found. The reason for that is a very low stock-to-order length ratio. Since the literature does not offer a definition of low stock-to-order length ratio we can define it as follows: stock-to-order length ratio is low if it is smaller than some threshold t. Since there are several different order and stock lengths in any problem instance, the ratio of stock length to order length can be e.g.