Pendekatan Linear Programming Untuk Persoalan Pemotongan Stok (Pola Pemotongan Satu Dimensi)

Abstract

In this study, one-dimensional cutting pattern is discussed. This includes fulfilling demands for some items with different lengths by cutting some stocks of standard length available. In this problem, the patterns – the way the standard length is cut – is obtained in such an optimal ways that the trim loss becomes as minimum as possible. The decision variables are the amount of the standard lengths cut according to certain patterns. Then the problem is formulated into a linear programming model. Due to very large number of the variables and restriction to integers, the problem is the type of large scale linear integer programming. For simplicity, restriction to integer is dropped. Then the very large number of the variables is handled by considering only the favorable cutting patterns; list of all possible
ways in which a standard stock may be cut is not needed. The favorable cutting pattern is then generated by using column generation technique by solving auxiliary problem in the form of a knapsack problem. The integer optimal solution is obtained by rounding it upward