DC FieldValueLanguage
dc.contributor.advisorRaidl, Günther-
dc.contributor.authorKlocker, Benedikt-
dc.date.accessioned2020-06-29T20:31:03Z-
dc.date.issued2019-
dc.date.submitted2019-04-
dc.identifier.urihttps://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-124214-
dc.identifier.urihttp://hdl.handle.net/20.500.12708/8448-
dc.description.abstractCutting 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.formatix, 83 Seiten-
dc.languageEnglish-
dc.language.isoen-
dc.subjectSet Covering problemde
dc.subjectCutting stock problemde
dc.subjectMetaheuristikende
dc.subjectganzzahlige lineare Programmierungde
dc.subjectSet covering problemen
dc.subjectcutting stock problemen
dc.subjectmetaheuristicsen
dc.subjectinteger linear programmingen
dc.titleSolving a weighted set covering problem for improving algorithms for cutting stock problems with setup costs by solution mergingen
dc.typeThesisen
dc.typeHochschulschriftde
dc.publisher.placeWien-
tuw.thesisinformationTechnische Universität Wien-
tuw.publication.orgunitE192 - Institut für Logic and Computation-
dc.type.qualificationlevelDiploma-
dc.identifier.libraryidAC15353154-
dc.description.numberOfPages83-
dc.identifier.urnurn:nbn:at:at-ubtuw:1-124214-
dc.thesistypeDiplomarbeitde
dc.thesistypeDiploma Thesisen
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.openaccessfulltextOpen Access-
item.openairetypeThesis-
item.openairetypeHochschulschrift-
item.fulltextwith Fulltext-
item.languageiso639-1en-
item.grantfulltextopen-
item.cerifentitytypePublications-
item.cerifentitytypePublications-
Appears in Collections:Thesis

Files in this item:


Page view(s)

25
checked on Sep 21, 2021

Download(s)

76
checked on Sep 21, 2021

Google ScholarTM

Check


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