Lösen kombinatorischer Probleme mit Constraintprogrammierung in Oz

Abstract

In dieser Dissertation beschäftigen wir uns mit der Lösung kombinatorischer Probleme durch Constraintprogrammierung. Wir zeigen, daß verschiedene kombinatorische Probleme in der nebenläufigen Constraintsprache Oz effizient gelöst werden können. Wir führen ein formales Modell von constraintbasiertem Lösen kombinatorischer Probleme ein, das unabhängig von einer konkreten Programmiersprache ist, und wir zeigen, wie einige der derzeit besten Schedulingtechniken (Techniken für Ablaufplanung) aus dem Operations Research für Constraintpropagierung und Distribuierung in dieses Modell integriert werden können. Wir zeigen, wie dieses Modell in die nebenläufige Constraintsprache Oz eingebettet werden kann und belegen mit einer Reihe von Fallstudien für große und schwierige Probleme aus dem Gebiet des Scheduling die Leistungsfähigkeit des entwickelten Systems.

In this doctoral dissertation we deal with combinatorial problem solving by constraint programming. We show that a number of combinatorial problems can be efficiently solved in the concurrent constraint language Oz. We introduce a formal model for constraint-based combinatorial problem solving which is independent from a particular programming language. We show how some of the currently best scheduling techniques from Operations Research can be integrated in the model of constraint propagation and distribution. We embed this model in the concurrent constraint language Oz and prove the efficiency of the developed system by a series of case studies for large and hard problems from the area of scheduling.