Investigating constraint programming and hybrid answer-set solving for industrial test laboratory scheduling

Abstract

In this thesis we deal with a complex real-world scheduling problem closely related to the well-known Resource-Constrained Project Scheduling Problem (RCPSP). The problem concerns industrial test laboratories in which a large number of tests has to be performed by qualified personnel using specialized equipment, while respecting deadlines and other constraints.We investigate exact approaches based on Constraint Programming and Answer-set Programming for this problem. First, we propose various Constraint Programming models based on existing approaches for the related problems and introduce new encodings for the complex constraints of the problem. Additionally, we provide novel redundant constraints and analyze the impact of various search strategies. Furthermore, we show how we can solve this problem by Answer-set Programming extended with ideas from constraint solving. We propose an innovative and efficient encoding, apply an answer-set solver for constraint logic programs called clingcon, and investigate different modeling options and solver configurations. We also propose a Very Large Neighborhood Search (VLNS) approach which exploits our exact methods and manages to drastically improve the quality of the solutions found by these methods.Our solution approaches are empirically evaluated both on real-world data and existing randomly generated benchmark instances of different sizes. Additionally, we compare our methods with a state-of-the-art metaheuristic approach for this problem and a Mixed-Integer Programming solver. Our approaches provide feasible solutions for all 31 instances and for 22 we could find optimal solutions. The VLNS approach currently yields the best known solutions for this problem outperforming existing metaheuristic approaches. In fact, we show that VLNS finds solutions which are within 5% of the optimum for 30 out of the 31 instances. Finally, the solution methods described in this thesis are currently in use in a real-world industrial test laboratory.

In dieser Diplomarbeit betrachten wir ein real auftretendes, komplexes Projektplanungsproblem. Dieses Planungsproblem ist eine Erweiterung des bekannten Resource-Constrained Project Scheduling Problem (RCPSP) und tritt in industriellen Testlaboren auf, bei denen eine grosse Anzahl an Tests durch qualifiziertes Personal und unter Einhaltung von Fristen und anderen Einschraenkungen durchgefuehrt werden muessen. Wir untersuchen exakte Methoden fuer dieses Problem basierend auf Constraint Programming und Answer-set Solving. Unter anderem schlagen wir verschiede Constraint Programming Modelle vor, welche zum Teil auf bestehenden Ideen aus der Literatur aufbauen, aber fuer die komplexen Constraints unseres Problems erweitert wurden. Ausserdem, stellen wir neuartige redundante Constraints vor und nutzen verschiedene Suchstrategien. Darueber hinaus zeigen wir, wie dieses Projektplanungsproblem mit Hybrid Answer-set Programming geloest werden kann. Im Speziellen stellen wir ein Encoding fuer den Constraint Answer-set Solver clingcon vor und untersuchen verschiedene Modellierungsoptionen und Konfigurationen. Wir liefern ausserdem einen Very Large Neighborhood Search (VLNS) Ansatz, welcher auf unseren exakten Methoden basiert und die Qualitaet, der von diesen Methoden gefundenen Loesungen, drastisch verbessert.Unsere Loesungsansaetze werden im Anschluss empirisch evaluiert, sowohl mit echten Daten als auch mit existierenden, zufaellig generierten Benchmark-Instanzen von verschiedenen Groessen. Zusaetzlich vergleichen wir unsere Methoden mit einem state-of-the-art meta heuristischen Ansatz fuer dieses Problem und einem Mixed-Integer Programming Solver. Unsere Methoden konnten gueltige Loesungen fuer alle 31 Testinstanzen finden, und fuer 22 sogar optimale Loesungen. Wir zeigen ausserdem, dass VLNS die momentan besten Ergebnisse fuer dieses Problem liefert. Zusaetzlich zeigen wir, dass VLNS fuer 30 der 31 Instanzen Loesungen findet, welche im Bereich von bis zu 5% des Optimums liegen.