Felix Godafoss König

Sorting with Objectives: Graph-theoretic Concepts in Industrial Optimization Felix Godafoss König

Applying combinatorial optimization in the industry frequently yields cost savings delighting practitioners. Beyond that, at the core of some applications lies a particularly pretty theoretical problem rejoicing the mathematician. This thesis is devoted to sorting with objectives as a new powerful way to model logistics and sequencing problems in industrial applications in an integrated fashion. Its contributions are twofold: On the one hand, we are motivated by optimization endeavors in the steel industry, for which we develop combinatorial algorithms revealing significant optimization potential in everyday production. On the other hand, the foundation of our algorithm design is an in-depth analysis of the problems at hand, and it unveils theoretically appealing subproblems for which we obtain complexity and approximation results of interest in their own right. Throughout the thesis, graph theoretic models appear as a recurrent theme.