A TWO-STEP MATH HEURISTIC SOLUTION APPROACH FOR THE TWO-DIMENSIONAL CUTTING STOCK PROBLEM

In this paper, we propose a two-step mathematical programming based heuristic solution approach to the two-dimensional guillotine cutting stock problem. In the first step, we assign all products that must be cut to stocks without regard to placement limits. The mathematical model built in this step imposes only area constraints and produces the demand list assigned to every stock. In the second step, we construct a mathematical model which generates a cutting pattern for the demand list produced in the first step from the matching stock material, by taking length and width limits and relevant assumptions into account. Because we do not enforce the placement constraints in the first step and solve the problem in the second step for only one stock and fewer items allotted to this stock (in the first step), both models are rapid and straightforward to solve. A two-step genetic algorithm based solution strategy that employs a problemspecific placement heuristic for solving the suggested mathematical models is developed. The performance of the suggested solution approach is tested on 30 problem instances from the literature, and the results are compared with those obtained by using both the GAMS software and the genetic algorithm.