Tech Report CS-92-43

Scheduling and Packing in the Constraint Language cc(FD)

Pascal Van Hentenryck

September 1992

Abstract:

Constraint logic programming (CLP), and its generalization in the cc framework, define a class of declarative constraint languages combining nondeterministic goal-directed programming with constraint techniques over an arbitrary domain. CLP languages are particularly attractive for combinatorial search problems as they offer a short development time and a reasonable efficiency. In this paper, we present the application of cc(FD), a CLP language using consistency techniques over finite domains, to two applications: the perfect square problem and a digital signal processing (DSP) problem. The perfect square problem amounts to placing squares of different sizes in a master square in an exact manner (i.e. no empty space remains). We show a natural and very short cc(FD) program solving the problem for 21 and 24 squares in a couple of seconds. The DSP application amounts to scheduling tasks on a multiprocessor in presence of precedence, capacity, and delay constraints. The complexity of the problem is exacerbated by the non-uniform communication delays coming from the architecture, which combines pipeline and master-slave processing. We present a short cc(FD) program which compares very well with a special-purpose branch and bound algorithm. Both applications show the versatility of languages such as cc(FD) for the solving of discrete combinatorial search problems.

(complete text in pdf or gzipped postscript)