<div class="csl-bib-body">
<div class="csl-entry">Klocker, B. (2019). <i>Solving a weighted set covering problem for improving algorithms for cutting stock problems with setup costs by solution merging</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2019.64801</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2019.64801
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/8448
-
dc.description.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.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Set Covering problem
de
dc.subject
Cutting stock problem
de
dc.subject
Metaheuristiken
de
dc.subject
ganzzahlige lineare Programmierung
de
dc.subject
Set covering problem
en
dc.subject
cutting stock problem
en
dc.subject
metaheuristics
en
dc.subject
integer linear programming
en
dc.title
Solving a weighted set covering problem for improving algorithms for cutting stock problems with setup costs by solution merging
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.identifier.doi
10.34726/hss.2019.64801
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Benedikt Klocker
-
dc.publisher.place
Wien
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
tuw.publication.orgunit
E192 - Institut für Logic and Computation
-
dc.type.qualificationlevel
Diploma
-
dc.identifier.libraryid
AC15353154
-
dc.description.numberOfPages
83
-
dc.identifier.urn
urn:nbn:at:at-ubtuw:1-124214
-
dc.thesistype
Diplomarbeit
de
dc.thesistype
Diploma Thesis
en
dc.rights.identifier
In Copyright
en
dc.rights.identifier
Urheberrechtsschutz
de
tuw.advisor.staffStatus
staff
-
tuw.advisor.orcid
0000-0002-3293-177X
-
item.languageiso639-1
en
-
item.fulltext
with Fulltext
-
item.openaccessfulltext
Open Access
-
item.mimetype
application/pdf
-
item.openairetype
master thesis
-
item.grantfulltext
open
-
item.openairecristype
http://purl.org/coar/resource_type/c_bdcc
-
item.cerifentitytype
Publications
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity