Solving a weighted set covering problem for improving algorithms for cutting stock problems with setup costs by solution merging

Abstract

Cutting stock problems occur in many industrial applications where parts have to be cut out of raw materials. Most of the algorithms for solving such problems involve producing many cutting patterns during their execution. We propose a set cover approach which makes use of those produced patterns and searches for the best combination of a subset of them to cover all demands. To solve the problem we propose four methods: an integer linear program (ILP) model, a greedy construction heuristic, a PILOT approach, and a beam search procedure. These algorithms are relatively independent from many specifics of the concrete variant of cutting stock problem to be solved. Furthermore, we propose a hybrid combination of the greedy set cover approach and a problem dependent construction heuristic. The methods work especially well on problems with setup costs, which are costs for each type of used pattern. In cases with setup costs it is enough to have a problem specific algorithm which ignores pattern setup costs. The set cover approach then optimizes the solution with regard to the pattern setup costs. We test our approaches for the K-staged two-dimensional cutting stock problem with variable sheet size and pattern setup costs. As a result of the testing, we can statistically significantly conclude that the ILP model works best on small instances, the greedy and the hybrid algorithms work best on large instances and the PILOT and beam search approach work better than the greedy and hybrid on small and medium-sized instances. Furthermore, the algorithms can improve over 50% of the tested solutions given by a problem specific algorithm if pattern setup costs are active.