Open Access

Peter Auer, György Dósa, Tibor Dulai, Armin Fügenschuh, Peggy Näser, Ronald Ortner, Ágnes Werner-Stark

• We deal with a very complex and hard scheduling problem. Several types of products are processed by a heterogeneous resource set, where resources have different operating capabilities and setup times are considered. The processing of the products follows different workflows, allowing also assembly lines. The goal is to process all products in minimum time, i.e., the makespan is to be minimized. Because of the complexity of the problem an exact solver would require too much running time. We propose a compound method where a heuristic is combined with an exact solver. Our proposed heuristic is composed of several phases applying different smart strategies. In order to reduce the computational complexity of the exact approach, we exploit the makespan determined by the heuristic as an upper bound for the time horizon, which has a direct in uence on the instance size used in the exact approach. We demonstrate the efficiency of our combined method on multiple problem classes. With the help of the heuristic the exact solver is able to obtainWe deal with a very complex and hard scheduling problem. Several types of products are processed by a heterogeneous resource set, where resources have different operating capabilities and setup times are considered. The processing of the products follows different workflows, allowing also assembly lines. The goal is to process all products in minimum time, i.e., the makespan is to be minimized. Because of the complexity of the problem an exact solver would require too much running time. We propose a compound method where a heuristic is combined with an exact solver. Our proposed heuristic is composed of several phases applying different smart strategies. In order to reduce the computational complexity of the exact approach, we exploit the makespan determined by the heuristic as an upper bound for the time horizon, which has a direct in uence on the instance size used in the exact approach. We demonstrate the efficiency of our combined method on multiple problem classes. With the help of the heuristic the exact solver is able to obtain an optimal solution in a much shorter amount of time.…
• Wir betrachten das folgende Planungsproblem: Verschiedene Arten von Produkten werden auf einer Menge von heterogenen Maschinen erstellt, welche unterschiedliche Betriebsarten und Umrüstzeiten haben. Die Verarbeitung der Produkte erfolgt nach unterschiedlichen Arbeitsablaufplänen, da die einzelnen Produkttypen unterschiedliche Fertigungsschritte erfordern. Das Ziel ist es, alle Produkte in minimaler Zeit herzustellen. Aufgrund der Komplexität des Problems benötigen exakte Lösungsverfahren eine recht hohe Rechenzeit. Wir schlagen eine zusammengesetzte Methode vor, bei dem eine Heuristik und ein exakter Löser kombiniert werden. Unsere vorgeschlagene Heuristik besteht aus mehreren Phasen, in denen verschiedene intelligente Strategien angewendet werden. Um die rechnerische Komplexität des exakten Ansatzes zu reduzieren, nutzen wir die durch die Heuristik bestimmte Fertigungsdauer als obere Grenze für den Zeithorizont, was einen direkten Einfluss auf die Instanzgröße des exakten Ansatzes hat. Wir demonstrieren die Effizienz unsererWir betrachten das folgende Planungsproblem: Verschiedene Arten von Produkten werden auf einer Menge von heterogenen Maschinen erstellt, welche unterschiedliche Betriebsarten und Umrüstzeiten haben. Die Verarbeitung der Produkte erfolgt nach unterschiedlichen Arbeitsablaufplänen, da die einzelnen Produkttypen unterschiedliche Fertigungsschritte erfordern. Das Ziel ist es, alle Produkte in minimaler Zeit herzustellen. Aufgrund der Komplexität des Problems benötigen exakte Lösungsverfahren eine recht hohe Rechenzeit. Wir schlagen eine zusammengesetzte Methode vor, bei dem eine Heuristik und ein exakter Löser kombiniert werden. Unsere vorgeschlagene Heuristik besteht aus mehreren Phasen, in denen verschiedene intelligente Strategien angewendet werden. Um die rechnerische Komplexität des exakten Ansatzes zu reduzieren, nutzen wir die durch die Heuristik bestimmte Fertigungsdauer als obere Grenze für den Zeithorizont, was einen direkten Einfluss auf die Instanzgröße des exakten Ansatzes hat. Wir demonstrieren die Effizienz unserer kombinierten Methode an einer großen Menge von Testinstanzen. Mit Hilfe der Heuristik ist der exakte Löser in der Lage, in deutlich kürzerer Zeit eine beweisbar-optimale Lösung zu bestimmen.…