Diese Masterarbeit legt einen Algorithmus zum Lösen des flexiblen job shop scheduling Problems mit Transportzeiten vor. Dieser Algorithmus besteht aus einem Subgradientenverfahren und einer List Scheduling Heuristic, welche das Ergebnis des Subgradientenverfahrens in einen zulässigen Ablaufplan verändert. Es werden drei Methoden zur sogenannten Preis Diskriminierung vorgestellt und ihr Einfluss auf die Qualität der Ergebnisse untersucht. Außerdem wurde der Algorithmus in Java programmiert und an realitätsnahen Probleminstanzen getestet. Die Ergebnisse werden interpretiert und mit den Ergebnissen anderer Algorithmen verglichen.

This thesis puts forth an algorithm for solving the flexible job shop scheduling problem. The algorithm consist of a subgradient search and of a list scheduling heuristic, which is designed to generate feasible solutions deriving from the infeasible solutions we obtain from the subgradient search. Several methods for so-called price discrimination are introduced and their effects on the subgradient search are examined. The list scheduling heuristic uses a priority function to rank operations and creates a schedule that does not violate any constraints. Implementation in Java was written to test the method. The results of testing the algorithm on realistic industrial data are shown, compared to results from other programs and interpreted.