Ein Vergleich von Verfahren zur Maschinenbelegungsplanung: Simulated Annealing, Genetische Algorithmen und mathematische Optimierung

摘要

Die Maschinenbelegungsplanung ist seit vielen Jahren Forschungsgegenstand in der Wirtschaftsinformatik und im Operations Research. Die klassischen Optimierungsverfahren lassen sich für die Verhältnisse und Größenordnungen der betrieblichen Praxis kaum nutzen, da das zugrundeliegende Problem NP-vollständig ist und der Rechenaufwand exponentiell wächst. In jüngerer Zeit wurden vermehrt heuristische Verfahren, auf Basis des Simulated Annealing, Genetischer Algorithmen u. a., vorgeschlagen. Diese garantieren zwar nicht Optimalität, können jedoch „gute" Lösungen in annehmbarer Zeit ermitteln. In dem Beitrag werden Simulated Annealing und Genetische Algorithmen für Maschinenbelegungsprobleme untersucht und bezüglich der Kriterien Lösungsgüte und Laufzeitverhalten detailliert verglichen. Die zum Vergleich benötigten optimalen Lösungen wurden mit Hilfe gemischt-ganzzahliger linearer Optimierung bestimmt.%Job-shop scheduling has been subject to investigations in the field of operations research and business informatics for many years. Traditional optimization techniques, like linear programming and branching-and-bounding, are usually not applicable to real-world scheduling because the underlying problem is NP-hard. Recently, heuristic techniques like simulated annealing and genetic algorithms have been proposed to solve scheduling problems. These techniques do not guarantee optimal solutions, but they compute good solutions in acceptable time. In this paper, application of simulated annealing and genetic algorithms to scheduling are investigated with respect to solution quality and computing time. Optimal solutions required for the comparisons were determined by mixed-integer linear optimization.