Article Preview
Top1. Introduction And Literature Review
Designing an efficient cutting algorithm is a common engineering activity in many industries. The need for an algorithm has arisen in recent years because competition among enterprises has significantly increased (Hussein, & Dayekh,, (2014); Baporikar (2015); Hosseini-Motlagh et al, (2018)). The problem is defined as follows: Given a “large” rectangle, R, and a finite set, S, of “small” rectangles, find a dissection of the large rectangle that minimizes the “loss,” i.e., the total area of any resulting rectangles that do not belong to set S. In this paper the raw material (R) to be cut is sponge; once cutting is complete, the cut pieces are used in the furniture industry (Miller, G., Pawloski, & Standrigde, 2010, and Bhamu, & Singh Sangwan 2014). The challenge is to find the solution that is the most economical for cutting large objects (200cm x100cm x 100cm sheets of sponge material) for producing smaller objects of specified sizes. In the furniture industry the loss of material due to placement and cutting constraints is an issue of concern and minimizing losses has been the goal of prior optimization efforts (For example Bhuiyan 2011, and Vellorrot, Tolonen., Harkonen, & Haapasalo 2017). have proposed a framework for implementing a new product development (NPD) process meant to achieve this goal.
The problem we are studying has been identified as the Two Dimensional Cutting Stock Problem (2DCSP), where cuts are parallel to one of the sides of the object and run from one side to the opposite one. The first known formulation of cutting stock problems was given by Kantorovich (1960). It was then studied by Gilmore and Gomory (1965), who discussed the pattern generation technique for solving the one dimensional trim loss minimization problem using linear programming. The outcome of this process is a guillotine pattern obtained by a sequence of guillotine cuts applied to the original bin (the first of these being a cut along the entire 13 meter length of the raw material) and then to the subsequent small rectangles that are obtained after each cut. (See Figure 3, where these smaller rectangles are first shown outlined on the 200cm x 100cm x 100cm piece that remains after the first guillotine cut.) A pattern is k-staged if it is obtained after performing k stages of cutting, sometimes with an additional stage to separate an item from a wasted area.
Israni and Sanders (1982) surveyed the progress made on researching the 2DCSP. In a separate review, Haessler and Sweeney (1991) discussed some of the basic formulation issues and procedures for solving these problems in both one and two dimensions, using procedures such as linear programming, sequential heuristic, and hybrid solutions. Cintra et al. (2008) investigated algorithms for two dimensional stock cutting and strip packing problems using dynamic programming and column generation procedures. The results of their study indicate that these algorithms are well-suited for solving real-life problems. Mellouli and Dammak (2008) developed a three-step heuristic algorithm to be implemented in the paper and sheet-metal industries. They first identify all feasible non-dominated combinations through a pattern generation procedure, and construct a constraints matrix. Then, a relaxation of the problem is performed in order to obtain a linear formulation. Finally, a solution to the original problem is generated from the solution of the relaxed problem. Seiden and Woeginger (2005) and Khanam et. al. (2016) gave a complete analysis of the quality of k-stage guillotine strip packaging versus globally optimal packing. Cristofides and Whitlock (1977) present a tree-search algorithm for the solution of the two-dimensional constrained cutting problem. The algorithm limits the size of the tree search by deriving and imposing necessary conditions for the cutting pattern to be optimal. The limits also include using the dynamic programming procedure for the unconstrained problem, together with the node evaluation method based on a transportation routine as sub-algorithms, to produce upper bounds during the search. Results indicate that the algorithm is an effective procedure for solving medium-sized cutting problems.