Article Preview
Top1. Introduction
The trim-loss or cutting stock problem (CSP) is an important applied optimization problem. CSP assumes a given a number of standard sizes of large objects, and customer demands for different quantities of smaller pieces. A CSP solution specifies the number of smaller pieces cut from each large standard-size object. Of course, many smaller-piece cut combinations may not consume the full size of the larger objects, resulting in smaller, unused remainders called trim loss. The main objective of CSP is to minimize the total trim loss (wasted material) left over after cutting all larger objects necessary to satisfy customer orders. In general, optimum solutions are difficult for practical, industrial-size CSP problems. According to Garey and Johnson (1979), CSP is a complex, NP-complete optimization problem. Therefore, heuristic techniques are usually used to solve real-world, applied trim-loss problems.
Cutting stock problems (CSP) are classified according to several criteria, but mainly according to the dimension of the problem. One-dimensional problems (1D-CSP) involve one-dimensional (i.e., length) cut decisions, as in the cutting of paper, fabric, and cable rolls that have the same width. Two-dimensional problems (2D-CSP) involve two-dimensional (i.e., length and width) cut decisions, as in the cutting of wood and glass. Three-dimensional problems (3D-CSP) have very limited applications in industry and in the literature. However, there are few recent exceptions, such as the 3-D knapsack problem considered by Baldi et al. (2012). This paper is concerned with a bi-objective one-dimensional cutting stock problem (1D-CSP).
Dyckhoff (1990) presents a four-criterion typology of cutting and packing problems, considering them as two types of “geometric combinatorics” problems related by material-space duality. Wäscher et al. (2007) enhance Dyckhoff’s classification and propose a five-criterion typology. According to the four-criterion topology of Dyckhoff (1990), the 1D-CSP problem considered in this paper can be classified as a classical cutting stock problem denoted by (1/V/I/R). Here, (1) denotes 1 dimension, (V) indicates all small items must be cut from a selection of large objects, (I) denotes identical (single) size of large objects, and (R) denotes many small items of the same shape. However, the classical cutting stock problem has a single objective (minimizing trim loss), while our problem has two objectives.
One-dimensional problems (1D-CSP) models may consider either a single given size or a few given standard sizes for all available large objects. Most previous 1D-CSP models focus on only minimizing the total trim loss quantity. This paper presents a bi-objective 1D-CSP model with one given large-object size, where the primary objective is to minimize the total amount of trim loss. The second objective is to minimize the number of partially cut large objects. Minimizing the number of partially cut large objects is a real-life objective for many companies, because partially cut objects are generally more difficult to reuse or cut again. Moreover, partially cut stocks are not as easy or profitable to sell as uncut objects.
An integer linear programming (ILP) model of the problem is formulated to determine the optimum number of used large objects, and the cutting pattern for each large object. As the optimum solution of this ILP model is difficult to obtain, a two-stage heuristic least-loss algorithm (LLA) is developed to solve the problem effectively and efficiently. In the first stage, a decreasing order of size is used to assign small items to cutting patterns in order to minimize trim loss. If the solution does not satisfy a specific performance criterion, then a second stage is required in which a different initial order of small items is used. The algorithm is effectively applied to a real-life industrial cutting-stock problem. Moreover, numerical comparisons on benchmark problems are carried out, demonstrating the superior performance of the proposed algorithm.