A study on the 1.5 dimensional coil slitting problem

Abstract

This thesis considers 1.5 dimensional (1.5D) coil slitting problem. The 1.5D coil slitting problem is a special case of the cutting stock problem which deals with the issue of how to cut out of required pieces from stock materials with given objectives. The problem is named 1.5D since it is more complex than the one dimensional problems, but are not true two dimensional problem due to the relative size of order and materials in each dimension. So we devised special algorithms to solve the problem. In coil slitting problem, we are given coils and orders. And objective function is weighted combination of three values, sum of overproduced amount of orders, sum of unmet amount of orders and sum of slitting loss of coils. We formulated an MIP model of the coil slitting problem. Coil slitting problem consists of two main decisions. One is generating patterns to be used and the other is selecting coils to each generated pattern. So we will solve the problem in two phase in this thesis. To effectively tackle the problem, we investigated the combinatorial nature of the coil slitting problem. Since the problem is obviously NP-hard. The special cases occur when we restrict the variety of size of orders and coils. We provided the special cases which can be solved in polynomial time, and proof of the NP-hardness of difficult cases. We also investigate the relation with one dimensional cutting stock problem for special cases to examine the applicability of known algorithms. In pattern generation phase, we devised the column generation procedure for coil slitting problem. It will be shown that the procedure is a generalization of the column generation procedure for one dimensional cutting stock problem. In coil selection phase, we developed pseudo-polynomial time algorithm which is based on dynamic programming algorithm for the subset sum problem. The algorithm selects optimal subset of coils for the given pattern. Then we provided the computational result to show that the algorithm produces optimal solution in reasonable time to the realistic size problem.