A Least-Loss Algorithm for a Bi-Objective One-Dimensional Cutting-Stock Problem

A Least-Loss Algorithm for a Bi-Objective One-Dimensional Cutting-Stock Problem

Hesham K. Alfares (King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia) and Omar G. Alsawafy (King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia)
Copyright: © 2019 |Pages: 19
DOI: 10.4018/IJAIE.2019070101

Abstract

This article presents a new model and an efficient solution algorithm for a bi-objective one-dimensional cutting-stock problem. In the cutting-stock—or trim-loss—problem, customer orders of different smaller item sizes are satisfied by cutting a number of larger standard-size objects. After cutting larger objects to satisfy orders for smaller items, the remaining parts are considered as useless or wasted material, which is called “trim-loss.” The two objectives of the proposed model, in the order of priority, are to minimize the total trim loss, and the number of partially cut large objects. To produce near-optimum solutions, a two-stage least-loss algorithm (LLA) is used to determine the combinations of small item sizes that minimize the trim loss quantity. Solving a real-life industrial problem as well as several benchmark problems from the literature, the algorithm demonstrated considerable effectiveness in terms of both objectives, in addition to high computational efficiency.
Article Preview
Top

1. 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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 7: 2 Issues (2020): Forthcoming, Available for Pre-Order
Volume 6: 2 Issues (2019)
Volume 5: 2 Issues (2018)
Volume 4: 2 Issues (2017)
Volume 3: 2 Issues (2016)
Volume 2: 2 Issues (2014)
Volume 1: 2 Issues (2012)
View Complete Journal Contents Listing