PhD defence Ashkan Safari

Keywords: Local Search, k-swap, Machine Scheduling, Ant Colony Optimization

"Theory of Local Search and Ant Colony Optimization in Combinatorial Problems"

This PhD thesis explores how complex decision problems can be tackled efficiently when finding an exact solution is simply not realistic. Such problems arise in many everyday settings, including planning, scheduling, and routing, where the number of possible choices grows extremely fast. In practice, people often rely on simple improvement-based methods that gradually make a solution better, even though theory sometimes suggests these methods could perform poorly.

This thesis explains why these methods usually work well in reality. First, it studies a machine scheduling problem and shows that, although very slow behaviour is possible in theory, it is unlikely to occur in practice. A more realistic analysis helps to bridge this gap between theory and real-world performance.

The thesis then examines algorithms inspired by the behaviour of ants, which learn from past experience. It shows how small changes in their learning rules can strongly influence their reliability and speed. Overall, the thesis helps to clarify why practical algorithms often succeed despite limited theoretical guarantees.

Click here for the full dissertation. 

Click here for the live stream.