Redundante Constraints und Heuristiken zum effizienten Lösen von Problemen der 
Ablaufplanung mit CHIP

by Hans-Joachim Goltz 
GMD FIRST, Berlin, Germany

Abstract 

Methoden zum Erzeugen optimaler Lösungen für n x m Maschinenbelegung-
sprobleme mit der constraintlogischen Programmiersprache CHIP werden beschrieben, wobei 
CHIP als "Blackbox"-System betrachtet wird. Zuerst werden redundante Constraints angegeben, 
durch die der Suchraum verkleinert werden kann. Da das Erzeugen aller möglichen redundanten 
Constraints nicht möglich ist, werden Heuristiken benötigt, die bestimmen, für welche Aufgaben-
mengen welche redundante Constraints erzeugt werden. Außerdem werden Heuristiken für die 
schrittweise Erzeugung der Bearbeitungsreihenfolge der Arbeitsaufgaben diskutiert. Ziel unserer 
Untersuchungen ist dabei, Methoden zu entwickeln, die in unserem Planungungstool integriert 
werden können, so dai in den relevanten Fällen bessere Lösungen als mit den allgemeineren Such-
methoden erzeugt werden können.