Awasthi, Abhishek (2016) Optimization of NP-hard Scheduling Problems by Developing Timing Algorithms and Parallelization. PhD, Universität Oldenburg.

Preview

Volltext (1494Kb)

Abstract

Scheduling plays an important role in the success of most logistic systems. Due to the NP-hard nature of such problems, they have predominantly been solved utilizing metaheuristic algorithms. This work is focused on a two-layered approach, which operates by splitting a 0-1 Integer programming formulation of a scheduling problem in two parts. One part of the problem is solved polynomially, while the other is solved by metaheuristic algorithms. The development of the polynomial algorithms is carried out by in-depth theoretical studies of the resulting linear programs of all scheduling problems considered in this work. The results for the benchmark instances of the schduling problems prove the potential of this approach. Another benefit is its inherent parallel structure that is demonstrated later in this work, along with its extension to other combinatorial optimization problems.

["eprint_fieldname_title_plus" not defined]

Optimierung von NP-Schweren Scheduling-Problemen durch die Entwicklung von Timing-Algorithmen und Parallelisierung

["eprint_fieldname_abstract_plus" not defined]

Ablaufplanung (Scheduling) spielt eine wichtige Rolle in den meisten Logistiksystemen. Weil sie NP-schwer sind, wurden sie in der Vergangenheit überwiegend mit Metaheuristiken gelöst. Diese Arbeit konzentriert sich auf einen zweischichtigen Lösungsansatz, bei dem ein 0-1 Integer-Programm in zwei Unterprobleme aufgeteilt wird. Das eine Teilproblem wird mit einem polynomiellen Ansatz gelöst, während das andere untergeordnete Problem mit einer Metaheuristik gelöst wird. Die Entwicklung des polynomiellen Algorithmus erfolgt durch eine intensive Analyse der sich ergebenden Linearen Programme für alle Scheduling-Probleme, die in dieser Arbeit berücksichtigt wurden. Die Ergebnisse verschiedener Scheduling-Benchmarks beweisen das Potential dieses Ansatzes. Ein weiterer Vorteil besteht in seiner inhärenten Parallelisierbarkeit, die später in dieser Arbeit gezeigt wird sowie seiner Erweiterbarkeit auf andere kombinatorische Optimierungsprobleme.

Item Type:	Thesis (PhD)
Uncontrolled Keywords:	Combinatorial optimization, Scheduling, NP-hard, Polynomial algorithms, Parallelization
Subjects:	Generalities, computers, information > Computer science, internet
Divisions:	School of Computing Science, Business Administration, Economics and Law > Department of Computing Science
Date Deposited:	06 Jan 2017 10:47
Last Modified:	06 Jan 2017 10:47
URI:	https://oops.uni-oldenburg.de/id/eprint/2915
URN:	urn:nbn:de:gbv:715-oops-29969
DOI:
Nutzungslizenz:

Actions (login required)

View Item