Title: Solving a weighted set covering problem for improving algorithms for cutting stock problems with setup costs by solution merging
Language: English
Authors: Klocker, Benedikt 
Qualification level: Diploma
Advisor: Raidl, Günther 
Issue Date: 2019
Number of Pages: 83
Qualification level: Diploma
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.
Keywords: Set Covering problem; Cutting stock problem; Metaheuristiken; ganzzahlige lineare Programmierung
Set covering problem; cutting stock problem; metaheuristics; integer linear programming
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-124214
Library ID: AC15353154
Organisation: E192 - Institut für Logic and Computation 
Publication Type: Thesis
Appears in Collections:Thesis

Files in this item:

Page view(s)

checked on Jul 25, 2021


checked on Jul 25, 2021

Google ScholarTM


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.