Solution Approaches for Balanced Task Planning and Employee Task Distribution

Abstract

In this thesis, we investigate two real-life optimization problems from the area of production planning. The first problem, the Balanced Task Planning Problem, is introduced in this thesis. While there are related problems in the literature, significant differences in the definition of constraints and objectives require the introduction of a new problem specification. The aim of the problem is to assign tasks to machines and planning periods so that the machine loads are balanced around a target value while prioritizing more critical tasks. The second problem was recently introduced to the literature and is called the Employee Task Distribution Problem. The goal is to fulfill demands by assigning employees to operations while satisfying various constraints. While promising solution approaches have been proposed in the literature, users of decision support systems that solve real-life problems often prefer more involvement in the employee planning process. This is particularly relevant for reacting to short-term changes in employee availabilities or capacity demands while keeping the adaptations as minimal as possible. For the first problem, we provide a formal problem description and prove that a decision variant of the problem is NP-complete. We introduce a mathematical model that can be used with Constraint Programming and Integer Programming solvers to find optimal solutions. Furthermore, we propose different local search variants based on Tabu Search to find solutions for large-scale problem instances. For the second problem, we propose an interactive optimization method that provides the user with traceable suggestions for improving employee assignments. For that, we introduce an interactive variant of the Employee Task Distribution Problem and propose a Tabu Search method to find solutions for this problem variant. To evaluate the methods, we generate random problem instances for the Balanced Task Planning Problem and perform an experimental evaluation of the different approaches. The results show that most of the small instances can be solved using the exact approach, and for some, optimal solutions can be obtained. Using Tabu Search, high-quality solutions could also be found for the large majority of large-scale instances. To demonstrate the effectiveness of the interactive optimization approach, we study practical use cases and show the usefulness in supporting human decision-makers.

In dieser Diplomarbeit untersuchen wir zwei für die Praxis relevante Optimierungsprobleme aus dem Bereich der Produktionsplanung. Das erste Problem, das Balanced Task Planning Problem, wird in dieser Arbeit erstmals beschrieben. Obwohl es verwandte Probleme aus der Literatur gibt, erfordern relevante Unterschiede in der Definition der Nebenbedingungen und Zielfunktionen die Einführung einer neuen Problemspezifikation. Das Ziel ist es verschiedene Aufgaben zu Planungsperioden und Maschinen zuzuordnen, sodass die Auslastungen der Maschinen ausgewogen um einen Zielwert liegen, während kritische Aufgaben priorisiert werden. Eine formale Problemspezifikation des zweiten Problems wurde kürzlich unter dem Namen Employee Task Distribution Problem veröffentlicht. Dabei handelt es sich um ein Optimierungsproblem mit dem Ziel Bedarfe zu erfüllen, indem Mitarbeiterinnen und Mitarbeiter zu Operationen zugeordnet werden. Außerdem muss eine Reihe an Nebenbedingungen berücksichtigt werden. In der Literatur wurden bereits Lösungsansätze für das Problem untersucht. In der Praxis gibt es jedoch zusätzlich den Bedarf einer interaktiven Lösungsvariante, um Entscheidungsträgerinnen und Entscheidungsträger enger in den Planungsprozess einzubinden. Dies ist vor allem relevant um auf kurzfristige Veränderungen der Mitarbeiterverfügbarkeiten oder -bedarfe reagieren zu können, während die Anpassungen des vorhandenen Plans möglichst gering gehalten werden sollen.Wir präsentieren eine Problemspezifikation für das erste Problem und beweisen, dass eine Entscheidungsvariante des Problems NP-vollständig ist. Wir stellen ein mathematisches Modell vor, welches mit modernen Constraint Programming und Integer Programming Lösungsverfahren optimale Lösungen bereitstellen kann. Außerdem schlagen wir verschiedene metaheuristische Varianten basierend auf Tabusuche vor, um qualitative Lösungen für große Probleminstanzen zu finden. Für das zweite Problem verwenden wir eine interaktive Optimierungsmethode, die nachvollziehbare Verbesserungen eines vorhandenen Plans vorschlägt. Dafür definieren wir eine interaktive Problemvariante des Employee Task Distribution Problems und schlagen einen Lösungsansatz basierend auf Tabusuche vor, der es ermöglicht, Lösungen zu dieser Problemvariante zu finden. Um die vorgeschlagenen Methoden zu evaluieren, erzeugen wir zufällige Probleminstanzen für das Balanced Task Planning Problem und führen eine experimentelle Auswertung der verschiedenen Lösungsansätze durch. Das Ergebnis dieser Auswertungen zeigt, dass die meisten kleinen Instanzen mithilfe der exakten Methoden gelöst werden können, wobei für einige eine optimale Lösung gefunden wurde. Bei Verwendung der Tabusuche konnten hochqualitative Lösungen auch für die überwiegende Mehrheit der großen Probleminstanzen gefunden werden. Um die Effektivität der interaktiven Optimierungsmethode zu demonstrieren, untersuchen wir praktische Anwendungsfälle und zeigen die Wirksamkeit unseres Ansatzes bei der Unterstützung menschlicher Entscheidungsträgerinnen und Entscheidungsträger.