PENYELESAIAN MASALAH CUTTING STOCK DENGAN PENGELASAN MENGGUNAKAN TEKNIK COLUMN GENERATION

Abstract

The cutting stock problem with welding is a problem for cutting a number of raw materials into a number of cutting patterns to meet every demand such that the raw material needed is minimum. In this study, column generation techniques are used to solve the problem. The technique contains two models i.e the master model and the column generator submodel. The master model is a linear programming model that is used to determine the minimum number of raw materials needed to meet the needs according the cutting patterns. The submodel is constructed to generate a new cutting pattern that will improve the optimal solution of the master model. The column generation step is complete if there is no cutting pattern that can give the better solution. Since column generation technique does not always produce integer solutions, an additional mixed integer programming model is needed to meet unmet demands. The computationl results show that column generation techniques can solve cutting stock problems with welding, and it can give an optimal solution.