Optimizing the Cell Assignment Problem

Abstract

In the modern industry, production networks often consist of multiple machines and cells, which serve as storage facilities for final or intermediate products. In this thesis we are investigating solutionapproaches for a real-life problem appearing in such production networks. In the considered problem, each machine processes a fixed sequence of jobs that consume and produce material. Each job must be assigned a cell, which is used for storing the produced material. Additionally, a feasible schedule of jobs over all machines needs to be found. The objective of the problem is to minimize the total tardiness of a set of delivery orders, which require a certain amount of material. Many variants of job scheduling problems from industrial manufacturing have been studied in the past. However, to the best of our knowledge, none of the investigated variants captures the specific resource constraints appearing in the considered problem. Thus, existing methods cannot be used to find good solutions efficiently. Due to the large size of real-life instances, finding high-quality solutions in a reasonable amount of time is a challenging problem that requires novel and innovative solution approaches. This thesis provides a formal specification of the problem at hand and investigates two alternative constraint programming formulations which can be used for exact solving approaches. Furthermore, a construction heuristic is developed and neighborhood operators for the considered problem are proposed. Based on these operators, Simulated Annealing is applied as a metaheuristic technique for solving the problem. Experiments are performed on one real-life instance and a diverse set of instances that we randomly generated. We compare the different methods regarding solution quality and runtime and present an overview of the results. Both constraint models turned out to be successful in finding optimal solutions for small instances. For many of the larger instances, only one model found solutions within the given time limit. Simulated Annealing could solve numerous instances optimally and found feasible solutions for the majority of instances. Furthermore, the Simulated Annealing approach provided improved solutions for most of the instances. None of the constraint models solved the real-life instance due to its large size, whereas the construction heuristic was able to provide a feasible solution.

Moderne Produktionswerke bestehen oft aus mehreren Maschinen und Zellen, in denen Zwischen- oder Enderzeugnisse gelagert werden. Diese Diplomarbeit beschäftigt sich mit Lösungsansätzen für ein in der Praxis relevantes Problem, welches in solchen Netzwerken auftritt. In dem behandelten Problem wird von jeder Maschine eine vorgegebene Sequenz an Aufträgen ausgeführt, welche Material konsumieren und produzieren. Für jeden Auftrag muss eine Zelle zugewiesen werden, um dessen produziertes Material zu lagern. Außerdem müssen gültige Startzeiten für die Aufträge aller Maschinen gefunden werden. Das Ziel des Problems ist, die kumulierte Verspätung aller Lieferaufträge zu minimieren, wobei ein Lieferauftrag gewisse Mengen von Materialien benötigt.In der Vergangenheit wurden bereits einige Varianten von Planungsproblemen aus der Produktionsbranche behandelt. Allerdings werden nach unserem Wissensstand die spezifischen Ressourceneinschränkungen des von uns untersuchten Problems von keiner Variante, die in der wissenschaftlichen Literatur untersucht wurde, behandelt. Daher können existierende Methoden nicht verwendet werden, um qualitative Lösungen auf effiziente Art und Weise zu finden. Da in der Praxis auftretende Probleminstanzen sehr groß sein können, ist es ein herausforderndes Problem, hochwertige Lösungen in akzeptablem Zeitraum zu finden. Um dieses Ziel zu erreichen, werden innovative Lösungsmethoden benötigt. In dieser Diplomarbeit stellen wir eine formale Spezifikation des zu lösenden Problems zur Verfügung und modellieren dieses mittels zwei verschiedener Constraint Optimization Formulierungen, welche für exakte Lösungsverfahren verwendet werden können. Weiters werden eine Konstruktionsheuristik sowie Nachbarschaftsoperatoren für das behandelte Problem entwickelt. Darauf basierend wird Simulated Annealing als metaheuristischer Lösungsansatz auf das Problem angewandt. Die verschiedenen Methoden werden auf einer praktischen Instanz, sowie einer großen Menge diverser, zufällig generierter Instanzen, getestet. Ein Vergleich bezüglich Qualität und Laufzeit wird aufgestellt. Beide Consttraintprogrammierungs-Modelle sind erfolgreich darin, optimale Lösungen für kleinere Instanzen zu finden. Für viele der größeren Instanzen kann nur eines der Modelle die optimale Lösung im gegebenen Zeitlimit finden. Der Ansatz mittels Simulated Annealing löst einige Instanzen optimal und findet gültige Lösungen für die meisten Instanzen. Außerdem können die meisten Lösungen, welche von der Konstruktionsheuristik erzeugt werden, durch Simulated Annealing verbessert werden. Die evaluierte praktische Instanz wurde wegen deren Größe von keinem der Constraintprogrammierungs-Modelle gelöst, die Konstruktionsheuristik konnte allerdings eine gültige Lösung erzeugen.