In fact, many practical applications, such as ship building, shoe, and garment, widely concern irregular nonconvex items. As far as we know, the 2D irregular (nonconvex) cutting stock problem is seldom mentioned in previous researches. presented an adapted heuristic to deal with irregular (convex) bin packing problem. proposed a constructive heuristic to solve 2D irregular (convex) bin packing problem with guillotine constraints. However, the researches devoted to 2D irregular cutting stock problem have not received as much attention as SPP. They still utilized no-fit polygon to reduce geometric complexity. They integrate a greedy bottom-left as placement rule and a genetic algorithm as metaheuristic searching engine. also proposed an approach to solve irregular strip packing problem with nonconvex shapes. They packed shapes with tradition line representation and utilized hill climbing and Tabu search methods. presented a new bottom-left-fill heuristic to solve irregular strip packing problem. Hopper and Turton reviewed the approaches developed to solve 2D strip packing problem with metaheuristic algorithms.
In SPP, only one large strip object with fixed width and variable length is used to pack items and the target is to minimize the length of the strip object after all items are allocated.
The work on packing problems with irregular items mainly focused on strip packing problem (SPP), which is a variant of 2D bin packing problem. Literature ReviewĪ number of researches on rectangular items in 2DCSP have been done in literatures.
In Section 5, the research is concluded and possible issues for future work are suggested. Section 4 gives experimental results on generated instances and real-world instances from ship building industry. The modification of Exact Fit selection heuristic and BLF placement heuristic is presented in detail and other common heuristics in literatures are introduced in Section 3. A brief review of previous work in the field is presented in Section 2. (2) Items must not overlap with each other. Typical assumptions areas follows: (1) All items must be within the stock sheet. It can be described as follows: Given a set of items, size of each one, to be cut from a set of rectangular cutting stock sheets (objects) of size (length and width ), the 2DCSP consist of finding cutting patterns that the solution minimizes the number of stock sheets used. According to the typology of Wäscher, this is Two-Dimensional Single Stock-Size Cutting Stock Problems (2DCSP). (2007) proposed a useful complete problem typology of cutting and packing problems on the basis of Dychoff (1990). This problem is to cut a finite set of two-dimensional irregular items from a couple of stocks such that the number of stocks is minimized. In this paper, we focus on the two-dimensional irregular cutting stock problem. Figure 1 provides an example of a layout from iron and steel industry.Īn example layout from iron and steel industry.Ĭutting and packing problems include knapsack problem, strip packing, bin packing, and cutting stock problem. The main goal is to minimize the number of stocks or bins and maximize the utilization of materials. The basic idea is to find an arrangement of a finite number of items to cut from stocks or pack inside bins. A wide variety of investigations in literatures exist into the two-dimensional cutting and packing problems. IntroductionĬutting and packing problem reflects the large application scope, such as ship building, wood, shoe, garment, steel, and glass manufacturing, packing on shelves or truck beds in transportation and warehousing, and the paging of articles in newspapers. The results demonstrate that the effectiveness and efficiency of the proposed approach are significantly better than some conventional heuristics. We evaluate the proposed approach using generated instance only with convex shapes in literatures and some instances with nonconvex shapes based on real problem from ship building industry. A placement heuristic relating to bottom-left-fill is presented. In the case referring to irregular shapes, a placement heuristics is more important to construct a complete solution. A modification of selection heuristic Exact Fit is applied in our research. Cutting stock problem is a common cutting and packing problem that arises in a variety of industrial applications. This paper presents an efficient approach for solving a real two-dimensional irregular cutting stock problem in ship building industry.