Tabusuche für Maschinenbelegungsprobleme (Diplomarbeit)

Title:
  Tabu Search for Scheduling Problems (master's thesis)

Advisor:
  Arnold Neumaier (co-advisor Fred Glover)

Date:
  April 1999

Abstract:

We apply a tabu search method to a scheduling problem of a company producing cables for cars: The task is to determine on what machines and in which order the cable jobs should be produced in order to save time and money.

First the problem is modeled as a combinatorial optimization problem. We then describe several meta-heuristic search algorithms in general and explain why they are often used to tackle these types of optimization problems. We also mention NP-completeness in this context.
We employ a tabu search algorithm as an approach to solve the specific problem of the company, adapt various intensification as well as diversification strategies within the algorithm, and demonstrate how these different implementations improve the results.
Moreover, we show how the computational cost can be reduced drastically from O(n^3) (naive implementation) to O(n) (smart implementation) by exploiting the specific structure of the problem (n refers to the number of cable orders).

Download thesis: (pdf) (in german)