Min-Sum Set Cover, OR-Scheduling, and Related Problems
Translated title:
Min-Sum Set Cover, OR-Scheduling und damit verwandte Probleme
Author:
Happach, Felix
Year:
2020
Document type:
Dissertation
Faculty/School:
Fakultät für Mathematik
Advisor:
Schulz, Andreas S. (Prof. Dr.)
Referee:
Schulz, Andreas S. (Prof. Dr.); Lidbetter, Thomas (Prof. Dr.)
Language:
en
Subject group:
MAT Mathematik
TUM classification:
WIR 527d
Abstract:
We address various scheduling problems with OR-precedence constraints that are extensions of min-sum set cover, minimum latency set cover and generalized min-sum set cover. Using machinery from the theory of scheduling, we devise new exact and approximative algorithms for variants of these problems. We consider two main objective functions: makespan and total weighted completion time. For the latter objective, we study the relation between min-sum covering problems and OR-scheduling, and we analyze different LP formulations.
«
We address various scheduling problems with OR-precedence constraints that are extensions of min-sum set cover, minimum latency set cover and generalized min-sum set cover. Using machinery from the theory of scheduling, we devise new exact and approximative algorithms for variants of these problems. We consider two main objective functions: makespan and total weighted completion time. For the latter objective, we study the relation between min-sum covering problems and OR-scheduling, and we anal...
»
Translated abstract:
Wir betrachten Schedulingprobleme mit OR-Vorgängerbeziehungen, welche Erweiterungen von Min-Sum Set Cover, Minimum Latency Set Cover und Generalized Min-Sum Set Cover sind. Mit Hilfe von Methoden aus der Schedulingtheorie leiten wir neue exakte und approximative Algorithmen für Varianten dieser Probleme her. Wir betrachten zwei der wichtigsten Zielfunktionen aus dem Gebiet des Scheduling: die gesamte Produktionsdauer und die Summe der gewichteten Fertigstellungszeiten. Für Letztere untersuchen wir den Zusammenhang von Min-Sum Set Cover und OR-Scheduling und analysieren verschiedene LP-Formulierungen.
«
Wir betrachten Schedulingprobleme mit OR-Vorgängerbeziehungen, welche Erweiterungen von Min-Sum Set Cover, Minimum Latency Set Cover und Generalized Min-Sum Set Cover sind. Mit Hilfe von Methoden aus der Schedulingtheorie leiten wir neue exakte und approximative Algorithmen für Varianten dieser Probleme her. Wir betrachten zwei der wichtigsten Zielfunktionen aus dem Gebiet des Scheduling: die gesamte Produktionsdauer und die Summe der gewichteten Fertigstellungszeiten. Für Letztere untersuchen w...
»