Penyelesaian Masalah Pemotongan Rol Kertas dengan Metode Penghasil Kolom

Abstract

Paper industry produces paper rolls called jumbo rolls using paper machines. The paper rolls are then cut into rolls with different widths. The widths of rolls are determined by the customers demands and the different number of ordered rolls so that it is necessary to have an organization of cutting pattern from a jumbo into small rolls. The organization of cutting pattern aims to minimize the number of jumbo rolls used and rest of cutting.

This research implements a column generation method to solve the problem. The column generation method is one of the linear programming techniques for the problem of supplies cutting. The iteration of column generation method uses revised simplex and knapsack problem with the completion of branch-and-bound method. If a solution is not an integer, the solution is converted into the integer using the first-fit decreasing method. Then, a display program with MATLAB is made based on the column generation algorithm. In this program, the solution may be in form of the number of rolls or the weight of rolls.

Numerical examples are then carried out to show the effectiveness of the method. Based on the result of the simulation, the optimal solution is obtained, namely the minimum number of jumbo rolls and rest for several incoming order cases. In comparison to the manual calculation commonly practiced by paper industry, the results are well fitted. However, for big problems our approach is better because manual calculation is almost impossible to be done due to the expanding number of possible cutting pattern combinations.