<div class="csl-bib-body">
<div class="csl-entry">Vass, J. (2019). <i>Exact and metaheuristic approaches for the production leveling problem</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2019.70283</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2019.70283
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/6542
-
dc.description.abstract
Im Rahmen dieser Diplomarbeit wird ein neues Problem im Gebiet der mittelfristigen Produktionsplanung eingeführt - das Production Leveling Problem. Dabei besteht die Aufgabe darin, Aufträge zu Produktionsperioden so zuzuteilen, dass die Auslastung der unterschiedlichen Perioden und Produktionsressourcen ausbalanciert wird. Außerdem sollen die Aufträge möglichst in jener Reihenfolge eingeplant werden, die von deren Priorität bestimmt wird. Das Production Leveling Problem ist ein wichtiger Zwischenschritt im mehrstufigen Prozess der Produktionsplanung, weil es dafür sorgt, dass möglichst ausgewogene Auftragsgruppen zum darauffolgenden Scheduling-Schritt gelangen. In dieser Arbeit wird zunächst ein formales Modell des Problems dargestellt und dessen Komplexität theoretisch analysiert. Als exakte Lösungsverfahren werden Mixed-IntegerProgramming und Constraint-Programming untersucht, welche optimale Lösungen für kleine Instanzen sowie untere Schranken beweisen sollen. Um auch große Probleminstanzen lösen zu können, werden in Folge Verfahren auf der Basis von metaheuristischer lokaler Suche erkundet. Dafür warden eine Greedy-Heuristik und zwei Nachbarschaftsstrukturen für die Lokale Suche eingeführt und die Verfahren Variable Neighborhood Descent und Simulated Annealing untersucht. Zur Evaluierung wird ein Set von realistischen Probleminstanzen eines Industriepartners veröffentlicht, sowie zwei zufallsbasierte Instanzgeneratoren. Die Forschungsfrage bezüglich der exakten Methoden ist, wie große Instanzen in einem fixen Zeitraum lösbar sind. Für die metaheuristischen Ansätze soll gezeigt werden, dass kleine Probleminstanzen annähernd optimal gelöst werden können und die Skalierbarkeit bis hin zu sehr großen Instanzen ebenfalls gegeben ist. Die wichtigsten theoretischen Ergebnisse dieser Arbeit stellen das formale Problemmodell sowie ein Beweis der NP-hardness dar, welche mittels Reduktion von Bin-Packing gezeigt wird. Die Evaluierung der Lösungsmethoden kommt zu dem Resultat, dass mithilfe von Mixed-Integer-Programming Instanzen mit bis zu 250 Aufträgen fast immer gelöst werden können, während bei größeren Instanzen meist keine Lösung gefunden wird. Von den untersuchten metaheuristischen Verfahren produziert Simulated Annealing die besten Resultate. Es wird gezeigt, dass kleine Instanzen, für die untere Schranken bewiesen werden konnten, mit durschnittlich weniger als 3% Optimality Gap gelöst werden können. Auf der anderen Seite sind aber auch die größten Instanzen mit tausenden Aufträgen und Dutzenden von Produktionsperioden in der Regel gut lösbar. Die vorgestellten metaheuristischen Verfahren wurden bereits in der Industrie zum Einsatz gebracht.
de
dc.description.abstract
This thesis introduces the Production Leveling Problem, which is a new problem in the field of mid-term production planning. The task is to assign orders to production periods such that the workload in each period and on each production resource is balanced, capacity limits are not exceeded and the orders priorities are taken into account. The Production Leveling Problem is an important intermediate step between long-term planning and the final scheduling of orders within a production period, as it responsible for selecting good subsets of orders to be scheduled within each period. A formal model for the Production Leveling Problem is proposed and the theoretical complexity is analyzed. Mixed Integer Programming and Constraint Programming are investigated as exact methods for solving moderately sized instances of the problem. In order to be able to solve also large problem instances, metaheuristic local search is investigated. A greedy heuristic and two neighborhood structures for local search are proposed, in order to apply them using Variable Neighborhood Descent and Simulated Annealing. A set of realistic problem instances from an industrial partner is contributed to the literature, as well as random instance generators and the instances which were generated for evaluation. Regarding exact techniques, the main question of research is, how large instances can be while still being solvable within a fixed amount of time. For the metaheuristic approaches the aim is to show that they produce near-optimal solution for smaller instances, but also scale well to very large instances. The main theoretical results of this thesis are a formal model of the Production Leveling Problem and the proof of NP-hardness by reduction from Bin Packing. The experimental evaluation conveys that the proposed MIP model works well for instances with up to 250 orders, but soon hits a glass ceiling if they get larger. Out of the investigated metaheuristic approaches, Simulated Annealing achieves the best results. It is shown to produce solutions with less than 3% average optimality gap on small instances and to scale well up to thousands of orders and dozens of periods and products. The presented metaheuristic methods are already being actively used in the industry.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Production Leveling, Constraint Programming, MIP, Metaheuristics
en
dc.title
Exact and metaheuristic approaches for the production leveling problem
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.70283
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Johannes Vass
-
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
AC15530552
-
dc.description.numberOfPages
76
-
dc.identifier.urn
urn:nbn:at:at-ubtuw:1-131589
-
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-3992-8637
-
item.fulltext
with Fulltext
-
item.openairecristype
http://purl.org/coar/resource_type/c_bdcc
-
item.languageiso639-1
en
-
item.cerifentitytype
Publications
-
item.mimetype
application/pdf
-
item.openaccessfulltext
Open Access
-
item.openairetype
master thesis
-
item.grantfulltext
open
-
crisitem.author.dept
E192-02 - Forschungsbereich Databases and Artificial Intelligence