Integrated production and distribution scheduling has emerged as an important research topic in the areas of combinatorial optimization and supply chain management. In this thesis we consider problems that occur frequently in the manufacturing of products with a short lifespan or in make-to-order business models, where the production is triggered only if a corresponding customer order is received. The focus is put on the coordination of production and distribution processes to meet the requirements of the customers as closely as possible while at the same time maximizing the revenues of the manufacturer. We analyze a basic production and distribution model and study several extensions in order to incorporate more restrictions from practice. These model extensions lead to complex scenarios that make the class of considered problems very challenging to solve. We address their complexity by developing appropriate heuristic solution methods based on meta-heuristics such as tabu search or iterated local search. Moreover, we evaluate the performance of the proposed algorithms on a set of test instances. Practical applications in which the previously mentioned problems need to be solved include the production and transportation of certain intermediate products like adhesive materials in chemical industry and the delivery of ready-mix concrete from a production plant to several construction sites by a fleet of delivery trucks.

Planar graphs have a rich history that dates back to the 18th Century. They form one of the core concepts of graph theory. In computational graph theory, they offer broad advantages to algorithm design and many groundbreaking results are based on them. Formally, a given graph is either planar or non-planar. However, there exists a diverse set of established measures to estimate how far away from being planar any given graph is. In this thesis, we aim at evaluating and improving algorithms to compute these measures of non-planarity. Particularly, we study (1) the problem of finding a maximum planar subgraph, i.e., a planar subgraph with the least number of edges removed; (2) the problem of embedding a graph on a lowest possible genus surface; and finally (3) the problem of drawing a graph such that there are as few edge crossings as possible. These problems constitute classical questions studied in graph drawing and each of them is NP-hard. Still, exact (exponential time) algorithms for them are of high interest and have been subject to study for decades. We propose novel mathematical programming models, based on different planarity criteria, to compute maximum planar subgraphs and low-genus embeddings. The key aspect of our most successful new models is that they carefully describe also the relation between embedded (sub-)graphs and their duals. Based on these models, we design algorithms that beat the respective state-of-the-art by orders of magnitude. We back these claims by extensive computational studies and rigorously show the theoretical advantages of our new models. Besides exact algorithms, we consider heuristic and approximate approaches to the maximum planar subgraph problem. Furthermore, in the realm of crossing numbers, we present an automated proof extraction to easily verify the crossing number of any given graph; a new hardness result for a subproblem that arises, e.g., when enumerating simple drawings; and resolve a conjecture regarding high node degree in minimal obstructions for low crossing number.

No description available.