Penyelesaian Masalah Pemotongan Rol Kertas dengan Metode Penghasil Kolom

Rosa Ajeng Mahadika, Hartono Ph.D


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.

Full Text:



B. Susanta. Program Linear. Jakarta: Depdikbud. 1996.

B. Harsanto, MM. Naskah Tutorial QM for Windows. Bandung. 2011.

J. Bisschop. A Cutting Stock Problem. AIMMS Optimization Modeling. AIIMS B.V. 2016; 235-244.

K. B. Parmar, dkk. Cutting Stock Problem: A Survey of Evolutionary Computing Based Solution in 2014 International Conference on Green Computing Communication and Electrical Engineering, 2014.

J. Desrosiers, Marco E. Lubbecke. A Primer in Column Generation. Springer. 2005.

M. E. Lubbecke. Column Generation. Wiley Encyclopedia of Operations Research and Management Science (EORMS). 2010.

M. E. Lubbecke, Jacques Desrosiers. Selected Topics in Column Generation. Operations Research. Informs. 2005.

V. Chvatal. Linear programming. New York: W. H. Freeman and Company. 1983.